一個城市究竟需要多少輛計程車？

隨著自動駕駛汽車的崛起，未來城市的交通出行方式將發生極大地變化。特別是，傳統的私家車出行將向

但若要讓共享交通得到更大發展，我們需要精確且高效的算法來有效地將個人與車輛進行匹配，才得以應對在大城市中經常出現的成千上萬次的出行需求。

然而，一個尚未解決的基本問題是，給定特定水平的個人出行需求，我們要如何制定出最優的車隊數量和運作方案。

由麻省理工學院的可感知城市實驗室主任Carlo Ratti帶領的小組，將這一問題稱之為“最少車隊問題”，併為其提供了一個有效的計算解決方案。他們的結果發表於5月23日的《自然》雜誌。

△ 與在路邊發現乘客的傳統出租車不同，新算法會根據交通狀況以及乘客的上車(Pick up)和下車(Drop-off)地點為他們分配車輛。我們用集合Τ來代表在一定時間間隔內的一部分城市出行需求。| 圖片來源：M.M.Vazifeh et al.

Ratti說：“我們之所以研究這個問題，是因為共享交通已是大勢所趨。而且隨著向自動駕駛的過渡，這一勢頭或許會越來越猛。如果對出行的需求由共享交通提供，那麼就有一個基本問題：我們需要多少輛車來滿足一個城市的出行需求，比如紐約市？”

在此之前，研究人員試圖借用“旅行推銷員問題”的變形來思考這個問題。旅行推銷員問題是指，如果一個推銷員需要訪問一定數量的城市，那麼如何才能將其總行程距離最小化。

但到目前為止，我們已經知道即便是在強大的計算機的幫助下，要找到旅行推銷員問題的最佳解決方案也是極困難的。據研究員Paolo Santi所述，對於車隊管理而言，優秀解決方案的提供受到車隊規模這一因素的嚴重限制，這意味著只有當某個車隊只擁有幾十輛車時，才能計算出最好的方案。

然而，這顯然不足以滿足像紐約這類大城市的要求。Santi說：“假如我們要用已優化過的車隊來替換紐約當前的出租車系統，就必須找出最好的方式，來應對目前由約13,500輛出租車提供的每天平均50萬次的出行需求。”

而為了解決這一問題，研究人員用的是一種被稱為“車輛共享網絡”的模型。在2014年的一篇論文中，他們已報告過一種類似的方法，叫“可共享性網絡”，目的是在大城市中尋找共享出行的最佳方式。

該算法用圖形來表示出租車車隊的可共享性，它是一個由節點（圓圈）和邊（節點間的連線）組成的數學抽象模型。在模型中，節點表示的是不同的行程，而兩個節點間的連線則表示這兩個特定行程可由單個車輛完成。

△ 構建車輛可共享性網絡。a. 在地圖中，幾個不同的用戶出行需求分別用TA……TF表示。地圖上的彩色路徑代表不同的車輛調度可能。b. 在車輛可共享性網絡中，用顏色來表明如何用該網絡上的路徑來表示不同的調度。兩個調度方案中的其中一個只需要用到兩輛車，而另一個需要三輛。c. 最佳的車輛調度路線。d. 在車輛可共享性網絡中，行程集合T和行程時間會被作為輸入。如果在下一個行程上車時間和第一次行程的下車時間之間存在足夠長的間隔，則允許同一輛車在兩點之間行駛，這兩個行程可通過直線連接。此外，連接時間一定不能超過上限時間δ。路徑覆蓋算法產生涵蓋所有節點集合的路徑集合，以確保所有行程都能得到服務，同時也最小化了解決方案中的路徑（車輛）數量。| 圖片來源：M.M.Vazifeh et al.

通過這種圖形，這一算法可以找到最佳的車輛共享方案。這一跨機構的研究團隊對紐約在一年時間裡的1.5億次出租車行程數據集進行了測試。他們用曼哈頓的真實道路網絡、和從租車行程數據集導出的基於GPS的估算來計算行程時間。

他們發現，與目前的出租車系統相比，若以接近最優的解決方案來實施，則可以

Ratti說，隨著網絡化、自動駕駛汽車的普及，這一解決方案在未來幾年會變得更具意義。“如果我們將曼哈頓看作是一個整體，理論上我們可以用大約14萬輛汽車來滿足它的出行需求，這一數字約是目前的一半。這意味著在將來，解決城市的交通問題不一定要靠更多的基礎建設，而是更多的智能。換句話說：越來越多的硅、越來越少的瀝青。”

倫敦大學學院高級空間分析中心的規劃教授Michael Batty說，研究人員證明，通過將集中調度系統中的車隊規模最小化，可以使城市中的交通流動變得更加高效。“在針對紐約的數據上，他們做出了非常不錯的結果，這意味著他們的算法或許可被用於其他大型城市中的運輸和旅行系統。”

現在，研究人員計劃展開進一步的測試工作，以探索城市中所需的最少停車位數量。

編譯：二宗主

參考鏈接：

https://www.nature.com/articles/s41586-018-0095-1

http://news.mit.edu/2018/minimum-vehicle-fleet-rider-demand-0523

閱讀更多 原理 的文章

關鍵字: 麻省理工學院 數學 交通