3
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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] &;

the shortest tour evluates as expected

FindShortestTour[placeData, 2, 5] // N
(*{0.282843, {2., 3., 1., 4., 5.}}*)
Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ So, @Ulrich, you have added a third twiddle that gets FindShortestTour to suddenly behave. Thanks. But are you suggesting that this might always be a fix? Or is it just another quirky alteration that helps the case of this one dataset? $\endgroup$
    – Carib John
    Commented Sep 6, 2018 at 12:56
  • 2
    $\begingroup$ @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}}*) $\endgroup$
    – Ulrich Neumann
    Commented Sep 6, 2018 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.