4.5 DIMACS挑战赛

各领域的研究者都在热火朝天地寻找TSP路线，这种涉猎领域的广度虽然是TSP的优势，但是也曾导致人们对当时的技术水平认识不足。事实上，在20世纪80年代，《自然》杂志之类的顶尖科学期刊都曾刊载有关计算的论文，而文中描述的TSP题目仅包含三五十座城市，发表的结果也往往只是弱逼近。然而与此同时，LK算法已经可以保证在转瞬之间给出最优解，Martin Grötschel和Manfred Padberg也在用精确算法求解包含成百上千座城市的题目。

20世纪90年代，两大事件试图解决这种矛盾状况。第一件事是TSP 90大会，举办方是莱斯大学并行计算研究中心。来自世界各地的研究者济济一堂，既有精确算法方面的专家，如Grötschel和Padberg等人，也有研究寻找路线方法的课题组。TSP的测试题目数据库TSPLIB由德国海德堡大学的Gerhard Reinelt创建。它于1991年面世，就是这次大会的重要产物。TSPLIB数据库收集了来自学术界和工业界的逾百道TSP难题，为各地区各学科的研究人员提供了公共的试验台。¹

^{1. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/.}

第二件则是DIMACS的“TSP挑战赛”（TSP Challenge），发起人是AT&T研究所的David S. Johnson。DIMACS全称为具体数学与理论计算机科学中心（Center for Discrete Mathematics and Theoretical Computer Science），坐落于罗格斯大学。20世纪90年代，该中心举办了一系列有关算法实现的挑战赛，其中最著名的就是TSP挑战赛。²

^{2. http://www2.research.att.com/∼dsj/chtsp/about.html.}

图4-29　左图：Martin Grötschel、Gerhard Reinelt和Manfred Padberg；右图：Robert Tarjan、Dorothy Johnson、Al Aho和David Johnson

TSP挑战赛的一大目标是纵览TSP启发式算法领域技术发展水平的现状，描绘出可以再现的全景图。这样，以后的算法设计者就能很快自行判断，新算法与现有TSP启发式算法相比有何优劣之处。

DIMACS向全世界的寻找路线研究者发出了征集请求，并收到了130种不同的算法和程序实现，最后得到了两项重大成果：其一是一家网站，研究者可以在网上直接对比不同解法；其二则是一篇优秀的综述，作者是Johnson和另一位组织者Lyle McGeogh。³

^{3. Johnson, D. S., L. A. McGeogh. 2002. In: G. Gutin, A. Punnen, eds. The Traveling Salesman Problem and Its Variations. Kluwer, Boston, MA. 369–443.}

Johnson在组织挑战赛方面付出了巨大的努力，他个人对于寻找路线的方法也做了详尽的计算研究。他的工作大大推动了算法工程的发展，决定了该领域的现状。2010年，他获得了美国计算机协会颁发的高德纳奖（Knuth Prize），获奖理由是他为算法理论分析与实验分析作出了杰出的贡献。他作为TSP研究的世界级领袖，这样的表彰当之无愧。