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