網站資訊 news
您現在的位置:首頁 > 網站資訊 > 匹配策略:為什么打車軟件不給你最近的車?
NEWS

新聞資訊

  • chrome瀏覽器如何將網頁保存為圖片
    2019/12/19

    1、ctrl+shift+i打開審查元素窗口 2、ctrl+shift+p,輸入full,回車 3、等待3秒鐘…

  • 老而不死的三種編程語言
    2019/11/07

    老而不死的三種編程語言 導讀: 在軟件世界中,鐵打的二進制,流水的語言。從計算機誕生至今,不知誕生了多少門編程語言。譯...

  • AI人工智能的10種常用算法
    2019/09/25

    ML的常用算法有個常識性的認識,沒有代碼,沒有復雜的理論推導,就是圖解一下,知道這些算法是什么,它們是怎么應用的,例子...

  • 網站如何進行安全設置
    2019/08/28

    為了安全起見,建議先做好全站數據和文件的備份,以下教程是AB模板網的總結經驗,本人也是這樣設置,并且沒有任何問題) 1、...

  • What’s your problem?
    2019/07/08

    今天在路上走著走著,突然下暴雨了,我抬頭問天:What‘s?your?problem?? 在前兩天的百度AI開發者大會上,百度創始人、...

  • 西部數碼網站備案率先告別幕布,備案全程電子化,全網首推!
    2019/07/05

    網站備案已經伴隨中國互聯網的發展走過了十余年。網站備案過程中的真實性核驗環節,需要網站負責人到指定的核驗點進行現場拍...

  • 如何做好百度移動搜索引擎優化?
    2019/06/19

    移動數字時代已經到來,沒有給人們太多的思考時間,而越來越多的用戶通過手機進行社交、查看新聞、移動辦公及瀏覽網頁等,隨...

匹配策略:為什么打車軟件不給你最近的車?

發布時間:2018/04/29 網站資訊 瀏覽次數:4585

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

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

1. 匹配度構建

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

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

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

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

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

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

2. 二分圖匹配

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

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

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

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

3. 給太長不看的朋友

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

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

云風網絡是集昆山網站制作,昆山網頁設計,昆山網站推廣于一體的昆山網絡公司,業務涵蓋:昆山手機網站制作,昆山網站設計,昆山網絡建設,昆山做網站,昆山網站建設,電話:13912673321

點擊這里給我發消息 技術咨詢
回到頂部
双色球在线自动选号