MIT新調度演算法可以減少3成的計程車
麻省理工學院的研究人員表示，他們發現了一種高效的調度演算法，可以將城市的計程車減少30％的數量。
他們在幾天前出版的一篇論文中介紹了他們的工作。
「如果優化我們對計程車的管理，甚至只需要指揮司機，紐約的計程車車輛就可以減少30％。」麻省理工學院可感知城市實驗室主任Carlo Ratti告訴IEEE Spectrum。無論對計程車還是對城市街道的利用率來說，這都是效率巨大的提升。紐約有一萬四千多輛計程車，每天搭載乘客總共要跑50萬趟左右。
這項技術似乎可以幫助陷入困境的計程車公司避開私人乘車服務的打擊，如優步和Lyft。他們有自己的演算法，有的演算法優化匹配司機和乘客，有的演算法分享乘客。
觸動Ratti和他的同事們進行研究的起因是，2014年，他們發現如果曼哈頓的計程車乘客願意多花五分鐘的時間，他們中就有近95％的行程可以共享。這將減少乘客花費在租車上達40％的總時間。
這次，研究人員分析了一個更好的調度模型需要如何更好地利用現有的計程車隊列，也就是說，不再假設同路的乘客共享里程。他們稱之為最小艦隊問題，並且他們以旗艦玩家的身份來調度所有船隻/車輛。通過適當地估計某趟運營中計程車的目的地與下一次潛在出行起點之間的最小化距離，該模型保證了在給定的時間段內每輛車可以運送最多的乘客。
一個通用的完美演算法可以解決著名的旅行推銷員問題，該問題試圖找到推銷員路過所有城市的最短路徑。然而，隨著城市數量的增加，這個問題很快變得異常的棘手。你可以在新加坡實現最優路徑，但無法為美國找到那個解。
相反，麻省理工學院的研究人員創建了他們所謂的車輛共享網路，類似於他們在2014年用於優化乘客共享歷程的網路。它看起來像一個圖表，其中每個節點代表一次發車，每條連接兩個節點的線代表一輛車可以連續接送的兩趟路程。調整圖的布局儘可能讓最多的點被線連接在一起。這樣就保證，所有的計程車司機，每次送走一個客人的時候，在幾乎相同的位置和時間點上就能接到另一位客人。節約了在路上尋找客人的時間。
如果曼哈頓全部28萬輛左右的汽車都採用自動駕駛，在麻省理工學院總體規劃的控制下，效率能提升多少呢？ 「如果我們有一座完全智能的城市，」Rotti說，「汽車減少量將接近50％。」
本文譯自 IEEE，由譯者 majer 基於創作共用協議(BY-NC)發布。
TAG:煎蛋 |