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

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

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

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.人工智能社會的未來

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

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