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

有效

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

本發(fā)明公開了一種面向大規(guī)模打車平臺的任務(wù)匹配公平方法，屬于計算機(jī)領(lǐng)域；具體是：首先，針對某城市，以固定時間頻率將打車場景中空閑的在線司機(jī)和未服務(wù)的訂單組成二分圖；更新當(dāng)前時間窗內(nèi)的二分圖各邊權(quán)；然后，在更新完邊權(quán)的二分圖上，計算出每個在線司機(jī)對應(yīng)的訂單匹配；最后，對在線司機(jī)與對應(yīng)訂單的匹配結(jié)果進(jìn)行學(xué)習(xí)，更新價值函數(shù)，用于下一個時間窗的評估；同時，根據(jù)更新的價值函數(shù)引導(dǎo)空閑的在線司機(jī)進(jìn)入訂單熱區(qū)，避免在線學(xué)習(xí)的冷啟動。本發(fā)明加入引導(dǎo)策略，調(diào)度司機(jī)到附近價值高的網(wǎng)格，實現(xiàn)了各司機(jī)的收益公平；同時，將公平性檢查嵌入到查找增廣路過程中，沒有增加額外的時間復(fù)雜度。

技術(shù)領(lǐng)域

本發(fā)明屬于計算機(jī)軟件領(lǐng)域，涉及一種時空眾包任務(wù)匹配方法，具體是一種面向大規(guī)模打車平臺的任務(wù)匹配公平方法。

背景技術(shù)

現(xiàn)有技術(shù)中，面向大規(guī)模打車平臺的任務(wù)匹配方法大部分都側(cè)重于提供理論性能保證；為了得到理論保證，現(xiàn)有方法通常會對司機(jī)和訂單(任務(wù))之間復(fù)雜的時序依賴做出簡單的假設(shè)，導(dǎo)致在現(xiàn)實應(yīng)用中無法達(dá)到預(yù)期效果；通過使用強(qiáng)化學(xué)習(xí)來提高打車平臺的運行效率，不僅在模擬環(huán)境中實現(xiàn)了最佳性能并且已經(jīng)成功部署到現(xiàn)實場景中。

針對公平性的匹配方法可分為兩類：靜態(tài)和動態(tài)。靜態(tài)公平任務(wù)匹配中，工人和任務(wù)都是靜態(tài)的，而在大規(guī)模打車場景中司機(jī)(工人)和訂單(任務(wù))都是動態(tài)出現(xiàn)，因此司機(jī)和訂單之間的公平匹配屬于動態(tài)公平匹配問題。在動態(tài)公平匹配領(lǐng)域，一些工作針對云計算和web請求分配問題研究的是如何實現(xiàn)多臺服務(wù)器之間的負(fù)載均衡。然而，這些工作的優(yōu)化目標(biāo)是服務(wù)器(工人)為同樣數(shù)量或價值的計算或web請求(任務(wù))提供服務(wù)。這一公平目標(biāo)不適用于打車場景，因為在打車場景中工人是司機(jī)，每個司機(jī)具有不同的工作時間以及時序依賴的工作范圍。

發(fā)明內(nèi)容

針對上述問題，本發(fā)明考慮真實大規(guī)模打車場景的特性，基于強(qiáng)化學(xué)習(xí)兼顧公平和效率；提出了一種面向大規(guī)模打車平臺的任務(wù)匹配公平方法，通過計算司機(jī)的收益率并通過公平性的量化指標(biāo)進(jìn)行驗證，同時利用強(qiáng)化學(xué)習(xí)明確司機(jī)與訂單匹配之間的時序依賴關(guān)系，學(xué)習(xí)可感知未來的匹配策略，并引導(dǎo)司機(jī)進(jìn)入訂單熱區(qū)，達(dá)到了司機(jī)之間的收入公平性和平臺總體效率雙優(yōu)化的效果。

所述的面向大規(guī)模打車平臺的任務(wù)匹配公平方法，具體步驟如下：

步驟一、針對某城市，以固定時間頻率將打車場景中空閑的在線司機(jī)和未服務(wù)的訂單組成二分圖；

二分圖中的節(jié)點為司機(jī)和訂單，司機(jī)和訂單之間如果滿足約束限制的空間距離，則兩者之間存在一條邊；

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

步驟二、初始化并更新當(dāng)前時間窗內(nèi)的二分圖的邊權(quán)；

具體過程為：

首先，將二分圖的邊權(quán)初始化為訂單的價格；

訂單價格為根據(jù)打車用戶的出發(fā)地和目的地，打車平臺自行計算的價格。

然后，根據(jù)初始的訂單價格，利用價值函數(shù)更新所有二分圖的邊權(quán)；

更新公式為：

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

步驟三、在更新完邊權(quán)的二分圖上，計算出每個在線司機(jī)對應(yīng)的訂單匹配。

具體過程為：

首先，利用BFS對二分圖進(jìn)行分解，對分解后的每個子圖進(jìn)行判斷，如果子圖只包含一個訂單對應(yīng)多個司機(jī)，或一個司機(jī)對應(yīng)多個訂單，直接從中選擇權(quán)值最大的邊作為匹配結(jié)果。