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