[發(fā)明專利]一種面向大規(guī)模打車平臺的任務匹配公平方法

有效

• 申請?zhí)枺?/td>: 202110642749.6
• 申請日: 2021-06-09
• 公開（公告）號: CN113240339B
• 公開（公告）日: 2022-08-30
• 發(fā)明（設計）人: 童詠昕;史鼎元;宋冰晨;徐毅;許可
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q30/06;G06Q50/30
• 代理公司: 北京永創(chuàng)新實專利事務所 11121
• 代理人: 易卜

1.一種面向大規(guī)模打車平臺的任務匹配公平方法，其特征在于，具體包括：首先，針對某城市，以固定時間頻率將打車場景中空閑的在線司機和未服務的訂單組成二分圖；將當前時間窗內(nèi)的二分圖的邊權初始化為訂單的價格，并利用狀態(tài)價值函數(shù)結合訂單取消概率更新二分圖的邊權；

所述的價值函數(shù)更新二分圖的邊權的計算公式為：

p為訂單被取消的概率，p_r為司機接受訂單r的初始訂單價格；y為折扣因子；τ_r為訂單r完成需花費的時間；d_r為訂單r的目的地位置；為司機w的狀態(tài)，包括司機當前位置和當前時間窗t；為狀態(tài)價值函數(shù)；

在更新完邊權的二分圖上，對在線司機和訂單進行匹配，并使各司機之間的收益率差距滿足公平性限制；

對在線司機和訂單進行匹配的過程為：

首先，利用BFS對二分圖進行分解，對分解后的每個子圖進行判斷，如果子圖只包含一個訂單對應多個司機，或一個司機對應多個訂單，直接從中選擇權值最大的邊作為匹配結果；否則，針對每個子圖，在KM算法中使用DFS遞歸查找增廣路；具體如下：

從司機w₁出發(fā)，當訪問到一個未匹配的訂單r₁，將該訂單r₁和司機w₁匹配；否則，司機w₁訪問到一個已經(jīng)和其他司機匹配的訂單r₂，則從該訂單r₂對應的匹配司機w₂出發(fā)執(zhí)行DFS查找增廣路，判斷司機w₂是否在新的增廣路上找到了新的匹配訂單，如果沒有，則司機w₁繼續(xù)訪問其他訂單；否則，司機w₂在新的增廣路上找到了新的匹配訂單r₃，按照KM算法將司機w₁和訂單r₂匹配，將司機w₂和訂單r₃匹配；

為了滿足公平性限制，對司機w₁和訂單r₂匹配，司機w₂和訂單r₃匹配后，判斷司機w₁和w₂的收益率差距是否超過公平性限制；如果是，則放棄司機w₁和訂單r₂匹配，保留w₂和訂單r₂匹配；否則匹配成功；

最后，對在線司機與對應訂單的匹配結果進行學習，更新價值函數(shù)，用于下一個時間窗的評估；

所述的更新價值函數(shù)具體為：

首先，對每個匹配結果中的司機價值函數(shù)更新，計算公式為：

其中，β為學習率，Δ_w的計算方式如下：

然后，根據(jù)同一個地理位置的多個司機共享價值函數(shù)，將價值函數(shù)簡化為：

其中，l表示該城市所有可能打車的位置集合；w:l_w是指在同一個地理位置的所有司機；Δ_w簡化為：

接著，將城市分為六邊形網(wǎng)格和正方形網(wǎng)格，并找到各司機所在位置屬于的六邊形網(wǎng)格和正方形網(wǎng)格，根據(jù)上面的更新方法得到兩個價值函數(shù)H()和S()，選取司機所屬網(wǎng)格附近網(wǎng)格的平均價值函數(shù)進行平滑，公式如下：

其中，DIR_H指定了六邊形層用于光滑的有向偏移量，DIR_S指定了正方形層用于光滑的有向偏移量，H()是城市空間的六邊形層對應的價值函數(shù)，S()是城市空間的正方形層對應的價值函數(shù)；

同時，根據(jù)更新的價值函數(shù)引導空閑的在線司機進入訂單熱區(qū)，實現(xiàn)司機之間的收益公平。

2.如權利要求1所述的一種面向大規(guī)模打車平臺的任務匹配公平方法，其特征在于，所述的二分圖中的節(jié)點為司機和訂單，司機和訂單之間如果滿足約束限制的空間距離，則兩者之間存在一條邊；

約束限制條件是指：在線空閑司機和未服務訂單的空間直線距離小于閾值，閾值根據(jù)實際情況人為設定。

3.如權利要求1所述的一種面向大規(guī)模打車平臺的任務匹配公平方法，其特征在于，所述的初始訂單價格為根據(jù)打車用戶的出發(fā)地和目的地，打車平臺自行計算的價格。