面向城市短途拼車服務的最短路徑匹配算法

摘 "要：以乘客、司機收益非負以及不耐煩等待時間、服務時間為約束，定義了基于月租付費的短途拼車優(yōu)化問題。將問題劃分成司機與乘客匹配子過程、路徑規(guī)劃子過程，設計貪心策略。實驗結果表明，在滿足短途接駁約束條件下，文中方法可顯著提升拼車成功率。

關鍵詞：拼車；收益；短途；優(yōu)化

中圖分類號：TP301.6 " " " " " " " " " " " " " 文獻標識碼：A 文章編號：1008-5483（2024）02-0021-04

Shortest Path Matching Algorithm for Short Distance

Carpooling Services in Cities

Wang Fuluo

（Anhui Vocational College of City Management， Hefei 230011， China）

Abstract： With non-negative returns of both passengers and drivers， patience time， and service time as constraints， the monthly paid short distance carpooling optimization problem was defined. The problem was divided into two sub-procedures： matching between passengers and drivers and path planning， and a greedy strategy was designed. The experimental results show that the proposed scheme can significantly improve the successful rate of carpooling while meeting the constraints of short distance carpooling.

Key words： carpooling; return; short distance; optimization

目前全國城市私家車保有量已達4.35億輛［1］，拼車服務可緩解道路擁堵。市場上拼車服務以長距離拼車為主，短途拼車服務由于乘客均單支付費用高，面臨乘客參與度低的挑戰(zhàn)。現(xiàn)有拼車機制［2-5］大多保障司機的效用，為司機提供路最短徑規(guī)劃，而忽視了對乘客服務預算需求的保障。一些研究［6-7］假設司機收益由運營平臺分配，導致司機的個體偏好如慣常行駛路徑、期望收益等因素被忽略。一些研究對乘客的預算需求進行保障，然而缺乏對于實際應用的支撐。高納會等［8］從理論上證明了采用拼車服務可以實現(xiàn)系統(tǒng)效用的帕累托最優(yōu)提升，但缺少對于應用情境的支持。曹斌等［9］以司機的最大繞路距離最小為優(yōu)化目標，基于歐氏距離，通過樸素的貪心選擇方法，實現(xiàn)對大規(guī)模拼車乘客與司機的快速匹配，然而未考慮司機預期收益約束。文獻［10］以一口價的方式考慮了司機的預期收益約束，但并不適用于短途拼車情景?；谠伦獾陌丛沦M用包干會員制度應用于大量實時快車運營服務［11］，但受制于現(xiàn)行拼車服務的計費標準，學術與產(chǎn)業(yè)界缺乏面向月租賃拼車的服務模式研究。為解決上述問題與挑戰(zhàn)，面向私家車短途拼車中存在的司機通勤路線和接駁半徑偏好以及乘客費用預算等實際問題，利用月租費用平攤乘客成本，在保障司機效用的基礎上激勵乘客提出拼車服務請求，通過設計高效的司機、乘客貪心匹配算法，提升短途拼車的用戶效益。

1 問題定義

拼車線路見圖1，乘客a線路長2 km，乘客b線路長2.8 km，司機線路長6 km。滴滴拼車［12］費乘客a需4.8元、乘客b需5.7元，司機拼車［12-13］收入為10.5元；而公交費均為2元，司機期望收入為10.91元，含路費10.23元、管理費0.18元、保險費0.5元，因此乘客和司機均缺乏動機，拼車失敗。文中提出一種短途拼車機制，旨在提高拼車成功率。

拼車時，乘客將人數(shù)、出發(fā)地、目的地等信息發(fā)送到服務器，同時司機將可載乘客數(shù)、出發(fā)點、出發(fā)時間信息發(fā)送到服務器，服務器根據(jù)司機、乘客提交的信息完成初始化，執(zhí)行匹配算法，保障參與拼車的乘客和司機所獲得的總效用最大。拼車初始化過程如下：假設乘客在司機的接載半徑內(nèi)，同時司機的最大服務時長不小于乘客所需的服務時長，則乘客與司機為潛在拼車關系，將乘客加入到司機的探測序列。假設提供拼車服務的司機和乘客集合分別為

[D=d1，d2，…，dm， " P=p1， p2，…， pn] （1）

式中：[di]為第i個司機；[pj]為第[j]個乘客。定義司機[di]的最大座位容量[Si]，0-1變量為

[xij=0， " 司機i不接駁乘客j1， " 司機i接駁乘客j] （2）

若乘客[pj]成功完成拼車，則司機從出發(fā)地到目的地的總服務時長[tj]為

[tj=LjV] （3）

式中：Lj為乘客[pj]的里程數(shù)。每月22個工作日，每天工作8 h，則拼車服務的單位時長費[Ai]定義為

[Ai=Mi30×8×60=6.94×10-5Mi] （4）

式中：[Mi]為司機的預期月收入。若不考慮月租費的影響，可定義乘客實際搭乘費[βj]為里程費與時長費之和，即

[βj=（αQCj+Aitj）xij] （5）

式中：[α]為單位里程油耗；[Q]為汽油單價；[Cj]為乘客[pj]從出發(fā)地到目的地的里程數(shù)。為更好地激勵司機服務短途拼車乘客，引入月費套餐[μj]。假設車輛起步價格為[Y]，定義短途拼車的預算[Bj]為

[Bj=0.3Y] （6）

為定義乘客每次拼車的效用函數(shù)，將月租費平攤到每日乘車花費。假設每月短途拼車次數(shù)為[hj]，每次拼車的效用函數(shù)為

[Upassengerj=Bj+μjhj-βj] （7）

定義序列yi中的乘客[pj]等待司機到達的時間為

[ωj（ψi）=rj+k∈ψi，k≠j（ωk（ψi））] （8）

式中：[ri]為司機的期望接駁半徑；[ψi]為拼車乘客序列。所有乘客平均月租費用的總和為

[μtotal=j=1n μj] （9）

司機在拼車過程中期望獲得的效用為

[Udriveri=Li（ψ*i）Qα+Li（ψ*i）VAi] （10）

式中：[Li（ψi）]為司機的總里程量；[ψ*i]為乘客的最優(yōu)序列，使得司機總里程數(shù)最??；[V]為司機在城市道路中的平均行駛速度。因此，基于月租的短途拼車優(yōu)化問題定義為

[maxi=1mUpassengerjs.t. " j=1nxijKj≤Si， " ?i∈{1，2，…，m} " " " "Upassengerjgt;0， " Udriverigt;0 " " " "Li（ψ*i）V≤Wi， " εj≥ωj（ψi）] （11）

式中：[Kj]為乘客[pj]單次拼車所需要的座位數(shù);[Wi]為單次最大服務時長；[εj]為最大容忍延遲。記月租短途拼車問題（monthly short-range carpooling optimization，MoSC）為問題[P]，忽略司機的接載半徑激勵約束得到問題[P']。問題[P']中，將每位司機的最大服務時長與提供的拼車服務座位看成背包。MoSC可在多項式時間復雜度內(nèi)，由0-1背包問題規(guī)約得到。由于0-1背包問題是NP難問題，問題[P]比問題[P']更加復雜，因此問題[P]為NP難問題。綜上，MoSC是一個NP難問題。

2 貪心求解

MoSC問題直接求解耗時較長，無法滿足拼車即時服務的需求。相較于遺傳算法、模擬退火算法、粒子群等啟發(fā)式算法，貪心求解策略可在多項式時間復雜度內(nèi)得到1組可行解。為此，將問題劃分成司機與乘客匹配子過程和路徑規(guī)劃子過程。采用貪心算法（Greedy algorithm for the MoSC problem， GM）實現(xiàn)司機與乘客的匹配。當司機的剩余服務時長不小于乘客需要的服務時長、乘客需要的座位數(shù)不大于司機的剩余接載量，且在司機的接駁半徑時，將乘客加入到司機接駁序列。按照聯(lián)盟博弈規(guī)則針對相鄰司機與乘客組成的聯(lián)盟進行兩兩交換匹配，直到輸出穩(wěn)定的司機與乘客聯(lián)盟。貪心地，將前一乘客的目的地與后一乘客的出發(fā)地以接駁半徑、后一位乘客的等待時長所容忍的距離中最小值進行聚類。聚類的圓心坐標作為接駁序列的中間點。利用Dijkstra算法得到上述序列的最短路徑。當一個乘客分配成功時，更新對應司機的服務隊列、剩余服務時長和剩余接載量，直到所有乘客分配到司機或者剩余未分配到司機的乘客都找不到合適的匹配司機為止。具體算法如下：

輸入：[pj]，[Kj]，乘客地理位置 （[xpj，ypj]），[εj]，[Bj]，[hj]，[di] [Mi]、司機地理位置（[xdi，ydi]）、[Si]、[ri]、[Wi]等

輸出：司機乘客匹配對、司機效用、乘客效用

For each [pj∈P]在司機[di]接駁半徑[ri]內(nèi)

If 司機剩余服務時長≥乘客需求服務時長

If 司機剩余座位≥乘客需要座位

司機乘客候選匹配

End if

End if

匹配成功乘客隊列更新

針對每位司機端匹配成功乘客隊列元素

End for

形成司機-乘客初始聯(lián)盟[C0]

If 聯(lián)盟內(nèi)部效用不再增加

穩(wěn)定聯(lián)盟輸出結果代表司機-乘客匹配對

Else 按照聯(lián)盟博弈兩兩交換司機-乘客匹配對

根據(jù)式（7）與式（10）計算費用

將前一乘客的目的地與后一乘客的出發(fā)地以接駁半徑、后一位乘客的等待時長所容忍的距離中最小值進行聚類

聚類的圓心坐標作為接駁序列的中間點，減少繞路

根據(jù)最短路徑Dijkstra算法得到上述序列的最短路徑

輸出接駁路徑

更新接駁序列與司機位置

If 停止運行匹配算法

Return 拼車結果

Exit

完成初始匹配，即司機與乘客聯(lián)盟的時間復雜度為[Omn]，多個潛在聯(lián)盟之間的排序時間復雜度為[Omlogm]，選擇最優(yōu)穩(wěn)定聯(lián)盟耗時為[Om]。路徑規(guī)劃由Dijkstra算法決定[Omn]上界為[Om+n2]，因此算法運行1輪的總時間復雜度為[Om+n2]。算法在為司機與乘客配對過程中尋找目標函數(shù)最優(yōu)的聯(lián)盟，采用的交換以及每次迭代均是記錄當前最優(yōu)值［14］，由此可知，經(jīng)過有限次迭代，算法最終將收斂。

3 實驗結果與分析

設置實驗參數(shù)[Q]為8.37元·L-1，[α]為0.08 L·km-1，[V]為40 km·h?1。[Mi]為10 000元，根據(jù)式（4）計算得到拼車服務時長費為0.69元·min-1，[Y]為12元，則根據(jù)式（7）得到乘客每次用于短途拼車的預算為3元/次。假設每月乘客乘車30天，月租默認為60元，則月租平攤每日約2元。在10 km×10 km的區(qū)域內(nèi)，隨機分布5輛司機和20名乘客。每輛車的最大座位數(shù)為4，每名乘客最多可選擇2個座位，實驗隨機進行100次，取平均值。乘客不耐煩等待時間設置為5 min。月租費用不超過60元，定義平均接駁里程為[Li（ψ′i）]，在保障司機效用的前提下，乘客的拼車成功率、總效用與平均接駁里程的關系如表1所示。為更好地比較算法性能，引入隨機算法生成乘客-司機匹配對，對符合MoSC所有約束條件的匹配對，計算算法的總效用與拼車成功率。月租費用為60元時，拼車成功率隨著平均接駁里程的增加而降低，總效用也呈現(xiàn)出遞減趨勢。當平均接駁里程為4 km、2 km時，拼車成功率分別為84.7%與95.4%，總效用為62.67與131.32。這是由于隨著接駁半徑的增大，繞路距離與乘客等待時間約束無法得到有效保障的情形將會增大。相較于現(xiàn)有長途拼車成功率80%左右的結果，具有一定的商用可行性。實驗結果表明，GM算法獲得的平均拼車成功率超過隨機算法的80.14%，平均總效用超過隨機算法的98%。

4 結論

針對短途拼車難問題，提出月租式短途拼車服務，采用貪心算法解決短途拼車中司機與乘客匹配以及路徑規(guī)劃的問題。根據(jù)實驗結果表明，通過合理的選擇月租費，在保障單次乘車費用滿足乘客預算的基礎上，可有效提高短途拼車的成功率，為拼車“最后3 km”問題提供了解決方法。

參考文獻：

［1］ "公安部網(wǎng)站. 全國機動車保有量［EB/OL］.（2024-1-11）［2024-4-07］. https：//www.gov.cn/lianbo/bumen/202401/content_6925362.htm.

［2］ "蔡文廣，劉佳旭，張小欣. 基于概率路由的出租車共乘調(diào)度算法［J］. 計算機應用研究，2024，41（2）：432-437.

［3］ "晏鵬宇，張逸冰，殷允強. 乘客到達時間不確定的機場動態(tài)拼車策略與算法研究［J］. 運籌與管理，2022，31（8）：129-136.

［4］ "李詠潔，袁鵬程. 隨機環(huán)境下考慮碳排放控制的拼車調(diào)度優(yōu)化模型［J］. 物流技術，2022，41（4）：63-67.

［5］ "陳玲娟，寇思佳，柳祖鵬. 網(wǎng)約拼車出行的乘客車輛匹配及路徑優(yōu)化［J］. 計算機與現(xiàn)代化，2021（7）：6-11.

［6］ "Kleiner A，Nebel B，Ziparo V A. A Mechanism for Dynamic Ride Sharing Based on Parallel Auctions［C］//Proceedings of the Twenty-Second international joint conference on Artificial Intelligence - Volume Volume One. ACM，2011：266-272.

［7］ "Cao B，Alarabi L，Mokbel M F，et al. SHAREK：a Scalable Dynamic Ride Sharing System［C］//2015 16th IEEE International Conference on Mobile Data Management. IEEE，2015：4-13.

［8］ "高納會，魏鳳，王建華. 二次交易的利益優(yōu)化策略選擇：以拼出租車行為為例［J］. 陜西農(nóng)業(yè)科學，2011，57（2）：186-189.

［9］ "曹斌，洪峰，王凱，等. Uroad：一種高效的大規(guī)模多對多拼車匹配算法［J］. 計算機研究與發(fā)展，2019，56（4）：866-883.

［10］ "Chen L，Dai H N，Yuan X Y，et al. D-SPAC：Double-sided Preference-aware Carpooling of Private Cars for Maximizing Passenger Utility［J］. IEEE Transactions on Intelligent Transportation Systems，2024（99）：1-18.

［11］ "崔東方. 網(wǎng)絡約車行業(yè)發(fā)展的問題與對策：以“滴滴出行”為例［J］. 重慶交通大學學報（社會科學版），2018，18（2）：64-70.

［12］ "滴滴出行. 滴滴網(wǎng)約車計價規(guī)則［EB/OL］. （2022-8-30）［2024-4-07］. https：//www.didiglobal.com/contact/platform.

［13］ "車主指南. 2022滴滴抽成比例 ［EB/OL］. （2022-1-11）［2024-4-07］. https：//www.icauto.com.cn/baike/67/670676.html.

［14］ "饒衛(wèi)振，袁露霞，劉露. 基于平臺的在線大規(guī)模協(xié)作配送聯(lián)盟拆分策略研究［J］. 系統(tǒng)工程理論與實踐，2023，43（5）：1425-1445.