关于中国邮递员问题研究和发展的历史回顾_管梅谷

年月运筹 学 学报第卷第期 ， ： 关于中国邮递员问题研究和发展的历史回顾管梅谷摘要中国邮递员问题是运筹学研宄的基本问题之一 回顾了中国邮递员问题提出和解决的历史， 同时，介绍了对此问题研究的发展概况关键词 最短路问题，图上作业法，中国邮递员问题中图分类号 数学分类号， ， ， ，引 言在数学史上 ， 以中国命名的问题或定理出现得不多 有一个 “中国余数定理” 是广为人知的 这个定理在多年前就知道了 不过， 在近代又出现了一个以中国命名的问题 ， 那就是 “中国邮递员问题（， 以下简称）”这个问题是：一个邮递员每次上班，要走遍他负责送信的所有街道最后回到邮局， 问应该怎样走才能使所走的路程为最短？这个问题之所以被称为 “中国邮递员问题” ， 可以想象是在中国并且是由中国人最早提出的 事实上， 最早是出现在我写的文中 在这篇文章中 ， 同时还给出了解这个问题的一个算法， 就是奇偶点图上作业法但是在中， 没有给出所提问题的名称国外有关的第一篇文章出现在年， 是 写的 文章的名称就是“”】 在这篇只有一页的论文中， 把中提出的问题收稿日期 ： 复旦大学管理学院，上海 ；，通信作者 ：管梅谷卷称为， 并指出用他在年发表的求任意图的最小权匹配的算法】，可以得到解的一个“好” 的算法， 即多项式算法的文章发表以后， 开始几年没有看到有后续的文章 过了五六年后， 有关的文章就多了起来 包括问题的推广， 以及在许多不同领域中的应用 由推广而得出的许多问题， 被统称为 “弧路线问题 即服务对象在 “弧” （就是线）上的问题， 以区别于服务对象在点上的 “点路线问题” ， 其典型问题为 “”？等人在年发表的和 中 ， 对弧路线问题做了综合性介绍 文中有多篇参考文献， 从中可以看到的各种推广和在不同领域中的应用 在 年和年， 各出版了一本以 为名的书， 年刚出版的 计有页， 分章， 每章附参考文献， 总数超过篇 最后 章讲应用， 依次是： 抄表员与撒盐（第章） 、 扫雪（第章） 、 废品收集（第章）和送报（第章） 从这本书可以看出 ， 在几十年来的发展之后， 弧路线问题已成为运筹学中不小的一个课题由于在世纪六七十年代， 中国与其他国家在学术上的交流比较少 国外对的历史不大了解， 所以有一些不太符合事实的说法 例如在写的冏中 ， 第一句话就是“（）”，这里引用的 和 的文章见这种说法当然是不对的，但是也难怪， 由为在国外能看到的第一篇系统讲述的文章就是丨 不过， 这种说法除了丨以外， 在其他文章中未见有出现过 另外， 在 于年发表的名为： 的一文中， 他把计算机画图作为重点论述的占容之一， 其中花了相当的篇幅介绍 命哥尼斯堡七桥问题， 然后转到 他说： “， ”这个讲法也是不对的， 因为中国的 “文化大革命” 是年才开始， 而是早在年就已经提出 由于互相引用 ， 这一说法也出现在其他文章中 ， 例如在问中 ， 也引用的这种说法年， 到上海访问， 我与他见过他说他在上海大学做报告时， 曾谈到他说由于他用了这个名称， 让我出了名，也让我在 “文革” 中受到了批判 他问我这个说法对不对？我告诉他这是不对的 因为虽然他是在年给出这个名称， 但是中国人知道却是多年以后， 很可能是在 “文革”结束之后了 所以 ， 与我在“文革” 中是否被批判并没有关系产生的时代背景那么 ， 实际情况究竟是怎样的呢？在文 中， 第一句话是 “在邮局搞线性规划时， 发现了下述问题， ”这句话实际上包含了产生的背景 在年的秋天， 山东省政府发动了一项名为大搞科学研宄的活动， 并提出两个课题，其中之一是 “大搞线性规划” 这种“大搞科学研宄”的做法，现在的年轻人是很难理解的 ， 外国人就更难理解了（例如 的一个英文译文中， 把“在邮局搞线性规划时”译成 “”， 说明译者没有弄清“大搞线性规划” 的意思丨但是在那个时期确实发生过， 有兴趣的读者可以从书中看到有关资料 另外， 在最近看到由 和袁亚湘合写的文章 中， 则把的产生与年的大跃进联系起来这一说法也可以， 因为年山东省的大搞线性规划实际上也可视为大跃进的一期关于中国邮递员问题研宄和发展的历史回顾部分由于我在年的上半年曾 自告奋勇做过一些数学联系实际的试验，又曾在年暑假期间参加过科学院数学所在北京举办的运筹学讲习班 于是， 我当时工作的山东师范学院就派我参加这一 “大搞线性规划” 的活动 从年秋到年夏， 我一直在做这项工作 其中年上半年， 由于华罗庚教授提出要于年月在济南召开“全国运筹学现场会” ， 让各地的数学工作者来看看山东大搞线性规划的情况 我又在这个会议的筹备组工作了几个月 在这期间 ， 我的工作之一是讲课， 到全省不少地方去讲线性规划 ， 主要是讲物资调运中的图上作业法和表上作业法， 等 另外一个任务，就是到生产单位去寻找可以用数学方法解决的问题 在这段时间里， 我去过不少单位， 有工厂、 运输公司、 物资调运部门等， 当然还包括邮局 就是在这种情况下发现并提出的产生的过程去邮局是因为我在一些文献（例如 ）中，看到过 “旅行售货员问题， 以下简称）” 我感到这个问题在邮局中可能有用， 所以就去了 的提法是： 一个售货员从城市出发， 要到城市 ，去推销产品， 最后回到城市 问应该怎样走， 才能使所走的路程最短？ 我在邮局里很快就发现有几个问题可以归结为 例如， 邮局里有一些“开箱员” ， 他们的任务是收取投入邮筒里的信件 一般，每个人负责？个邮筒 ， 他们面临的是一个大约为？的 另外 ， 邮局每天要派车到十几个分局去收取各种邮件， 也会遇到为十几的 当然， 邮递员送信也会面临一个般地， 邮递员每次要送？个邮件（包括信和报刊等） ， 从而他面临的是一个为？ 的在当时， 由于对的研宄还很少， 计算机也没有普及， 因此要解？！为？的实际上是不可能的 为了研宄如何解决邮递员送信的问题， 我曾经跟邮递员一起骑自行车送过信 我所去的邮局把它的送信范围划分成块（称为个段），每个段由一位邮递员负责送信 当时， 我几乎跑遍了所有的这些段， 并画出了不少邮递员走的路线 在这个过程中 ， 逐步产生了不用 而用其它模型的想法把从用作为投递路线问题的模型， 转变为用作为模型的要点 ， 是把服务对象在 “点” 上变为服务对象在“线”上 产生这个想法的原因有以下两点 第一， 设若在一条街道路上从东到西依次排列着 ， ， ， 等个地方要送信， 如果把这一问题归结为， 那么在考虑各种可能的送法时， （ ， ，）的各种排列都应考虑到 但是事实上，如（ ， ， ， ，）这样的排列是用不到考虑的 邮递员一般或者按， ， 的顺序来送信 ，或者按， ，的顺序来送 因此， 我想到应该把一条街道上介于两个交叉点之间的一段路作为一个整体来考虑 也就是说， 不是考虑如何走遍所有要送信的点， 而是考虑如何走遍一些“一段一段的街道这样做， 至少服务对象的个数要少得多 第二， 按一般想法，如果一位邮递员为了在送信时少走一些路 他在拿到了要送的信之后， 应该看一下这些信的地址， 然后把这些地址在地图上标出来 再想想应该怎样送这些信走的路才会最短或者用现代的说法， 应该先把要送的信的地址输入计算机， 然后由计算机按编好的软件求出最短的投递路线在与邮递员一起送信后发现， 他们的做法却是这样的： 他们在拿到信以后， 就把这些信进行排序 ， 排完序后就出去送信了 在送信时， 先看第一封信的地址， 就去送第一封信 然后， 再看第二封的地址再送第二封， 直到把信送完， 就回邮局 那么 ， 他们是按什么原则来对这些信作出排序的呢？ 原来， 他们早就记住了一条走遍他负责送信的那个段的管梅谷卷投递路线， 就是从邮局出发后， 先走哪条路， 再走哪条路， 最后回到邮局 每次拿到信后 ， 就是按照这些信的地址在他的既定路线上的位置来排序， 把在路线上先走到的信排在前面，排好后就可以出去送信了 从上述邮递员的具体操作过程，我看到了一个重要的原则 就是邮递员走的路线实际上是一条走遍他送信的段内所有街道的路线， 而且每个段都有一条固定的路线 （与要送的信的地址无关） 我问过邮递员 ： “这种走法你是怎样想出来的？ ” 回答是：“从师傅那里学来的 原来当时训练新邮递员的办法是， 当一位邮递员快要退休前， 就会让他带一名徒弟 徒弟跟着师傅送信， 等过一段时间完全熟练了， 就可以独立工作 所以， 徒弟送信的路线和师傅的路线是一样的 我问过不少邮递员 ， 发现有很少几个改动过师傅的走法，而且改动得很少从邮递员送信的经验可以看出， 如果想要让邮递员走的路最短， 应该做的是使那条“师傅传给徒弟” 的路线为最短 也就是为他们设计一条： “从邮局出发， 走遍他送信的段内所有街道， 最后回到邮局的最短的路线 我就把这个问题定为要解决的问题有了明确的问题以后， 我就考虑如何给这个问题设计一个数学模型 因为我经常在纸上画邮递员走的路线， 很快就发现了这个问题与一笔画的关系 我小时候很喜欢玩数学游戏， 我有一位亲戚在我上初中的时候就教我玩一笔画的游戏一笔画作为游戏时， 主要是考虑能不能把一个图形用 “笔不离纸， 不重复的”方式画出来 他还教我如何判断一个图形能不能用一笔画出的办法 就是在年证明的定理：“一个图能从某一个点开始， 不重复地一笔画出， 并且最后回到起点的充要条件是： 图中所有的点都是偶点（即连接该点的弧是偶数条）” 由于在一个投递段的地图中经常会出现奇点，这时不重复的一笔画出是不可能的， 于是我想到了应该考虑允许重复的一笔画 也就是说， 求一条走遍一个段内所有街道的路线实际上就是把这个段的地图用一笔画（允许重复）的方式画出来这样， 我就明确了要解决的问题的数学模型是： “如何把一个给定的图形以一笔画（允许重复）的方式画出来， 并且所画的路线为最短有趣的是， 上面讲的定理现在只要学过图论的年轻人都知道 但是在年， 国内还没有出版过任何图论的书，我也不知道图论这个名称 我是因为小时候喜欢数学游戏才知道一笔画的 在写文章时， 我看到的参考文献只有 数学通报 上关于 “物资调运问题的图上作业法”一篇， 似乎太少了 后来想到在一本讲趣味数学的书中看到过一笔画， 于是把这本书也列在参考文献中 关于的算法有了的数学模型之后， 就想为它找一个算法 因为我在那段时间里， 经常在不同的地方讲物资调运问题的图上作业法， 并且刚完成了一篇 “图上作业法的改进” 的文稿 因此，很自然地想到模仿物资调运问题中的图上作业法， 来设计一个求最短投递路线的算法 很快， 这些事情就都解决了， 于是就写了“奇偶点图上作业法” 一文此文中的算法是一个迭代方法， 包括： （ ）求第一个可行解； （）捡查现有可行解是不是最优的 ； （）调整 这些步骤， 都与物资调运在图上作业法相似， 可以在中看到， 这里就不详述了有了算法， 接下来当然就想试试能不能把它用于解决实际问题 好在我己画了不少投递段上邮递员实际走的路线于是，我就用算法中的最优性判别定理来检查这些路线我原以为用这个算法， 可以对当时在邮局中正在使用的路线做出一定的改进 但是检查的结果使我吃了一惊！ 就是， 除了一个段可以做一些很小的改进外， 其余全是最优的 也就是说，这个算法在真实的投递路线问题上没有产生经济效益 不过 ， 仔细想想，这个结期关于中国邮递员问题研究和发展的历史回顾果也不意外 因为我检查的那些投递段， 规模都不大而那些投递路线都已用了很长的时间， 从师傅传给徒弟， 徒弟再传给新徒弟， 几代人用下来， 不断改进， 应该早就是最优的了 另外， 奇偶点图上作业法有一个很大的弱点 就是在检查一个可行解是不是最优解时， 要检查图中 “所有” 的圈 但一个图中圈的个数，是点或边数的指数函数 这一点我是一开始就知道的， 因为在我那时写的 中， 就指出了解物资调运问题的图上作业法有这个弱点， 并提出了改进的办法， 即：把检查所有的圈改进为只检查很少几个圈 所以，在发表以后， 我一直在考虑能不能对中的算法也作出改进， 但没有结果 那么 ， 既然有这一弱点， 我怎么用这个算法来判定投递员用的路线基本上都是最优的呢？ 那是因为每个投递段都不是很大， 投递路线上重复路比较少，所以能在检查时借助经验看出它们是最优的， 但并非绝对正确不过， 在世纪年代， 算法复杂性理论还没有出现 在评论一个算法的好坏时， 常常把容易学习和容易普及等作为标准 在解物资调运问题的图上作业法出现的时候， 也是以易学， 易普及备受称赞的 所以在当时， 对这些算法中的这类弱点， 并不太引起注意但是， 在算法复杂性出现以后， 这个弱点就应该看成是很严重的了 名称的产生我第一次知道国外有这一名称， 是在世纪年代 当时，看到了和合写的 一书丨 该书中有一章讲 提出的求一个任意图的最大 （或最小） 权匹配的算法， 其中有一节专门讲 书中指出用的算法结合图的最短路算法，可以得到解的算法 从该书中所讲 的内容可以看出， 这就是我在文中提出的问题 看到这些， 当然是很高兴的 后来我又进一步发现， 引用的是一篇用英文写的， 发表在名为 的杂志上的文章“”丨， 作者的名字被翻译为（ 年我遇到时， 他才知道我的姓是） 我从来没听说过名为 的杂志， 也不知道它是在哪个国家出版备 由于当时没有互联网 ， 要弄清一些问题不容易 所以一直到很多年后， 我才知道 是美国出版的， 目的是把中国发表的数学论文翻译成英文， 以供西方人阅读 我的两篇文章和的英文译文都刊载在这份杂志的第一卷中 但是， 这份杂志出到第二卷就停刊了 关于这个名称的来源， 在谈到历史的文章中几乎都提到了这个人 年时， 在 （现改名为， 简称）工作 在的网页上看到一篇报道说： “ ， （） ” 也就是说， 是因为在文章中 “提到的是投递路线的优化， 作者是中国人， 发表在中国的数学杂志上”， 所以建议使用这个名称的我想和给一个由外国人提出的数学问题取名 ，是因为他们看到了这个数学问题与研究的匹配问题之间的密切关系 在发表了一般图上的最管梅谷卷小权匹配算法时， 并没有提到它的应用 当他看到了文章， 就看出用匹配算法可以解决最短投递路线问题， 而使得他的算法有了一个很实际的应用 我感到他在中发表的算法是非常精彩的 但是在有了之后， 他的算法就成为不仅在理论上很重要， 并且是一个能用来解决实际问题的算法了 有关的发展文章是年在中国发表的 ， 它的英文译文年在美国刊出年， ？发表了在世纪年代， 就没有其它有关的文章了 唯一有点关系的是和发表的 在中， 两作者提出把一笔画问题推广为“允许重复并使重复边数最少” 的问题，并提出了用动态规划解决这个问题的办法 这个问题其实就是边的长都是的 在整个年代， 也就只有这几篇文章年， 的研宄生的硕士论文 就是写的在公用事业中的应用这可能是在 以后， 最早出现的与有关的文章 年， 和发表了丨文这是第一篇系统地研宄的论文 同年， 发表了文，这也是与有关的早期研究 之后，和他领导的小组做了很多有关 的研宄年和的 ，以及年和 的， 也是早期关于应用性的文章这几位作者，都是美国马里兰大学的 他们的研究队伍，在此后的几十年中对的理论与应用做了许多工作 年， 证明了混合图上的是完全的 在已知无向图和有向图上的都是有多项式算法的情况下， 这是第一个出现的完全问题 不过， 以后出现的新的推广就几乎都是完全的了世纪年代中期， 出现了弧路线问题这个名称 此后， 与有关的文章就愈来愈多了 包括问题的推广、 变形以及实际应用 ， 等等 这些资料在前面提到的中都可以看到 另外， 在理论研究方面， 也出现了不少与有关的成果 例如， 在所著的 關中 ， 以及文章和圳中， 都可以看到有关的一些理论研宄内容结束语我想， 在运筹学的研究中， 每年都会出现许多新的问题和模型 不少问题过了一段时间就被遗忘了 上面所提到的关于的研宄的发展， 则大大出乎我的意料 在世纪年代提出 时， 想到的只是为了解决投递路线问题 把一个原来服务对象在点上的问题变成一个服务对象在线上的问题来解决 没有想到世界上本来就有许多应该归结为服务对象在线上的问题，而没有被人研究过 结果是，文章成为研究服务对象在线上的路线问题， 即弧路线问题的第一篇文章让许多服务对象在线上的问题有了数学模型，从而使在几十年中得到了很大的发展我曾看到过一份名为 的报道， 其中按年度记载了与运筹学有关的重要事件的标题（只有标题，没有说明） 它包括： 模型的提出、 书籍的出版、 学会的建立、 新杂志的发行、 等等 其中包括有：“；”另外， 在 和 所写的 ， 中， 有一个同样标题的条目 ， 并附有说明和照片 我想可能是引起的后续研宄很多， 所以他们把的产生看成是一个重要的事件期关于中国邮递员问题研究和发展的历史回顾在我国，自世纪年代后期以来， 的名称和内容逐渐为运筹学界所认知 并且，从年代开始出版的 数学词典 数学名词 和 数学辞海 中， 都己列有专门的词条 但在中国的研宄和实际应用的报道则不是很多 今后， 希望有更多年轻的运筹学工作者能在这方面做一些工作， 更期待在中国能得到更多的实际应用参 考文献：管梅谷 奇偶点图上作业法 ？ 数学学报， ， ： ，（ ）： ， ，：，：，：， ， ：， ， ： ，：， ：，： ， ， ， ，？，： ， ： ：， 王元 华罗庚阐 北京： 开明出版社， ， ， ， ，： 管梅谷 图上作业法的改进数学学报， ， ： ，： ， ，：， ： ， ：， ，：， ，：， ，：，： ， ， ， ： ：， ，：，：， 谷超豪 数学词典 上海： 上海辞书出版社，： 丨丨 数学名词审定委员会 数学名词丨 北京 ： 科学出版社，：丨 胡毓达主编 数学辞海（第五卷）一运筹学丨 山西教育出版社、 东南大学出版社、 中国科学技术出版社， ：