TSP with bidirectional tunnels

[donthomasitos]

Problem description
My routing problem consists of "tunnels", which can be traversed in both directions, but should only be traversed once. So it's basically a TSP problem, but each vertex has two positions: An entry and exit - but accessible from two directions. Therefore, I don't think it's just an asymmetric TSP.

Current approach
With N tunnels, I have a distance matrix of (2*N)**2, where I set the distance between each exit/entry to 0. This works most of the time, but it's not a guaranteed constraint.

Question
How can I force the routing algorithm to either:

• Traverse an asymmetric TSP in both directions per vertex or
• Ensure that my pairs in the Current approach do not become separated?

Thanks!

[Mizux]

2. Why not using only one node for entry/exit, and an other node for the other direction (i.e. where you swap entry and exit) duplicate this node several time.

• make them optional i.e. part of a disjunction
• you can compute the travel distance from tunnel to any point, as the sum of tunnel travel time + travel time from exit to next location.

1. for allowing only one traversal, i would use a count dimension (+1 for any tunnel node, 0 for other) and limit of 1 as vehicle capacity

[donthomasitos]

Thank you Mizux, this seems to work!