文章對(duì)派單策略的思考、敘述圍繞一兩個(gè)特定角度展開(kāi)。而出行場(chǎng)景業(yè)務(wù)復(fù)雜，針對(duì)特定問(wèn)題制定對(duì)策，很多時(shí)候只能是腳痛醫(yī)腳頭痛醫(yī)腳；解決系統(tǒng)性的問(wèn)題，人工智能、機(jī)器學(xué)習(xí)方法可能會(huì)更加高效。

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

這就是最近我在思考如何提高司乘匹配效率問(wèn)題時(shí)一些感觸。

當(dāng)你覺(jué)得在自己所在領(lǐng)域遇到特別棘手的問(wèn)題時(shí)，說(shuō)不定在千百年前，在另外一個(gè)跟當(dāng)前相似場(chǎng)景的行業(yè)里，也遇到過(guò)類似的問(wèn)題，而且已經(jīng)有高人給出了不止一種解。

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

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

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

第一步

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

圖書(shū)館找書(shū)，大家應(yīng)該都很熟悉：我們?cè)诖髮W(xué)校園圖書(shū)館見(jiàn)到的書(shū)，書(shū)脊上都貼有一個(gè)標(biāo)簽，標(biāo)簽上印刷的是該書(shū)的索書(shū)號(hào)，索書(shū)號(hào)上有該書(shū)的分類信息代碼。

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

例如：要去首都圖書(shū)館借閱《史蒂夫·喬布斯傳》這本書(shū)，我們先去檢索系統(tǒng)里查找有沒(méi)有這本書(shū)。檢索結(jié)果告訴我們，這本書(shū)存放在B座四層歷史、地理文獻(xiàn)去（K837)。這樣就能很容易找到這本書(shū)。

當(dāng)然，我們借閱完成，將書(shū)還回圖書(shū)館，管理員再將書(shū)放回對(duì)應(yīng)的書(shū)架位置，也是按照這種方法進(jìn)行的。

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

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

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

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

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

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

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

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

例如，圖中將地圖劃分成了若干蜂窩狀區(qū)域，并對(duì)區(qū)域進(jìn)行了編號(hào)：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í)就是增加地圖索引的過(guò)程，就像是將圖書(shū)館內(nèi)分為歷史、地理區(qū)、經(jīng)管區(qū)一樣。

但是，地圖上的點(diǎn)是通過(guò)精度和維度來(lái)定義的，是二維的。如果每次通過(guò)經(jīng)度緯度其中之一來(lái)進(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級(jí)，最小0級(jí)可將網(wǎng)格劃分為0.48cm^2，最大為30級(jí)，將地球劃分為6個(gè)網(wǎng)格，每個(gè)網(wǎng)格是地球面積的六分之一。

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

關(guān)于算法不是本文的重點(diǎn)，有興趣的同學(xué)可以到Google官網(wǎng)去查閱有關(guān)S2算法的資料。

這篇文章只介紹了司乘匹配中，如何根據(jù)預(yù)先設(shè)定的派單范圍，高效地找到符合條件的司機(jī)，算是完成了第一步。

第二步

對(duì)于乘客而言，希望平臺(tái)將距離自己最近的空閑司機(jī)指派給我，司機(jī)越快到達(dá)上車點(diǎn)，乘客的滿意度越高。

對(duì)于司機(jī)也是一樣，接客距離越近，空駛里程就越少，節(jié)約成本，提升運(yùn)營(yíng)效率。

那么對(duì)于平臺(tái)來(lái)說(shuō)，是不是把距離最近的乘客、司機(jī)進(jìn)行匹配，就是最合理的呢？

我們先從一個(gè)有針對(duì)性的場(chǎng)景入手：

如下圖a，假設(shè)在某可派單區(qū)域內(nèi)，同時(shí)有O1、O2、O3三名乘客同時(shí)開(kāi)始呼叫，此時(shí)在該區(qū)域內(nèi)正好有四名司D1、D2、D3、D3。

在考慮實(shí)時(shí)路況下，表1給出了每一位司機(jī)到達(dá)乘客上車點(diǎn)所需要的時(shí)間，系統(tǒng)該如何進(jìn)行一一匹配呢？

在回答上面的問(wèn)題之前，我們需要弄明白一個(gè)前提：司乘匹配策略背后希望達(dá)到得目的是什么？

不同的場(chǎng)景和業(yè)務(wù)，可能會(huì)有不同的目的，有的可能以平臺(tái)收益為核心，有的可能是為了優(yōu)先滿足核心用戶利益，本文討論的前提是建立在平臺(tái)運(yùn)營(yíng)效率最大化基礎(chǔ)上的。

現(xiàn)在再來(lái)考慮文章開(kāi)頭提出如何匹配的問(wèn)題：從平臺(tái)運(yùn)營(yíng)效率最大化的角度，是希望能找到運(yùn)營(yíng)效率最高的司乘匹配關(guān)系。

運(yùn)營(yíng)效率是一個(gè)不好直接量化的指標(biāo)，通過(guò)拆解后，其中最關(guān)鍵的可衡量指標(biāo)就是接客時(shí)長(zhǎng)：平均接客時(shí)長(zhǎng)越短，司機(jī)資源利用效率就越高，為平臺(tái)創(chuàng)造價(jià)值越大。

為了讓接客時(shí)長(zhǎng)最短，我們最容易想到的是只要依次保證每位乘客匹配給耗時(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í)長(zhǎng)的情況下，系統(tǒng)可以等待最后一位乘客呼叫后，再來(lái)進(jìn)行組合決策。

如下圖3所示，可能得到另外一種組合匹配關(guān)系：O1-D2，O2-D1，O3-D4，該種組合決策下，平均耗時(shí)約2.7分鐘，總共耗時(shí)8分鐘。

相比前一種組合策略，第二種組合策略總耗時(shí)減少了20%。

這里是我們隨意列舉情況，如果放在Uber、滴滴等日均上千萬(wàn)單的平臺(tái)，第二種策略將帶來(lái)極大的效率提升。

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

解決這個(gè)問(wèn)題有如下幾個(gè)方法：

1. 貪心算法

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

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

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

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

二分圖

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

匹配：在圖論中，一個(gè)匹配是一個(gè)邊的集合，其中任意兩條邊都沒(méi)有公共頂點(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)過(guò)非匹配邊、匹配邊、非匹配邊……形成的路徑叫交替路，如圖f。

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

增廣路定理：通過(guò)不斷找增廣路來(lái)增加匹配中的匹配邊和匹配點(diǎn)，當(dāng)找不到增廣路時(shí)，即達(dá)到最大匹配。

3. KM算法

通過(guò)匈牙利算法可以找到二分圖的最大匹配，在司乘匹配場(chǎng)景中，即最大的司機(jī)乘客匹配數(shù)量（可能乘客找不到司機(jī)，也可能司機(jī)找不到乘客），其算法時(shí)間復(fù)雜度為n（O^4)。

在匈牙利算法基礎(chǔ)之上，Kuhn-Munkres發(fā)明時(shí)間復(fù)雜度為O^3的KM算法，在解決帶權(quán)值最優(yōu)匹配的問(wèn)題上更高效。

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

（2）對(duì)于Oi部中的每個(gè)頂點(diǎn)，在相等子圖中利用匈牙利算法找一條增廣路徑.如果沒(méi)有找到，則修改頂標(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)講解，這里不再贅述。

作者：花四爺，微信公眾號(hào)：花四爺（ID：siyesay）

本文由 @花四爺 原創(chuàng)發(fā)布于人人都是產(chǎn)品經(jīng)理。未經(jīng)許可，禁止轉(zhuǎn)載

題圖來(lái)自Unsplash，基于 CC0 協(xié)議