好久沒有更新，最近大出行領(lǐng)域風(fēng)起云涌，那么就趁著這個(gè)機(jī)會簡單聊一下打車的匹配策略。

本身服務(wù)匹配算法是非常復(fù)雜的，要考慮多個(gè)因素，但是如果我們只看最基本的邏輯，服務(wù)匹配就是將多個(gè)服務(wù)者和多個(gè)用戶之間進(jìn)行匹配。這篇文章會簡單介紹如何構(gòu)建匹配度，同時(shí)具體如何對匹配問題求解。

1. 匹配度構(gòu)建

匹配度的構(gòu)建其實(shí)并不復(fù)雜，就是構(gòu)造一個(gè)計(jì)算用戶需求和服務(wù)者之間的相關(guān)性的方法。復(fù)雜的是確認(rèn)清楚我們的目標(biāo)是什么。介紹核心函數(shù)的構(gòu)建我們?nèi)匀灰源蜍嚍槔?/p>

比如在打車的時(shí)候，我們可以先思考下有哪些因素是乘客叫車的時(shí)候乘客比較關(guān)心的。首先乘客最關(guān)心的就是司機(jī)和乘客之間的距離。對于每個(gè)乘客而言，距離越近就意味著司機(jī)趕過來越快，等待時(shí)間越短，在大多數(shù)情況下，快速上車出發(fā)是乘客的第一需求。乘客關(guān)心的第二個(gè)問題是司機(jī)的服務(wù)，具體體現(xiàn)在乘客對于司機(jī)的評價(jià)和司機(jī)的服務(wù)單量上，用戶評分越高的司機(jī)往往更能提供優(yōu)質(zhì)的服務(wù)，如果可以周圍有大量司機(jī)可以選擇的話，乘客期待評分更好的司機(jī)。對于司機(jī)而言，司機(jī)期待乘客的終點(diǎn)是熱點(diǎn)地區(qū)，這樣可以獲得更高的收入，如果周圍有大量的乘客，那么單純從效率的角度看，我們更應(yīng)該匹配目的地在時(shí)空價(jià)值更高時(shí)間域的訂單。如果業(yè)務(wù)取向真的是上面分析的這樣，那么用戶和司機(jī)的匹配度函數(shù)就應(yīng)該由三個(gè)因子構(gòu)而成。不過當(dāng)多個(gè)參數(shù)在同一個(gè)函數(shù)中的時(shí)候，就需要對每個(gè)參數(shù)進(jìn)行有效的歸一化和變形，才能讓結(jié)果符合預(yù)期。

需要強(qiáng)調(diào)的一點(diǎn)是，當(dāng)我們對每個(gè)用戶和周圍的司機(jī)都有相關(guān)度計(jì)算，可以知道對每個(gè)用戶最合適的司機(jī)，也并不意味著所有用戶都可以得到最合適的司機(jī)。這就回到了一個(gè)用戶經(jīng)常抱怨的問題：為什么打車軟件不給我派最近的車？

即使核心函數(shù)中只有距離一個(gè)因子，也不一定會給每個(gè)用戶都匹配最近的車。具體case如下圖所示：

在左邊的圖中，距離用戶A最近的車是a，在這種情況下可以給用戶A派最近的車。但是如果如右邊圖所示，同時(shí)有兩個(gè)用戶呼叫，這種情況下，給用戶A分配車輛a，會導(dǎo)致B分配到的車都會比較遠(yuǎn)。就應(yīng)該給用戶A分配車輛b，給用戶B分配車輛a。而實(shí)際在設(shè)計(jì)的服務(wù)匹配方法中還需要考慮多種其他因素，比如服務(wù)、公平等因素，就更不可能給所有用戶都分配最近的車。

從這個(gè)例子中看出，系統(tǒng)應(yīng)該尋求的是整個(gè)系統(tǒng)匹配度最大化。下面我們會詳細(xì)闡述可以用什么樣的方法來達(dá)到系統(tǒng)的最優(yōu)化。

2. 二分圖匹配

二分圖是圖論中的一種特殊模型。 通俗解釋的話，二分圖有兩個(gè)特點(diǎn)，在二分圖圖中的點(diǎn)可以分到兩個(gè)互不相交的子集中，同時(shí)每條邊都需要連接這兩個(gè)子集。如果有這個(gè)定義去看的話，一段時(shí)間內(nèi)，乘客和司機(jī)的匹配問題就是典型的二分圖問題，兩個(gè)集合分別代表司機(jī)和乘客，司機(jī)和乘客的匹配度則代表司機(jī)的邊長。

在二分圖中，有一個(gè)經(jīng)典問題就是如何求二分圖的最大匹配。最大匹配的定義就是任意交點(diǎn)只連接一條邊的最優(yōu)解。具體到打車問題中，就是尋找讓整個(gè)系統(tǒng)叫做多的人叫到車，所有人和司機(jī)之前的匹配度之和最大。這也正是我們希望得到的線下交易系統(tǒng)最好的匹配結(jié)果。如果我們能找到二分圖的最大匹配算法，就能用這個(gè)算法作為線下交易匹配的問題。

值得慶幸的是二分圖問題是有典型的求最大匹配的算法的。二分圖問題本質(zhì)上也是線性規(guī)劃問題，用線性規(guī)劃的單純形法也可以作為迭代方法。不過因?yàn)檫@種方法效率低下，工程上不會使用。在工程上使用最大流、匈牙利算法或者KM算法都可以作為最大匹配問題的解法，尤其是KM算法基本就是為了解決二分圖這種特殊問題設(shè)計(jì)的算法。這三種算法在效率和原理上是基本通用的，這里涉及一些基礎(chǔ)圖論問題，就不對這些算法做數(shù)學(xué)展開，有興趣的讀者可以從網(wǎng)上查找KM算法相關(guān)資料。

當(dāng)然，即使不了解KM算法的數(shù)學(xué)原理，但是并不妨礙我們理解使用這種方法。KM算法要求的兩個(gè)集合中的不同點(diǎn)的匹配度作為邊長，權(quán)重越大則代表匹配度越高。算法通過迭代會給出匹配度最高的匹配組合，也就是我們需要的全局最優(yōu)解。在KM算法中，只要將所有我們需要的因素都考慮進(jìn)入匹配度算法中，那么這個(gè)算法就可以每隔一段（比如10s）時(shí)間執(zhí)行一次，每次服務(wù)者和用戶退出匹配系統(tǒng)，也會有新的服務(wù)者和用戶加入匹配系統(tǒng)，算法循環(huán)執(zhí)行，不斷匹配。

3. 給太長不看的朋友

打車的匹配策略就和男生和女生相親一樣。為什么不給所有男生自己最喜歡的女生，因?yàn)橘Y源有限，一個(gè)女生也不能分給一堆男生。那么最好的結(jié)果就是每個(gè)人都找到差不多和自己匹配的人，讓整個(gè)系統(tǒng)成雙入對的情侶滿意度總和最高。

那么回到打車的問題，為什么不給你最近的車，因?yàn)橥瑫r(shí)有一堆人想要最近的車，系統(tǒng)不能保證給每個(gè)人最近的車。那么最終系統(tǒng)的優(yōu)化目標(biāo)就變成了最大化整體的效率和體驗(yàn)指標(biāo)。不給一個(gè)特定最近用戶最近的車，是因?yàn)閷τ谙到y(tǒng)而言，最優(yōu)化的目標(biāo)是系統(tǒng)的最優(yōu)化，不是針對每個(gè)人的最優(yōu)化。

#專欄作家#

潘一鳴，公眾號：產(chǎn)品邏輯之美，人人都是產(chǎn)品經(jīng)理專欄作家。畢業(yè)于清華大學(xué)，暢銷書《產(chǎn)品邏輯之美》作者；先后在多家互聯(lián)網(wǎng)公司從事產(chǎn)品經(jīng)理工作，有很多復(fù)雜系統(tǒng)的構(gòu)建實(shí)踐經(jīng)驗(yàn)。

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

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