|
供应链管理上，涉及运筹计算的，有个著名的问题，叫做旅行推销员问题，而同样出名的还有一个中国邮递员问题。 此问题由中国数学家管梅谷于1960年首先研究并给出算法，因此被命名为“中国邮递员问题”。 中国邮递员问题，又称为中国邮递员路径问题或者邮递员巡逻问题，是图论和组合优化领域的一个经典问题。 它来源于实际的邮递问题：简而言之：中国投递员问题是指邮递员从邮局出发送信，要求对辖区内每条街，都至少通过一次，再回邮局。这个问题可以看作是更著名的欧拉路径问题的推广，其中欧拉路径要求每条边恰好走一次，而中国邮递员问题则允许某些边被重复走过。 在此条件下，怎样选择一条最短路线？邮递员如何能够以最短的总距离遍历所有的路线至少一次，并最终返回到出发点。这个问题的目的是最小化邮递员在完成任务时的总行走距离。 假设这个城市有8个街道，每个街道都有一个编号（1到8），邮局位于街道1。街道之间的距离如下：
根据中国邮递员问题的解决方法，我们可以使用动态规划来求解这个问题。首先，我们定义一个二维数组dp[i][j]表示从中心出发访问前i个街道并返回中心的最小距离。其中，i表示街道的数量，j表示当前访问的街道编号。初始时，dp[1][1] = 0，因为中心到自己的距离为0。然后，我们按照从左到右、从上到下的顺序依次计算dp[i][j]。对于每个dp[i][j]，我们可以考虑两种情况：
最终，要求的是dp[8][1]，即从中心出发访问前8个街道并返回中心的最小距离。根据动态规划的递推公式和初始条件，可以得到以下结果： dp[8][1] = dp[7][2] + d[2][3] + d[3][4] + d[4][5] + d[5][6] + d[6][7] + d[7][8] + d[8][1] = 100 + 200 + 150 + 250 + 300 + 250 + 350 + 100 = 1650 因此，中国邮递员问题的解为最小距离为1650米。这个结果可以帮助邮局规划出最优的投递路径，提高投递效率。 上面的算法就是动态规划，很头疼，但为什么要考虑这个问题呢？大家有没有想过，平时路上的洒水车、铲雪车，还有马路清扫是怎么规划行车路线的呢？ 不能理所应当的想这还不简单，哪儿没有跑过就去跑一遍不就行了嘛。这种方法的确能保证所有的道路都被打扫了，但是车子可能会在某几段马路上重复开，损失燃油和时间。而且实际生活中扫马路、洒水和铲雪要比这复杂得多。 比如，高速公路的整洁对司机的生命财产安全更重要，所以要早点清扫完毕；一些路段是单行线，或者对大型车辆限行。此外，“邮差”也不只一个人，而且不能无限“肝”活，清洁车之间的交接班也要考虑在内等各种情况。 而且最难搞定的是奇数分叉的道路，遇到三岔路口、五岔路口，走回头路几乎是必然。 所以，是这样的，扫马路、洒水车、铲雪车这类问题在数学上就都属于中国邮差问题。中国邮递员问题的解法可以通过动态规划、启发式算法、模拟退火算法等多种方法实现。 比如到了20世纪90年代，随着计算机技术的进步，一些数学家开始尝试把中国邮差问题应用到日常生活中。比如，明尼苏达大学的数学教授 Peh Ng 就曾用图论的思想帮明州莫里斯市政府规划冬季的铲雪线路。 而从2001年开始，北美的一些大城市就开始用比较成熟的软件（如 ArcGIS）来规划铲雪车的行车路径。这些软件一般会把一大块城市交通网分割成一小块一小块的，然后分别再进行计算。
多伦多在用图论原理对铲雪线路进行规划后，铲雪费用比之前减少了三分之一，每年节省了大约3百万美金（约合2千万人民币）。 多伦多的市政道路交通的运营经理 Hector Moreno 表示，在用ArcGIS之前，行车路线主要靠经验和人工计算，现在就不需要这么麻烦了。 2010年，波士顿市政府也组建了自己的数学团队——Mayor's Office of New Urban Mechanics，用数学和计算机来规划铲雪路线。 像波士顿这样的大城市用数学进行规划真的太有必要了。2015年，为了铲雪，波士顿的铲雪车一共开了47万千米，差不多可以绕地球12圈了。铲雪的花费也是惊人的，那年的暴雪让波士顿一共掏出了3500万美金（约合2.3亿人民币）。 除了道路养护，中国邮差问题的算法在很多领域还有应用。比如在交互设计时，中国邮差问题就被用于终端产品的可用性检测。 🌰： 一个手机被制造出来以后，手机制造商想要看看每个功能是不是和名称相符。比如按下主键，点开“设置”，再点开“网络”，是不是真的会出现网络设定功能。 因为手机的功能很复杂，不同功能之间形成的网络要怎么样才能有效地走个遍，这个问题有时连制造商也搞不太明白。1996年诺基亚出的2110的菜单有88个项目，一共有273种操作。如果随便按，可能一些菜单永远也不会得到检测。 但是利用中国邮差问题的算法就能规划测试路径和计算步骤数量了：最少就只需要按594次键盘按钮就可以把所有的菜单和功能都过一遍了。 它们涉及到不同的领域和问题类型。但是，无论是哪种应用场景，中国邮递员问题的解决方法都可以帮助人们找到最优的路径规划方案。 |
|
|
