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

甘少君, 趙遠(yuǎn)洋, 王燕霞

(北京工業(yè)大學(xué)城市建設(shè)學(xué)部, 北京 100124)

收稿日期: 2023-12-20.

基金項(xiàng)目: 國家自然科學(xué)基金資助項(xiàng)目(62003011).

作者簡介: 甘少君(1988—), 男, 副教授, 研究方向?yàn)榻煌ù髷?shù)據(jù)分析與人工智能算法. E-mail:s.gan@bjut.edu.cn.

0 引言

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

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

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

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

1 仿真場景設(shè)計(jì)

1.1 電動(dòng)出租車運(yùn)營狀態(tài)設(shè)計(jì)

本文從電動(dòng)出租車運(yùn)營的角度,將其狀態(tài)劃分為以下5種:巡航狀態(tài)(車輛處于待命狀態(tài),隨時(shí)準(zhǔn)備接受訂單)、接單狀態(tài)(車輛接受乘客訂單請求,前往乘客上車地點(diǎn))、載客狀態(tài)(車輛正在為乘客提供出行服務(wù))、去充電狀態(tài)(車輛前往充電站或等待充電機(jī)會(huì))和充電狀態(tài)(車輛正在充電站進(jìn)行充電). 5種狀態(tài)及其轉(zhuǎn)移關(guān)系如圖1所示.

圖1 車輛運(yùn)營狀態(tài)轉(zhuǎn)換關(guān)系

1.2 訂單和充電站設(shè)計(jì)

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

一類是在乘車地約單,如公交站、小區(qū)門口和交叉口. 在此類訂單中,唯一的等待狀態(tài)是乘客等待車輛到達(dá).

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

圖2 2類訂單關(guān)系圖

為每個(gè)訂單設(shè)置最大等待響應(yīng)時(shí)間屬性,如果平臺(tái)長時(shí)間沒有為訂單分配車輛,超過此時(shí)間視為訂單流失. 此外,本文在場景中設(shè)置訂單存儲(chǔ)池,作為訂單動(dòng)態(tài)產(chǎn)生和消耗的載體. 此外,本文在場景中設(shè)置訂單存儲(chǔ)池,作為訂單動(dòng)態(tài)產(chǎn)生和消耗的載體.

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

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

待分配給車輛的訂單表示該訂單已經(jīng)被線上平臺(tái)明確指定給特定車輛完成;

新產(chǎn)生的訂單表示此時(shí)研究場景中出現(xiàn)新的訂單請求等待平臺(tái)分配車輛接單;

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

圖3 訂單池設(shè)計(jì)

為應(yīng)對(duì)車輛在充電站可能出現(xiàn)的排隊(duì)情況,本文將充電站設(shè)計(jì)為單通道多服務(wù)臺(tái)(多個(gè)相同充電功率的快充樁)的充電系統(tǒng),并規(guī)定車輛進(jìn)入充電站后的充電行為:

1)進(jìn)入排隊(duì)隊(duì)列后,中途不允許有車輛插隊(duì);

2)隊(duì)列遵循先進(jìn)先出的單向充電順序;

3)單個(gè)充電樁不能同時(shí)為多臺(tái)車輛提供充電服務(wù).

1.3 線上調(diào)度平臺(tái)設(shè)計(jì)

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

任務(wù)1:處理乘客發(fā)起的出行訂單,并指派合適的車輛接單. 平臺(tái)需要結(jié)合車輛狀態(tài)與訂單信息,使用派單策略做出最佳派單決策.

任務(wù)2:實(shí)時(shí)監(jiān)控系統(tǒng)內(nèi)各對(duì)象的運(yùn)行狀態(tài). 平臺(tái)需要跟蹤車輛位置和電量信息、訂單的起終點(diǎn)位置和數(shù)量信息以及充電站的空閑樁數(shù)量等,全面掌握仿真場景中各要素的動(dòng)態(tài)變化狀況.

圖4 調(diào)度平臺(tái)的主要任務(wù)

1.4 仿真系統(tǒng)設(shè)計(jì)

系統(tǒng)設(shè)計(jì)主要圍繞電動(dòng)出租車的充電事件、排隊(duì)事件和接單事件的處理流程展開說明.

1.4.1 充電

車輛在行駛過程中會(huì)不斷檢查自身的剩余電量,在充電調(diào)度策略介入線上調(diào)度平臺(tái)前,車輛使用臨界最低電量作為觸發(fā)巡航狀態(tài)轉(zhuǎn)移到去充電狀態(tài),車輛會(huì)前往距離最近的充電站充電.

1.4.2 排隊(duì)

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

1.4.3 接單

作為觸發(fā)車輛從巡航狀態(tài)轉(zhuǎn)移到接單狀態(tài)的關(guān)鍵,本文從線上調(diào)度平臺(tái)的角度設(shè)計(jì)派單邏輯從而實(shí)現(xiàn)接單的處理. 具體來說,平臺(tái)會(huì)定期掃描訂單存儲(chǔ)池內(nèi)所有未被服務(wù)的訂單,并根據(jù)訂單里程、乘客等待時(shí)間以及車輛當(dāng)前位置和狀態(tài)信息,指派合適的車輛完成接單任務(wù). 在選定目標(biāo)車輛后,平臺(tái)會(huì)下發(fā)指令,要求該車輛前往訂單起點(diǎn)接單.

2 派單指標(biāo)的建立

為反映乘客等車和司機(jī)候客對(duì)出行服務(wù)的影響,本文提出訂單期望值和訂單評(píng)價(jià)值2個(gè)指標(biāo).

圖5 排隊(duì)的處理邏輯圖

對(duì)乘客而言,適當(dāng)?shù)牡溶嚂r(shí)間對(duì)出行心理的影響還在可接受的范圍內(nèi). 然而,對(duì)出租車司機(jī)而言,等待乘客上車會(huì)導(dǎo)致有效運(yùn)營時(shí)間的損失. 此外,接單距離也是其他派單平臺(tái)(如滴滴打車)考慮的重要因素之一.

2.1 出發(fā)地預(yù)約訂單

出發(fā)地預(yù)約訂單對(duì)應(yīng)的訂單期望值和評(píng)價(jià)值參數(shù)如表1所示.

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

如圖6藍(lán)線部分所示,訂單評(píng)價(jià)值的計(jì)算與乘客等車時(shí)間和車輛候客時(shí)間有關(guān). 對(duì)司機(jī)而言,如果車輛過早地到達(dá)乘客上車地點(diǎn),則會(huì)得到較低的訂單評(píng)價(jià)值. 這部分對(duì)應(yīng)于評(píng)價(jià)值曲線的T1區(qū)間.

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

表1 訂單期望值與評(píng)價(jià)值參數(shù)表

圖6 出發(fā)地預(yù)約訂單的訂單期望值與評(píng)價(jià)值曲線圖

按時(shí)間順序?qū)τ唵纹谕岛陀唵卧u(píng)價(jià)值曲線進(jìn)行組合,如圖7所示.

序號(hào)①代表乘客在出發(fā)地發(fā)起訂單時(shí)對(duì)應(yīng)的評(píng)價(jià)值曲線;

序號(hào)②代表乘客在前往乘車地途中的訂單評(píng)價(jià)值曲線;

序號(hào)③代表乘客在乘車地等車的訂單評(píng)價(jià)值曲線;

序號(hào)④代表乘客已經(jīng)在乘車地等待一段時(shí)間,其可用的評(píng)價(jià)值曲線最短.

圖7 不同時(shí)刻出發(fā)地預(yù)約訂單的訂單期望值與評(píng)價(jià)值曲線變化圖

2.2 乘車地預(yù)約訂單

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

圖8 乘車地預(yù)約訂單的訂單期望值與評(píng)價(jià)值曲線圖

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

圖9 不同時(shí)刻乘車地預(yù)約訂單的訂單期望值與評(píng)價(jià)值曲線變化圖

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

3.1 延遲接受算法

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

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

3.2 偏好關(guān)系的定義

在訂單和車輛之間的偏好關(guān)系計(jì)算中,本文有如下定義:

車輛對(duì)訂單的偏好值使用cevaluation+cratio,其中cevaluation是訂單評(píng)價(jià)值,cratio是訂單的有效里程比(衡量每個(gè)訂單載客里程所占比重,值越高說明每訂單空載里程越少),車輛優(yōu)先選擇cevaluation+cratio值高的訂單.

訂單對(duì)車輛的偏好值使用cexp,其中,cexp表示訂單期望值,訂單優(yōu)先選擇訂單期望值高的車輛.

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

3.3 算法執(zhí)行

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

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

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

4 實(shí)例分析

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

圖10 研究區(qū)域圖

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

圖11 出租車訂單數(shù)量變化圖

考慮到實(shí)際出租車全天平均接單量為30單,平均載客距離10 km,平均載客時(shí)間30 min,本實(shí)例對(duì)仿真場景中相關(guān)參數(shù)進(jìn)行了調(diào)整,具體信息如表 2所示.

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

通過設(shè)置更高的日均接單量(90單)和更短的平均訂單距離(3.6 km)增加車輛運(yùn)營強(qiáng)度與復(fù)雜性,可驗(yàn)證調(diào)度策略在復(fù)雜場景下的適用性. 此外,導(dǎo)航數(shù)據(jù)的應(yīng)用提高了位置信息和訂單距離的準(zhǔn)確度,使仿真場景更加真實(shí).

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

表2 實(shí)例場景參數(shù)設(shè)計(jì)

表3 車輛不同運(yùn)營狀態(tài)累計(jì)時(shí)間分布表 (16:00—22:00) min

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

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

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

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

5 結(jié)論

1) 建立了1個(gè)高精度出租車運(yùn)營仿真場景. 該場景不僅考慮電動(dòng)出租車充電需求和載客需求,還考慮充電設(shè)施容量對(duì)車輛充電過程的影響,同時(shí)可準(zhǔn)確反映電動(dòng)出租車、充電站與乘客出行訂單的復(fù)雜交互過程.

2) 通過定量分析乘客和司機(jī)的等待行為對(duì)出行體驗(yàn)和收益的影響,建立了評(píng)估訂單價(jià)值的指標(biāo),并以此作為派單的依據(jù),基于該指標(biāo)使用延遲接受算法找到訂單與車輛之間的穩(wěn)定匹配結(jié)果,以滿足出行需求.

3) 以上海市黃浦區(qū)為例進(jìn)行實(shí)例驗(yàn)證. 結(jié)果表明,本文提出的派單策略達(dá)到了優(yōu)化乘客出行體驗(yàn)的目的,同時(shí)也提高了車輛的運(yùn)營效率.