概述

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

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

初出茅廬：2001-2014

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

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

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

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

尋求突破：如何構(gòu)建你自己的路徑優(yōu)化引擎

我們已經(jīng)用黃金ETA很久了，但是隨著我們?cè)诟喑鞘泻头?wù)上的擴(kuò)展（比如在2014年3月開(kāi)啟的 UberRUSH 服務(wù)以及 我們?cè)?014年春天開(kāi)啟的 UberPOOL 服務(wù)），我們需要為Uber打造一個(gè)自己的路徑引擎的需求已經(jīng)變得非常迫切了。因此，在2014年，我們開(kāi)始著手打造我們自己的全套路徑引擎，我們稱之為 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)過(guò)。其他一些像單行道，轉(zhuǎn)彎限制、轉(zhuǎn)彎成本以及速度限制等概念都在這個(gè)圖結(jié)構(gòu)模型被考慮到了。

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

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

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

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

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

1. 采用動(dòng)態(tài)的收縮層次算法

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

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

2. 分片

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

3. A星算法

對(duì)于小范圍的實(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í)非常有效的。

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

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

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

化蛹成蝶：2015之后

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

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

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

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

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

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

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

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

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

我們還想讓打電話保平安也變得更加可靠、智能。如果這聽(tīng)起來(lái)像是一個(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)載請(qǐng)保留作者信息并注明作者 Harry Zhu 的 FinanceR專欄:https://segmentfault.com/blog/harryprince

from:?https://segmentfault.com/a/1190000005162383?utm_source=tuicool&utm_medium=referral

總結(jié)

以上是生活随笔為你收集整理的[译]解密 Uber 数据科学团队路径选择算法的优化之路的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。