陳立軍, 張 屹, 陳孝如, 楊 微

(廣州軟件學院 軟件工程系, 廣州 510990)

網(wǎng)約車是一種新興的共享出行服務, 可顯著提高城市交通容量, 例如, 中國的一個主要網(wǎng)約車平臺在2020 年的日出行量已超過 5000 萬[1]. 網(wǎng)約車服務由司機、乘客和平臺組成, 平臺將乘客提交給司機與出租車請求進行匹配, 出租車請求和司機之間匹配, 也就是任務分配, 是網(wǎng)約車研究的核心問題[2].

現(xiàn)有研究主要從平臺或乘客的角度優(yōu)化任務分配,而很少從駕駛員的角度研究問題, 例如, 已經(jīng)設計了許多分配算法來最大化效用[2,3]或最小化旅行成本[4]或乘客的等待時間[5], 直到最近, 先行工作[6]才探索司機的收益公平性, 例如在任務分配期間平衡司機之間的收入. 本文認為, 盲目地將司機分配到最大化效用的任務可能會損害司機之間顯著的收入差距[7]. 圖1 通過僅最大化效用的分配算法模擬了4 個駕駛員的軌跡, 司機1 首先被分配一個請求, 該請求在偏遠區(qū)域結(jié)束, 完成這個訂單后, 他很難回到繁忙的地區(qū), 導致他每小時收入很低; 相比之下, 司機3 很幸運, 在繁忙區(qū)域結(jié)束一個訂單后, 又立即被分配到另一個繁忙區(qū)域請求, 他可以獲得更高的每小時收入; 司機2 留在繁忙區(qū)域, 但很少被分配到請求, 長時間的空閑時間導致他低小時收入; 相比之下, 司機4 碰巧被分配了許多請求, 而且空閑時間短有助于提高每小時收入. 司機之間的這種每小時收入差距(在本例中為司機 1、司機2 與司機 3、司機4)可能會使司機氣餒并導致不公平的任務分配.

圖1 模擬駕駛員軌跡

盡管在云計算中的負載平衡[8]等應用領(lǐng)域中, 任務分配的公平性得到了廣泛的研究, 但網(wǎng)約車中的公平任務分配面臨著獨特的挑戰(zhàn): (1) 在線設置: 網(wǎng)約車是一種雙向在線分配場景, 具有高時空依賴性和變化[9]; (2) 雙目標優(yōu)化: 一個理想的網(wǎng)約車分配算法應該在各種實際約束下優(yōu)化司機之間的效用和公平性; (3) 高效率要求: 現(xiàn)實世界的網(wǎng)約車平臺需要對城市規(guī)模的數(shù)據(jù)進行快速分配. 最先進的網(wǎng)約車公平分配算法[6,10]未能解決所有這些挑戰(zhàn). 首先, 這些解決方案是短視的,也就是說, 他們忽略了當前分配對未來分配的影響, 這在很大程度上縮小了優(yōu)化空間, 從而顯著降低了可實現(xiàn)的效用和公平性; 其次, 它們要么依賴于線性規(guī)劃[6],要么需要多輪重新分配[10], 這使得它們對于大規(guī)模數(shù)據(jù)的實時響應效率低下.

本文提出了公平分配學習(learning to assign with fairness, LAF)方法, 一個有效和高效的任務分配方案,優(yōu)化了效用(以所有司機的期望總收入衡量) 和公平(以司機之間的時間收入公平衡量). LAF 通過強化學習, 學習未來感知分配策略, 明確地說明了作業(yè)之間的依賴性, 這種學習分配策略可以整體優(yōu)化效用和公平性. 為了實現(xiàn)高效分配, LAF 將公平性和效用優(yōu)化嵌入到相同的賦值操作中, 并利用二部圖的稀疏性進一步加速. 值得一提的是, 本文提出了一個加權(quán)平攤公平度量而不是傳統(tǒng)的未加權(quán)[6]來表征司機在更細的時間粒度上的收入公平性, 如小時收入公平性.

評價結(jié)果顯示, 在公平和效用方面, 比普通水平分別提高了45.7%–86.7%和7.7%–29.1%[6,10]. 本文的LAF 也比文獻[6,10]快到700. 本文主要貢獻如下:

(1)據(jù)本文所知, 這是第一個明確考慮當前和未來任務之間的依賴性的工作, 以提高公平的任務分配在網(wǎng)約車服務的表現(xiàn);

(2)提出了一種新的基于強化學習的公平任務分配方案LAF, 該方案適應高度動態(tài)的交通, 符合實際設置, 適合大規(guī)模的網(wǎng)約車應用;

(3)廣泛的評估表明, 本文的LAF 在公平性、效用和效率方面遠遠優(yōu)于最先進的文獻[6,10].

本文其余部分組織如下: 第1 節(jié)回顧相關(guān)工作, 第2 節(jié)介紹本文的問題, 第3 節(jié)解釋本文的方法, 第4 節(jié)給出評估, 第5 節(jié)進行總結(jié).

1 相關(guān)工作

本文的工作主要涉及兩個研究方向: 網(wǎng)約車中的任務分配和分配問題的公平性.

1.1 任務分配

由于打車服務在大城市的快速擴張, 引起了廣泛的研究興趣, 其中一個核心課題是為特定的優(yōu)化對象向司機分配打車請求. 網(wǎng)約車的共同目標包括最大化利潤[3,11]、最小化旅行成本[9,12]、最小化乘客等待時間[1,5]等. 許多任務分配算法關(guān)注于提供理論上的性能保證[5], 然而, 他們經(jīng)常會做出假設——比如司機和任務之間的獨立性, 這往往會阻止他們在現(xiàn)實世界的應用程序中實現(xiàn)預期的性能. 一個很有前途的替代方案是, 在很少的假設下, 自動學習從歷史數(shù)據(jù)中優(yōu)化分配,例如, 文獻[13]最近的一些工作通過使用強化學習優(yōu)化效用實現(xiàn)了最先進的性能. 在這項工作中, 本文也針對適合大規(guī)模應用的實際任務分配算法, 但本文是第一個設計基于強化學習的解決方案, 以優(yōu)化效用和公平性.

1.2 分配任務的公平性

在各種應用中, 公平一直是分配問題的一個重要因素[14,15]. 關(guān)于公平分配的研究可以根據(jù)任務和員工是靜態(tài)的還是動態(tài)的而分為兩類. 在靜態(tài)公平任務分配中, 工作者和任務都是靜態(tài)的; 動態(tài)公平分配比較困難,因為其中一方或雙方都是動態(tài)的, 這個設置適用于云計算[16]和Web 請求分配[8]等應用程序, 它們的目標是平衡服務器的負載. 一些工作(如文獻[17])研究了空間眾包中的公平分配, 公平意味著員工承擔相同數(shù)量或價值的任務, 這個公平的目標不適合網(wǎng)約車, 因為不同的出租車司機有不同的工作時間.

網(wǎng)約車公平屬于動態(tài)公平分配問題, 特別令人感興趣的是司機收入的公平性[6,10]. 由于任務和司機的強烈時空動態(tài), 網(wǎng)約車中的公平分配具有挑戰(zhàn)性. 在這項工作中, 本文提出了一種新的駕駛員收入公平指標, 該指標解釋了這種時空動態(tài), 并設計了高效且有效的分配算法, 其性能明顯優(yōu)于最先進的公平分配算法[6,10].

2 問題陳述

與之前的研究(文獻 [6,10]) 一樣, 本文考慮將司機批量分配給請求, 令W和R是感興趣的時間范圍T中的司機和請求的集合, 在每個批次t中, 該批次中可用的請求R(t)和司機W(t)之間的分配被表述為二部圖匹配問題, 以優(yōu)化效用和公平性, 批量設置在現(xiàn)實世界的大規(guī)模乘車應用中被廣泛采用[2,13].

定義1 (請求). 一輛出租車請求r∈R, 表示為一個元組,or,dr,pr, τr分別代表出發(fā)地、目的地、價格和持續(xù)時間.

在現(xiàn)實世界的網(wǎng)約車應用中, 請求的來源和目的地由乘客輸入并上傳到平臺上, 本文對請求的來源和目的地不作任何假設, 平臺收到請求后, 根據(jù)行程距離和交通擁堵等因素, 確定價格并估計請求持續(xù)時間, 為簡單起見, 本文假設持續(xù)時間是t的倍數(shù), 如果請求被分配給一個司機, 則比值pr/τr決定他的每批收益, 本文將在下面解釋.

定義3 (二部圖). 本文使用二部圖G(t)= , 表示候選人之間的作業(yè)司機和第t批次的請求,節(jié)點集R(t)請求被分配到第t批次的可用司機W(t). 如果請求r可以分配給司機w, 則有一個邊(r,w)∈E(t),帶有一個權(quán)重θr,w.

根據(jù)之前關(guān)于網(wǎng)約車[11]中任務分配的研究, 為了避免乘客等待時間過長, 只有當請求-司機距離在某一閾值內(nèi)時才存在優(yōu)勢. 本文還為每條邊(r,w)指定了一個拒絕率λr,w, 以考慮其他與用戶體驗相關(guān)的因素, 距離閾值和拒絕率由平臺設置, 權(quán)重θr,w初始設定為請求r的價格pr.

本文的目標是為每個批次t∈{1, 2, ···,T}找到一個匹配M(t)的候選分配G(t), 優(yōu)化總效用和時間收入公平性, 定義如下.

定義4 (總效用). 給定可重用的司機集W和動態(tài)出現(xiàn)的請求集R, 總實用程序是所有司機在T批之前的預期累積收益, 即:

定義5 (加權(quán)公平平攤). 駕駛員w的加權(quán)攤銷公平性為其累計收益除以其加權(quán)活躍時間:

其中,ξ(t)是與收益相關(guān)的權(quán)重, 用于將一天中不同時段的潛在收益變化正常化, 通常, 關(guān)注的時間范圍T是一天, 批次t以秒為刻度(例如2 s), 時間權(quán)重ξ(t)以每小時為基礎變化, 這是因為報告顯示, 出租車司機在決策時關(guān)注小時和日工資, 研究表明出租車需求按小時大幅波動. 為簡單起見, 本文使用包含批次t的當前小時內(nèi)司機收入的中位數(shù)為ξ(t).

為了量化各司機間的公平性分布, 本文定義了基于權(quán)重攤銷的時間收益公平性, 如定義6 所示.

定義6 (時間收益公平). 給定可重用的司機集W和動態(tài)出現(xiàn)的請求集R,W之間的時間收益公平性由加權(quán)平攤公平性的熵變量來度量:

較大的F表示駕駛員之間的分散加權(quán)平攤公平,即高收入不平等. 因此, 本文的目標是最小化F.

對大型網(wǎng)約車應用的總效用U和時間收益公平性F進行分析是具有挑戰(zhàn)性的, 以往的解決方案[6,10]有以下局限性:

(1)忽視當前和未來作業(yè)之間的時間依賴性: 許多現(xiàn)有的建議通過假設新司機在時間范圍內(nèi)獨立到達來簡化問題設置. 然而, 司機在下一批中的可用性和位置會受到當前批中的分配的影響, 這種依賴關(guān)系會影響效用和公平性的優(yōu)化, 特別是在短期內(nèi), 出租車的供需可能會在空間和時間上發(fā)生劇烈波動.

(2)對于大規(guī)模應用程序來說效率低下: 以往的研究采用線性規(guī)劃的方法來解決雙目標匹配問題, 這可能會導致大規(guī)模叫車的實時響應速度較慢.

3 建議的方法

在本節(jié)中, 介紹了LAF 方法, 這是一種新的解決方案, 用于優(yōu)化大規(guī)模網(wǎng)約車應用的總效用和時間收入公平. LAF 采用一種基于強化學習的重新加權(quán)方案,明確地考慮了匹配過程中當前和未來任務之間的時間依賴性. 該方案采用在線方式實現(xiàn), 以適應出租車供需的動態(tài)變化. LAF 還包含了一組剪枝和加速策略, 用于大規(guī)模數(shù)據(jù)上的高效雙目標(效用和公平性)分配. 本文在第3.1 節(jié)對LAF 進行了概述, 并在第3.2 節(jié)和第3.3 節(jié)詳細闡述了細節(jié).

3.1 公平分配學習(LAF)概述

LAF 由一個基于學習的重新加權(quán)模塊和一個有效的雙目標分配模塊組成, 見圖2.

圖2 LAF 工作流程

在每個批次中, 基于學習的重新加權(quán)模塊首先考慮分配之間的時間依賴性, 重新調(diào)整給定二部圖的邊權(quán)重, 然后高效的雙目標分配模塊通過公平增強和其他加速技術(shù)找到分配, 最后, 基于學習的重新加權(quán)模塊根據(jù)分配結(jié)果更新權(quán)重, 并在必要時引導空閑駕駛員.

基于學習的重新加權(quán)模塊(第 3.2 節(jié))細化二部圖中的邊權(quán)重, 這些邊權(quán)重被初始化為旅行價格(見定義3), 以反映當前分配對未來效用和公平性的影響, 權(quán)重細化策略是通過在線強化學習獲得的, 本文還設計了一個駕駛員指導方案來緩解在線學習的冷啟動問題.

高效的雙目標分配模塊(第 3.3 節(jié))將出租車請求分配給司機, 同時考慮實用性和公平性, 它的核心是公平增強算法, 它應用 Kuhn-Munkres 算法[18]來最大化效用并檢查司機的收入率以確保公平.

在每個批次中, LAF 分4 個階段運行: 評估、分配、指導和學習(如圖2), 每個批次都從評估開始, 給定一個邊權(quán)重由旅行價格初始化的二部圖, 基于學習的重新加權(quán)模塊將更新權(quán)重, 以便權(quán)重反映當前和未來的收益, 然后在分配階段, 高效的雙目標分配模塊在細化的二部圖上計算新的匹配, 同時考慮效用和公平性. 由于: (1) 更新的權(quán)重考慮了當前分配對未來分配的影響; (2) 分配算法是雙目標的, 因此產(chǎn)生的分配以整體方式優(yōu)化了效用和公平性; 最后是學習和指導階段. 重新加權(quán)模塊將從匹配結(jié)果中學習以改進其下一批的重新加權(quán)策略, 并引導空閑駕駛員到繁忙區(qū)域以避免在線學習的冷啟動.

3.2 基于學習的重新加權(quán)

本小節(jié)解釋了如何應用在線強化學習來模擬當前分配對未來效用和公平性的影響, 第3.2.1 節(jié)介紹基本公式, 第3.2.2 節(jié)至第3.2.4 節(jié)討論實際問題, 第3.2.5節(jié)介紹完整的設計.

3.2.1 基于在線強化學習的公式

強化學習[8]是一種智能體, 隨時間與環(huán)境交互的學習方法, 代理每一步都采取行動并從環(huán)境中獲得獎勵, 基于獎勵, 代理更新其價值函數(shù), 如果代理按照策略π采取行動, 該函數(shù)將從代理w的狀態(tài)映射到預期的累積獎勵, 可以通過評估與環(huán)境交互獲得的獎勵來學習最優(yōu)策略.

由于本文的目標不是明確的策略π, 為了簡潔起見, 在其余的論文中省略了上標π. 另請注意, 本文采用在線強化學習模型來適應城市交通的短期動態(tài), 將交通模式預測與強化學習相結(jié)合超出了本文的范圍.

3.2.2 減少狀態(tài)數(shù)

上面的公式有太多的狀態(tài)供智能體探索, 這阻礙了有效的強化學習. 簡單的狀態(tài)離散化是不夠的, 狀態(tài)總數(shù)是空間狀態(tài)數(shù)Ns乘以時間狀態(tài)數(shù)NT, 考慮將一個城市劃分為 1 km2的方塊, 將一天的時間范圍劃分為跨度為 20 min (平均旅行持續(xù)時間)的片段, 那么Ns和NT將分別約為 8 000 和 72, 導致超過總共 500 000個方塊, 這超出了代理在一天 25 200 次操作中的探索,假設活動時間為 14 h (允許的最大工作時間)并每 2 s探索一個狀態(tài)(一批), 如果排除服務請求的時間, 實際探索次數(shù)要低得多.

本文通過兩種方法減少狀態(tài)數(shù):

(1)空間值近似函數(shù): 本文將時空狀態(tài)空間中的原始價值函數(shù)近似為空間狀態(tài)空間, 即Vw(dr,t+τr)=Vw(dr,t), 這是合理的, 因為大多數(shù)請求持續(xù)時間不到半小時,價值函數(shù)的變化可以忽略不計. 因此, 更新方程可以改寫為:折扣因子γ糾正了長時間請求的近似誤差.

(2)代理之間的信息共享: 使用一個結(jié)合所有代理的價值函數(shù)的共享價值函數(shù), 這是合理的, 因為處于相似時空狀態(tài)的駕駛員應該對位置具有相似的評估, 因此, 更新方程進一步簡化為:

第1 種方法將狀態(tài)總數(shù)從NT·Ns減少到Ns; 第2 種方法使所有司機探索相同的價值函數(shù)以擴展探索,由于城市中司機的數(shù)量可能在 10 000 的數(shù)量級, 每個方塊平均會被探索一百次, 這足以收斂.

3.2.3 適應不同的城市布局

在實際的網(wǎng)約車應用中, 空間通常是離散的[2,13],這限制了價值函數(shù)在城市布局上的變化, 為了消除這些限制, 本文從不同方向?qū)r值函數(shù)進行平滑, 這包括兩個步驟: (1) 將位置離散為一個兩層結(jié)構(gòu); (2)對不同層值進行平滑.

在LAF 中, 這兩層分別是六邊形層和正方形層,城市在這兩層中分別被分割成六邊形和正方形. 這兩種形狀提供了不同的平滑特性: 六邊形有更多的方向,通過這些方向的平滑有利于不規(guī)則的城市布局; 正方形的邊界與經(jīng)緯度平行, 適用于規(guī)則區(qū)域. 如圖3 所示,六邊形層為與主干道形狀一致的徑向模式(圖3(a)), 而正方形層為區(qū)域模式(圖3(b)), 表示部分繁忙區(qū)域.

圖3 下午17:00 的六邊形和正方形值函數(shù)(H 和s 中間較暖的顏色表示較高的值)

最后, 本文將價值函數(shù)平滑如下:

其中,H和s為六邊形和正方形的價值函數(shù), 由式(8)更新,DIRH和DIRs為兩層的平滑方向偏移量.

3.2.4 在線學習中避免冷啟動

由于在線學習的方式, 價值函數(shù)被初始化為零, 導致值評估退化為初始權(quán)值(出行價格), 這樣的冷啟動禁止初始批的分配是未來感知的, 為此, 本文建議提前指引司機前往適當?shù)攸c, 適當?shù)膮^(qū)域由價值函數(shù)的距離和增量決定(即算法3 中的第4 行). 為簡單起見, 本文使用價值函數(shù)H中的六邊形區(qū)域(Ah)作為候選的引導目的地.

3.2.5 再加權(quán)模塊

基于學習的再加權(quán)模塊由評估、學習和指導3 個階段組成. 算法1、算法2 和算法3 分別說明了過程,在算法3 的第4 行中, 函數(shù)dist計算距離. 重新加權(quán)模塊利用強化學習明確考慮當前作業(yè)對未來作業(yè)的影響,它不會直接促進公平. 在LAF 中, 公平目標的優(yōu)化嵌入到總效用的優(yōu)化中, 將在下面解釋.

算法1. 重新加權(quán)模塊的評估階段輸入: 二部圖G(t)= , 拒絕概率λ, 六邊形H 價值函數(shù),S 方值函數(shù)輸出: 重權(quán)后的二部圖G(t) =< W(t), R(t), E′(t) >E′(t) ← ? for w, r, θw, r ∈ E(t) do calculate V(lw) and V(dr) by Eq(9)θw, r ← (1?λw, r)·(pr+γτrV(dr)?V(lw))∪E′(t) ← E′(t) (w, r, θw, r)end Return E′(t)算法2. 重權(quán)模塊的學習階段輸入: 賦值結(jié)果M(t), 司機W(t), 六邊形值函數(shù)H, 正方形值函數(shù)S輸出: 更新后的值函數(shù)H 和S for w in W (t) do if there exists an order r, s.t. (w, r) ∈ M (t) then ΔH ← pr + γτr H(dr ) ? H(lw)ΔS ← pr + γτr S(dr ) ? S(lw)

end else ΔH ← 0, ΔS ← 0 end H ← H + β · ΔH, S ← S + β · ΔS end return H, S算法3. 重稱重模塊引導階段wti輸入: 空閑司機 , 候選目的地Ah, 從第1 批到當前批t 的權(quán)重ξ輸出: 指導方案δ δ← ?∑ti=1 u(i)w /ξ(i)基于遞增排序司機for w ∈ W (t) do g←argmaxg′∈AhV(g′)?V(?w)∑ti=1 a(i)w x dist(g′,?w)δ←δ∪(w,g)end Return δ

3.3 有效的雙目標分配

本節(jié)介紹了優(yōu)化效用和公平性的分配算法.

3.3.1 公平增長

不像以前的雙目標解決方案, 要么依賴于緩慢的線性規(guī)劃[16], 要么在公平和效用[5]的單獨優(yōu)化之間進行重復的重新分配, 本文建議直接將公平檢查嵌入到過程中, 以最大化更快的分配的效用.

在二部圖上尋找效用最大化的匹配的標準方法是Kuhn-Munkras 算法[8], 其中的基本操作是增長, 即首先嘗試找到一條由匹配邊和不匹配邊交替組成的路徑,而未匹配邊的權(quán)值之和大于已匹配邊的權(quán)值之和, 如果發(fā)現(xiàn), 則將未匹配邊和已匹配邊進行切換, 以增加總效用. 本文的公平增長算法的思想是, 在尋找增長路徑時, 檢查駕駛員的未來收益率, 拒絕收益率方差較大的增長, 然而, 拒絕增長可能會損害已實現(xiàn)的效用, 考慮一個新上線的司機在增長路徑上, 由于他的空閑時間幾乎為零, 所以他在服務請求后的收益比會非常大, 導致增長頻繁被拒絕. 還要注意, 在找到一個擴展路徑后,檢查所有司機的方差是非常耗時的, 因此, 本文不檢查所有的司機, 只檢查增長路徑中相鄰的兩個司機, 一旦發(fā)現(xiàn)方差比, 立即中斷并停止增長. 算法4 說明了公平的增長算法, 時間復雜度為O(N2M), 其中,M=m ax(|W(t),||R(t)|2,N=min(|W(t)|,|R(t)|.

3.3.2 加速度

算法5 利用二部圖的稀疏性, 進一步加速了均勻增長算法, 具體地說, 執(zhí)行廣度優(yōu)先搜索(BFS), 將as 分配圖分成幾個部分, 其中很多部分只包含一個司機(請求), 所以本文使用特殊的判斷來快速地為單個節(jié)點找到最佳的請求(司機).

算法4. 公平增長輸入: 二部圖G(t)= , 當前批t, 權(quán)重ξ, t 從第一批輸出: 作業(yè)M(t)M (t) ← ? for w ∈ W (t) do while there exists an augment Path P do accept ← True for every pair of adjacent drivers wpre, wcur do rpre ← current assigned request of wpre rcur ← current assigned request of wcur u(i)wpre u(i)wcur if■■■■■■■■■■■■∑ti=1 ξ(i) +prpre ξ(t)∑ti=1∑ti=1 a(i)wpre+τrpre ξ(i) +prcur ξ(t)?∑ti=1 a(i)wcur+τrpre■■■■■■■■■■■■>ε then accept ← False break end end If accept then Update M(t) based on P end end end Return M(t)算法5. 分配算法輸入: 二部圖 G (t) =< W (t), R(t), E(t) >輸出: 作業(yè)M(t)P(t) ← split G(t) by BFS.M(t) ← ? for p ∈ P (t) do if there is only one driver w (request r) then Mp ← end else Mp ← Fair Augmentation(p)end∪M (t) ← M (t) Mp end return M(t)

4 評價

4.1 實驗設置

驗證環(huán)境: 在一個大型網(wǎng)約車平臺的模擬器上進行了實驗, 在3 個城市進行了21 天的實驗, 該模擬器生成請求, 模擬駕駛員和乘客的行為(即空閑駕駛員轉(zhuǎn)換和乘客拒絕), 構(gòu)建二部圖, 并執(zhí)行本文的分配算法.

基線: 將本文的方法與以下基線進行比較:

(1)距離貪婪(DG): 它將每個請求分配給它最近的可用司機, 這是一個廣泛使用的基線叫車.

(2)收益比率貪婪(ERG): 它首先按加權(quán)攤銷公平性Fw按降序?qū)λ锌捎盟緳C進行排序, 然后按每批次的獎勵(pr/τr)降序?qū)φ埱筮M行排序, 然后它根據(jù)順序?qū)⒄埱蠓謩e分配給司機.

(3)整數(shù)線性規(guī)劃(ILP)[6]: 這是第一個應用攤銷公平性來評估網(wǎng)約車收益公平性的工作, 它將問題轉(zhuǎn)換為整數(shù)線性規(guī)劃問題. 為了公平比較, 本文從其優(yōu)化目標中省略了乘客側(cè)的公平性.

(4)重新分配(REA)[10]: 它首先分別計算優(yōu)化效用和公平性的兩個分配(調(diào)整為 minwFw以進行相等比較), 然后它將匹配從一個分配重新分配到另一個分配,以找到效用和公平之間的權(quán)衡. 這是最先進的解決方案, 可優(yōu)化網(wǎng)約車服務的實用性和公平性.

評價指標: 本文通過公平、效用和效率來評估不同方法的性能, 其中, 公平是通過時間收益公平(定義6)來衡量; 效用是通過總效用(定義4)來衡量; 效率是通過每小時累積的分配消耗時間來衡量的.

實現(xiàn): 所有算法都是在Python 3 中實現(xiàn)的, 本文將折扣因子γ(式(7))設為0.9, 學習率β＇(式(8))設為0.025. 實驗在Intel Xeon CPU E5-2630 v4 @ 2.20 GHz,12 GB 內(nèi)存上進行.

4.2 總體性能

表1 總結(jié)了3 個城市數(shù)據(jù)集上不同分配方法的公平性和效用指標, 總體而言, LAF 在工作日比基線提高了45.7%–81.4%, 在周末提高了52.0%–86.7%. LAF 總效用最高, 工作日比基線高7.7%–29.1%, 周末比基線高11.3%–28.5%. 特別是, 本文的LAF 在公平性和效用方面分別比ILP 平均高出68.4%和22.1%. 對于REA,LAF 在公平性和效用上的平均提高分別為69.3%和20.1%. 此外, LAF 在這3 個城市的表現(xiàn)都優(yōu)于基線.

表1 不同分配算法的公平性F 和效用U 的總體結(jié)果

圖4 比較了不同算法的效率, 簡單基線DG 和ERG 的時間復雜度分別為O(|E| log |E|)和O(|W| log|W|), 但在公平方面表現(xiàn)不佳, 在周末, 公平和效用方面,本文這兩個簡單的解決方案幾乎一樣快, LAF 的運行時間相對穩(wěn)定, ILP 和REA 比LAF 慢797%. 此外, 他們的運行時間是敏感的變化, 交通在高峰期, 當請求數(shù)量急劇增加時, 這兩種方法的時間成本也會顯著增加.

圖4 每個算法在A 城市每天的執(zhí)行時間

4.3 實驗結(jié)果分析

現(xiàn)在深入研究不同方法在3 個城市中規(guī)模最大的城市A的數(shù)據(jù)集上的性能, 以進一步了解本文方法的有效性.

4.3.1 LAF 與其他算法的差異

為了說明不同分配算法之間的差異, 本文在圖5中繪制了駕駛員的軌跡.

(1) DG 不顧公平, 將最近的請求分配給司機, 第2 次分配后, 駕駛員被困在偏遠地區(qū), 無法返回進行其他請求(圖5(a)); ERG 將收益比率最低的駕駛員分配給最高的pr/τr, 在第2 個請求后, 司機的收益比較低,并被分配到一個長途請求(圖5(b)).

(2) ILP 對這個司機做了與DG 相同的分配(圖5(c)),這是因為司機在完成長途請求后, 其收益比較高, 導致下一批請求的距離較近, 而在偏遠地區(qū), 由于兩次服務后的收入比較高, 司機很難再接到另一次服務.

(3) REA 兼顧了公平性和實用性, 實用程序的優(yōu)化增加了分配給司機的請求數(shù)量(圖5(d)), 但是, REA 仍然不知道目的地, 司機只能選擇一個短距離的請求, 可能被困在偏遠地區(qū).

圖5 不同分配算法下的駕駛員軌跡

(4)本文的LAF 通過考慮它們對未來任務的影響來進行任務, 該指導還避免了司機被困在偏遠地區(qū). 如圖5(e)所示, 在繁忙區(qū)域服務了一些請求后, 司機的收益比相對較高, 然后, 為了公平起見, 將請求分配給其他駕駛員, 然后, 為了避免長時間的閑置, 司機會被引導到他/她可以得到請求的區(qū)域, 然后返回到繁忙的區(qū)域.

4.3.2 流量動態(tài)與公平性的相關(guān)性

本文的貢獻之一是使用加權(quán)平攤公平Fw作為公平度量(定義5), 通過顯示Fw中的權(quán)重ξ?1(t)與流量動態(tài)之間的相關(guān)性來證明本文的加權(quán)平攤公平度量的優(yōu)勢.

圖6(a)繪制了一天中不同時間內(nèi)司機和請求的數(shù)量以及權(quán)重ξ?1(t), 司機和請求的數(shù)量反映了交通的變化, 如圖6所示, 交通流量從早上6 點到8 點上升, 白天波動, 晚上下降, 權(quán)重ξ?1(t)也呈現(xiàn)出同樣的趨勢. 這表明本文在高峰時段更注重公平, 因為那里有更多的司機, 因此需要更多的公平. 還需要注意的是, 司機在當前小時內(nèi)的收入中值, 如ξ是一個不錯的選擇, 因為它的變化略早于交通, 這是因為有經(jīng)驗的司機往往在高峰時間之前更早開始活躍, 導致收入中值提前下降,因此權(quán)重ξ可以預見地增加.

圖6(b)顯示了隨機抽樣的3500 名司機的時薪, 如圖所示, 以公平性度量作為優(yōu)化目標時, 駕駛員的時薪分布相對均勻, 而LAF 算法在減少時薪極高/極低的駕駛員數(shù)量方面表現(xiàn)最好.

圖6 不同時間司機和請求的數(shù)量

4.3.3 優(yōu)化未加權(quán)平攤公平的有效性

表2 比較了優(yōu)化未加權(quán)平攤公平性(即在所有時間t內(nèi)將ξ(t)設置為1)和效用的不同算法, DG 被排除在外是因為它不公平, 算法的效用結(jié)果與表2 相同. 結(jié)果表明, 盡管ILP 和REA 的設計是為了優(yōu)化未加權(quán)平攤公平性, 但LAF 的公平性提高了57.9%–62.2%, 效用提高了17.3%–17.6%. 因此, 本文的LAF 在未加權(quán)和加權(quán)攤銷公平性方面都優(yōu)于目前的水平.

表2 未加權(quán)平攤公平性與效用的比較

5 結(jié)論

在本文中, 提出了公平分配學習(LAF)方法, 它有效地優(yōu)化了總效用(駕駛員的預期總收入)和駕駛員的公平性(駕駛員收入的加權(quán)攤銷公平性). 關(guān)鍵的創(chuàng)新之處在于應用強化學習來進行分配, 這些分配明確說明了分配之間的依賴性, 從而可以從整體角度優(yōu)化效用和公平性. LAF 還結(jié)合了一組技術(shù)來適應交通動態(tài)和不同的城市布局, 并在大規(guī)模數(shù)據(jù)上進行快速分配.實驗結(jié)果表明, LAF 在公平性、實用性和效率方面比最先進的網(wǎng)約車公平分配算法提高了 86.7%、29.1%和 797%. 此工作將成為在現(xiàn)實世界網(wǎng)約車應用中實際采用公平任務分配的指南.