匹配策略：為什麼打車軟體不給你最近的車？

04-30

好久沒有更新，最近大出行領域風起雲湧，那麼就趁著這個機會簡單聊一下打車的匹配策略。

本身服務匹配演算法是非常複雜的，要考慮多個因素，但是如果我們只看最基本的邏輯，服務匹配就是將多個服務者和多個用戶之間進行匹配。這篇文章會簡單介紹如何構建匹配度，同時具體如何對匹配問題求解。

1 匹配度構建

匹配度的構建其實並不複雜，就是構造一個計算用戶需求和服務者之間的相關性的方法。複雜的是確認清楚我們的目標是什麼。介紹核心函數的構建我們仍然以打車為例。

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

需要強調的一點是，當我們對每個用戶和周圍的司機都有相關度計算，可以知道對每個用戶最合適的司機，也並不意味著所有用戶都可以得到最合適的司機。這就回到了一個用戶經常抱怨的問題：為什麼打車軟體不給我派最近的車？

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

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

從這個例子中看出，系統應該尋求的是整個系統匹配度最大化。下面我們會詳細闡述可以用什麼樣的方法來達到系統的最優化。

2.二分圖匹配

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

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

值得慶幸的是二分圖問題是有典型的求最大匹配的演算法的。二分圖問題本質上也是線性規劃問題，用線性規劃的單純形法也可以作為迭代方法。不過因為這種方法效率低下，工程上不會使用。在工程上使用最大流、匈牙利演算法或者KM演算法都可以作為最大匹配問題的解法，尤其是KM演算法基本就是為了解決二分圖這種特殊問題設計的演算法。這三種演算法在效率和原理上是基本通用的，這裡涉及一些基礎圖論問題，就不對這些演算法做數學展開，有興趣的讀者可以從網上查找KM演算法相關資料。

當然，即使不了解KM演算法的數學原理，但是並不妨礙我們理解使用這種方法。KM演算法要求的兩個集合中的不同點的匹配度作為邊長，權重越大則代表匹配度越高。演算法通過迭代會給出匹配度最高的匹配組合，也就是我們需要的全局最優解。在KM演算法中，只要將所有我們需要的因素都考慮進入匹配度演算法中，那麼這個演算法就可以每隔一段（比如10s）時間執行一次，每次服務者和用戶退出匹配系統，也會有新的服務者和用戶加入匹配系統，演算法循環執行，不斷匹配。

3. 給太長不看的朋友

打車的匹配策略就和男生和女生相親一樣。為什麼不給所有男生自己最喜歡的女生，因為資源有限，一個女生也不能分給一堆男生。那麼最好的結果就是每個人都找到差不多和自己匹配的人，讓整個系統成雙入對的情侶滿意度總和最高。

那麼回到打車的問題，為什麼不給你最近的車，因為同時有一堆人想要最近的車，系統不能保證給每個人最近的車。那麼最終系統的優化目標就變成了最大化整體的效率和體驗指標。不給一個特定最近用戶最近的車，是因為對於系統而言，最優化的目標是系統的最優化，不是針對每個人的最優化。