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

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

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

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

1 問(wèn)題定義

拼車線路見(jiàn)圖1，乘客a線路長(zhǎng)2 km，乘客b線路長(zhǎng)2.8 km，司機(jī)線路長(zhǎng)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元、保險(xiǎn)費(fèi)0.5元，因此乘客和司機(jī)均缺乏動(dòng)機(jī)，拼車失敗。文中提出一種短途拼車機(jī)制，旨在提高拼車成功率。

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

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

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

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

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

[tj=LjV] （3）

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

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

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

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

式中：[α]為單位里程油耗；[Q]為汽油單價(jià)；[Cj]為乘客[pj]從出發(fā)地到目的地的里程數(shù)。為更好地激勵(lì)司機(jī)服務(wù)短途拼車乘客，引入月費(fèi)套餐[μj]。假設(shè)車輛起步價(jià)格為[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á)的時(shí)間為

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

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

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

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

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

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

[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ù)時(shí)長(zhǎng)；[εj]為最大容忍延遲。記月租短途拼車問(wèn)題（monthly short-range carpooling optimization，MoSC）為問(wèn)題[P]，忽略司機(jī)的接載半徑激勵(lì)約束得到問(wèn)題[P']。問(wèn)題[P']中，將每位司機(jī)的最大服務(wù)時(shí)長(zhǎng)與提供的拼車服務(wù)座位看成背包。MoSC可在多項(xiàng)式時(shí)間復(fù)雜度內(nèi)，由0-1背包問(wèn)題規(guī)約得到。由于0-1背包問(wèn)題是NP難問(wèn)題，問(wèn)題[P]比問(wèn)題[P']更加復(fù)雜，因此問(wèn)題[P]為NP難問(wèn)題。綜上，MoSC是一個(gè)NP難問(wèn)題。

2 貪心求解

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

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

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

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

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

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

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

End if

End if

匹配成功乘客隊(duì)列更新

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

End for

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

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

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

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

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

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

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

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

輸出接駁路徑

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

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

Return 拼車結(jié)果

Exit

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

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

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

4 結(jié)論

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

參考文獻(xiàn)：

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

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

［3］ "晏鵬宇，張逸冰，殷允強(qiáng). 乘客到達(dá)時(shí)間不確定的機(jī)場(chǎng)動(dòng)態(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ì)算機(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］ "高納會(huì)，魏鳳，王建華. 二次交易的利益優(yōu)化策略選擇：以拼出租車行為為例［J］. 陜西農(nóng)業(yè)科學(xué)，2011，57（2）：186-189.

［9］ "曹斌，洪峰，王凱，等. Uroad：一種高效的大規(guī)模多對(duì)多拼車匹配算法［J］. 計(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ā)展的問(wèn)題與對(duì)策：以“滴滴出行”為例［J］. 重慶交通大學(xué)學(xué)報(bào)（社會(huì)科學(xué)版），2018，18（2）：64-70.

［12］ "滴滴出行. 滴滴網(wǎng)約車計(jì)價(jià)規(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)振，袁露霞，劉露. 基于平臺(tái)的在線大規(guī)模協(xié)作配送聯(lián)盟拆分策略研究［J］. 系統(tǒng)工程理論與實(shí)踐，2023，43（5）：1425-1445.