Solving Large Traveling Salesman Problems: The Last Gasp

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

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

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.

1992年4月，一个由大卫阿普尔盖特组成的小组， 美国电话电报公司贝尔实验室，罗伯特比克斯比赖斯大学，瓦塞克& 罗格斯大学的Chvatal和Bellcore的William Cook 打破了10项世界纪录， 未解决的问题，规模从1,060到3038不等 城市，从一个标准的测试数据库称为TSPLib。 (In特别是，3,038个城市的问题是最大的TSPLib 曾经解决过）。 撰写论述的任务 的新算法是压倒性的：程序，开发 在四年的时间里， 千行，不包括实现 单纯形法 这个奖项是为了让Chvatal可以为自己买 在罗格斯大学的春季学期， 1993年，为了全身心投入写作， 与AT T贝尔实验室的同事们不断磋商& 在新泽西州的默里山和新泽西州莫里斯敦的贝尔科尔。