crossing edges in the travelling salesman problem

Does there exist a travelling salesman prob开发者_StackOverflowlem where the optimal solution has edges that cross?

The nodes are in an x-y plane, so crossing in this case means if you were to draw the graph, two line segments connecting four separate nodes would intersect.

If two edges in a closed polygonal line cross, then there is a polygonal line with the same vertices but with smaller perimeter. This is a consequence of the triangle inequality. So, a solution to the TSP must be a simple polygon. See this article (Figure 4).

If you consider a non-Euclidean metric like L1 (Manhattan distance), then it's pretty easy to construct shortest tours that self-intersect.

+--3--+
|  |  |
|  |  |
2--+--1
|  |  |
|  |  |
+--4--+

If each neighboring pair of intersections is at distance 1, then all tours have length 8, including the self-intersecting one that goes 1 --> 2 --> 3 --> 4 --> 1.

You could get crossing edges if the cost of going from node A->C plus the cost B->D > cost A->B and C->D. You might get this when the cost in not propertional to the distance between the nodes.

A real life example might be that there is a bonus from going from A to C (for example you can smuggle some contrabande) or the cost is dependant on the previous steps (turing left a traffic lights might cost you a lot of time).

Trivially, any connected graph where every node has two edges has only one TPS solution, and if drawn with crossings will meet your stated criteria.

If you put other constraints, such as if you were modelling travelling around the globe using trade winds, so costs are only somewhat related to position in space, you might find a more complex case where crossing is optimal.