基于穩(wěn)定匹配的網(wǎng)約車合乘優(yōu)化

彭子烜,魏 然,單文軒,王文思,郭 震,蔡婉君

(1.北京交通大學(xué) 交通運(yùn)輸學(xué)院,北京 1000441; 2.北京航空航天大學(xué) 交通科學(xué)與工程學(xué)院,北京 102206;3.中國石化化工銷售有限公司 華南分公司,廣東 廣州 510620)

0 引 言

隨著“互聯(lián)網(wǎng)+”和共享經(jīng)濟(jì)的蓬勃發(fā)展,網(wǎng)約車行業(yè)應(yīng)運(yùn)而生并迅速擴(kuò)張。根據(jù)中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)調(diào)查,2016年末至2018年末,網(wǎng)約車用戶規(guī)模和用戶使用率進(jìn)入增速迅猛期,截至2022年6月,我國網(wǎng)約車用戶規(guī)模達(dá)4.05億人,網(wǎng)約車用戶使用率達(dá)到38.50%。截至2023年1月,獲得網(wǎng)約車平臺公司獲得經(jīng)營許可已有300多家。網(wǎng)約車的快速發(fā)展得益于優(yōu)惠的價(jià)格、良好的乘車體驗(yàn)和高效快速的需求響應(yīng)。其中,如何快速匹配供需,及時(shí)對需求進(jìn)行響應(yīng)成為網(wǎng)約車可持續(xù)發(fā)展的關(guān)鍵。

當(dāng)前越來越多的網(wǎng)約車平臺都推出了拼車服務(wù),它們根據(jù)乘客提交的信息(起點(diǎn),終點(diǎn),時(shí)間),整合相似出行路徑的乘客給司機(jī)派單。在這種模式下,乘客和司機(jī)被動選擇接受或拒絕平臺的指派。然而,作為利己的乘客和司機(jī),他們更關(guān)注如何使自身利益得到最大化,因此,司機(jī)對乘客存在選擇偏好(比如,司機(jī)更偏好搭載收益高的乘客),同理,乘客對司機(jī)也存在選擇偏好(比如,乘客更偏好與距離近的司機(jī)匹配)[1-3]。隨著偏好信息的納入,乘客和網(wǎng)約車匹配機(jī)制變得越來越重要。在網(wǎng)約車匹配中,如果忽視乘客和司機(jī)雙方的選擇偏好,不僅會降低他們的滿意度,還會影響他們進(jìn)入匹配市場的動力。因此,有必要提出穩(wěn)定的匹配機(jī)制,在穩(wěn)定匹配下,任何乘客和司機(jī)都無法通過單方面改變匹配對象而獲得更高的效益,實(shí)現(xiàn)匹配的均衡。

近年來,國內(nèi)外學(xué)者對網(wǎng)絡(luò)車合乘問題進(jìn)行了大量的研究[1-3],一部分學(xué)者從系統(tǒng)最優(yōu)視角出發(fā),一部分學(xué)者則從均衡視角開展研究[4-5]。D.J. FAGNANT等[6]構(gòu)建了以最小化乘客等待時(shí)間和車內(nèi)時(shí)間為目標(biāo)函數(shù)的網(wǎng)約車匹配模型;在N. AGATZ等[7]的研究中,目標(biāo)函數(shù)是最小化車輛走行距離,通過隨機(jī)優(yōu)化方法進(jìn)行求解,相比于貪婪算法,匹配效率更高;侯立文等[8]建立了多目標(biāo)合乘模型,分別為乘客效用最大化和司機(jī)總行程最小化;QIAN Xinwu等[9]的研究對象包括了出租車和網(wǎng)約車,根據(jù)主從博弈方法,研究了兩者的競爭關(guān)系和均衡狀態(tài)的存在性;WANG Xing等[2]立足于利己參與人視角,將穩(wěn)定匹配概念引入到乘客和司機(jī)的匹配中,定義并驗(yàn)證了匹配的均衡狀態(tài);胡盼等[10]研究了選擇出租車出行的影響因素;周樂欣等[11]考慮了網(wǎng)約車定價(jià)均衡問題。

穩(wěn)定匹配的概念是由D. GALE等[12]提出,并在多個(gè)領(lǐng)域均有所應(yīng)用[13-16]。近年來,穩(wěn)定匹配理論在交通領(lǐng)域得到了一定的應(yīng)用和推廣。在停車匹配方面,HE Fang等[17]研究了車輛-車位穩(wěn)定匹配問題,并對穩(wěn)定匹配狀態(tài)進(jìn)行了公式化描述,在價(jià)格的調(diào)整下,系統(tǒng)最優(yōu)解也能夠滿足穩(wěn)定匹配條件;在船貨匹配方面,PENG Zixuan等[18]研究了干散貨船-貨物穩(wěn)定匹配問題,針對供需平衡、供大于求、供小于求3種場景,設(shè)計(jì)了價(jià)格博弈策略,實(shí)現(xiàn)匹配均衡和價(jià)格均衡;在航空領(lǐng)域,ZHANG Dapeng等[19]對航線-機(jī)場的匹配穩(wěn)定問題進(jìn)行研究。

筆者設(shè)計(jì)了考慮乘客和司機(jī)選擇偏好的雙邊穩(wěn)定匹配,體現(xiàn)了乘客和司機(jī)希望能夠最大化自身利益,主要?jiǎng)?chuàng)新點(diǎn)在于:①在乘客和網(wǎng)約車的匹配中引入穩(wěn)定性的概念,將乘客和司機(jī)的選擇偏好公式化;②在網(wǎng)約車匹配中考慮乘客合乘問題,應(yīng)用沙普利值對合乘乘客的出行費(fèi)用進(jìn)行分?jǐn)?構(gòu)建無偏好假設(shè)的多對一穩(wěn)定匹配模型,并設(shè)計(jì)算法進(jìn)行求解。

1 問題描述

在網(wǎng)約車運(yùn)營中,供給方和需求方分別是司機(jī)和乘客。司機(jī)作為出行服務(wù)的提供者,在系統(tǒng)內(nèi)的位置是已知的,每個(gè)司機(jī)可以選擇搭載一位或者多位乘客。乘客是出行服務(wù)的需求者,提供了起點(diǎn)、終點(diǎn)以及時(shí)間窗等出行信息。網(wǎng)約車平臺基于以上信息,將乘客進(jìn)行分組并匹配相應(yīng)的網(wǎng)約車。乘客分組如圖1(a)。圖1(a)中,圈內(nèi)的乘客表示可以合乘出行。假設(shè)乘客希望匹配與自己距離近的司機(jī),而司機(jī)希望搭載收益高的乘客組。表1展示了司機(jī)和乘客組的偏好排序情況。比如,司機(jī)1搭載乘客組1的收益要高于搭載乘客組3,因此,他把乘客組1排在第1位。

表1 乘客和司機(jī)的偏好排序

圖1 網(wǎng)約車合乘優(yōu)化

根據(jù)以上信息,將乘客組和司機(jī)進(jìn)行匹配。其中,司機(jī)1搭載乘客組3、司機(jī)2搭載乘客組2、司機(jī)3搭載乘客組1、司機(jī)4搭載乘客組4是一個(gè)可行匹配。但是這個(gè)匹配是不穩(wěn)定的,因?yàn)樗緳C(jī)1和乘客組1把彼此排在偏好排序的第一位,卻沒有匹配到一起,他們會拒絕系統(tǒng)指派,選擇私下匹配。筆者將司機(jī)1和乘客組1稱之為阻礙匹配對。而穩(wěn)定匹配如圖1(b),司機(jī)到達(dá)乘客的起點(diǎn),將乘客送達(dá)目的地。在該匹配中,不存在任何上述的阻礙匹配對。

2 基于穩(wěn)定匹配的網(wǎng)約車合乘模型

為了便于理解匹配的穩(wěn)定性,在問題描述中,假設(shè)乘客和乘客之間沒有選擇偏好,但是在實(shí)際中,一起合乘出行的乘客之間是存在相互影響的。因此,在構(gòu)建網(wǎng)約車合乘模型時(shí),打破原有假設(shè),即文中司機(jī)對乘客組有偏好,而乘客則同時(shí)對司機(jī)和合乘乘客組合存在偏好。

2.1 乘客和司機(jī)的偏好排序

乘客作為利己的出行者,通常希望出行成本越小越好。當(dāng)有司機(jī)d搭載乘客組ρ時(shí),乘客i∈ρ的出行成本包括了車費(fèi)和時(shí)間成本兩部分,如式(1);ρ中的乘客根據(jù)沙普利值進(jìn)行車費(fèi)分?jǐn)?如式(2):

Ci(ρ,d)=Fi(ρ,d)+γ×(TGi-ei) (?i∈ρ,?d∈D)

(1)

{ε×[l(s)-l(s′)]} (?i∈ρ,?d∈D)

(2)

式中:Ci(ρ,d)為司機(jī)d搭載乘客組ρ時(shí),乘客i∈ρ的出行成本;Fi(ρ,d)為司機(jī)d搭載乘客組ρ時(shí),乘客i∈ρ付給司機(jī)的車費(fèi);γ為乘客的時(shí)間成本;TGi為司機(jī)到達(dá)乘客i終點(diǎn)的時(shí)間;ei為乘客i的最早出發(fā)時(shí)間;ρ(i)為乘客組ρ中包含乘客i的所有子集形成的集合;ε為每公里車費(fèi)單價(jià);l(s)為服務(wù)乘客集合s時(shí)車輛的最短道路距離;s′為集合s中去除元素i后剩下元素的集合。

令(ρ,d)為一個(gè)匹配對,如果乘客i∈ρ在(ρ,d)中的出行成本小于在(ρ′,d′)中的出行成本,那么乘客i更偏好匹配對(ρ,d),乘客的偏好由式(3)表示:

(3)

然而,司機(jī)通常希望收益越高越好。當(dāng)有司機(jī)d搭載乘客組ρ時(shí),司機(jī)的收益如式(4);同理,司機(jī)的偏好由式(5)表示:

(4)

ρd>ρ′d,R(ρ,d)>R(ρ′,d)

(5)

式中:R(ρ,d)為司機(jī)d搭載乘客組ρ時(shí)的收益;ξ為司機(jī)每公里收益。

2.2 穩(wěn)定匹配模型

網(wǎng)約車合乘不僅可以提高乘客的匹配率,還可以節(jié)約乘客的出行里程。而節(jié)約出行里程也有利于提高司機(jī)的收益。因此,文中目標(biāo)函數(shù)是最大化乘客節(jié)約出行里程:

(6)

(7)

(8)

(9)

(10)

3 算法設(shè)計(jì)

為了對上述多對一穩(wěn)定匹配模型進(jìn)行求解,筆者基于DA(deferred acceptance)算法進(jìn)行算法設(shè)計(jì)[12]。DA算法是求解穩(wěn)定匹配問題的算法之一,該算法可以從任意偏好排序出發(fā),通過請求和拒絕操作,產(chǎn)生一個(gè)穩(wěn)定解。DA算法已廣泛地應(yīng)用于交通問題中,如船貨匹配、共享停車匹配、網(wǎng)約車匹配等[9,17-18]。

筆者基于DA算法的思想,設(shè)計(jì)尋找穩(wěn)定匹配解的具體流程如下:

Step1:生成初始匹配解:每個(gè)參與人自我匹配(匹配對象為自己本身)。

Step2:尋找匹配解:每個(gè)乘客i尋找當(dāng)前還未被拒絕的排名最高的匹配方案。

Step3:尋找阻礙匹配對:遍歷每個(gè)乘客i和司機(jī)d的當(dāng)前匹配解,尋找是否存在一個(gè)阻礙匹配對,如果存在,則該阻礙匹配對中每個(gè)參與者均被當(dāng)前匹配方案拒絕,并轉(zhuǎn)入Step2,否則當(dāng)一個(gè)匹配解中不存在任何阻礙匹配對時(shí),算法結(jié)束。

4 案例分析

筆者以大連市為依托進(jìn)行了算例設(shè)計(jì),以驗(yàn)證模型和算法的有效性。大連市路網(wǎng)長402 km,共有個(gè)228個(gè)節(jié)點(diǎn)和383個(gè)路段?；诖筮B市出租車GPS數(shù)據(jù)得到了乘客的起點(diǎn)和終點(diǎn)以及最早出發(fā)時(shí)間。由于乘客的時(shí)間窗無法獲得,假設(shè)乘客靈活時(shí)間分為兩種,一種是緊時(shí)間窗,以(0,15)min均勻隨機(jī)生成,一種是松時(shí)間窗,以(5,30)min均勻隨機(jī)生成。最晚到達(dá)時(shí)間等于最早出發(fā)時(shí)間、起終點(diǎn)間的出行時(shí)間和靈活時(shí)間之和。假設(shè)每輛車最多載3位乘客,車速為30 km/h,單位運(yùn)營成本為0.5元/km。運(yùn)價(jià)為2元/km,乘客的時(shí)間成本為26元/h(即大連市人均稅前收入除以每月工作小時(shí)數(shù))。

4.1 小規(guī)模算例

為了說明匹配的過程,首先設(shè)計(jì)了一個(gè)包含2個(gè)司機(jī)和6個(gè)乘客的小規(guī)模算例,如圖2。假設(shè)乘客的時(shí)間窗為松時(shí)間窗?；谝陨闲畔?可以生成25個(gè)匹配對,如表2。以匹配對6為例,司機(jī)1匹配乘客1和乘客5。根據(jù)司機(jī)和乘客在各個(gè)匹配對下的收益和成本,得到偏好排序如表3。以司機(jī)1為例,最偏好的是匹配對12,即{司機(jī)1,乘客1,乘客2,乘客3}?；谄门判?計(jì)算車輛的載客能力分別為1、2和3時(shí)的匹配結(jié)果。

表2 匹配對集合

表3 乘客和司機(jī)對匹配對偏好排序

圖2 小規(guī)模算例

當(dāng)車輛的載客能力為1時(shí),匹配結(jié)果如圖3(a)。司機(jī)1匹配乘客1,司機(jī)2匹配乘客2。由于司機(jī)的數(shù)量少于乘客的數(shù)量,在非合乘下,司機(jī)更偏好搭載長距離的乘客。通常,長距離的乘客帶來的收益更高。當(dāng)車輛的載客能力為2時(shí),司機(jī)1匹配乘客1和乘客5,司機(jī)2匹配乘客2和乘客6,如圖3(b)。如果司機(jī)2搭載乘客3和乘客4,司機(jī)1匹配對象保持不變,這也是一個(gè)匹配解,但是該解不穩(wěn)定。因?yàn)楦鶕?jù)式(9),這個(gè)解會被匹配對21所阻礙。當(dāng)車輛的載客能力為3時(shí),匹配結(jié)果如圖3(c),即司機(jī)1匹配乘客1、乘客2和乘客3,司機(jī)2匹配乘客5和乘客6。乘客4由于時(shí)間窗限制沒有匹配到司機(jī)。乘客4僅參與到匹配對16和22中,但是包含這兩個(gè)匹配對的解均不穩(wěn)定。綜上所述,以上匹配解均是穩(wěn)定的,即沒有乘客或者司機(jī)能夠通過單方面改變匹配對象獲得更高的效益。

4.2 不同規(guī)模算例

筆者設(shè)計(jì)了不同規(guī)模的算例,算例的需求分為低需求(A)和高需求(B),算例包含了司機(jī)的數(shù)量,乘客的數(shù)量和時(shí)間窗。如300-600-r代表算例中有300 位司機(jī)和600位乘客,乘客時(shí)間窗為松時(shí)間窗。不同規(guī)模算例的計(jì)算結(jié)果如表4。首先,從時(shí)間窗的角度進(jìn)行結(jié)果分析,松時(shí)間窗下乘客的匹配率較高,同時(shí)乘客合乘比例也有所增加。這是因?yàn)槌丝偷臅r(shí)間窗松弛后,降低了時(shí)間約束的影響,增加了乘客合乘的可能性,乘客匹配率平均提高18%,合乘比例平均提高21%。乘客合乘有利于增加司機(jī)的平均收益,但是隨著乘客合乘的比例增加,乘客的平均等待時(shí)間也有所增加,同時(shí)可能發(fā)生一些不可避免的繞行,使得繞行比例增加。然后分析低需求(A)和高需求(B)下的計(jì)算結(jié)果,需求增加了兩倍后,司機(jī)匹配率增加,乘客合乘的比例有了大幅提升,同時(shí)司機(jī)的收入也有所提高。乘客的需求影響了合乘的可能性,參與的乘客越多,合乘的可能性就越大。

表4 不同規(guī)模的計(jì)算結(jié)果

5 結(jié) 論

筆者在研究網(wǎng)約車合乘問題時(shí),考慮了利己乘客和司機(jī)希望實(shí)現(xiàn)自身利益的最大化,基于合乘乘客間的相互影響,構(gòu)建了多對一穩(wěn)定匹配模型并設(shè)計(jì)了相應(yīng)的算法和不同規(guī)模的算例進(jìn)行分析,得到以下主要結(jié)論:

1)提出合乘模式下乘客和司機(jī)穩(wěn)定匹配模型。通過計(jì)算結(jié)果可得,非合乘模式下,司機(jī)受收益驅(qū)動更偏好于搭載出行距離較長的乘客。在供給小于需求時(shí),出行距離相對較短的乘客處于劣勢地位,出行需求難以被滿足。合乘模式下,隨著載客能力的提升,乘客的匹配率增加,但由于合乘出行時(shí)繞行不可避免,在時(shí)間窗的約束下,部分乘客合乘出行受限。在有限運(yùn)力下,合乘模式可以增加乘客的匹配幾率,減少乘客總出行里程,降低碳排放。

2)時(shí)間窗和參與人數(shù)量對合乘模式下的匹配率尤為重要。隨著乘客時(shí)間窗的松弛,形成了更多的合乘出行方案,乘客匹配率平均提高18%,合乘比例平均提高21%。同時(shí),高需求放大了乘客匹配率和合乘比例的提升幅度,與低需求相比,高需求下的提升比例是低需求的2倍之多。在打車需求旺盛時(shí)段,是可以通過合乘緩解打車難題,而且高的需求也為合乘提供了有利條件,乘客可以通過釋放一定時(shí)間窗要求以提高匹配的概率,降低等待時(shí)間。