乘客到達時間不確定的機場動態(tài)拼車策略與算法研究

晏鵬宇, 張逸冰, 殷允強

(1.電子科技大學(xué) 長三角研究院(湖州),浙江 湖州 313001; 2.電子科技大學(xué) 管理與經(jīng)濟學(xué)院,四川 成都 611731)

0 引言

在智慧交通和共享經(jīng)濟的迅猛發(fā)展下，在線拼車模式(Online Ride-sharing)在我國和歐美國家逐漸流行。在該模式下，乘客通過智能手機將出行需求實時發(fā)送至在線拼車平臺。平臺收到訂單后，將多個具有相似出行路線和出發(fā)時間的乘客匹配在一起，指派同一輛網(wǎng)約車接送乘客。相對于公交地鐵等公共交通方式，該模式為乘客提供更加舒適和個性化的出行服務(wù)；而相對于傳統(tǒng)出租車和網(wǎng)約專車，該模式可提高車輛利用率，降低乘客出行成本，同時對緩解城市交通擁堵和減少環(huán)境污染等方面具有積極作用[1]。

機場作為城市重要交通樞紐，具有客流量大，位置相對偏遠和往返機場交通成本高等特點，并且機場乘客具有大致相似的出行路線。這些特點和因素更能促成乘客的拼車匹配，為在線拼車模式提供了良好的應(yīng)用場景。目前，已經(jīng)有部分互聯(lián)網(wǎng)出行平臺和航空公司推出了機場前往市區(qū)的拼車服務(wù)，如四川航空公司在成都等多個城市推出的“鐵航專線”服務(wù)。由于乘客到達機場拼車服務(wù)點的時間具有不確定性，機場在線拼車運作優(yōu)化屬于復(fù)雜的隨機動態(tài)優(yōu)化問題。在實際運營中，由于缺乏科學(xué)的乘客匹配策略和網(wǎng)約車路徑規(guī)劃方法，導(dǎo)致乘客在拼車服務(wù)點等待時間過長和網(wǎng)約車繞路行駛成本高等突出問題。由此，本文針對機場在線拼車模式，提出動態(tài)環(huán)境下機場拼車匹配策略和車輛路徑規(guī)劃算法，以提高在線拼車平臺的服務(wù)水平并降低運營成本。

目前針對在線拼車模式，研究者分別提出了考慮接送乘客的時間窗、車輛容量以及繞路距離等約束的匹配策略與路徑規(guī)劃算法[2,3]。這些研究針對城市內(nèi)拼車場景，乘客匹配策略主要根據(jù)第一位乘客的路線，沿途匹配其他乘客，并且要求乘客必須提前到達拼車點等候。針對機場在線拼車，部分文獻將機場拼車點視作多車輛路徑規(guī)劃(MVRP)問題中的固定車場(depot)，乘客目的地為交通網(wǎng)絡(luò)中需要訪問的服務(wù)點，而訂單中乘客數(shù)量則對應(yīng)于服務(wù)點需要配送貨物數(shù)量[4]，但未考慮乘客到達的隨機性。目前有關(guān)動態(tài)MVRP的研究主要關(guān)注車輛隨機行駛時間[5]，服務(wù)點隨機需求量[6]，顧客訂單隨機到達[7]等以及多種隨機因素的組合[8]。然而，通過對實際機場拼車平臺運營數(shù)據(jù)分析發(fā)現(xiàn)，乘客到達拼車點的時間具有不確定性。這類隨機因素可視為MVRP問題中運送貨物(乘客)在車場的釋放時間(releasing time)的不確定性，目前尚未引起足夠重視[9]。此外，在優(yōu)化目標上，除了需要優(yōu)化車輛行駛成本外，還需要盡量減少乘客在機場拼車點的等待時間。

針對動態(tài)MVRP問題，大部分文獻提出了基于隨機優(yōu)化[10,11]和智能啟發(fā)式[12,13]的求解算法。差分進化(Differential Evolution，DE)除了具有遺傳算法諸多優(yōu)點外，在連續(xù)空間優(yōu)化中具有更強的魯棒性[14]。然而，DE算法基于實數(shù)對進化個體進行編碼和解碼，主要用于求解連續(xù)優(yōu)化問題。文獻[15]直接采用實數(shù)編碼方式，根據(jù)進化個體基因中的整數(shù)部分指派訂單到不同的車輛，并根據(jù)小數(shù)部分的大小排序安排具體的配送順序。然而基于實數(shù)編碼的算法搜索范圍過大，在求解過程中可能存在大量不可行解。文獻[16]采用序數(shù)編碼方法構(gòu)造進化個體基因，運用基于整數(shù)序規(guī)范(Integer Order Criterion, IOR)的輔助算子將差分變異操作后的實數(shù)轉(zhuǎn)化為整數(shù)，使之能繼續(xù)進行交叉和選擇操作。在上述DE算法的個體解碼方法中，根據(jù)車輛裝載容量約束分配車輛，這種方法能夠有效提高車輛利用率，適用于貨物配送問題。而在本文所研究的機場拼車問題中，需要同時權(quán)衡車輛利用率和乘客等待時間。

基于文獻回顧和實際問題背景，本文首先提出前瞻式乘客動態(tài)匹配策略，建立聯(lián)合未來和已到達乘客訂單信息的兩階段隨機規(guī)劃模型。為了高效求解模型，提出結(jié)合航班實時信息的乘客到達時間貝葉斯估計。在網(wǎng)約車路徑規(guī)劃中，開發(fā)了基于序數(shù)編碼的DE算法，設(shè)計出基于訂單相似度的進化個體解碼規(guī)則。最后，利用真實訂單數(shù)據(jù)建立仿真實驗平臺，驗證了匹配策略在降低乘客等待時間和網(wǎng)約車行駛成本方面，均優(yōu)于實際采用的兩種匹配策略，相比文獻[15,16]，本文提出的改進DE算法可明顯提高解的質(zhì)量。

1 問題描述

本文研究的機場在線拼車平臺的運作流程，如圖1所示。

機場在線拼車平臺每日有限的運營周期內(nèi)需要在時刻t，t∈{1,,2,…,T}，根據(jù)訂單集合Gt決策當(dāng)前需要匹配出發(fā)的訂單集合Xt,Xt?Gt，并規(guī)劃網(wǎng)約車運送Xt中乘客的拼車路線，以最小化乘客在拼車點的等待時間和網(wǎng)約車的行駛的總成本。該問題屬于多階段隨機規(guī)劃問題，決策Xt不僅決定當(dāng)前時刻t的運作成本F(Xt)，而且還影響后續(xù)運作周期的成本。由此，本文將首先提出考慮未來到達乘客的前瞻式動態(tài)匹配策略，建立兩階段隨機規(guī)劃模型。

3 前瞻式動態(tài)匹配策略與模型

3.1 匹配策略設(shè)計

ModelPS

(1)

s.t.Xt?Gt

(2)

3.2 基于乘客期望到達時間的情景空間壓縮

(3)

3.3 近似最優(yōu)確定性模型

利用3.2節(jié)貝葉斯估計的乘客期望到達時間，可將隨機規(guī)劃模型PS轉(zhuǎn)為確定性乘客匹配與車輛路徑規(guī)劃模型PD,其中0-1整數(shù)決策變量xi,j,k=1表示訂單i和j匹配到車輛k，并且車輛完成訂單i的運送后立即開始訂單j的運送；實數(shù)決策變量tk表示車輛k的發(fā)車時間。

ModelPD

(4)

(12)

4 改進差分進化(DE)算法

模型PD為經(jīng)典MVRP問題拓展，具有NP-難特性。本節(jié)首先提出基于乘客目的地和到達拼車點時間兩個維度的訂單相似度計算方法，并基于此設(shè)計改進DE算法中進化個體解碼方式和初始種群產(chǎn)生方法，從而提高DE算法搜索到近似最優(yōu)解的效率與質(zhì)量。

4.1 訂單相似度計算

(13)

(14)

由此，考慮上述時空維度的訂單相似度Ii,j為:

(15)

上式中ω為時間相似度相對權(quán)重，當(dāng)兩個訂單之間的到達時間間隔大于Δtw時，有Ii,j=0。

4.2 進化個體編碼與解碼

Algorithm1:基于訂單相似度個體基因序列解碼初始化:車輛k=1并且設(shè)置車輛k的當(dāng)前容量vk=m[1],發(fā)車時間tk=tForn=2,…,N-1do Ifvk+m[n]?gkThen 在區(qū)間(0,1]內(nèi)隨機生成實數(shù)γ Ifγ>1-I[n-1],[n]Thenvk=vk+m[n] Iftk

對于基因序列Z，相鄰基因?qū)?yīng)的訂單相似度越大，則被拆分的概率就越低，對應(yīng)的解碼方案質(zhì)量也就越好。為保證解碼質(zhì)量，避免剔除優(yōu)良子代，對每個個體的基因序列可重復(fù)進行多次解碼并比較對應(yīng)解碼方案的適應(yīng)度，選擇適應(yīng)度高的方案作為個體最終解碼方案。通過這種鄰域搜索方法，可在滿足車輛裝載量約束的條件下有效提高個體解碼方案質(zhì)量，并能有效增強種群多樣性。

4.3 初始種群產(chǎn)生

在初始種群產(chǎn)生中，利用訂單之間的相似度，按照下面Algorithm 2步驟產(chǎn)生初始個體。該方法能夠保證相似度較高的基因個體有更大的概率匹配到一起，從而有效提高初始種群質(zhì)量。

Algorithm2:基于訂單相似度的初始個體產(chǎn)生在N個訂單中隨機選出訂單i作為個體基因序列的第1位,即基因[1]=訂單i,并將訂單i添加至已選擇集合S;Fork=2,…,|Gt∪Gt′| Forn=1,…,|Gt∪Gt′/S| φn=∑nm=1I[k-1],Gt∪Gt′/S[m],其中Gt∪Gt′/S[m]表示剩余訂單中的第n個訂單,φ0=0;Endfor生成隨機數(shù)γ∈(0,φ|Gt∪Gt′/S|]并判斷其所處位置,若φn-1?γ?φn,則將剩余訂單集合中對應(yīng)位置的訂單Gt∪Gt′/S[n]放入基因序列第k位,并將該訂單添加至已選擇集合S;Endfor

4.4 變異和交叉

本文采用文獻[16]的基于整數(shù)序規(guī)范(IOR)的變異和交叉算子進行種群個體進化迭代。其中變異操作是在當(dāng)前種群中隨機選擇的個體a和b的基因進行差分運算，并按照縮放因子ρ調(diào)整差分值，再與目標個體c相結(jié)合而生成變異個體v。由于該方法產(chǎn)生的變異個體基因為實數(shù)，可利用IOR算子對變異個體v基因進行排序，根據(jù)基因順序生成整數(shù)基因的變異個體。

交叉操作則是目標個體c以一定的概率與變異個體v交叉部分基因片段，從而生成新的試驗個體u。為確保個體持續(xù)進化，試驗個體u中的基因至少有一位是來自于變異個體v，剩余基因片段則根據(jù)交叉概率因子來確定是否進行交叉。交叉率越大，則變異個體所占試驗個體的比例越大，反之則目標個體所占比例越大。為了提高算法效率，采用自適應(yīng)交叉率δ，在種群進化前期交叉率較高，提高算法全局搜索能力；而在進化后期交叉率降低，從而提高算法局部搜索能力，加速收斂。

4.5 適應(yīng)度評價及選擇

在進化個體適應(yīng)度評價中，利用(16)式計算個體適應(yīng)度。

π(u)=1/(C(u)+D(u))

(16)

其中，C(u)可利用目標函數(shù)(4)計算出個體u的總成本，D為等待時間約束破壞的懲罰成本，計算為:

(17)

該式表示一旦某輛車中任意兩個乘客的到達時間差大于Δtw，則設(shè)置D(u)為足夠大的懲罰值，其中?為極大懲罰因子。

在選擇操作中，比較試驗個體u與目標個體c的適應(yīng)度，若π(u)>π(c)，則選擇試驗個體u進入下一代，否則保留目標個體c。

5 仿真實驗

為驗證前瞻式匹配策略和改進DE算法的有效性和性能，本文提取了某在線拼車平臺在成都雙流國際機場8天內(nèi)664個機場拼車訂單，具體訂單數(shù)據(jù)描述請見文獻[17]?；谶@些訂單數(shù)據(jù)，利用Python語言搭建仿真實驗平臺，對本文提出的前瞻式匹配策略與實際中采用的兩種匹配策略進行對比分析，同時對比測試改進DE算法與文獻[15]和[16]中針對不同編碼解碼方式DE算法的性能。

5.1 匹配策略對比測試分析

實驗利用真實訂單數(shù)據(jù)，檢驗前瞻式匹配策略(PM)和實際中采用的固定匹配策略(FS)和實時觸發(fā)策略(RT)的效果。后面兩種基于規(guī)則的匹配策略的介紹，請參考文獻[17]。實驗采用PM、FS和RT三種策略，分別確定每個決策周期內(nèi)待匹配的訂單集合，并利用CPLEX軟件求解模型PD獲得最優(yōu)的訂單匹配和車輛路徑規(guī)劃方案。本文選取問題目標函數(shù)(4)，乘客平均等待時間和車輛行駛路程作為評價指標。

首先，設(shè)置目標函數(shù)(4)中等待時間成本系數(shù)σ=0.1，對應(yīng)的平臺目標函數(shù)總成本如圖3所示。其中，PM策略的總成本最低，其平均成本相對于FS和RT策略分別減少了17.52%和11.96%。其次，如圖4所示，在乘客平均等待時間方面，PM策略具有較明顯優(yōu)勢。乘客平均等待時間保持在大約5分鐘左右，而FS策略和RT策略的等待時間平均為14.4和16.2分鐘。較長的等待時間影響了乘客對拼車服務(wù)的體驗，進而降低了乘客后續(xù)使用拼車服務(wù)的意愿。在車輛行駛路程方面，如圖5所示，F(xiàn)S策略對應(yīng)的車輛總路程最長，PM策略與RT策略的總路程相對接近。但平均看來PM策略的總路程仍然是最低，比FS和RT策略分別減少了10.26%和1.52%。

上述實驗結(jié)果表明，盡管在大幅縮短乘客等待時間情況下，PM策略依然能夠有效降低車輛行駛路程，其原因在于PM策略考慮了即將到達乘客的訂單信息，因此能獲得更優(yōu)的方案。

5.2 改進DE算法性能對比測試

本部分通過將改進DE算法與文獻中提出的實數(shù)編碼DE算法[15]和序數(shù)編碼DE算法[16]進行數(shù)值算例對比測試。為此，按下面方式隨機產(chǎn)生N=4,6,8,…,30不同訂單數(shù)的算例。其中，訂單i和訂單j到達拼車點時間間隔服從Δti,j泊松分布P(λ=5個訂單/30分鐘)；利用正態(tài)函數(shù)N(19.9,4.32)km隨機生成機場到訂單目的地的距離，利用N(7.3,4.52)km隨機產(chǎn)生訂單到參考點的距離，再根據(jù)歐幾里得距離公式計算出訂單i和訂單j目的地之間的距離di,j。同時，設(shè)置訂單i中乘客數(shù)量mi=1,2,3,4的概率分別0.4,0.3,0.2,0.1。上述參數(shù)的設(shè)置來源于文獻[17]對實際訂單數(shù)據(jù)的統(tǒng)計結(jié)果。針對上述每組參數(shù)，隨機產(chǎn)生50個算例，并分別采用CPLEX優(yōu)化軟件，改進DE、實數(shù)編碼DE和序數(shù)編碼DE求解模型PD。由于模型PD為NP-難，設(shè)置CPLEX軟件的計算時間上限為30分鐘。當(dāng)CPLEX在30分鐘內(nèi)無法搜索到最優(yōu)解，則停止運算并輸出當(dāng)前最好下界。本文統(tǒng)一設(shè)置三個DE算法的種群規(guī)模為200，進化代數(shù)為200，差分縮放因子ρ=0.5。

上述算法求解數(shù)值算例的平均計算時間如圖6所示?？梢钥闯觯S著訂單數(shù)量的增加，CPLEX的計算時間呈顯著增長，當(dāng)訂單數(shù)量N≥18時，CPLEX的求解時間超過30分鐘。對于所有算例，三個DE算法的計算時間均在1分鐘內(nèi)。其中，采用實數(shù)和序數(shù)編碼的兩種DE算法求解速度最快，本文的改進DE算法相對較慢。原因是改進DE算法在初始種群產(chǎn)生和個體解碼階段采用了基于訂單相似度的方法，增加了計算時間，但總體上改進DE算法仍可以滿足實際運營過程中對響應(yīng)速度的苛刻要求。

在解的質(zhì)量方面，如表1所示，當(dāng)訂單數(shù)量較小時，三個啟發(fā)式算法均能獲得最優(yōu)解，但隨著訂單數(shù)量的增加，實數(shù)編碼和序數(shù)編碼DE算法搜索到的解質(zhì)量明顯下降。在CPLEX所能求解到最優(yōu)解的訂單范圍內(nèi)(N≤16)，改進DE算法與最優(yōu)解的GAP值最高為0.55%。對于所有算例，改進DE算法平均GAP為14.68%，相對于實數(shù)編碼和序數(shù)編碼DE算法，改進幅度分別為53.62%和52.15%。原因主要是實數(shù)編碼DE算法將整數(shù)范圍優(yōu)化問題的解空間擴大到了連續(xù)的實數(shù)范圍，隨著訂單數(shù)量的增加，解空間呈指數(shù)級增長趨勢，導(dǎo)致算法收斂效果較差；而序數(shù)編碼DE算法的進化個體解碼，車輛往往需要達到載重上限才會分配新的車輛，但本文的機場拼車問題中，把多位乘客指派到同輛網(wǎng)約車會增加乘客的等待時間。

表1 三個DE算法求解質(zhì)量偏差對比

5.3 靈敏度分析

本節(jié)利用5.2節(jié)數(shù)值算例產(chǎn)生方法，進一步分析訂單乘客數(shù)量和最晚等待時間對三種策略匹配效果的影響，并分析PM策略中等待時間成本系數(shù)的影響，為機場拼車服務(wù)的實際運營提供指導(dǎo)與借鑒。

首先，為了測試訂單中不同乘客數(shù)對策略的影響，設(shè)置算例中總乘客數(shù)量M=40,50，…,160，并將M個乘客完全隨機指派給40個訂單，對于給定參數(shù)M產(chǎn)生30個算例。三種策略對應(yīng)的車輛平均行駛路程和乘客平均等待時間如圖7和8所示。

從圖7可以發(fā)現(xiàn)，隨著訂單中乘客數(shù)量增加，拼車匹配的可能性逐漸降低，三種策略對應(yīng)的車輛平均行駛里程也隨之上升。特別是當(dāng)M=160，即每個訂單有4位乘客，由于車輛座位數(shù)限制，乘客無法實現(xiàn)拼車出行，車輛行駛距離最大。從圖8可以發(fā)現(xiàn)，PM策略中乘客平均等待時間隨著M的增加而減小，其余兩種策略沒有明顯變化。特別地，當(dāng)M=160時由于無法拼車匹配，PM和RT策略對應(yīng)的乘客等待時間為0，而FS策略下乘客仍然需要等待較長時間。

此外，本節(jié)分析乘客最長等待時間Δtw=15， 20,…,60分鐘對三種策略匹配效果的影響。對于FS策略，直接設(shè)置ΔT=Δtw。

由圖9和10可以發(fā)現(xiàn)，隨著Δtw增加，PM和RT策略可以在更長時間范圍內(nèi)匹配訂單，因此對應(yīng)的車輛平均行駛路程明顯下降，但乘客平均等待時間上升。對于FS策略，乘客的等待時間略微有所上升，但車輛平均行駛路程無明顯變化趨勢。

此外，乘客等待時間成本是本文研究問題的主要特征，由于FS和RT策略中未考慮乘客等待時間影響，本文僅對PM匹配策略設(shè)置σ=0.01,0.1,0.5,1，隨機生成30組算例進行測試，分析在匹配決策周期內(nèi)乘客等待時間成本系數(shù)σ對PM匹配策略的影響。實驗結(jié)果如圖11和圖12所示。

隨著權(quán)重參數(shù)σ的不斷增大，乘客的平均等待時間呈明顯下降趨勢，但相應(yīng)的訂單平均里程則會顯著上升。因此在實際運營中，需要充分權(quán)衡平臺服務(wù)水平(乘客等待時間)和車輛運營成本(行駛路程)，有效提高平臺運營水平。

綜上，針對機場動態(tài)拼車問題，本文所提出的前瞻式匹配策略和改進DE算法能夠保證在實際運營中平臺對乘客隨機到達的實時響應(yīng)，并且相對于已有的兩種匹配策略和文獻中的DE算法，可獲得更好的乘客匹配和車輛路徑規(guī)劃方案。

6 總結(jié)

在線拼車作為共享出行的重要模式已在實踐中蓬勃發(fā)展，但目前尚缺少相關(guān)運作策略與優(yōu)化方法。本文針對機場在線拼車平臺面臨的顧客等待時間長和網(wǎng)約車行駛成本高的突出問題，提出了前瞻式動態(tài)匹配策略和對應(yīng)的兩階段隨機規(guī)劃模型。為了滿足實際運營中對模型求解時間的要求，提出了基于貝葉斯更新的近似最優(yōu)確定性模型和求解網(wǎng)約車路徑規(guī)劃的改進DE算法。在DE算法中構(gòu)建了考慮時空維度的訂單相似度計算方法，并基于此設(shè)計出進化個體解碼方式以及初始種群的產(chǎn)生方法，從而提高算法的求解質(zhì)量。最后，本文通過對比測試驗證了前瞻式匹配策略和改進DE算法的有效性和計算效率。本文研究成果不僅可以應(yīng)用于機場等城市交通樞紐的在線拼車問題，而且對互聯(lián)網(wǎng)環(huán)境下的快遞、餐飲配送和新零售場景下的訂單動態(tài)分配和配送路線規(guī)劃也有借鑒價值。