# 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. Jun 19, 2017 at 6:10