别催快递小哥了!他们可能正在画路线图!

作者: 张远南 张昶

来源: 原点阅读

发布日期: 2021-12-01 15:03:25

文章讨论了运输和快递路线优化的数学方法,包括运筹学中的图上运筹论供需和奇偶点原理在投递线路问题中的应用。通过详细的图解和实例,展示了如何通过调整流向和投递路线来减少运输成本和提高效率。

在我们这个繁忙的星球表面,布满了密密麻麻的交通网,每日每时都有数不清的车辆在这种网状的道路上奔驰,也有无数快递员穿梭在城市之中,他们的任务是把各种物资从地球上的一个角落移动到另一个角落。但是,很少有人思考一下这样做是否合理。很多快递员和司机全都我行我素,按各自既定的想法去做:多装,快跑,减少空车!

我们先来聊聊运送货物的货车。倘若各位能有机会向那些司机们打听一下,问问他们在尘土飞扬的道路上忙碌些什么,或许你会发现一些极为奇怪的现象:运输力存在着惊人的浪费,不少车辆正在不遗余力地做无用功!举例来说,下图是一张某种物资调运的流向图。图中的“○”表示该地调出物资;“×”表示该地调入物资;写在旁边的数字为供需数量;道路右侧的箭头“ →”表示物资流向,箭头上的读数(m)为该流向上的流量。

很明显,图(a)的调运方案是不合理的。因为在BE—段道路上出现了运输对流的现象。这种对流无疑造成了浪费,不如改为图(b)的调运方案更好!另一种运输力浪费的现象是迂回:在成圈的交通图上,从一地到另一地的两条路中,如果有一条小于半圈长,则另一条必大于半圈长。假如这时我们不走小半圈而走大半圈(下图),这便是迂回。

迂回现象有时似乎相当隐蔽。

如下图所示的调运方案,交通供需图上有大小3个圈,其中由〔CDEFGH〕所围成圈的外圈流向长(简称外圈长)为GF+ED+CH =252+317+180=749超过了该圈长度1381的一半,所以外圈流向出现了迂回。这是不太容易一眼看出的!数学家已经从理论上证明,凡是有对流和迂回的调运方案一定不是最好的。对流的不合理性是不言而喻的。迂回的出现,则表明至少存在一个圈,它的外圈长或内圈长大于该圈长的一半。

这时,我们一定有办法通过调整,使它变为所有的外圈长和内圈长都小于半圈长的流向图!而这样的调整必然使总运输量相应减少,从而得到比原来更优的方案。反过来,数学家们还证明了没有对流和迂回的调运方案一定是最优的!

这一判定法则可以归纳为以下的口诀:物资流向画两旁,发生对流不应当;里圈外圈分别算,都不超过半圈长。很显然,对于不成圈的供需图,自然谈不上什么迂回。因此只要流向图不出现对流,调运方案便是最优的。要做到这一点,只要从端点起逐步由外向内供需配平就可以了。

现在我们再看看,怎样去寻找有圈供需图的最优调运方案? 下面介绍一种称为“缩圈法”的巧办法。为了说明这种方法,我们仍旧采用前面讲过的例子。先在交通供需图上画出一个没有对流的初始方案。这是容易做到的。实际上前面图中标的就可以看成是一种初始方案。相应于这一方案的调运表如表所示。

说完运送货物的巧方法,我们再来聊聊离我们生活更近的快递小哥。

先来明确一个概念:一个连通的网络,当且仅当它的奇点数为0或2时,才能由“一笔画”画成。而且要使它成为一个首尾相接的封闭回路,网络的顶点必须全是偶点。这是大数学家欧拉于1736年首先发现的。1959年,我国山东大学的一些学者,把前文中讲到的物资调运的图上作业法,与200多年前欧拉发现的奇偶点原理联系起来,巧妙地运用于以下的投递线路问题,在实践应用上迈出了可喜的一步!

大家知道,快递小哥为了完成投递任务,每天必须从快递点出发,走经投递区域内的所有道路,最后返回快递点。快递小哥应当怎样安排自己的投递路线,才能使投递线路最短呢? 这显然是邮递员所苦恼的问题。下面让我们分析一下投递线路问题的实质。

很显然,投递的线路必须是连通的。因而,对某个邮递员来说,他所负责的投递路线,可以看成是一个脉络。如果上述脉络所含的全是偶点,那么脉络中的所有弧线便能形成一条封闭的回路。此时,求最短投递线路,实际上就是“一笔画”问题。而且邮递员从邮局出发,最后回到了邮局,完成了一次循环。

如果一个投递网络除了偶点之外还含有奇点,由于网络的奇点必定成双,因而我们可以将奇点分为若干对,在每对奇点之间用弧线连接,使添加弧线后的新图形成为不含奇点的脉络。前面说过,这样的脉络的全部弧线可以构成一条封闭回路,从而为邮递员提供了一条可行的投递线路。

下是一个简单的例子。图中的方格状道路网代表投递区域,“★”为快递点,奇点间添加的弧线画成虚线,相应的投递路线为K(★)→H →G→F→E→D→C→B→A→I→A →B→J→D→E→K→J→I→H →K(★)容易算出这条投递路线的总长度为140个单位长度。

你可能已经注意到,对于一个网络,奇点间用弧线连接的方法是多种多样的,各种添加的方法都提供了一种可行的投递路线。问题是,哪一种投递路线才是最合理的呢?答案几乎是显而易见的!即添加进去的弧线应当越短越好。要达到这一点,显然必须做到以下两点。

(1)添加进去的弧线不能出现重叠;(2)在每一个圈状的道路图上,添加进去的弧线,其长度的总和不能超过该圈长的一半。

用上面两条原则,判断一下前面例子中的那种弧线的添加方法,就会发现其中有不合理的地方。在〔ABKH〕圈中,添进弧线的总长度显然大于该圈长度的一半!对于添加进去弧线的总长度大于圈长一半的情形,有一种简单易行的调整办法,可以使得添加弧线的总长度小于半圈长。小伙伴们只要看一看下图,便能了解这种方法。即在该圈中,撤去原先添加的弧线,改为添加原先没有添加的部分。

这样做,网络所有顶点的奇偶性都没有改变,但却使总弧线的长度减小了,其道理是显而易见的!

现在回到前面的例子上来。按上面的办法调整后可得上图。此时,相应的投递路线为K(★)→J→K→H→G→F→E→D→C→B→A →I→H →I→J→B→J→D→E→K(★) 投递路线的总长度容易算得为132个单位,比原先少了8个单位。不难看出,所得的新网络已经符合前面提到的两条原则,因而相应投递线路已是最为合理的了!

邮递线路问题的解决,是奇偶点原理与图上作业法的科学结合,是数学知识古为今用的典范。以下生动的口诀,将帮助你记住这一有用的方法:先分奇偶点,奇点对对连;连线不重叠,重叠要改变;圈上连线长,不得过半圈。

UUID: 3f290f5b-b2b1-4b29-8f9f-5ffe3b81d680

原始文件名: /home/andie/dev/tudou/annot/AI语料库-20240917-V2/AI语料库/中科院物理所公众号-pdf2txt/2021/中科院物理所_2021-12-01_「转」别催快递小哥了!他们可能正在画路线图!.txt

是否为广告: 否

处理费用: 0.0073 元