滴滴APP派車算法分析
2019-04-22
抽象、簡化問題的能力比解決問題的方法更重要，幾乎很少有問題是人類星球首次出現(xiàn)的，絕大多數(shù)問題總能在前人的經(jīng)歷、總結(jié)中找到相似解。
這是最近我在思考如何提高司乘匹配效率問題時(shí)一些感觸。
當(dāng)你覺得在自己所在領(lǐng)域遇到特別棘手的問題時(shí)，說不定在千百年前，在另外一個(gè)跟當(dāng)前相似場景的行業(yè)里，也遇到過類似的問題，而且已經(jīng)有高人給出了不止一種解。
所以，遇到問題，不要一上來就想要靠自己的能力做個(gè)翻天覆地的創(chuàng)新，先搞清問題是什么，再想想有沒有現(xiàn)成的方法，或者其他行業(yè)學(xué)科有沒有類似的場景，去研究別人是怎么做的。把別人的方法理解透徹后，再來結(jié)合自己的業(yè)務(wù)，進(jìn)行異域遷移或者拆解重構(gòu)。
出行行業(yè)對司乘匹配效率的追求永無止境，每一位乘客都希望以最快的速度叫到車，讓司機(jī)能在最短的時(shí)間到達(dá)自己面前；而對于司機(jī)，高效的匹配能提高司機(jī)的人效，賺到更多收入。
司乘匹配一般來說，分為兩步完成：第一步是為乘客找到合適的司機(jī)，第二步是將訂單指派給系統(tǒng)認(rèn)為最優(yōu)的司機(jī)。
第一步
為乘客找到合適的司機(jī)本質(zhì)是一個(gè)搜索問題。既然是搜索問題，我們可以枚舉多個(gè)成熟的案例：傳統(tǒng)的圖書館找書，Google、百度搜索引擎，地圖的搜索。
圖書館找書，大家應(yīng)該都很熟悉：我們在大學(xué)校園圖書館見到的書，書脊上都貼有一個(gè)標(biāo)簽，標(biāo)簽上印刷的是該書的索書號，索書號上有該書的分類信息代碼。
一般圖書館都有多層，每一層又有多個(gè)書架，書架又分多層。而書架的管理跟索書號類似——書架本身的位置可以用樓層、區(qū)域來鎖定，而每一個(gè)書架上又都定義了存放圖書類別，并貼有該類圖書的分類大號。
例如，要去首都圖書館借閱《史蒂夫·喬布斯傳》這本書，我們先去檢索系統(tǒng)里查找有沒有這本書，檢索結(jié)果告訴我們，這本書存放在B座四層歷史、地理文獻(xiàn)去（K837)。這樣就能很容易找到這本書。
當(dāng)然，我們借閱完成，將書還回圖書館，管理員再將書放回對應(yīng)的書架位置，也是按照這種方法進(jìn)行的。
如果圖書館沒有這一套圖書管理方法，而是將成千上萬冊數(shù)隨意堆放在館內(nèi)，那么要找到特定的一本書，就只有一本一本去找，直到發(fā)現(xiàn)你想要的那本書為止——運(yùn)氣好可能第10本就是，運(yùn)氣不好可能第100萬本才是。
出行行業(yè)司乘匹配，就像圖書館讀者找書和管理員將退還的書放回書架一樣。
最容易想到的辦法是：我們預(yù)先設(shè)定一個(gè)派單范圍，用戶叫車，平臺先根據(jù)用戶的上車位置，計(jì)算篩選出全城所有司機(jī)中；再以用戶上車位置為中心，以派單范圍為半徑的圓形區(qū)域范圍內(nèi)的司機(jī)，然后選擇距離最近的司機(jī)，將訂單指派給該司機(jī)。
這種策略下，每一次呼叫系統(tǒng)都會(huì)去計(jì)算全城司機(jī)的位置距離，對于司機(jī)數(shù)量不大的小公司，這種策略還勉強(qiáng)湊合；但是像Uber、滴滴這類在一個(gè)城市擁有幾十萬司機(jī)的獨(dú)角獸，每一次呼叫系統(tǒng)需要計(jì)算幾十萬司機(jī)的位置距離，這種策略就不現(xiàn)實(shí)了。
要提高司機(jī)之間匹配效率，快速找到合適的司機(jī)，我們可以借鑒圖書館圖書管理的辦法；與圖書館管理圖書不同的是：書是固定不動(dòng)的，而車輛是可移動(dòng)的。
首先將地圖劃分成更小的固定區(qū)域，并對這些區(qū)域進(jìn)行標(biāo)記。對于落在這些區(qū)域的司機(jī)或乘客，向服務(wù)器上報(bào)位置數(shù)據(jù)時(shí)，都附帶該區(qū)域的標(biāo)記。
這樣就把找到合適司機(jī)分解成兩步完成：先根據(jù)乘客所在位置區(qū)域標(biāo)記，去搜索數(shù)據(jù)庫有相同標(biāo)記（或附近區(qū)域）的司機(jī)，然后再去計(jì)算這些司機(jī)距離乘客上車點(diǎn)的位置。
這樣就把全程搜索變成了在一個(gè)更小，更精準(zhǔn)的區(qū)域進(jìn)行搜索，降低了算法時(shí)間復(fù)雜度，提高了匹配效率。
例如，圖中將地圖劃分成了若干蜂窩狀區(qū)域，并對區(qū)域進(jìn)行了編號：S、A、B、C、D、E、F，綠色點(diǎn)為乘客呼叫位置，藍(lán)色點(diǎn)為可派單范圍司機(jī)。
乘客呼叫時(shí)，系統(tǒng)已經(jīng)知道乘客在S區(qū)，這時(shí)系統(tǒng)只需要去檢索當(dāng)前在S區(qū)的司機(jī)，或S區(qū)臨近的其他區(qū)域司機(jī)。就能得到當(dāng)前乘客附近的可服務(wù)司機(jī)信息。
以上思考模型中，關(guān)鍵在于如何將地圖劃分成更小的區(qū)域。將地圖進(jìn)行區(qū)域劃分，其實(shí)就是增加地圖索引的過程，就像是將圖書館內(nèi)分為歷史、地理區(qū)、經(jīng)管區(qū)一樣。
但是地圖上的點(diǎn)是通過精度和維度來定義的，是二維的。如果每次通過經(jīng)度緯度其中之一來進(jìn)行檢索，那么檢索完一次，還得進(jìn)行二次檢索；如果是多維空間，就需要就那些多次檢索。
這就涉及多維空間點(diǎn)索引算法機(jī)制，關(guān)于這方面的算法應(yīng)用最廣的是Google S2算法。
Google S2算法是將地圖劃分成正方形網(wǎng)格，網(wǎng)格的大小可根據(jù)實(shí)際業(yè)務(wù)情況進(jìn)行設(shè)置，一共分30級，最小0級可將網(wǎng)格劃分為0.48cm^2，最大為30級，將地球劃分為6個(gè)網(wǎng)格，每個(gè)網(wǎng)格是地球面積的六分之一。
Uber 在一次公開分享上，提到了他們用的是六邊形的網(wǎng)格，把城市劃分為很多六邊形；而國內(nèi)滴滴也是劃分為六邊形，目前劃分成六邊形是最優(yōu)也是最復(fù)雜的方法。
關(guān)于算法不是本文的重點(diǎn)，有興趣的同學(xué)可以到Google官網(wǎng)去查閱有關(guān)S2算法的資料。
這篇文章只介紹了司乘匹配中，如何根據(jù)預(yù)先設(shè)定的派單范圍，高效地找到符合條件的司機(jī)，算是完成了第一步。
第二步
對于乘客而言，希望平臺將距離自己最近的空閑司機(jī)指派給我，司機(jī)越快到達(dá)上車點(diǎn)，乘客的滿意度越高。
對于司機(jī)也是一樣：接客距離越近，空駛里程就越少，節(jié)約成本，提升運(yùn)營效率。
那么對于平臺來說，是不是把距離最近的乘客、司機(jī)進(jìn)行匹配，就是最合理的呢？
我們先從一個(gè)有針對性的場景入手：
如下圖a，假設(shè)在某可派單區(qū)域內(nèi)，同時(shí)有O1、O2、O3三名乘客同時(shí)開始呼叫，此時(shí)在該區(qū)域內(nèi)正好有四名司D1、D2、D3、D3。
在考慮實(shí)時(shí)路況下，表1給出了每一位司機(jī)到達(dá)乘客上車點(diǎn)所需要的時(shí)間，系統(tǒng)該如何進(jìn)行一一匹配呢？
在回答上面的問題之前，我們需要弄明白一個(gè)前提：司乘匹配策略背后希望達(dá)到得目的是什么？
不同的場景和業(yè)務(wù)，可能會(huì)有不同的目的，有的可能以平臺收益為核心，有的可能是為了優(yōu)先滿足核心用戶利益，本文討論的前提是建立在平臺運(yùn)營效率最大化基礎(chǔ)上的。
現(xiàn)在再來考慮文章開頭提出如何匹配的問題：從平臺運(yùn)營效率最大化的角度，是希望能找到運(yùn)營效率最高的司乘匹配關(guān)系。
運(yùn)營效率是一個(gè)不好直接量化的指標(biāo)，通過拆解后，其中最關(guān)鍵的可衡量指標(biāo)就是接客時(shí)長：平均接客時(shí)長越短，司機(jī)資源利用效率就越高，為平臺創(chuàng)造價(jià)值越大。
為了讓接客時(shí)長最短，我們最容易想到的是只要依次保證每位乘客匹配給耗時(shí)最短到達(dá)上車點(diǎn)的司機(jī)，就能保證總的耗時(shí)最短。
如下圖表2所示，依次按照O1、O2、O3順序去尋找耗時(shí)最短的司機(jī)，將會(huì)得到如下匹配關(guān)系：O1-D1、O2-D3、O3-D4，平均耗時(shí)約3.3分鐘，總共耗時(shí)10分鐘。
假設(shè)O1、O2、O3乘客呼叫時(shí)間相差很小，在不明顯增加用戶等待時(shí)長的情況下，系統(tǒng)可以等待最后一位乘客呼叫后，再來進(jìn)行組合決策。
如下圖3所示，可能得到另外一種組合匹配關(guān)系：O1-D2，O2-D1，O3-D4，該種組合決策下，平均耗時(shí)約2.7分鐘，總共耗時(shí)8分鐘。
相比前一種組合策略，第二種組合策略總耗時(shí)減少了20%。
這里是我們隨意列舉情況，如果放在Uber、滴滴等日均上千萬單的平臺，第二種策略將帶來極大的效率提升。
到此為止，司乘匹配問題就轉(zhuǎn)化為：在一段時(shí)間內(nèi)（很短，一般幾秒），在可派單區(qū)域，存在多個(gè)乘客呼叫或有多個(gè)可服務(wù)司機(jī)，每一乘客最終只能匹配一位司機(jī)，如何實(shí)現(xiàn)派單效率最大化（總的接客時(shí)長最短）。
解決這個(gè)問題有如下幾個(gè)方法：
01.貪心算法
通過將所有可能的匹配關(guān)系進(jìn)行一一枚舉，計(jì)算每種匹配關(guān)系的總共耗時(shí)，然后再進(jìn)行排序，最終挑選出接客時(shí)長最短的匹配關(guān)系。但是這種算法的復(fù)雜度是階乘級別的（若有 m 個(gè)乘客呼叫，n 個(gè)可服務(wù)司機(jī)，則算法復(fù)雜為 m！· n）。
02.圖論-二分圖的最大權(quán)值匹配
下圖 b 是著名的男女配對問題：左側(cè)3名女孩，右側(cè)3名男孩，連線代表他們互相喜歡，如果將互相喜歡的進(jìn)行兩兩配對，最多可以配出多少對？
1965年，匈牙利數(shù)學(xué)家Edmonds利用圖論給出了這個(gè)問題的數(shù)學(xué)解法，被稱為匈牙利算法。在介紹匈牙利算法之前，先介紹幾個(gè)概念：
二分圖
圖論是組合數(shù)學(xué)一個(gè)分支，在圖論中，圖是由點(diǎn)和這些點(diǎn)的連線所組成的，邊在實(shí)際業(yè)務(wù)場景中的衡量值，如時(shí)間，距離等，被稱之為權(quán)。把一個(gè)圖的頂點(diǎn)劃分為兩個(gè)不相交的點(diǎn)集合，使得每一條邊都分別連接這兩個(gè)集合中的頂點(diǎn)。如果存在這樣的劃分，則此圖為一個(gè)二分圖（或二部圖），如下圖 c ：
匹配：在圖論中，一個(gè)匹配是一個(gè)邊的集合，其中任意兩條邊都沒有公共頂點(diǎn)。例如，圖 d、圖 e 中紅色的邊就是圖 c 的匹配。構(gòu)成匹配的邊稱為匹配邊，匹配邊上的頂點(diǎn)稱為匹配點(diǎn)。
最大匹配：一個(gè)圖所有匹配中，所含匹配邊數(shù)最多的匹配，稱為這個(gè)圖的最大匹配。圖 e 是一個(gè)最大匹配，它包含 4 條匹配邊。
完美匹配：如果一個(gè)圖的某個(gè)匹配中，所有的頂點(diǎn)都是匹配點(diǎn)，那么它就是一個(gè)完美匹配。圖 e 是一個(gè)完美匹配。
交替路：從一個(gè)未匹配點(diǎn)出發(fā)，依次經(jīng)過非匹配邊、匹配邊、非匹配邊……形成的路徑叫交替路，如圖f。
增廣路：從一個(gè)未匹配點(diǎn)出發(fā)，走交替路，如果途經(jīng)另一個(gè)未匹配點(diǎn)（出發(fā)的點(diǎn)不算），則這條交替路稱為增廣路。例如，圖 f 中的一條增廣路：8→4→7→1→5→2。
增廣路定理：通過不斷找增廣路來增加匹配中的匹配邊和匹配點(diǎn)，當(dāng)找不到增廣路時(shí)，即達(dá)到最大匹配。
KM算法
通過匈牙利算法可以找到二分圖的最大匹配，在司乘匹配場景中，即最大的司機(jī)乘客匹配數(shù)量（可能乘客找不到司機(jī)，也可能司機(jī)找不到乘客），其算法時(shí)間復(fù)雜度為n（O^4)，在匈牙利算法基礎(chǔ)之上，Kuhn-Munkres發(fā)明時(shí)間復(fù)雜度為O^3的KM算法，在解決帶權(quán)值最優(yōu)匹配的問題上更高效。
1.如圖 g 首先選擇頂點(diǎn)數(shù)較少的Oi，初始時(shí)將dj的頂點(diǎn)頂標(biāo)設(shè)為0，對Oj的每一個(gè)頂點(diǎn)設(shè)置頂標(biāo)，頂標(biāo)的值均為為該點(diǎn)關(guān)聯(lián)的最大邊的權(quán)值。
2.對于Oi部中的每個(gè)頂點(diǎn)，在相等子圖中利用匈牙利算法找一條增廣路徑，如果沒有找到，則修改頂標(biāo)，擴(kuò)大相等子圖，繼續(xù)找增廣路徑。當(dāng)每個(gè)點(diǎn)都找到增廣路徑時(shí)，此時(shí)意味著每個(gè)點(diǎn)都在匹配中，即找到了二分圖的完備匹配。該完備匹配即為二分圖的最佳匹配。
完備匹配：如果一個(gè)匹配中，圖中的每個(gè)頂點(diǎn)都和圖中某條邊相關(guān)聯(lián)，則稱此匹配為完全匹配，也稱作完備匹配。
相等子圖：邊權(quán)值等于兩端點(diǎn)的頂標(biāo)之和的邊，它們組成的圖稱為相等子圖。
有關(guān)KM算法的實(shí)現(xiàn)，在互聯(lián)網(wǎng)上已經(jīng)有很多相關(guān)講解，這里不再贅述。
訪問手機(jī)端更方便
技術(shù)創(chuàng)造價(jià)值 服務(wù)締造品牌
Copyright ? 2011-2024 鄭州開拓者電子科技有限公司 All Rights Reserved
友情鏈接：
小程序開發(fā)