Euclidian Traveling Salesman Problem Solver

Click anywhere on the map. Wait for an "x" to show where you clicked. Do this for from two to twenty places, to define a trip. Then click in the SOLVE box. An optimal, or nearly optimal, path will connect the points of the trip. Click the ERASE box to clear the map for a new trip.

Log Policy

This page maintains a log of entered data and returned results. The log data is treated as confidential, and is used only to debug and improve the page. The oldest data in the log is purged regularly to keep its size reasonably small.

The Euclidean traveling salesman problem is:

Given a number of points located in a plane, find the shortest path, consisting of straight lines connecting pairs of points, that visits each point exactly once and returns to the starting point.

The optimal path algorithm is based on the outline in Appendix B of:

     Computer Solutions of the Traveling Salesman problem
     Shen Lin
     Bell System Technical Journal 44(1965), pp. 2245-2269

See the download page for source code for the optimal path calculator (based on Shen Lin's algorithm).

To send a comment: Contact Us

Last updated Sunday, 06-Sep-2009 14:04:24 CDT