用高等數學清掃馬路

孫偉敬

城市道路一年四季都要清掃，怎樣才能讓市政車輛在完成任務的同時少走重復路線，既高效便捷又節省成本呢？加拿大多倫多市的做法或許能帶給我們一些啟示。

作為加拿大最大的城市，也是加拿大的經濟、文化、交通中心，多倫多市每年的道路清潔花費不菲。從20世紀90年代起，多倫多市政部門嘗試著用“中國郵遞員問題”規劃清潔道路的路線，結果發現一年可以節省三百多萬加元。

“中國郵遞員問題”是一個高等數學問題，它是1962年由中國數學家管梅谷提出來的，即一個郵遞員走遍自己負責投遞的每個街道去送信，最后再回到郵政局，最短的路線是哪條？

美國數學家將這個問題命名為“中國郵遞員問題”。1973年，加拿大和美國的科學家為研究這個問題聯合提出了一個算法，這個算法受到了瑞士數學家歐拉的啟發。1735年，瑞士數學家歐拉提出了這樣一個數學問題：“某地有兩個小島，總共有七座橋連接這兩個小島和附近的陸地，怎樣走才能正好經過每座橋一次？”

這個問題是不是和你玩過的一筆畫成某種圖案的游戲很相似？這種能一筆畫成的圖形就叫歐拉圖。在數學家的眼里，這不僅僅是一個游戲，其中還蘊含了數學問題。經過眾多數學家的不斷探索，歐拉提出的問題后來發展成了圖論和拓撲學。

歐拉經過研究得出如下結論：只有當圖形的奇頂點（也就是邊的數量是奇數的頂點）的數量等于0或2時，這個圖才能被一筆畫出。北美科學家在此基礎上進一步發現：奇數分叉的路線，即遇到三岔路口或五岔路口，必然要走回頭路。

這個研究有什么實用價值呢？我們可以將其應用于清潔城市道路的路線規劃上。具體的做法是：首先單獨計算奇數路口，找到這些路口間的最短路徑;然后找到偶數路口之間只走一次的路徑;最后綜合起來找到最佳路線。

但是，現實生活中的情況往往比較復雜，比如單行線、交接班等，所以當時這個方法只能停留在理論探討層面。直到20世紀90年代，計算機技術取得了長足發展，上述種種復雜問題可以通過計算機進行通盤考慮，“中國郵遞員問題”才真正被用于指導多倫多市政部門開展道路清潔工作，他們發現這樣能節約大量的人力和物力。

有了多倫多市這個成功的先例，北美其他大城市也開始應用成熟的計算機軟件規劃市政道路清潔路線。這些軟件將城市的路線分割成塊，依據“中國郵遞員問題”的思路分別計算，然后規劃出最高效、最便捷的路線。以美國波士頓市為例，2015年波士頓突降大雪，鏟雪車共行駛47萬千米，鏟雪費用高達3500萬美元。幸虧早在2010年波士頓市政部門就感到非常有必要提高效率，節約成本，成立了工作團隊用數學方法和計算機來合理規劃鏟雪路線，否則鏟雪的費用還會大大增加。

除了清掃馬路，“中國郵遞員問題”還可以應用到許多方面。比如加拿大曾運用同樣的思路研究過城市中警車的配置、負責范圍及出事故以后警車的行走路線等。另外，和運輸有關的一些問題也可以運用這個思路解決，比如某個食品公司需要給30個超市送貨，如果不規劃路線亂送一氣，結果只會費時費力，還可能有所遺漏。

按照歐拉的理論，漢字“串”字可以一筆寫成，因為它的奇頂點只有兩個，分別位于最上面和最下面。感興趣的朋友不妨試一下。

（王世全摘自《知識窗》2021年第1期/圖 沐陽）