抽象、簡化問題的能力比解決問題的方法更重要，幾乎很少有問題是人類星球首次出現(xiàn)的，絕大多數(shù)問題總能在前人的經(jīng)歷、總結(jié)中找到相似解。但是，在按圖索驥之前，你必須得知道這是個什么問題，如若不然，千百次的擦肩而過也換不來一次回眸一笑。

這是最近我在思考如何提高司乘匹配效率問題時一些感觸。當你覺得在自己所在領(lǐng)域遇到特別棘手的問題時，說不定在千百年前，在另外一個跟當前相似場景的行業(yè)里，也遇到過類似的問題，而且已經(jīng)有高人給出了不止一種解。

所以，遇到問題，不要一上來就想要靠自己的能力做個翻天覆地的創(chuàng)新，先搞清問題是什么，再想想有沒有現(xiàn)成的方法，或者其他行業(yè)學科有沒有類似的場景，去研究別人是怎么做的。把別人的方法理解透徹后，再來結(jié)合自己的業(yè)務(wù)，進行異域遷移或者拆解重構(gòu)。

出行行業(yè)對司乘匹配效率的追求永無止境。每一位乘客都希望以最快的速度叫到車，讓司機能在最短的時間到達自己面前。而對于司機，高效的匹配能提高司機的人效，賺到更多收入。

司乘匹配一般來說，分為兩步完成，第一步是為乘客找到合適的司機，第二步是將訂單指派給系統(tǒng)認為最優(yōu)的司機。

為乘客找到合適的司機本質(zhì)是一個搜索問題。既然是搜索問題，我們可以枚舉多個成熟的案例，傳統(tǒng)的圖書館找書，Google、百度搜索引擎，地圖的搜索。

圖書館找書，大家應該都很熟悉，我們在大學校園圖書館見到的書，書脊上都貼有一個標簽，標簽上印刷的是該書的索書號，索書號上有該書的分類信息代碼。

一般圖書館都有多層，每一層又有多個書架，書架又分多層。而書架的管理跟索書號類似，書架本身的位置可以用樓層、區(qū)域來鎖定，而每一個書架上又都定義了存放圖書類別，并貼有該類圖書的分類大號。

例如，要去首都圖書館借閱《史蒂夫·喬布斯傳》這本書，我們先去檢索系統(tǒng)里查找有沒有這本書，檢索結(jié)果告訴我們，這本書存放在B座四層歷史、地理文獻去（K837)。這樣就能很容易找到這本書。當然，我們借閱完成，將書還回圖書館，管理員再將書放回對應的書架位置，也是按照這種方法進行的。

如果圖書館沒有這一套圖書管理方法，而是將成千上萬冊數(shù)隨意堆放在館內(nèi)，那么要找到特定的一本書，就只有一本一本去找，直到發(fā)現(xiàn)你想要的那本書為止。運氣好可能第10本就是，運氣不好可能第100萬本才是。

出行行業(yè)司乘匹配，就像圖書館讀者找書和管理員將退還的書放回書架一樣。

最容易想到的辦法是，我們預先設(shè)定一個派單范圍，用戶叫車，平臺先根據(jù)用戶的上車位置，計算篩選出全城所有司機中，在以用戶上車位置為中心，以派單范圍為半徑的圓形區(qū)域范圍內(nèi)的司機，然后選擇距離最近的司機，將訂單指派給該司機。

這種策略下，每一次呼叫系統(tǒng)都會去計算全城司機的位置距離，對于司機數(shù)量不大的小公司，這種策略還勉強湊合。但是像Uber、滴滴這類在一個城市擁有幾十萬司機的獨角獸，每一次呼叫系統(tǒng)需要計算幾十萬司機的位置距離，這種策略就不現(xiàn)實了。

要提高司機之間匹配效率，快速找到合適的司機，我們可以借鑒圖書館圖書管理的辦法，與圖書館管理圖書不同的是，書是固定不動的，而車輛是可移動的。

首先將地圖劃分成更小的固定區(qū)域，并對這些區(qū)域進行標記。對于落在這些區(qū)域的司機或乘客，向服務(wù)器上報位置數(shù)據(jù)時，都附帶該區(qū)域的標記。

這樣就把找到合適司機分解成兩步完成，先根據(jù)乘客所在位置區(qū)域標記，去搜索數(shù)據(jù)庫有相同標記（或附近區(qū)域）的司機，然后再去計算這些司機距離乘客上車點的位置。

這樣就把全程搜索變成了在一個更小，更精準的區(qū)域進行搜索，降低了算法時間復雜度，提高了匹配效率。

例如，圖中將地圖劃分成了若干蜂窩狀區(qū)域，并對區(qū)域進行了編號：S、A、B、C、D、E、F，綠色點為乘客呼叫位置，藍色點為可派單范圍司機。乘客呼叫時，系統(tǒng)已經(jīng)知道乘客在S區(qū)，這時系統(tǒng)只需要去檢索當前在S區(qū)的司機，或S區(qū)臨近的其他區(qū)域司機。就能得到當前乘客附近的可服務(wù)司機信息。

以上思考模型中，關(guān)鍵在于如何將地圖劃分成更小的區(qū)域。將地圖進行區(qū)域劃分，其實就是增加地圖索引的過程，就像是將圖書館內(nèi)分為歷史、地理區(qū)、經(jīng)管區(qū)一樣。但是地圖上的點是通過精度和維度來定義的，是二維的。

如果每次通過經(jīng)度緯度其中之一來進行檢索，那么檢索完一次，還得進行二次檢索，如果是多維空間，就需要就那些多次檢索。這就涉及多維空間點索引算法機制，關(guān)于這方面的算法應用最廣的是Google S2算法。

Google S2算法是將地圖劃分成正方形網(wǎng)格，網(wǎng)格的大小可根據(jù)實際業(yè)務(wù)情況進行設(shè)置，一共分30級，最小0級可將網(wǎng)格劃分為0.48cm^2，最大為30級，將地球劃分為6個網(wǎng)格，每個網(wǎng)格是地球面積的六分之一。

Uber 在一次公開分享上，提到了他們用的是六邊形的網(wǎng)格，把城市劃分為很多六邊形。而國內(nèi)滴滴也是劃分為六邊形。目前劃分成六邊形是最優(yōu)也是最復雜的方法。

對于乘客而言，希望平臺將距離自己最近的空閑司機指派給我，司機越快到達上車點，乘客的滿意度越高。對于司機也是一樣，接客距離越近，空駛里程就越少，節(jié)約成本，提升運營效率。那么對于平臺來說，是不是把距離最近的乘客、司機進行匹配，就是最合理的呢？

我們先從一個有針對性的場景入手，如下圖a，假設(shè)在某可派單區(qū)域內(nèi)，同時有O1、O2、O3三名乘客同時開始呼叫，此時在該區(qū)域內(nèi)正好有四名司D1、D2、D3、D3。在考慮實時路況下，表1給出了每一位司機到達乘客上車點所需要的時間，系統(tǒng)該如何進行一一匹配呢？

在回答上面的問題之前，我們需要弄明白一個前提：司乘匹配策略背后希望達到得目的是什么？不同的場景和業(yè)務(wù)，可能會有不同的目的，有的可能以平臺收益為核心，有的可能是為了優(yōu)先滿足核心用戶利益，本文討論的前提是建立在平臺運營效率最大化基礎(chǔ)上的。

現(xiàn)在再來考慮文章開頭提出如何匹配的問題，從平臺運營效率最大化的角度，是希望能找到運營效率最高的司乘匹配關(guān)系。運營效率是一個不好直接量化的指標，通過拆解后，其中最關(guān)鍵的可衡量指標就是接客時長，平均接客時長越短，司機資源利用效率就越高，為平臺創(chuàng)造價值越大。

為了讓接客時長最短，我們最容易想到的是只要依次保證每位乘客匹配給耗時最短到達上車點的司機，就能保證總的耗時最短。如下圖表2所示，依次按照O1、O2、O3順序去尋找耗時最短的司機，將會得到如下匹配關(guān)系：O1-D1、O2-D3、O3-D4，平均耗時約3.3分鐘，總共耗時10分鐘。

假設(shè)O1、O2、O3乘客呼叫時間相差很小，在不明顯增加用戶等待時長的情況下，系統(tǒng)可以等待最后一位乘客呼叫后，再來進行組合決策。如下圖3所示，可能得到另外一種組合匹配關(guān)系：O1-D2，O2-D1，O3-D4，該種組合決策下，平均耗時約2.7分鐘，總共耗時8分鐘。

相比前一種組合策略，第二種組合策略總耗時減少了20%。這里是我們隨意列舉情況，如果放在Uber、滴滴等日均上千萬單的平臺，第二種策略將帶來極大的效率提升。

到此為止，司乘匹配問題就轉(zhuǎn)化為：在一段時間內(nèi)（很短，一般幾秒），在可派單區(qū)域，存在多個乘客呼叫或有多個可服務(wù)司機，每一乘客最終只能匹配一位司機，如何實現(xiàn)派單效率最大化（總的接客時長最短）。解決這個問題有如下幾個方法：

01.貪心算法

通過將所有可能的匹配關(guān)系進行一一枚舉，計算每種匹配關(guān)系的總共耗時，然后再進行排序，最終挑選出接客時長最短的匹配關(guān)系。但是這種算法的復雜度是階乘級別的（若有m個乘客呼叫，n個可服務(wù)司機，則算法復雜為m！·n）。

02.圖論-二分圖的最大權(quán)值匹配

下圖 b 是著名的男女配對問題，左側(cè)3名女孩，右側(cè)3名男孩，連線代表他們互相喜歡，如果將互相喜歡的進行兩兩配對，最多可以配出多少對？

1965年，匈牙利數(shù)學家Edmonds利用圖論給出了這個問題的數(shù)學解法，被稱為匈牙利算法，在介紹匈牙利算法之前，先介紹幾個概念：

-二分圖-

圖論是組合數(shù)學一個分支，在圖論中，圖是由點和這些點的連線所組成的，邊在實際業(yè)務(wù)場景中的衡量值，如時間，距離等，被稱之為權(quán)。把一個圖的頂點劃分為兩個不相交的點集合，使得每一條邊都分別連接這兩個集合中的頂點。如果存在這樣的劃分，則此圖為一個二分圖（或二部圖），如下圖 c ：

匹配：在圖論中，一個匹配是一個邊的集合，其中任意兩條邊都沒有公共頂點。例如，圖d、圖e 中紅色的邊就是圖 c的匹配。構(gòu)成匹配的邊稱為匹配邊，匹配邊上的頂點稱為匹配點。

最大匹配：一個圖所有匹配中，所含匹配邊數(shù)最多的匹配，稱為這個圖的最大匹配。圖 e 是一個最大匹配，它包含 4 條匹配邊。

完美匹配：如果一個圖的某個匹配中，所有的頂點都是匹配點，那么它就是一個完美匹配。圖 e 是一個完美匹配。

交替路：從一個未匹配點出發(fā)，依次經(jīng)過非匹配邊、匹配邊、非匹配邊……形成的路徑叫交替路，如圖f。

增廣路：從一個未匹配點出發(fā)，走交替路，如果途經(jīng)另一個未匹配點（出發(fā)的點不算），則這條交替路稱為增廣路。例如，圖 f 中的一條增廣路：8→4→7→1→5→2。

增廣路定理：通過不斷找增廣路來增加匹配中的匹配邊和匹配點，當找不到增廣路時，即達到最大匹配。

-KM算法-

通過匈牙利算法可以找到二分圖的最大匹配，在司乘匹配場景中，即最大的司機乘客匹配數(shù)量（可能乘客找不到司機，也可能司機找不到乘客），其算法時間復雜度為n（O^4)，在匈牙利算法基礎(chǔ)之上，Kuhn-Munkres發(fā)明時間復雜度為O^3的KM算法，在解決帶權(quán)值最優(yōu)匹配的問題上更高效。

1.如圖 g 首先選擇頂點數(shù)較少的Oi，初始時將dj的頂點頂標設(shè)為0，對Oj的每一個頂點設(shè)置頂標，頂標的值均為為該點關(guān)聯(lián)的最大邊的權(quán)值。

2.對于Oi部中的每個頂點，在相等子圖中利用匈牙利算法找一條增廣路徑，如果沒有找到，則修改頂標，擴大相等子圖，繼續(xù)找增廣路徑。當每個點都找到增廣路徑時，此時意味著每個點都在匹配中，即找到了二分圖的完備匹配。該完備匹配即為二分圖的最佳匹配。

完備匹配：如果一個匹配中，圖中的每個頂點都和圖中某條邊相關(guān)聯(lián)，則稱此匹配為完全匹配，也稱作完備匹配。

相等子圖：邊權(quán)值等于兩端點的頂標之和的邊，它們組成的圖稱為相等子圖。

有關(guān)KM算法的實現(xiàn)，在互聯(lián)網(wǎng)上已經(jīng)有很多相關(guān)講解，這里不再贅述。

最后，請大家不要被文章標題所誤導，本人僅是借滴滴的業(yè)務(wù)場景，思考對應策略，作自我提升學習之用。而文章中對派單策略的思考、敘述，也僅是站在一兩個點的角度來考量的，出行場景業(yè)務(wù)復雜，很難找到一套萬精油策略能應對所有問題。

且，針對特定問題制定對策，很多時候只能是腳痛醫(yī)腳頭痛醫(yī)腳。解決系統(tǒng)性的問題，人工智能、機器學習方法可能會更加高效。

本文來自于公眾號花四爺（siyesay），作者為花四爺。