用高等數(shù)學(xué)清掃馬路

孫偉敬

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

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

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

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

這個(gè)問題是不是和你玩過的一筆畫成某種圖案的游戲很相似？這種能一筆畫成的圖形就叫歐拉圖。在數(shù)學(xué)家的眼里，這不僅僅是一個(gè)游戲，其中還蘊(yùn)含了數(shù)學(xué)問題。經(jīng)過眾多數(shù)學(xué)家的不斷探索，歐拉提出的問題后來發(fā)展成了圖論和拓?fù)鋵W(xué)。

歐拉經(jīng)過研究得出如下結(jié)論：只有當(dāng)圖形的奇頂點(diǎn)（也就是邊的數(shù)量是奇數(shù)的頂點(diǎn)）的數(shù)量等于0或2時(shí)，這個(gè)圖才能被一筆畫出。北美科學(xué)家在此基礎(chǔ)上進(jìn)一步發(fā)現(xiàn)：奇數(shù)分叉的路線，即遇到三岔路口或五岔路口，必然要走回頭路。

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

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

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

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

按照歐拉的理論，漢字“串”字可以一筆寫成，因?yàn)樗钠骓旤c(diǎn)只有兩個(gè)，分別位于最上面和最下面。感興趣的朋友不妨試一下。