昨天我們發(fā)了一篇發(fā)表在Nature上的一篇論文相關(guān)的文章，非常有價(jià)值。該論文表示，他們通過(guò)提出一個(gè)數(shù)學(xué)模型，解決了最小車(chē)隊(duì)問(wèn)題（minimum fleet problem）。本文是張江教授對(duì)這篇論文的解讀：隨著共享出行的普及，以及全路網(wǎng)的自動(dòng)駕駛變得越來(lái)越可能，我們完全可以實(shí)現(xiàn)一個(gè)由算法管理的烏托邦式的城市交通系統(tǒng)。這樣的系統(tǒng)可以做到按需交通（On-demand urban mobility），即根據(jù)每個(gè)人的需求動(dòng)態(tài)地分配運(yùn)載車(chē)輛，從而實(shí)現(xiàn)整體的最優(yōu)化。從技術(shù)上說(shuō)，作者首先把按需交通問(wèn)題映射為一個(gè)理想化數(shù)學(xué)問(wèn)題——最小車(chē)隊(duì)問(wèn)題，并在與實(shí)際紐約市出租汽車(chē)15億條出行數(shù)據(jù)相結(jié)合的情況下，給出了該問(wèn)題的最優(yōu)解。結(jié)果表明，使用算法管理的交通系統(tǒng)可以將出租車(chē)使用數(shù)量減少40%左右。即使在考慮到出行需求可能實(shí)時(shí)提交處理的情況，這一縮減量也可以達(dá)到30%。因此，該問(wèn)題的解決不僅可以大大提升共享出行系統(tǒng)的運(yùn)行效率，也為未來(lái)人工智能治理的社會(huì)模式提供了一個(gè)非常好的示范案例。

自動(dòng)駕駛與車(chē)聯(lián)網(wǎng)，以及共享出行模式這三種大的趨勢(shì)將會(huì)徹底變革我們未來(lái)的交通系統(tǒng)與出行模式，這使得整個(gè)交通系統(tǒng)都可能都統(tǒng)一被算法所管理。因此，一個(gè)“烏托邦式”的交通系統(tǒng)將不再遙遠(yuǎn)，在其中，算法可以調(diào)度每一部車(chē)輛，從而讓系統(tǒng)在整體的運(yùn)行效率達(dá)到最高，并能最大化地實(shí)現(xiàn)綠色環(huán)保。這種模式將會(huì)大大優(yōu)于現(xiàn)有的交通模式，私家車(chē)、出租車(chē)、公交車(chē)將有可能成為歷史。

要實(shí)現(xiàn)這樣的“烏托邦式”交通系統(tǒng)，算法是其中最重要的一環(huán)。因?yàn)?，為了滿(mǎn)足所有市民的出行需求，我們需要合理地調(diào)度每一部奔跑在道路網(wǎng)絡(luò)上的自動(dòng)駕駛汽車(chē)，從而做到：（1）能夠盡可能高效地滿(mǎn)足每一位市民的出行需求；（2）能夠在整體上達(dá)到成本最小，也就是用最少的車(chē)輛和交通來(lái)實(shí)現(xiàn)盡可能多的出行需求。這樣的算法存在嗎？一個(gè)來(lái)自MIT、意大利比薩信息與通信技術(shù)研究院以及康奈爾大學(xué)、康奈爾技術(shù)的合作研究團(tuán)隊(duì)給出了肯定的回答。

1.最小車(chē)隊(duì)問(wèn)題

該合作團(tuán)隊(duì)首先將人們的出行需求簡(jiǎn)化成了一道并不簡(jiǎn)單的數(shù)學(xué)題。讓我們來(lái)考慮A、B、C、D、E、F這六個(gè)人的出行需求，如圖1所示：

圖1：ABCDEF六個(gè)人的出行軌跡示意圖，分別用T_A、T_B……T_F來(lái)表示

T_A、T_B、……、T_F這每一段折線(xiàn)都代表一個(gè)用戶(hù)的出行需求，即用戶(hù)要從時(shí)間點(diǎn)t_p，和地點(diǎn)l_p出發(fā)，并在時(shí)間t_d到達(dá)地點(diǎn)l_d。其中，t_p是自動(dòng)駕駛汽車(chē)能夠接到用戶(hù)A的最早時(shí)間，而t_d時(shí)間點(diǎn)則可以根據(jù)出發(fā)時(shí)間t_p和路網(wǎng)情況（交通流等因素）估計(jì)出來(lái)的時(shí)間點(diǎn)。

假設(shè)，我們可以調(diào)度一組自動(dòng)駕駛車(chē)隊(duì)來(lái)滿(mǎn)足這一組用戶(hù)的出行需求。于是，我們可以給每一條出行路線(xiàn)分配不同的汽車(chē)，也可以讓同一輛汽車(chē)先后滿(mǎn)足兩個(gè)用戶(hù)的出行需求，只需要第二個(gè)用戶(hù)的出行需求與上一個(gè)用戶(hù)的完成時(shí)間和空間都相隔不太遠(yuǎn)就可以完成。也就是說(shuō)，一輛自動(dòng)駕駛汽車(chē)在完成了一個(gè)用戶(hù)的任務(wù)之后，還可以繼續(xù)接另一個(gè)用戶(hù)，只要該用戶(hù)所產(chǎn)生的需求時(shí)間t_p與該自動(dòng)駕駛汽車(chē)完成上一個(gè)任務(wù)的結(jié)束時(shí)間t_d，并考慮到自動(dòng)駕駛汽車(chē)從上一個(gè)l_d開(kāi)到下一個(gè)l_p之間的時(shí)間間隔不算太大就可以了。

在圖1中，彩色的折線(xiàn)段就是一輛自動(dòng)駕駛汽車(chē)在完成了上一個(gè)任務(wù)之后，進(jìn)一步完成下一個(gè)任務(wù)的轉(zhuǎn)換路徑。例如，當(dāng)自動(dòng)駕駛汽車(chē)接到A，并完成任務(wù)后，就可能沿著綠色箭頭走到B的出發(fā)點(diǎn)把B接上送到B的目的地，然后又可以順著綠色折線(xiàn)箭頭趕到C的出發(fā)點(diǎn)，從而滿(mǎn)足C的需求。

當(dāng)然，這輛接送A的自動(dòng)駕駛汽車(chē)也可以在載完A后沿著橙色箭頭走到E的出發(fā)點(diǎn)，然后又去接C，……。因此，在一組給定的用戶(hù)出行的地點(diǎn)、時(shí)間和目的地的情況下，我們的自動(dòng)駕駛汽車(chē)車(chē)隊(duì)可以有不同的方式來(lái)滿(mǎn)足盡可能多的出行需求。

那么，所謂的最小車(chē)隊(duì)問(wèn)題也就是：在一組給定的出行需求情況下，我們能否用最少的自動(dòng)駕駛汽車(chē)數(shù)量來(lái)服務(wù)所有的出行任務(wù)？

可以想到，如果我們能夠從數(shù)學(xué)上解決這個(gè)問(wèn)題，那么我們就可以用一種最“經(jīng)濟(jì)”的方式來(lái)運(yùn)作我們的自動(dòng)駕駛交通系統(tǒng)，從而做到節(jié)約能源、綠色環(huán)保。

2.車(chē)輛共享網(wǎng)絡(luò)

然而，這樣的抽象問(wèn)題一下子很難解決，我們必需一個(gè)中間過(guò)渡工具，這就是“車(chē)輛共享網(wǎng)絡(luò)”（Vehicle-shareability network）。這一網(wǎng)絡(luò)模型是在參考文獻(xiàn)[7]中提出的一種描述共享交通模式的網(wǎng)絡(luò)模型。他可以用來(lái)建模不同的車(chē)輛分配方案。例如，圖2的有向網(wǎng)絡(luò)就是一個(gè)車(chē)輛共享網(wǎng)絡(luò)，它建模了圖1所對(duì)應(yīng)的不同的車(chē)輛分配方案：

圖2 圖1所對(duì)應(yīng)的車(chē)輛共享網(wǎng)絡(luò)

在圖2這張網(wǎng)絡(luò)中，一個(gè)節(jié)點(diǎn)就對(duì)應(yīng)了圖1的一個(gè)用戶(hù)的出行需求，因此A就對(duì)應(yīng)圖1中T_A這條出行路徑。而該圖中的一條有向連邊則對(duì)應(yīng)了一種可能的任務(wù)切換，換句話(huà)說(shuō)，如果節(jié)點(diǎn)A和B之間有連邊就表示自動(dòng)駕駛汽車(chē)有可能在完成了A任務(wù)之后再去完成B任務(wù)；如果沒(méi)有鏈接，就表示自動(dòng)駕駛汽車(chē)可能在完成了A任務(wù)之后由于時(shí)間間隔太長(zhǎng)，或空間距離太遠(yuǎn)而不可能再去完成任務(wù)B。

圖1中的可能路徑切換都對(duì)應(yīng)到了圖2中的有向連邊中。其中，某一輛汽車(chē)的完成任務(wù)方案就對(duì)應(yīng)為圖2中的一條同顏色的有向路徑。例如圖2中的綠色路徑則對(duì)應(yīng)了陸續(xù)接送了A、B、C三個(gè)用戶(hù)的自動(dòng)駕駛汽車(chē)。

要想滿(mǎn)足所有人的出行需求，就是要尋找到一組路徑劃分方案，從而使得這些路徑能夠覆蓋共享出行網(wǎng)絡(luò)上的所有點(diǎn)（服務(wù)所有出行需求）。很顯然，這樣的路徑劃分方案有很多種，那么什么是最優(yōu)的呢？

非常有趣的是，這一最少覆蓋路徑問(wèn)題恰好就是前文敘述的最小車(chē)隊(duì)問(wèn)題。于是，利用車(chē)輛共享網(wǎng)絡(luò)，我們巧妙地將最小車(chē)隊(duì)問(wèn)題轉(zhuǎn)化為了共享網(wǎng)絡(luò)上的最少路徑覆蓋問(wèn)題。

總結(jié)來(lái)看，我們可以從實(shí)際數(shù)據(jù)出發(fā)，利用車(chē)輛共享網(wǎng)絡(luò)來(lái)構(gòu)造一個(gè)“最少路徑覆蓋問(wèn)題”，它的步驟如下：

圖3 最小車(chē)隊(duì)問(wèn)題解決流程

接下來(lái)，這個(gè)問(wèn)題怎么求解呢？壞消息是，對(duì)于一般意義上的最優(yōu)路徑覆蓋問(wèn)題來(lái)說(shuō)，這是一個(gè)NP難的問(wèn)題，我們無(wú)法找到有效的計(jì)算求解方案；但好消息是，由于我們這個(gè)交通工具共享網(wǎng)絡(luò)具有特殊性，即它是一個(gè)有向無(wú)環(huán)圖（directed acycled graph）。這也就意味著，我們可以使用Hopcroft-Karp算法找到該問(wèn)題的有效解法（具體參見(jiàn)論文附錄）。

3.“烏托邦交通”的運(yùn)行效果

接下來(lái)，就讓我們來(lái)看看這樣的最優(yōu)共享方案的效果如何。作者們結(jié)合了紐約市2011年所有出租車(chē)的出行數(shù)據(jù)來(lái)構(gòu)建車(chē)輛共享網(wǎng)絡(luò)。這套數(shù)據(jù)集中包含了15億條出行記錄，每一條出行記錄都對(duì)應(yīng)了用戶(hù)被出租車(chē)接上的時(shí)間，也就是t_p、地點(diǎn)，也就是l_p，以及在什么時(shí)間，即t_d，用戶(hù)被送達(dá)到指定地點(diǎn)，也就是l_d。這樣，我們就可以套用圖3所示的算法流程，來(lái)計(jì)算出每一天，甚至每一小時(shí)最優(yōu)的出租車(chē)數(shù)量，并與實(shí)際出租車(chē)使用數(shù)量進(jìn)行對(duì)比。

圖4 在紐約市出租車(chē)出行數(shù)據(jù)上計(jì)算得出的

最優(yōu)汽車(chē)數(shù)量或總車(chē)隊(duì)運(yùn)行時(shí)間與不同工作日出行數(shù)量的關(guān)系

首先，如圖4所示，我們看到最優(yōu)的出租車(chē)使用數(shù)量是會(huì)隨著人們出行需求的增加而線(xiàn)性增加的。其中不同顏色的點(diǎn)表示不同的工作日（周一、周二等）。右側(cè)的圖則展示了車(chē)隊(duì)運(yùn)行的總時(shí)間隨著出行次數(shù)的增加而線(xiàn)性增加。而我們看到，當(dāng)出行量在從300,000到550,000之間的時(shí)候，增長(zhǎng)的斜率會(huì)小一些，這表明不僅僅是出行密度，人們出行的模式也會(huì)影響最優(yōu)的數(shù)量。

圖5 最優(yōu)車(chē)隊(duì)數(shù)量、實(shí)際出租車(chē)使用數(shù)量隨時(shí)間的變化曲線(xiàn)

其次，圖5展示了實(shí)際出租車(chē)使用數(shù)量（黑色）、最優(yōu)出租車(chē)使用數(shù)量（紅色），以及處于不同模式的出行出租車(chē)數(shù)量（其它顏色）隨時(shí)間的波動(dòng)曲線(xiàn)。虛線(xiàn)對(duì)應(yīng)的是它們的平均值。我們看到，如果使用算法來(lái)管理整個(gè)交通系統(tǒng)的話(huà)，我們每天平均僅需要實(shí)際出租車(chē)數(shù)量的60%就可以了，這足足減少了3000輛出租車(chē)的使用！

4.更現(xiàn)實(shí)的考慮

雖然60%這個(gè)數(shù)字是相當(dāng)驚人的，但是這個(gè)數(shù)字是建立在一天內(nèi)所有的需求都是同時(shí)提交給優(yōu)化系統(tǒng)的假設(shè)前提下的，這樣系統(tǒng)能夠有條不紊地安排所有車(chē)輛的出行，從而最優(yōu)化出行配置。

然而，現(xiàn)實(shí)情況會(huì)比這種情況更加“骨感”得多：一天內(nèi)的出行需求不可能一下子同時(shí)提交給我們的服務(wù)器，而必然是實(shí)時(shí)地、一個(gè)個(gè)地提交給系統(tǒng)的。那么在這種情況下，我們就需要改進(jìn)算法。于是，作者提供了兩種改進(jìn)，分別叫直接（on-the-fly）算法和批次算法（batch）。

在第一個(gè)算法中，出行需求是序列地一個(gè)個(gè)被處理的。系統(tǒng)會(huì)在所有的車(chē)輛中自動(dòng)選擇一個(gè)能夠讓用戶(hù)等待時(shí)間最短的車(chē)輛來(lái)服務(wù)。

在批次算法中，系統(tǒng)是每間隔δ = 1分鐘，收集一個(gè)批次的需求數(shù)據(jù)，并利用最大匹配算法來(lái)滿(mǎn)足所有用戶(hù)，并讓等待時(shí)間最短。

為了對(duì)比這兩種算法，我們使用比最小車(chē)隊(duì)問(wèn)題略大的車(chē)輛數(shù)（N_{min}x,其中N_{min}是最小車(chē)隊(duì)數(shù)量，x是一個(gè)略大于1的參數(shù)）來(lái)運(yùn)作，并通過(guò)比較兩個(gè)不同算法的服務(wù)總需求的百分比作為評(píng)測(cè)的指標(biāo)，結(jié)果如圖所示：

圖6: 每天不同小時(shí)直接算法和批次算法的服務(wù)比率隨時(shí)間的變化

圖7: 不同日期直接算法和批次算法所能服務(wù)的百分比隨日期的變化

圖6、7中的橫坐標(biāo)是時(shí)間，縱坐標(biāo)是算法服務(wù)的出行百分比，這個(gè)百分比越高說(shuō)明算法越好。我們看到，無(wú)論是從小時(shí)為單位衡量的出行還是以天為單位的出行，批模型的服務(wù)百分比更高。

通過(guò)結(jié)合出行實(shí)際數(shù)據(jù)和優(yōu)化算法，我們發(fā)現(xiàn)，使用批次模型，我們可以使用實(shí)際數(shù)量70%的出租車(chē)來(lái)服務(wù)超過(guò)90%的出行需求。這雖然沒(méi)有最優(yōu)模型酷炫，但也說(shuō)明考慮到實(shí)時(shí)服務(wù)的情況下，我們?nèi)匀豢梢宰龅奖M可能的高效和足夠多用戶(hù)的滿(mǎn)意。

5.人工智能社會(huì)的未來(lái)

最后，作者總結(jié)道：雖然這套算法僅僅解決了單一出行模式、單一車(chē)隊(duì)的優(yōu)化問(wèn)題，但它完全可以擴(kuò)展到多種出行模式的混合交通的優(yōu)化問(wèn)題，這為我們解決出行問(wèn)題提供了更多的想象空間。盡管更便捷的出行很有可能刺激人們更多的出行需求，但是總體來(lái)講，由高效算法管理的自動(dòng)駕駛交通系統(tǒng)將必然會(huì)讓我們的交通更加高效和智能。

筆者甚至認(rèn)為，這篇工作的意義可能還可以延伸到更多的共享經(jīng)濟(jì)模式中。利用算法而非人類(lèi)的主觀(guān)決策來(lái)統(tǒng)一調(diào)配管理整個(gè)宏觀(guān)系統(tǒng)將在未來(lái)成為可能。