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

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

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

當(dāng)五年以前Uber平臺剛剛開始運(yùn)營的時(shí)候，到達(dá)時(shí)間估算（ETA）是我們推出的第一個(gè)特性。這是乘客對我們的第一印象。

2012年早些時(shí)候，應(yīng)用內(nèi)顯示的 ETA

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

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

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

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

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

一旦你的數(shù)據(jù)結(jié)構(gòu)確定了，你就可以使用不同的路徑規(guī)劃算法來尋優(yōu)。舉一個(gè)簡單的例子，你可以嘗試的最基礎(chǔ)的Dijkstra搜索算法，這種方法是今天大多數(shù)搜索算法的基石。但是在生產(chǎn)環(huán)境下，Dijkstra或者其他一些算法常常沒法處理太大規(guī)模的圖結(jié)構(gòu)，它總是顯得速度太慢了。

OSRM 是基于收縮的層次結(jié)構(gòu)的。系統(tǒng)基于收縮層次結(jié)構(gòu)來提升性能，通過預(yù)處理路線的圖結(jié)構(gòu)只用毫秒級的時(shí)間就完成整個(gè)路徑的計(jì)算。下面99%的響應(yīng)都是在100毫秒內(nèi)完成的。因?yàn)樵诿看诬囕v收到用車請求的時(shí)候我們都需要計(jì)算所以我們非常需要這個(gè)功能。但是，因?yàn)檫@個(gè)預(yù)處理步驟是十分緩慢的，想要做實(shí)時(shí)的交通處理是非常困難的。而我我們的數(shù)據(jù)會(huì)用全世界的道路花12個(gè)小時(shí)來構(gòu)建這個(gè)收縮圖結(jié)構(gòu)。這意味著我們很難去更新這個(gè)交通流量的信息。

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

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

在我們的路徑圖結(jié)構(gòu)中，隨著新交通信息涌入，我們需要能夠動(dòng)態(tài)更新這些圖結(jié)構(gòu)的邊權(quán)重。就像我們提到的，我們所用的 OSRM 是用 收縮層次來做路徑尋優(yōu)算法的。收縮層次的一個(gè)缺點(diǎn)就在與當(dāng)邊權(quán)重更新，預(yù)處理過程需要用整個(gè)圖結(jié)構(gòu)重新再跑一邊，當(dāng)我們跑稍微大一點(diǎn)的圖結(jié)構(gòu)就需要好幾個(gè)小時(shí)，更不要說全世界了。所以這個(gè)收縮層次算法對于實(shí)時(shí)的交通變化并不適合，我們需要一個(gè)增量算法。

收縮層次的預(yù)處理步驟可以通過動(dòng)態(tài)更新來快速實(shí)現(xiàn)，這種情況下大多數(shù)節(jié)點(diǎn)的排序?qū)⒈Ａ?，而只是更新需要更新的?jié)點(diǎn)，這樣我們就可以大大減少預(yù)處理的計(jì)算量了。（這不是Virtual Dom嗎？）用這種方法，我們以每次更新整個(gè)世界的圖結(jié)構(gòu)中10%的路段，僅僅用10分鐘就可以實(shí)現(xiàn)動(dòng)態(tài)更新。但是，要估算ETA的話，10分鐘看起來對交通流的變化還是有點(diǎn)延遲。因此，這條路最后也是一條死胡同。

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

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

不過我們知道A星算法是一個(gè)權(quán)宜之計(jì),因?yàn)樗鼘τ诒容^長的路線規(guī)劃顯得非常的慢：A星的響應(yīng)速度與深度遍歷的節(jié)點(diǎn)是相關(guān)的，以幾何增長。(例如,從普雷西迪奧到舊金山地區(qū)教會(huì)區(qū)的路線計(jì)算時(shí)間是120毫秒,這相比收縮層次算法花費(fèi)了數(shù)倍的時(shí)間)。

即使A星算法利用地標(biāo)、三角不等式和幾個(gè)預(yù)先估計(jì)技巧,不會(huì)增加A星遍歷的時(shí)間，足以使它成為一個(gè)可行的解決方案。

但是對于長途旅行來說，A星還是不能夠快速響應(yīng)，因此我們又回到了使用靜態(tài)收縮圖結(jié)構(gòu)的老路。

我們既需要使用預(yù)處理來加速計(jì)算，又想要快速更新邊權(quán)重來支持實(shí)時(shí)交通。我們的解決方案僅僅通過重新刷新整個(gè)圖結(jié)構(gòu)的一部分就可以完成預(yù)處理過程，有效解決了實(shí)時(shí)交通更新的問題。
因?yàn)槲覀兊慕鉀Q方案將圖像劃分為層相對獨(dú)立的小模塊,通過并行執(zhí)行預(yù)處理，讓我們能夠在必要時(shí)讓這個(gè)過程加速計(jì)算。(了解更多,點(diǎn)擊這里!)

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

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

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

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

Goldeta 對比 Gurafu: 通過超過十萬次的行程采樣，系統(tǒng)計(jì)算預(yù)計(jì)到達(dá)時(shí)間(ETA)與實(shí)際到達(dá)時(shí)間(ATA)的差距。新的ETA系統(tǒng)Gurafu的誤差分布更尖更高,這意味著新系統(tǒng)比舊系統(tǒng)在預(yù)測是更加穩(wěn)定（方差更?。??？v軸是行程估計(jì)錯(cuò)誤的數(shù)量。這意味著只有在很少概率會(huì)有小錯(cuò)誤發(fā)生。

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

超高效路線規(guī)劃和高精度的ETA是至關(guān)重要的。我們用現(xiàn)代的路線算法來建立一個(gè)精心優(yōu)化系統(tǒng)來應(yīng)對每秒成千上萬請求并且做出毫秒級的快速響應(yīng)。我們所有的新服務(wù),如uberPOOL和UberEATS都開始部署這個(gè)系統(tǒng)。

這個(gè)優(yōu)化之旅還沒有結(jié)束。隨著我們擴(kuò)展和改進(jìn)像UberPOOL這樣的產(chǎn)品，根據(jù)地點(diǎn)和時(shí)間的上下文確定最優(yōu)路線還將使得服務(wù)準(zhǔn)確性和效率進(jìn)一步提升。

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

OSRM的GItHub地址

OSRM在線服務(wù)Demo

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