这是加拿大乐活网公众号的第150篇原创文章
图源：Darryl Dyck/The Canadian Press
每年冬天，在加拿大各个城市的“除雪战役”中，都需要部署大量的铲雪车和撒盐车，沿着城市道路作业。
随着雪一直下，想要保持道路清洁，并不是随随便便派出一堆铲雪车那么简单。
尤其是遇上暴雪，铲雪车的数量又有限，想要快速有效地清除所有道路积雪，同时还要节省时间和车辆燃油消耗，就需要尽可能选择一条最优的路线。
而这条路线，可不是铲雪车司机说了算。
位于高纬度地区的加拿大，天气寒冷，暴风雪是常事，一些城市甚至要下半年的雪。如何选择一条可以到达所有道路、且总路程最短的铲雪路线呢？
这时候，就要中国人的数学原理出马了。
图源：munciepower
小时候学过奥数的人也许还有印象，常常要解的一类题叫做“邮递员问题”：邮递员必须把信件送到每条街道上的每个家庭，但是，他要尽可能少走回头路。
这个原理其实也适用于城市清洁的多种情况，从收垃圾到除雪。
图源：Worker”s Daily
早在18世纪，瑞士数学家莱昂哈德·欧拉（Leonhard Euler）在他著名的“哥尼斯堡七桥问题”上，就证明过，确实可以找到一条路线，不用折返就能完全覆盖每一个路段。
什么是“哥尼斯堡七桥问题”呢？
说的是有一条河穿过哥尼斯堡，河中有两个小岛，有七座桥把小岛和两岸相连，如下图a：
图源：researchgate
有个人提出了一个问题：一个步行者怎样才能不重复、不遗漏地一次走完七座桥，最后回到出发点？
于是大数学家欧拉就把它转化成了一个几何问题，即“一笔画问题”，如上图b。这个一笔画的游戏，我们小时候也都玩过。
但这个问题有解决方案的前提是，每个交叉口需要有偶数条道路连接，比如双向和四向交叉路口就满足这个条件。但如果是连接三条道路的丁字路口，或者连接五条道路的多向路口，就不能实现。
这意味着，在任何一个现实中的城市，一些道路的折返是不可避免的。
瑞士数学家莱昂哈德·欧拉（图源：wikipedia）
既然折返不能避免，那总能想办法把折返次数降到最少，找到最短、最省时的线路吧？
这时，中国的数学家就出马了。
1962年，中国数学家管梅谷将欧拉的结论延申，以邮递员送信的方式描述了他的问题：送信的邮递员要设法找到一条最短的路径，可以走过地区内所有的街道，且最后要回到出发点。
管梅谷根据奇数和偶数的交点分叉数量，提出了有效的解决方案，使每一个点都能走到，路径有可能有重复，但可以找到总长度最短的最优线路。
管梅谷的解法叫做“奇偶点图上作业法”，世界上称之为“中国邮递员问题”（Chinese Postman Problem）。
中国数学家管梅谷（图源：sina）
“中国邮递员”是如何工作的呢？
简单地说就是，需要在连接奇数条道路的交叉路口间找到最有效的路线。
正如欧拉所展示的那样，这些路口是唯一迫使你回头折返的地方。因此，要找到最佳的整体路线，你必须确定所有奇数条道路的交叉口和所有可能的行进方式，以找到最有效的路径。
然后，把这些路线和所有连接偶数条道路的交叉口的路线结合起来，就能找到最有效率的路线。
美国数学家杰克·埃德蒙兹（Jack Edmonds）还在1973年为此研究出了一个算法，可以快速有效地找到答案。
图源：sciencedirect
数学家们都觉得，“中国邮递员问题”简直就是一个完美的铲雪方式！
明尼苏达大学数学家Peh Ng认为，即使是一个由22万条道路和30万个交叉口组成的城市布局，这个方法也是可行的。
在20世纪90年代，她还把这个算法应用到了家乡莫里斯（Morris）的除雪线路优化计算中，城市管理者们也采用了这个方法。
图源：wikipedia
但是，现实生活永远要比数学题复杂得多。
“中国邮递员问题”的解决方案只适用于简单的场景，比如只有一台铲雪车在工作。但大多数城市都有几十台、甚至上百台铲雪车，而且每辆车只负责特定的区域。
其他一些因素也需要被考虑进去，比如高速公路和快速路的除雪通常要优先于普通住宅街道；铲雪车是从位于城市各个角落的车库被发配出来，而不是同一起点；每位铲雪车司机需要有相同的工作时间，又能完成自己辖区里的除雪任务……
这让工程师们需要先将城市“分解”，将一个街道网络划分为更小的网络，然后再使用“邮递员算法”单独处理。
图源：wikipedia
很多规划“铲雪车怎么走”的商业软件也被研发出来，比如ArcGIS，加拿大一些大城市开始使用这类软件来规划铲雪车的行车路线。
维多利亚铲雪车路线（图源：arcgis）
比如多伦多自2001年开始使用这个系统以来，在城市道路除雪效率方面有了显著的提升。
从前，人们总是凭感觉手工规划路线；现在，不必再依赖个人经验，就算老员工离职或退休也不会有任何知识和经验的流失。
新计划同时也节省了资金。多伦多冬季大部分道路的维护还包括撒融雪盐，和铲雪一样，撒盐的路线同样需要优化。
自2001年以来，效率更高的路线使多伦多的冬季除雪成本降低了30%。这个城市每年在雪季要撒放13万吨盐，在花费上节约了500万加币。
中国邮递员的数学原理，果真帮了大忙。
图源：TorontoComms/Twitter
但也有一个让人忧心的事实。
以温哥华为例，这里今冬的第一场雪，厚度约为10厘米。从1981年至今，温哥华的年平均降雪量一直在减少，从十年前的45厘米降至了24厘米。
随着温室效应和碳排放量的增大，有科学家预计，全球未来的降雪量将逐年减少。
网络时代，邮递员的书信已经渐渐消失；说不定哪一天，我们连用“邮递员算法”找出最经济的除雪路线都不需要了，那才悲哀。
封面图源：maximinc
