摘要：下面是之前解決路徑規劃問題的方法并且講解了我們是如何從五年以前三藩市單一的服務成長的到現在每天百萬以上用車量的。在更高的層面上，星是搜索算法的啟發式實現，因此星優先找到從到之間的一條可能的最優路徑。

一鍵用車現在已經爛大街，但是 Uber 簡單的界面下又隱藏著怎樣復雜的后端架構和服務呢？這些復雜的路徑規劃和訂單匹配算法又是如何讓車找到人，將人送到目的地的呢？現在讓我們揭開Uber App這神秘的面紗。

下面是Uber之前解決路徑規劃問題的方法并且講解了我們是如何從五年以前 三藩市單一的 UberBLACK 服務成長的到現在每天百萬以上用車量的。

當五年以前Uber平臺剛剛開始運營的時候，到達時間估算（ETA）是我們推出的第一個特性。這是乘客對我們的第一印象。

2012年早些時候，應用內顯示的 ETA

在Uber早期，我們用了一系列路徑引擎的組合（包括OSRM）來做ETA。（我們剛開始并沒有應用內的導航功能，因此我們只能用它來做ETA并且匹配所顯示的車輛位置。

我們稱這種服務為”黃金ETA”，而它是需要在一個路徑引擎上建立模型并且用Uber 數據在同時同地的類似數據中調整初始的估計值。這種解決方案通常要同時觀察成千上萬的Uber行程，用初始路徑引擎對比它們的ETA。黃金ETA比之前沒有數據對比的ETA顯然來得更好。但是，這里又產生了一個冷啟動的問題：當我們進軍一個新的城市拓展業務的時候，我們是沒有足夠的數據來打造”黃金ETA”的。也就是說，隨著我們不斷擴張，我們定期需要一些新特性來滿足我們快速增長的需要，這時候用之前的開源解決方案（OSRM）已經滿足不了我們高度定制化的需求了。

我們已經用黃金ETA很久了，但是隨著我們在更多城市和服務上的擴展（比如在2014年3月開啟的 UberRUSH 服務以及 我們在2014年春天開啟的 UberPOOL 服務），我們需要為Uber打造一個自己的路徑引擎的需求已經變得非常迫切了。因此，在2014年，我們開始著手打造我們自己的全套路徑引擎，我們稱之為 Gurafu。Gurafu的目標是為Uber量身定制一個高性能、高精度的ETA計算工具。

在我們具體實施之前，讓我討論一下我們需要一個路徑引擎的必要性。這整個的路網就像一個圖結構（運籌學中圖論的概念）。節點表示十字路口，邊表示道路。這個邊的權重表示一個有趣的度量：這段距離或時間路線經常被人經過。其他一些像單行道，轉彎限制、轉彎成本以及速度限制等概念都在這個圖結構模型被考慮到了。

當然，這不是通往真實世界的唯一模型。有些人也把道路作為節點，而兩個路段的轉換作為邊。相對于之前提到的基于點的表達式這就是所謂的基于邊的表達式。每種表達式都有自己的權衡，因此在確定使用哪種模型之前明白我們需要什么就變得非常重要了。

一旦你的數據結構確定了，你就可以使用不同的路徑規劃算法來尋優。舉一個簡單的例子，你可以嘗試的最基礎的Dijkstra搜索算法，這種方法是今天大多數搜索算法的基石。但是在生產環境下，Dijkstra或者其他一些算法常常沒法處理太大規模的圖結構，它總是顯得速度太慢了。

OSRM 是基于收縮的層次結構的。系統基于收縮層次結構來提升性能，通過預處理路線的圖結構只用毫秒級的時間就完成整個路徑的計算。下面99%的響應都是在100毫秒內完成的。因為在每次車輛收到用車請求的時候我們都需要計算所以我們非常需要這個功能。但是，因為這個預處理步驟是十分緩慢的，想要做實時的交通處理是非常困難的。而我我們的數據會用全世界的道路花12個小時來構建這個收縮圖結構。這意味著我們很難去更新這個交通流量的信息。

這是就是為什么一些預處理和變換常常需要加速查詢。（這類算法的最近例子包括了高速公路層次算法、ALT算法以及自定義路徑規劃算法）

這里是從2014年開始嘗試構建自己的路徑引擎所做的工作：

在我們的路徑圖結構中，隨著新交通信息涌入，我們需要能夠動態更新這些圖結構的邊權重。就像我們提到的，我們所用的 OSRM 是用 收縮層次來做路徑尋優算法的。收縮層次的一個缺點就在與當邊權重更新，預處理過程需要用整個圖結構重新再跑一邊，當我們跑稍微大一點的圖結構就需要好幾個小時，更不要說全世界了。所以這個收縮層次算法對于實時的交通變化并不適合，我們需要一個增量算法。

收縮層次的預處理步驟可以通過動態更新來快速實現，這種情況下大多數節點的排序將保留，而只是更新需要更新的節點，這樣我們就可以大大減少預處理的計算量了。（這不是Virtual Dom嗎？）用這種方法，我們以每次更新整個世界的圖結構中10%的路段，僅僅用10分鐘就可以實現動態更新。但是，要估算ETA的話，10分鐘看起來對交通流的變化還是有點延遲。因此，這條路最后也是一條死胡同。

我們也用一種叫作分片的方式，將整個圖結構分解成幾個小的地理區域，分而治之。分片加速了我們構建圖結構的時間。但是，這里需要在我們的基礎設施上為此做一些工作，并且在每個地區的服務器集群大小上總是會遇到瓶頸。如果一個地區在高峰期一下子有太多的請求，那么其他服務就不能共享加載這種分片的資源了。我們想要利用我們有限的服務器資源，因此我們也并沒有采用這種解決方案。

對于小范圍的實時更新，我們嘗試使用A星搜索算法。在更高的層面上，A星是Dijkstra搜索算法的啟發式實現，因此A星優先找到從A到B之間的一條可能的最優路徑。這意味著我們可以實時更新圖結構的邊權重，而且在不需要做任何預處理的條件下計算交通流量的情況。既然大多數航線我們需要計算是短途旅行(從司機乘客途中時間),那么A *在這種情況下其實非常有效的。

不過我們知道A星算法是一個權宜之計,因為它對于比較長的路線規劃顯得非常的慢：A星的響應速度與深度遍歷的節點是相關的，以幾何增長。(例如,從普雷西迪奧到舊金山地區教會區的路線計算時間是120毫秒,這相比收縮層次算法花費了數倍的時間)。

即使A星算法利用地標、三角不等式和幾個預先估計技巧,不會增加A星遍歷的時間，足以使它成為一個可行的解決方案。

但是對于長途旅行來說，A星還是不能夠快速響應，因此我們又回到了使用靜態收縮圖結構的老路。

我們既需要使用預處理來加速計算，又想要快速更新邊權重來支持實時交通。我們的解決方案僅僅通過重新刷新整個圖結構的一部分就可以完成預處理過程，有效解決了實時交通更新的問題。
因為我們的解決方案將圖像劃分為層相對獨立的小模塊,通過并行執行預處理，讓我們能夠在必要時讓這個過程加速計算。(了解更多,點擊這里!)

在我們的第一個Gurafu版本已經準備好測試之后，為了知道我們我們之前推出的新路徑引擎的效果，我們打算在2015年1月分別紀錄了Gurafu和黃金ETA的實時ETA準確度。

2015年1月份我們制作了一個內部的儀表盤來顯示ETA準確性：Gurafu（紫色）相比黃金ETA（綠色和紅色）每次預測ETA都更加精準。注意到往往在交通通勤的高峰期（周三晚上和周四早上）Gurafu的表現在這時候一騎絕塵。這里，我們顯示的三藩市，但是這個模式在我們所有的其他城市也是如此。

2015年4月,我們在全球范圍內推出了一個全新的更精確的ETA預測的路線引擎系統。新系統是基于我們新的路線引擎Gurafu。另外，基于我們從司機端收集的GPS數據，我們還推出了 Uber的第一個歷史交通系統，我們稱之為 Flux。

我們使用獨有的ETA系統主要是為了獲取乘客,但我們也在整個行程中記錄每次ETA預測的準確性。為了衡量ETA的準確性,我們用從Kafka日志獲取的實時檢索實際到達時間(ATA)對比我們的ETA并以此構建了一個工具。此外,我們的團隊成員也可能直接從應用程序內報告ETA 的 bug。衡量線路質量有時需要在個案基礎上做可視化檢查，我們還建立了一組豐富的web可視化工具,檢查和比較不同模型和路線從提供者的ETA預測情況。

Goldeta 對比 Gurafu: 通過超過十萬次的行程采樣，系統計算預計到達時間(ETA)與實際到達時間(ATA)的差距。新的ETA系統Gurafu的誤差分布更尖更高,這意味著新系統比舊系統在預測是更加穩定（方差更小）。縱軸是行程估計錯誤的數量。這意味著只有在很少概率會有小錯誤發生。

這些健康檢查顯示去年我們已經走過了漫長的道路。

超高效路線規劃和高精度的ETA是至關重要的。我們用現代的路線算法來建立一個精心優化系統來應對每秒成千上萬請求并且做出毫秒級的快速響應。我們所有的新服務,如uberPOOL和UberEATS都開始部署這個系統。

這個優化之旅還沒有結束。隨著我們擴展和改進像UberPOOL這樣的產品，根據地點和時間的上下文確定最優路線還將使得服務準確性和效率進一步提升。

我們還想讓打電話保平安也變得更加可靠、智能。如果這聽起來像是一個你感興趣的挑戰,我們希望你加入我們的行列。?

OSRM的GItHub地址

OSRM在線服務Demo

原文作者： THI NGUYEN 譯者： Harry Zhu 英文原文地址:
https://eng.uber.com/engineering-an-efficient-route/
作為分享主義者(sharism)，本人所有互聯網發布的圖文均遵從CC版權，轉載請保留作者信息并注明作者 Harry Zhu 的 FinanceR專欄:https://segmentfault.com/blog/harryprince，如果涉及源代碼請注明GitHub地址：https://github.com/harryprince。微信號: harryzhustudio
商業使用請聯系作者。