2.1 数学家出场之前

人类早就开始着手解决具体的TSP应用问题，而关于它的数学研究在很久以后才渐渐蔚然成风。无疑早在穴居人的年代，我们的祖先就在狩猎采集时解决了一些路线规划问题。这些规划问题的规模很小，可能不像长期规划那样有意义。然而，最近几百年来，在某些特定行业，精心规划的路线显然对从业人员很有帮助。我们的讨论不妨就从观察这些人的旅途开始。

2.1.1 商人

说起旅行商问题的由来，须知旅行商确实是最早开始规划路线的人。图2-1是一张城市列表，来自旅行商H. M. Cleveland在1925年写的书信。¹Cleveland在美国培基种子公司（Page Seed Company）上班，工作内容是收集玉米等农作物的订单。这张表摘自一份文件，全文共5页，列出了他在缅因州巡回的主要目的地。差旅从7月9日开始，一直持续到8月24日才结束，全程共经过350站，数目相当惊人。

_{1. 这张表来自本书作者从eBay购买的一组藏品。这批收藏品数量很大，都是H. M. Cleveland寄给培基种子公司的账单和信件，能买到它们实在是运气不错。但我并不是总能买到有意思的东西，比如我还买过某个旅行商写了50年的日记，结果发现，他的“旅行”只限于纽约州雪城周围的五六座城市而已。}

图2-1　培基种子公司旅行商的缅因州目的地列表（全文共5页），1925年

显然，Cleveland和培基种子公司当时很关心如何才能让旅途时间最短。我们有两个证据：第一，如图2-2所示，他的旅行路线明显效率很高，虽然有一些回头路，但都是限于当时的道路建设情况，个别城镇与外界之间只有一条路相通，所以只能选择原路返回；第二，请仔细阅读下面这封Cleveland写给其老板的信。

尊敬的先生：

我的路线乱得一团糟，从没见过这么乱的。又要花掉去年一半的工夫来整理路线了。我已经改了一部分，从斯托克顿斯普林斯开始，挨个经过法兰克福、温特波特、汉普登海兰兹、班戈、斯蒂尔沃特、奥罗诺、奥尔德敦、米尔福德、布拉德利、布鲁尔、南布鲁尔、奥灵顿、南奥灵顿、巴克斯波特，然后到了奥兰，再接着走原来的路线。

希望您能将我1924年用过的单子寄给我，我想要从德克斯特开始的后半程路线。那个路线比手头这个好太多了。我不明白您到底为什么要让路线有那么大的跳跃，特别是从阿尔比恩居然一下子跳到麦迪逊，简直是从地图这一头跳到那一头。这部分我自己改了。

从班戈开始，往南就没有桥能过河了，可您还把那里的城镇都列在单子上，就好像我有本事过去似的。上一季列出来的单子是最好的，我实在看不出为什么要改。我想我已经把话都说清楚了。

您忠诚的H. M. Cleveland

1925年7月15日

可见，Cleveland对部分路线非常不满，并且自己动手改进路线的设计。

图2-2　培基种子公司旅行商的缅因州差旅路线图，1925年。旅行从基特里出发，最终回到斯普林韦尔。两座城市距离很近，均位于缅因州南部

1925年，Cleveland去了很多地方，缅因州只是目的地之一。他的旅途还经过了康涅狄格州、马萨诸塞州、纽约州和佛蒙特州，总共到了一千多个目的地。他也绝不是唯一一个来回奔波的人。Timonthy Spear为美国旅行商写了一本书，名为100 Years on the Road: The Traveling Salesman in American Culture（《百年奔波：美国文化中的旅行商》）。他在书中提到，据Commercial Travelers Magazine（《旅行推销员杂志》）估计，1883年美国有20万旅行商；到了19世纪末20世纪初，估计有35万人；20世纪早期，这个数字仍在增长；到了Cleveland的年代，旅行商已经是大多数美国乡镇的常客了。

Spear也描述了这些旅行商如何参考L. P. Brockett的Commercial Traveller's Guide Book（《旅行推销员指导手册》）之类的工具书，在自己工作的区域内设计路线。然而，多数情况下，路线是由总部预先制定好的，就像培基种子公司的做法一样。一种优化方法如图2-3所示，工作人员在地图上用图钉和细绳标出各条备选路线，并借此比较路线长度。

图2-3　兰德·麦克纳利的地图收纳柜与标针地图，《秘书学》（Secretarial Studies），1922年

一本1832年出版的德国手册是这段故事的重要参考文献，这本书德语书名为Der Handlungsreisende — Von einem alten Commis-Voyageur，翻译成中文就是《老推销员写给新旅行商的指南手册》²。简便起见，以后都称其为《指南手册》。手册里提到，好的路线很有必要。³

_{2. Der Handlungsreisende — wie er sein soll und was er zu thun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiss zu sein — Von einem alten Commis-Voyageur. B. Fr. Voigt, Ilmenau, 1832. 完整书名意为《老推销员写给新旅行商的指南手册：你该如何表现、如何工作、如何确保成功》}

_{3. 该书节选片段由Linda Cook从德文原文翻译为英文，后转译为中文。——译者注}

图2-4 　德国旅行商指南手册，1832年

由于商务需求，旅行商四处旅行。放之四海而皆准的好路线并不存在，但是通过有效的选取和分解路线，可以节省大量旅行时间，因此我们觉得有义务提供一些这方面的指导意见。只要这些建议对你们有帮助，你们就应当尽量采纳和实践。我们可以保证，对于穿行德国的旅途，由于距离遥远，再加上来回奔波（请格外注意这一点），其他路线都不可能比我们的做法更节约。要记住，重点是到达尽可能多的地点，同时避免重复经过同一个地点。

这里明确叙述了旅行商问题，而叙述者本人就是一名旅行商！

《指南手册》提供了经过德国和瑞士境内不同地区的5条路线。在其中4条路线里，都出现了作为局部根据地的城市，因此这些城市都要到达不止一次。但是第5条路线如图2-5所示，是一条真正的旅行商路线，其旅行区域在德国所处的位置参见图1-9。正如《指南手册》所说，这条路线非常好，考虑到当时的道路情况，它甚至可能是最优路线。

若以为推销员的生活

没有艰难困苦与风波，

你必然大错特错。

因为他在泥泞中跋涉，

冒着雨雪和冰雹工作。

他拎起提包，勇敢上路，

走南闯北寻顾客。

图2-5 《指南手册》提供的路线，1832年

19世纪中后期，人们精挑细选美国、英国等国家的旅行路线，集结成册出版了大量书籍。旅行商的形象充满浪漫色彩，也在戏剧、电影、文学与歌曲中留下了身影。在19和20世纪之交的旅行商诗作中，下面这段很有代表性。它摘自一本作品汇编集，出版于1892年。⁴

若以为推销员的生活
没有艰难困苦与风波，
你必然大错特错。
因为他在泥泞中跋涉，
冒着雨雪和冰雹工作。
他拎起提包，勇敢上路，
走南闯北寻顾客。

_{4. 这段诗是诗歌The Drummer（《推销员》）的开头部分。作品集：Marshall, G. L. 1892. O'er Rail and Cross-ties with Gripsack. A Compilation on the Commercial Traveler. New York, G. W. Dillingham。}

推销员的辛苦工作与寻找路线的任务甚至出现在桌面游戏中。1890年，麦克劳克林兄弟公司（McLoughlin Brothers）发明了“旅行推销员游戏”（Commercial Traveller），玩家要在铁路系统里自己建造路线。

选择旅行商作为TSP的代言人，显然有理有据。

图2-6　旅行推销员游戏，由麦克劳克林兄弟公司于1890年推出，Pamela Walker Laird供图

2.1.2 律师

虽然最先出场的是旅行商，但是也曾有一些从事其他职业的人需要四处奔波。早在15世纪，《牛津英语词典》里就收录了“circuit”一词，意为巡回旅行或巡回路线。这个词的由来与英国的司法管辖区制度有关。当时英国各地的法庭是每年定期开庭审理案件的，因此法官和律师都要在自己管辖的各城镇之间巡回。后来，美国也采用了这种制度。时至今日，虽然法官不再需要巡回奔波了，但美国人仍然把地方法庭称为巡回法庭。

美国历史上最著名的巡回律师很可能是青年时代的亚伯拉罕·林肯。林肯在成为美国第16任总统之前，曾经在法律界工作，参与伊利诺伊州第八法庭区的巡回，负责14个县的公务。Guy Fraker描述了林肯的旅途。¹

_{1. Fraker, G. C. 2004. Journal of the Abraham Lincoln Association 25, 76-97.}

每年春秋两季，法庭都会连续开审数周，依次在14个县²分别开庭。除了斯普林菲尔德（Springfield）以外，其他每个县开庭最多一周。斯普林菲尔德是桑加蒙县的首府，也是伊利诺伊州的首府。秋季法庭在这里开庭两周。然后所有律师动身前往55英里以外的北京（Pekin），这里于1850年取代特里蒙特成为了塔兹韦尔县的首府。一周以后，他们再行进35英里，在麦特毛拉（Metamora）待三天时间。接下来向东南方向前进30英里，到达布鲁明顿（Bloomington）。这是旅途中的第二大城市，因此事务较多，他们可能要在此地多逗留几日。下一站是相距35英里的普拉斯基山（Mt. Pulaski），这里于1848年取代波斯特维尔成为了洛根县的首府，几年后又将被新成立的林肯市取代——但是此时林肯尚是巡回律师中的一员。众人继续赶赴下一个县，然后是另一个，目的地一个接一个，直到走完整条巡回路线。全程一共经过11周时间，总路程超过400英里。

_{2. 美国政治区划制度与我国不同。虽然“county”翻译为“县”（有时翻译为“郡”），但这一级行政区仅次于州，不应与我国的“县”混淆。——译者注}

文中，Fraker还提到，多次走完巡回全程的法庭工作人员为数极少，林肯是其中之一。图2-7中画出了1850年林肯和其他工作人员的巡回路线。这跟最短路线还有一些差距，至少只考虑距离、不考虑路况的话还可以更短。但是可以明显看出，规划路线的人确实有意尽量缩短巡回路线的长度。

图2-7　1850年伊利诺伊州第八法庭区的巡回路线

2.1.3 牧师

也许是法官和律师的差旅带来了巡回一词，但是若论巡回工作的名气，18世纪和19世纪的基督教牧师毫不逊色。约翰·卫斯理（John Wesley）是基督教新教卫斯理宗¹的创立者。1791年，John Hampson在卫斯理的传记中写道：“在英国和美国，每个地区都分成固定的几部分。这些小区域称为巡回区域，一般包含20～30个地点，由巡回牧师负责。巡回牧师人数一般在二到四人之间，每巡回一次需要花费一个月或者一个半月的时间。”²在英国、美国和加拿大的民间，都留下了关于这些巡回牧师的旅行情况的传说。你可以从下面这些摘录里体会到他们的路程有多长。

_{1. 又称为循道宗、卫理宗，是基督教新教主要宗派之一。——译者注}

_{2. Hampson, J. 1791. Memoirs of the late Rev. John Wesley. J. Johnson, London, UK.}

我路上经过了大约5000英里，向人们做了大约500场布道，走过了弗吉尼亚州和北卡罗来纳州的大部分路线。

——Freeborn Garrettson，1781年³

_{3. Banks, N. 1830. The Life of the Rev. Freeborn Garrettson: Compiled from his Printed and Manuscript Journals, and other Authentic Documents. New York. Published by J. Emory and R. Waugh.}

当时我们的巡回路线全程500英里，我在短短四周之内做了63场布道，赶了500英里路。这实在太难了，但是我向上帝呼喊，上帝听到了我的祈求，赐予了我强大的力量。

——Billy Hibbard，1825年⁴

_{4. Hibbard, B. 1825. Memoirs of the Life and Travels of B. Hibbard: Minister of the Gospel, Containing an Account of his Experience of Religion. New York. Published by the author.}

他们都是卫理公会教派的牧师，我没有资料，不知道较长的巡回传道路线具体是怎么走的。但是完全可以推测，他们选择的路线肯定也经过了一定的规划。对他们来说，工作的一大目标就是接触尽可能多的教友，因此缩短旅途中的时间肯定是个重要的考虑因素。