Help with algorithm to find optimal route between various routes, where order matters

Question

This seems to be a variation on the Travelling Salesman problem, and I started (as far as some reading at least) going down that route to solve it, but the ordering restrictions are confusing me a bit.

• I have a map with an arbitrary number of destinations on it.
• An agent is given a set of trade routes.
• Each individual route must be processed in order, but all routes can be intermingled.

For example:

• I start at S0.
• I have a route Alpha that needs to visit A1, A2 and A3.
• I have a route Beta that needs to visit B4, B5 and B6.

A valid option would be to simply join the routes together:

S0 -> A1 -> A2 -> A3 -> B4 -> B5 -> B6

But perhaps parts of Beta are actually near the beginning parts of Alpha, so it would be better to go:

S0 -> A1 -> B4 -> B5 -> A2 -> A3 -> B6

Is there a way to calculate an optimal (or "probably quite optimal") route between these nodes, without calculating every distance between every possible pair of nodes? Alternatively I could construct a graph of every possible journey, but that also seems like it could get problematic.

• Euphoric: To me it seems like normal traveling salesman, with additional constraint, that some nodes must be visited in specific order.

Answer 1

The striking thing about this problem is that every time there are only two choices, the next A or the next B. That means I could encode the route as AAABBB. Which in that case means choose all the A's then all the B's.

That makes exploring every possible journey simple. Just permute that string. If you're reluctant to calculate all of those you could run the greedy algorithm and just always choose which ever is shorter, A or B, at each step. It can't guarantee to be optimal but it is likely to be reasonable.

• Jan Hudec: Well, you can easily apply Dijkstra's algorithm. Put A and B in a priority queue by their length so far. Then pick the shortest, add A and B to it and put those in the queue. When the first element is complete, you have the solution.
• Cylindric: I've gone for a nearest-neighbour algorithm to start with, as you suggested in your second paragraph. I'll have to see anything more precise or fancy is needed.