Travelling Salesman

Monday, 2 December 2002
There is no perfect solution for the problem of the travelling salesman (TSP).

What is the shortest route
for a travelling salesman, departing from home,
visiting a number of cities during the day,
and returning home in the evening?

An optimal route for 5 points

This demo of the travelling sales manager problem needs a Java plug-in.
This browser has no active Java plug-in yet.

Advice: Download the free Java plug-in from:
java.sun.com/getjava/download.html

The problem of the travelling salesman is NP-complete.
Number of possibilities grows exponentially with the number of points
Number of possibilities
grows exponentially
with the number of points.

There is one known algorithm that finds the optimal solution: using brute force to scan all possibilities. For larger problems this is undoable, as the number of possibilities grows exponentially.

Yet you see a Java applet above that finds an excellent solution extremely quickly, even along hundreds or even a thousand points.

How is this possible?

The applet above does not always show the optimal solution, but it does find a solution that is at least excellent. It scores sometimes 10 out of 10, mostly 9.9!

The underlying advanced algorithm is quite complex. It has taken me several sessions with the frog to invent it. The algorithm requires quite a few calculations, but still finds an excellent solution quickly, one with low or even minimal costs.

Applications

  • route planning for businessmen, service mechanics, delivery services, airplanes, ships, containers, trucks and busses visiting several places,
  • Task sequence planning for robots that must repeat work at a sequence of locations,
  • picklist to collect goods from a storehouse as quick as possible.
Do you have a situation where this algorithm can help you to optimise your business? Contact SUMit!

Till next week,
Nut