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

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.

• To me it seems like normal traveling salesman, with additional constraint, that some nodes must be visited in specific order. Commented Jun 19, 2017 at 6:10

## 1 Answer

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.

• 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. Commented Jun 19, 2017 at 10:44
• 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. Commented Jun 20, 2017 at 15:14