Solving Large Traveling Salesman Problems: The Last Gasp

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

In April 1992, a team consisting of David Applegate of AT&T Bell Laboratories, Robert Bixby of Rice University, Vasek Chvatal of Rutgers University, and William Cook of Bellcore 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 task of writing up an exposition of the new algorithm is overwhelming: the program, developed by four people in the course of four years has some 50 thousand lines not counting the part that implements the simplex method. The award is so that Chvatal can buy himself out of his teaching duties at Rutgers for the Spring term of 1993 in order to dedicate himself full-time to writing in constant consultations with his colleagues at AT&T Bell Labs in Murray Hills, NJ and Bellcore in Morristown, NJ.