VERIFIED SOLUTION i
X

How to understand the way that TSP is calculated in RouteFinder 4.12

UPDATED: September 11, 2017


QUERY

A customer has a problem to understand why the results of two TSP calculations are so different as just two stops (selected below) are not in route 2. See the image below:

User-added image

ANSWER

This essentially illustrates why researches has spent so much time on solving the TSP.

If it was just a matter of adding a new point to an existing route where it fits the best, then we could solve TSP in O(N^2) (*).
  • 1st point = 1 iteration
  • 2nd point = 2 iterations
  • 3rd point = 3 iterations
  • etc.
In total N*N/2. In reality it is much worse, up to O(2^N) since tiny differences can mean a whole different solution.
Moving a single point 100 meters down the road, but without adding new points, may also flip the whole solution.

What RouteFinder does, is actually following the steps above and then doing random permutations for a number of iterations to see if it can be improved.
For as little as 15 points, the initial solution is usually the best, but it definitely happens that it can be improved.
And with oneway restrictions in place, it happens even more often.

After the random permutations has been running, we usually have the best solution all the way up to 100 points. After that the risk of finding a good, but non-optimum solution increases.

When we get to RouteFinder 5 (Summer 2016), you may also get different results for what seems to be the same input, due to differences in calculation accuracy, random number generators and other implementation details.


 

Environment Details

Product Feature: General
Product: MapInfo Routefinder

Downloads

  • No Downloads