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

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

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

0 引 言

隨著“互聯(lián)網(wǎng)+”和共享經(jīng)濟的蓬勃發(fā)展,網(wǎng)約車行業(yè)應(yīng)運而生并迅速擴張。根據(jù)中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計調(diào)查,2016年末至2018年末,網(wǎng)約車用戶規(guī)模和用戶使用率進入增速迅猛期,截至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)惠的價格、良好的乘車體驗和高效快速的需求響應(yīng)。其中,如何快速匹配供需,及時對需求進行響應(yīng)成為網(wǎng)約車可持續(xù)發(fā)展的關(guān)鍵。

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

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

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

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

1 問題描述

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

表1 乘客和司機的偏好排序

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

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

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

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

2.1 乘客和司機的偏好排序

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

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

(1)

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

(2)

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

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

(3)

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

(4)

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

(5)

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

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

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

(6)

(7)

(8)

(9)

(10)

3 算法設(shè)計

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

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

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

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

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

4 案例分析

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

4.1 小規(guī)模算例

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

表2 匹配對集合

表3 乘客和司機對匹配對偏好排序

圖2 小規(guī)模算例

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

4.2 不同規(guī)模算例

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

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

5 結(jié) 論

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

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

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