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.
2
-
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.– SjoerdCommented 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.– Doc BrownCommented Feb 10, 2018 at 6:21
Add a comment
|
3 Answers
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.
answered Feb 10, 2018 at 6:43
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.
answered Feb 10, 2018 at 17:57
-
-
2
-
As far as I understand your question, the problem that you are trying to solve has been studied under the name of traveling salesman problem with precedence constraint, this could constitute a good starting point for your search.
If you solve the problem with Mixed Integer Programming, you can add an Integer variable to each node representing its sequence. The sequence of the depot is fixed to be 0. For all other nodes if s_i represents the sequence of node i in the solution and if x_ij is a binary variable representing whether or not the arc between nodes i and j are used, then we can add the following constraints: s_j >= s_j + 1 - M * ( 1 - x_ij), for all pair of nodes i,j
Where M represents a large enough value.
Then if A should be visited before B you should add a constraint stating s_A < s_B
