The Traveling Salesman Problem

animated screenshot

The traveling salesman problem is a traditional computer science challenge. Its goal is to find the shortest circuit through a set of points. A common approach is to construct an initial path and then improve it incrementally through local optimizations.

The travels.icn program illustrates several construction algorithms followed by application of the "2-opt" improvement algorithm; that algorithm deletes two segments at a time and reconnects their endpoints. If you look closely you may spot sections of a path that could be further improved by the "3-opt" algorithm which is not implemented here.

Further Reading

David S. Johnson. Local Optimization and the Traveling Salesman Problem. Proc. 17th Colloquium on Automata, Languages, & Programming, Springer-Verlag (1990), pp. 446-461.


Icon home page