Solving Large Travelling Salesman Problems: The Last Gasp

点击翻译按钮获取中文摘要

This project's goal is to develop an exposition of a new algorithm for the Traveling Salesman problem. This problem is theoretically intractable, and practical heuristic techniques for large TSP problems have been elusive. In April 1992, a team of researchers established a new world record by solving ten previously unsolved problems, with sizes ranging from 1,060 to 3,038 cities, from a standard library of test data called TSPLib. (In particular, the 3,038-city problem is the largest TSPLib instance ever solved.) The program, developed by four people in the course of four years, has some 50 thousand lines, not counting the code that implements the simplex method. The algorithm consists of new ideas on every level of its design, from novel approaches to finding cutting planes all the way down to the minute details of data structures, not to mention the strategies of parallelizing the computations.