# FindShortestTour finds very long tour

The documentation claims FindShortestTour works extremely well for hundreds or thousands of cities. I show an example set of 5 cities where it does an abominable job. I also show a couple of absurd changes that fix the problem. Does anyone have more experience with this?

placeData = {{1.3, 31.8}, {1.5, 32.}, {1.5, 32.}, {1.3, 31.8}, {1.3, 31.8}};
Outer[EuclideanDistance, placeData, placeData, 1] // TableForm

0.      0.282843    0.282843    0.  0.
0.282843    0.      0.      0.282843    0.282843
0.282843    0.      0.      0.282843    0.282843
0.      0.282843    0.282843    0.  0.
0.      0.282843    0.282843    0.  0.


Note from the matrix above that one quirk of the data is that there are only 2 different positions. The best route is {2,3,1,4,5}, which traverses the distance between the two positions only once. The tour returned by FindShortestTour makes the traversal 3 times, which is shockingly far from optimal (3 times as bad as the best!):

tourLength[cities_] := Total[(EuclideanDistance @@ #) & /@ Partition[cities, 2, 1]]
FindShortestTour[placeData, 2, 5]
tourLength[Part[placeData, Last@%]]
tourLength[Part[placeData, {2, 3, 1, 4, 5}]]

{0.848528, {2, 1, 3, 4, 5}}
0.848528
0.282843


Just by shifting the data by 1 unit, FindShortestTour works properly:

Plus[{0,-1},#]&/@placeData
FindShortestTour[%,2,5]

{{1.3,30.8},{1.5,31.},{1.5,31.},{1.3,30.8},{1.3,30.8}}
{0.282843,{2,3,1,4,5}}


Adding(!) another (duplicate!) city also fixes the problem, surprisingly:

placeData
FindShortestTour[%,2,5]
Append[%%,Last@%%]
FindShortestTour[%,2,5]

{{1.3,31.8},{1.5,32.},{1.5,32.},{1.3,31.8},{1.3,31.8}}
{0.848528,{2,1,3,4,5}}
{{1.3,31.8},{1.5,32.},{1.5,32.},{1.3,31.8},{1.3,31.8},{1.3,31.8}}
{0.282843,{2,3,6,4,1,5}}


Advice, anyone? Since no errors or messages are thrown, the only way I can think of to detect this problem is to write another version of FindShortestTour to check it against. I'd like to avoid that. ;-)

I know about this SE report, but that was 4 years ago. I am currently running version 11.1.0 on MacOS 10.13.6.

If you choose exact data
placeData = {{1.3, 31.8}, {1.5, 32.}, {1.5, 32.}, {1.3, 31.8}, {1.3,31.8}} // Rationalize[#, 0] &;

FindShortestTour[placeData, 2, 5] // N

• @Carib John When I first read your question I thought about the scaling of your data. If you normalize the data everything seems to work: m = Mean[data];\[Sigma] = StandardDeviation[data];FindShortestTour[ Map[{(#[[1]] - m[[1]])/\[Sigma] [[1]], (#[[2]] - m[[2]])/\[Sigma] [[2]]} &, data], 2, 5](*{2.58199, {2, 3, 1, 4, 5}}*) Sep 6, 2018 at 13:26