一個“烏托邦式”的交通系統(tǒng)將不再遙遠

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

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

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

1.最小車隊問題

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

圖1：ABCDEF六個人的出行軌跡示意圖，分別用T_A、T_B……T_F來表示

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖3 最小車隊問題解決流程

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

3.“烏托邦交通”的運行效果

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

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

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

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

圖5 最優(yōu)車隊數(shù)量、實際出租車使用數(shù)量隨時間的變化曲線

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

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

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

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

在第一個算法中，出行需求是序列地一個個被處理的。系統(tǒng)會在所有的車輛中自動選擇一個能夠讓用戶等待時間最短的車輛來服務(wù)。

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

為了對比這兩種算法，我們使用比最小車隊問題略大的車輛數(shù)（N_{min}x,其中N_{min}是最小車隊數(shù)量，x是一個略大于1的參數(shù)）來運作，并通過比較兩個不同算法的服務(wù)總需求的百分比作為評測的指標，結(jié)果如圖所示：

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

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

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

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

5.人工智能社會的未來

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

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