# How to implement the travelling salesman algorithm with dependecies between locations

Is there a way to implement the traveling salesman or purchaser algorithm with constraints between locations? For example, I have to grab item X before item B, c before D and F,G,H in any order.

• Well, Traveling salesman is NP, so you have to try every route anyway. Adding a check "grab X before B" won't affect the complexity. Feb 9, 2018 at 22:53
• @Sjoerd: the OP did not state he wants a perfect solution. And finding "good" instead of "perfect" solutions is not NP hard. Feb 10, 2018 at 6:21

Wikipedia lists several approaches for exact and heuristical solutions for the standard TSP. Any of those approaches explores the space of solutions and partial solutions in a special order. So I guess most of them (maybe all of them) can be extended by restricting the search space to those (partial and full) solutions which fulfill your additional dependencies.

As a simple example, the nearest-neighbor heuristics normally picks one location after the other, and it picks always the nearest unvisited location. Now extend this by the additional constraint of picking the nearest location except B, as long as X has not been visited before.

Of course, for finding really good solutions which are near the optimum, you need to implement something more sophisticated like simulated annealing, restricted to the search space of (partial) solutions fulfilling the list of constraints.

If you have only one dependency, "grab item X before item B", then the solution is trivial.

Find the shortest possible route. Either you encounter X before B on that route, or you travel the route in the opposite direction.

• No its not just X before B, I have multiple points Feb 11, 2018 at 1:06