基于延遲接受算法的電動出租車線上派單策略

甘少君, 趙遠洋, 王燕霞

(北京工業大學城市建設學部, 北京 100124)

收稿日期: 2023-12-20.

基金項目: 國家自然科學基金資助項目(62003011).

作者簡介: 甘少君(1988—), 男, 副教授, 研究方向為交通大數據分析與人工智能算法. E-mail:s.gan@bjut.edu.cn.

0 引言

隨著出租車行業信息化水平的提高,線上派單的模式得到了廣泛應用,越來越多的出租車司機利用線上平臺開展接單業務. 出租車線上派單流程包括2個步驟:首先用戶使用移動應用發起出行服務請求,然后通過派單系統的計算將訂單分配給合適的司機. 與以往的路邊叫車方式不同,這種方式可讓用戶在不用離家的情況下叫車,而且可更方便地確定出行價格和出發時間,同時節省了司機等單的時間成本,提高了車輛運營效率. 因此,高效的線上派單策略是提升用戶出行體驗和司機收益的關鍵.

在電動出租車線上派單系統中,關于訂單分配的相關方法包括:通過對歷史訂單數據的分析,使用神經網絡預測乘客的出行需求,并根據預測的結果進行派單[1-2],Liu等[3]基于圖卷積神經網絡預測各區域的訂單需求,協調各區域內的車輛資源. 也可使用協同過濾算法來分析乘客的出行偏好向用戶推薦合適的車輛. 此外,還可結合多種算法來提高出租車線上派單系統的效率[4-5]. 例如,Alisoltani等[6]提出了1種基于滾動視窗的動態優化方法,以最小化乘客等待時間. Hu等[7]提出1種結合整數線性規劃和機器學習的實時調度模型,仿真結果表明應用該模型可減少車輛空駛距離.

在設計派單策略時,現有研究大多直接采用接單距離或接單時間作為決策依據,這種做法僅考慮縮短司機空駛距離或乘客等待時間,而未能綜合評估訂單與司機的匹配程度,從而導致派單結果難以實現全局最優. 此外,電動出租車運營是1個動態轉換過程,但是現有研究在構建仿真場景時,往往忽視了車輛和乘客的行為具有動態性. 例如,乘客可能因為等車時間過長而取消訂單;司機需要考慮車輛剩余電量,電量過低時將放棄接單而去充電. 因此,設計派單策略和仿真場景時,應該充分考慮車輛與乘客的實際情況和動態變化特征,以提高派單策略的準確性和適用性.

本文構建了1個考慮實際路網情況和電量約束的電動出租車運營仿真場景. 在此基礎上,開發了 1個具有全局控制和監控功能的線上派單平臺. 我們提出“訂單評價值”指標衡量等待時間對司機接單意愿的影響,該指標可反映不同候客時間下訂單對司機的吸引力;同時提出“訂單期望值”指標評估不同等車時間對乘客滿意度的影響. 進而以車輛接單空載里程比和訂單評價值為目標建立了電動出租車司機的偏好關系,以訂單期望值為目標建立了乘客的偏好關系,采用延遲接受算法求解電動出租車與訂單之間的匹配問題. 通過仿真驗證所設計的派單策略的有效性.

1 仿真場景設計

1.1 電動出租車運營狀態設計

本文從電動出租車運營的角度,將其狀態劃分為以下5種:巡航狀態(車輛處于待命狀態,隨時準備接受訂單)、接單狀態(車輛接受乘客訂單請求,前往乘客上車地點)、載客狀態(車輛正在為乘客提供出行服務)、去充電狀態(車輛前往充電站或等待充電機會)和充電狀態(車輛正在充電站進行充電). 5種狀態及其轉移關系如圖1所示.

圖1 車輛運營狀態轉換關系

1.2 訂單和充電站設計

為了量化乘客與司機之間的等待行為對出行體驗和收益的影響,根據乘客發起出行請求的位置,本文將訂單劃分為2類(如圖2所示):

一類是在乘車地約單,如公交站、小區門口和交叉口. 在此類訂單中,唯一的等待狀態是乘客等待車輛到達.

另一類是在出發地約單,如寫字樓、公園和商場內. 在此類訂單中,可能存在2種等待狀態:乘客等待車輛到達與車輛到達后等待乘客.

圖2 2類訂單關系圖

為每個訂單設置最大等待響應時間屬性,如果平臺長時間沒有為訂單分配車輛,超過此時間視為訂單流失. 此外,本文在場景中設置訂單存儲池,作為訂單動態產生和消耗的載體. 此外,本文在場景中設置訂單存儲池,作為訂單動態產生和消耗的載體.

圖3展示了訂單池中4類訂單狀態,其含義如下:

超時訂單表示訂單產生后在訂單池中的停留時間超過乘客最大等待時間,此時視為乘客取消訂單;

待分配給車輛的訂單表示該訂單已經被線上平臺明確指定給特定車輛完成;

新產生的訂單表示此時研究場景中出現新的訂單請求等待平臺分配車輛接單;

未超時且未被分配的訂單表示在上輪派單過程中沒有分配給合適的車輛接單,而訂單未被乘客取消,所以可繼續參與本輪派單.

圖3 訂單池設計

為應對車輛在充電站可能出現的排隊情況,本文將充電站設計為單通道多服務臺(多個相同充電功率的快充樁)的充電系統,并規定車輛進入充電站后的充電行為:

1)進入排隊隊列后,中途不允許有車輛插隊;

2)隊列遵循先進先出的單向充電順序;

3)單個充電樁不能同時為多臺車輛提供充電服務.

1.3 線上調度平臺設計

在仿真場景中,線上調度平臺的主要任務包括如下2部分(如圖4所示):

任務1:處理乘客發起的出行訂單,并指派合適的車輛接單. 平臺需要結合車輛狀態與訂單信息,使用派單策略做出最佳派單決策.

任務2:實時監控系統內各對象的運行狀態. 平臺需要跟蹤車輛位置和電量信息、訂單的起終點位置和數量信息以及充電站的空閑樁數量等,全面掌握仿真場景中各要素的動態變化狀況.

圖4 調度平臺的主要任務

1.4 仿真系統設計

系統設計主要圍繞電動出租車的充電事件、排隊事件和接單事件的處理流程展開說明.

1.4.1 充電

車輛在行駛過程中會不斷檢查自身的剩余電量,在充電調度策略介入線上調度平臺前,車輛使用臨界最低電量作為觸發巡航狀態轉移到去充電狀態,車輛會前往距離最近的充電站充電.

1.4.2 排隊

排隊發生在車輛由去充電狀態向充電狀態轉移的過程中,其處理邏輯如圖5所示. 已到達充電站的車輛通過檢查排隊隊列的長度,決定是否立即轉為充電狀態. 如果隊列長度為空且有可用充電樁,車輛開始充電,否則車輛進入隊列排隊.

1.4.3 接單

作為觸發車輛從巡航狀態轉移到接單狀態的關鍵,本文從線上調度平臺的角度設計派單邏輯從而實現接單的處理. 具體來說,平臺會定期掃描訂單存儲池內所有未被服務的訂單,并根據訂單里程、乘客等待時間以及車輛當前位置和狀態信息,指派合適的車輛完成接單任務. 在選定目標車輛后,平臺會下發指令,要求該車輛前往訂單起點接單.

2 派單指標的建立

為反映乘客等車和司機候客對出行服務的影響,本文提出訂單期望值和訂單評價值2個指標.

圖5 排隊的處理邏輯圖

對乘客而言,適當的等車時間對出行心理的影響還在可接受的范圍內. 然而,對出租車司機而言,等待乘客上車會導致有效運營時間的損失. 此外,接單距離也是其他派單平臺(如滴滴打車)考慮的重要因素之一.

2.1 出發地預約訂單

出發地預約訂單對應的訂單期望值和評價值參數如表1所示.

如圖6黃線部分所示,訂單期望值隨等待時間的增加而減少,剛發起請求時值為1,表示乘客希望盡快有車輛接單. 隨著等待時間超過T5(訂單最大等待響應時間),期望值降為0,表示乘客失去耐心取消訂單.

如圖6藍線部分所示,訂單評價值的計算與乘客等車時間和車輛候客時間有關. 對司機而言,如果車輛過早地到達乘客上車地點,則會得到較低的訂單評價值. 這部分對應于評價值曲線的T1區間.

對乘客而言,如果等車時間沒有超過乘客可接受的等車時間,訂單評價值會保持不變. 但是,一旦超過最大閾值,乘客會變得越來越焦慮,并給接單司機帶來負面影響,因此評價值逐漸下降. 這部分對應于曲線的T2和T3區間. 評價值曲線形狀為梯形,同類型訂單曲線形狀相近.

表1 訂單期望值與評價值參數表

圖6 出發地預約訂單的訂單期望值與評價值曲線圖

按時間順序對訂單期望值和訂單評價值曲線進行組合,如圖7所示.

序號①代表乘客在出發地發起訂單時對應的評價值曲線;

序號②代表乘客在前往乘車地途中的訂單評價值曲線;

序號③代表乘客在乘車地等車的訂單評價值曲線;

序號④代表乘客已經在乘車地等待一段時間,其可用的評價值曲線最短.

圖7 不同時刻出發地預約訂單的訂單期望值與評價值曲線變化圖

2.2 乘車地預約訂單

乘客在乘車地預約訂單,意味著乘車地點就是出發地點,所以t1和T1值為0,其他參數表示與出發地預約訂單相同(如圖8所示).

圖8 乘車地預約訂單的訂單期望值與評價值曲線圖

與圖7表示類似,將圖中序號①和序號②排除,則在乘車地預約訂單的狀態組合(如圖9所示),即不包括乘客前往乘車地的行程時間.

圖9 不同時刻乘車地預約訂單的訂單期望值與評價值曲線變化圖

3 基于延遲接受算法的派單策略

3.1 延遲接受算法

該算法[8-10]是由David Gale和Lloyd Shapley提出的,旨在解決“婚姻市場”中的一對一雙邊匹配問題,同時證明了該算法所得匹配結果的穩定性,即一對一雙邊匹配市場中的集合A與集合B,不存在對象a∈A和對象b∈B相較于當前匹配對象,a更傾向于b,同時b也更傾向于a.該算法被廣泛應用于解決雙邊市場的資源匹配問題.

與伴侶匹配過程類似,派單過程也需要從司機和乘客雙方的角度考慮.具體來說,假設有1個包括n輛電動出租車的集合ET={et1,et2,et3,…,etn}和1個包括m個訂單的集合O={o1,o2,o3,…,om}.對于電動出租車et∈ET,都存在1個關于訂單集合O的偏好關系>et,o1>eto2表示在偏好排序上,et更偏向于選擇o1而非o2.如果對于訂單o∈O有偏好關系o>etet,則表示對電動出租車et來說,訂單o是可接受的,否則我們稱訂單o對電動出租車et是不可接受的.同樣,每個訂單o也存在1個關于電動出租車et的偏好關系.

3.2 偏好關系的定義

在訂單和車輛之間的偏好關系計算中,本文有如下定義:

車輛對訂單的偏好值使用cevaluation+cratio,其中cevaluation是訂單評價值,cratio是訂單的有效里程比(衡量每個訂單載客里程所占比重,值越高說明每訂單空載里程越少),車輛優先選擇cevaluation+cratio值高的訂單.

訂單對車輛的偏好值使用cexp,其中,cexp表示訂單期望值,訂單優先選擇訂單期望值高的車輛.

另外,構建偏好值序列,必須遵循如下2個約束條件:首先,車輛在完成訂單后的剩余電量應大于其臨界最低電量,以確保車輛正常運營.其次,訂單的有效里程比必須大于0.5,以防止因接受超遠距離訂單而造成的虧損.這些約束條件可使我們的匹配策略更加準確地反映車輛與訂單之間的關系.

3.3 算法執行

步驟1:比較訂單數量m和車輛數量n,以確定請求者和接受者,如果m>n,則將車輛作為請求者;否則,將訂單作為請求者.以下使用車輛作為請求者進行說明.

步驟2:計算雙方的偏好值,將不滿足約束條件的偏好值設為不可接受.然后依據偏好值對訂單進行排序,每輛車選擇偏好值最高的訂單作為請求對象.

步驟k≥3:每輛車向其偏好值最高的訂單發出請求,每一個訂單都拒絕接受任何車輛的請求,收到一次以上請求的訂單會拒絕除其偏好值最高的請求外的所有請求,如果在此步驟中沒有拒絕車輛,則算法停止.否則,轉到步驟k+1.

4 實例分析

本實例構建的仿真場景選取上海市黃浦區作為背景參照(如圖10所示),場景中包括200輛電動出租車,19個公共充電站和121個快充樁.

圖10 研究區域圖

從上海市出租車全天GPS數據中提取出行訂單的時空分布特征,訂單數量在時間上的分布如下圖11所示,出租車訂單的數量隨時間呈現出明顯的高峰和低谷特征.

圖11 出租車訂單數量變化圖

考慮到實際出租車全天平均接單量為30單,平均載客距離10 km,平均載客時間30 min,本實例對仿真場景中相關參數進行了調整,具體信息如表 2所示.

為了使仿真場景更加貼近實際運營狀況,本實例選取16:00—22:00作為仿真時段,總時長360 min. 仿真開始前,所有車輛狀態均處于巡航狀態. 車輛具體位置信息和位置點間距離均使用百度地圖導航數據.

通過設置更高的日均接單量(90單)和更短的平均訂單距離(3.6 km)增加車輛運營強度與復雜性,可驗證調度策略在復雜場景下的適用性. 此外,導航數據的應用提高了位置信息和訂單距離的準確度,使仿真場景更加真實.

從車輛運營的角度進行分析,表3的結果可看出,與就近派單策略相比,本文提出的派單策略使車輛總巡航時間減少了719 min,而載客時間增加了1 794 min,這說明該策略優化了車輛運營狀態,使更多車輛處于載客狀態,減少了浪費在巡航狀態的時間. 此外,接單時間減少了942 min,排隊時間減少了171 min,這從側面說明本文提出的派單策略加快了車輛運營狀態轉換的速度,在一定程度上分散了充電需求. 其他運營狀態時間的變化均在10%以內,說明在釋放運力的同時,本文提出的派單策略并未對車輛整體運營狀態產生顯著影響.

表2 實例場景參數設計

表3 車輛不同運營狀態累計時間分布表 (16:00—22:00) min

表4記錄了在不同派單策略下,乘客與司機之間的等待時間差異. 使用就近派單策略實現了將車輛及時派往乘客上車地點的目的,但同時增加了司機在現場候客的時間. 而在使用本文提出的派單策略后,將司機候客時間顯著減少了1 725 min,同時也減少了乘客等待車輛到達的時間532 min. 這說明本文提出的派單策略在保證服務響應速度的同時,也平衡了乘客和司機的等待時間,有效減少了系統運營過程中的無效等待時間,提高了運營效率.

表4 乘客-司機總等待時間(16:00—22:00) min

為驗證所設計的派單策略能有效減少訂單高峰時段乘客等車時間和司機候客時間,我們選擇09:00—15:00作為仿真時段. 相較于16:00—22:00,該時段內的訂單量更大,系統運力更緊張,相應的車輛接單數增加. 因此,與表4的結果相比,表5中乘客等車和司機候客時間均有不同程度的增加. 但是在應用本文提出的派單策略后,乘客等車時間減少了 1 532 min,司機候客時間減少了2 509 min. 這表明該派單算法在訂單高峰時段同樣可起到減少系統內無效等待時間的作用.

表5 乘客-司機總等待時間(09:00—15:00) min

5 結論

1) 建立了1個高精度出租車運營仿真場景. 該場景不僅考慮電動出租車充電需求和載客需求,還考慮充電設施容量對車輛充電過程的影響,同時可準確反映電動出租車、充電站與乘客出行訂單的復雜交互過程.

2) 通過定量分析乘客和司機的等待行為對出行體驗和收益的影響,建立了評估訂單價值的指標,并以此作為派單的依據,基于該指標使用延遲接受算法找到訂單與車輛之間的穩定匹配結果,以滿足出行需求.

3) 以上海市黃浦區為例進行實例驗證. 結果表明,本文提出的派單策略達到了優化乘客出行體驗的目的,同時也提高了車輛的運營效率.