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

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

中圖分類號：TP301.6 " " " " " " " " " " " " " 文獻(xiàn)標(biāo)識碼：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

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

1 問題定義

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

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

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

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

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

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

[tj=LjV] （3）

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

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

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

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

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

[Bj=0.3Y] （6）

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

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

定義序列yi中的乘客[pj]等待司機(jī)到達(dá)的時間為

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

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

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

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

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

式中：[Li（ψi）]為司機(jī)的總里程量；[ψ*i]為乘客的最優(yōu)序列，使得司機(jī)總里程數(shù)最小；[V]為司機(jī)在城市道路中的平均行駛速度。因此，基于月租的短途拼車優(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]為單次最大服務(wù)時長；[εj]為最大容忍延遲。記月租短途拼車問題（monthly short-range carpooling optimization，MoSC）為問題[P]，忽略司機(jī)的接載半徑激勵約束得到問題[P']。問題[P']中，將每位司機(jī)的最大服務(wù)時長與提供的拼車服務(wù)座位看成背包。MoSC可在多項式時間復(fù)雜度內(nèi)，由0-1背包問題規(guī)約得到。由于0-1背包問題是NP難問題，問題[P]比問題[P']更加復(fù)雜，因此問題[P]為NP難問題。綜上，MoSC是一個NP難問題。

2 貪心求解

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

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

輸出：司機(jī)乘客匹配對、司機(jī)效用、乘客效用

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

If 司機(jī)剩余服務(wù)時長≥乘客需求服務(wù)時長

If 司機(jī)剩余座位≥乘客需要座位

司機(jī)乘客候選匹配

End if

End if

匹配成功乘客隊列更新

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

End for

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

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

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

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

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

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

聚類的圓心坐標(biāo)作為接駁序列的中間點(diǎn)，減少繞路

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

輸出接駁路徑

更新接駁序列與司機(jī)位置

If 停止運(yùn)行匹配算法

Return 拼車結(jié)果

Exit

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

3 實(shí)驗結(jié)果與分析

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

4 結(jié)論

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

參考文獻(xiàn)：

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

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

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

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

［5］ "陳玲娟，寇思佳，柳祖鵬. 網(wǎng)約拼車出行的乘客車輛匹配及路徑優(yōu)化［J］. 計算機(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è)科學(xué)，2011，57（2）：186-189.

［9］ "曹斌，洪峰，王凱，等. Uroad：一種高效的大規(guī)模多對多拼車匹配算法［J］. 計算機(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)絡(luò)約車行業(yè)發(fā)展的問題與對策：以“滴滴出行”為例［J］. 重慶交通大學(xué)學(xué)報（社會科學(xué)版），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)工程理論與實(shí)踐，2023，43（5）：1425-1445.