Solving Large Travelling Salesman Problems: The Last Gasp

解决大型旅行推销员问题：最后的喘息

• 批准号: 9528462
• 负责人: Vasek Chvatal
• 金额: $ 2.33万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1995
• 资助国家: 美国
• 起止时间: 1995-09-01 至 1996-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9528462&HistoricalAwards=false
• 关键词: Solving; Large; Travelling; Salesman; Problems

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.

该项目的目标是 开发一个新的算法的阐述旅行推销员问题。 这个问题在理论上是难以解决的，并且对于大型TSP问题的实用启发式技术一直难以捉摸。 1992年4月，一组研究人员通过解决名为TSPLib的标准测试数据库中的十个以前未解决的问题，创造了新的世界纪录，这些问题的规模从1，060个城市到3，038个城市不等。 (In特别是，3，038个城市的问题是有史以来解决的最大的TSPLib实例。 这个程序由四个人在四年的时间里开发出来，有大约5万行，还不包括实现单纯形法的代码。 该算法在其设计的每一个层面上都包含了新的想法，从新颖的方法到寻找切割平面，一直到数据结构的微小细节，更不用说并行计算的策略了。