Nature最新論文解讀：最小車隊問題與「烏托邦」交通系統

07-07

來自專欄人工智慧學習筆記

導語

隨著共享出行的普及，以及全路網的自動駕駛變得越來越可能，我們完全可以實現一個由演算法管理的烏托邦式的城市交通系統。這樣的系統可以做到按需交通（On-demand urban mobility），即根據每個人的需求動態地分配運載車輛，從而實現整體的最優化。從技術上說，作者首先把按需交通問題映射為一個理想化數學問題——最小車隊問題，並在與實際紐約市出租汽車15億條出行數據相結合的情況下，給出了該問題的最優解。結果表明，使用演算法管理的交通系統可以將計程車使用數量減少40%左右。即使在考慮到出行需求可能實時提交處理的情況，這一縮減量也可以達到30%。因此，該問題的解決不僅可以大大提升共享出行系統的運行效率，也為未來人工智慧治理的社會模式提供了一個非常好的示範案例。

自動駕駛與車聯網，以及共享出行模式這三種大的趨勢將會徹底變革我們未來的交通系統與出行模式，這使得整個交通系統都可能都統一被演算法所管理。因此，一個「烏托邦式」的交通系統將不再遙遠，在其中，演算法可以調度每一部車輛，從而讓系統在整體的運行效率達到最高，並能最大化地實現綠色環保。這種模式將會大大優於現有的交通模式，私家車、計程車、公交車將有可能成為歷史。

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

Nature 新論文：https://www.nature.com/articles/s41586-018-0095-1（文末附原文下載地址）

1.最小車隊問題

該合作團隊首先將人們的出行需求簡化成了一道並不簡單的數學題。讓我們來考慮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出發，並在時間t_d到達地點l_d。其中，t_p是自動駕駛汽車能夠接到用戶A的最早時間，而t_d時間點則可以根據出發時間t_p和路網情況（交通流等因素）估計出來的時間點。

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

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

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

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

可以想到，如果我們能夠從數學上解決這個問題，那麼我們就可以用一種最「經濟」的方式來運作我們的自動駕駛交通系統，從而做到節約能源、綠色環保。

2.車輛共享網路

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

圖2 圖1所對應的車輛共享網路

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

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

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

非常有趣的是，這一最少覆蓋路徑問題恰好就是前文敘述的最小車隊問題。於是，利用車輛共享網路，我們巧妙地將最小車隊問題轉化為了共享網路上的最少路徑覆蓋問題。

總結來看，我們可以從實際數據出發，利用車輛共享網路來構造一個「最少路徑覆蓋問題」，它的步驟如下：

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

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

3.「烏托邦交通」的運行效果

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

圖4 在紐約市計程車出行數據上計算得出的最優汽車數量或總車隊運行時間與不同工作日出行數量的關係

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

圖5 最優車隊數量、實際計程車使用數量隨時間的變化曲線

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

4.更現實的考慮

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

然而，現實情況會比這種情況更加「骨感」得多：一天內的出行需求不可能一下子同時提交給我們的伺服器，而必然是實時地、一個個地提交給系統的。那麼在這種情況下，我們就需要改進演算法。於是，作者提供了兩種改進，分別叫直接（on-the-fly）演算法和批次演算法（batch）。

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

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

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

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

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

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

通過結合出行實際數據和優化演算法，我們發現，使用批次模型，我們可以使用實際數量70%的計程車來服務超過90%的出行需求。這雖然沒有最優模型酷炫，但也說明考慮到實時服務的情況下，我們仍然可以做到儘可能的高效和足夠多用戶的滿意。

5.人工智慧社會的未來最後，作者總結道：雖然這套演算法僅僅解決了單一出行模式、單一車隊的優化問題，但它完全可以擴展到多種出行模式的混合交通的優化問題，這為我們解決出行問題提供了更多的想像空間。儘管更便捷的出行很有可能刺激人們更多的出行需求，但是總體來講，由高效演算法管理的自動駕駛交通系統將必然會讓我們的交通更加高效和智能。

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

參考文獻：

[7] Santi, P. et al. Quantifying the benefits of vehicle pooling with shareability networks. Proc. Natl Acad. Sci. USA 111, 13290–13294 (2014).

論文下載：

鏈接：https://pan.baidu.com/s/1weycQSRQISv8xEl1cgtkkg 密碼:0zpw

Nature最新論文解讀：最小車隊問題與「烏托邦」交通系統

導語

1.最小車隊問題

2.車輛共享網路

3.「烏托邦交通」的運行效果

4.更現實的考慮

推薦閱讀