時(shí)變路網(wǎng)下機(jī)場接駁車輛-用戶共享路徑優(yōu)化

歐陽瑞祥，周和平，劉靜波，郭權(quán)

(長沙理工大學(xué) 交通運(yùn)輸工程學(xué)院，湖南 長沙 410114)

民航運(yùn)輸是人們出行不可或缺的方式。目前，機(jī)場接駁運(yùn)輸智能化水平較低，而研究機(jī)場接駁車輛-用戶選擇方法有助于構(gòu)建智慧化民航接駁運(yùn)輸系統(tǒng)。國內(nèi)外學(xué)者對需求響應(yīng)式接駁進(jìn)行了深入研究。靳文舟[1]等人通過 K-means 算法，響應(yīng)公交臨時(shí)停靠點(diǎn)規(guī)劃的需求。并基于精英選擇遺傳算法，選擇公交線路規(guī)劃方案。申嬋[2]等人基于可靠性時(shí)空網(wǎng)絡(luò)，建立了定制公交線路優(yōu)化模型，并采用禁忌搜索算法進(jìn)行求解。Zheng[3?4]等人研究了可變線路與可變站點(diǎn)的公交模式選擇，且提出了一種動(dòng)態(tài)離站時(shí)間窗的策略。Sun[5?6]等人考慮了乘客滿意度和軌道站點(diǎn)同步換乘的需求響應(yīng)，建立了接駁公交調(diào)度模型。Li[7]等人研究了集成站點(diǎn)選址的需求響應(yīng)，建立了接駁公交調(diào)度模型。

機(jī)場接駁車輛-用戶選擇過程，實(shí)質(zhì)上是考慮新增用戶需求的動(dòng)態(tài)車輛路徑問題(Dynamic Vehicle Routing Problem，簡稱為DVRP)，國內(nèi)外對DVRP進(jìn)行了許多的研究。Abdallah[8]等人對新增客戶需求，構(gòu)建了帶容量約束的DVRP 模型，按時(shí)間段將動(dòng)態(tài)需求的車輛路徑問題轉(zhuǎn)化成靜態(tài)車輛路徑問題，并采用遺傳算法進(jìn)行求解。Chen[9]等人考慮新增客戶需求對車輛容量和時(shí)間窗的影響，建立了容量和時(shí)間窗約束的DVRP 模型，采用生成初始路徑和按時(shí)間段定期更新路徑的兩階段策略。Ulmer[10]等人將隨機(jī)顧客請求的多周期車輛路徑問題視為馬爾可夫決策，以接受服務(wù)請求數(shù)最大化作為優(yōu)化目標(biāo)，提出了一種基于近似動(dòng)態(tài)規(guī)劃的預(yù)期動(dòng)態(tài)策略。祁航[11]等人基于交通網(wǎng)絡(luò)的動(dòng)態(tài)性及乘客需求的定制性與動(dòng)態(tài)性，建立了高鐵站定制性靈活線路接駁巴士路徑優(yōu)化模型，并采用改進(jìn)的蟻群算法求解。智路平[12]等人先對路段行程時(shí)間進(jìn)行分狀態(tài)的隨機(jī)動(dòng)態(tài)預(yù)測，然后建立以行程時(shí)間可靠性為關(guān)鍵控制變量的三階段單車輛路徑選擇模型。作者在時(shí)變路網(wǎng)下，對新增用戶需求進(jìn)行實(shí)時(shí)響應(yīng)，擬建立共享式機(jī)場接駁車輛-用戶選擇模型，根據(jù)約束規(guī)劃和分枝定界算法，設(shè)計(jì)了算法并進(jìn)行求解。以期實(shí)現(xiàn)機(jī)場接駁運(yùn)輸系統(tǒng)中有限資源的共享，提高接駁效率。

1 問題描述及符號注明

設(shè)預(yù)排班方案Y=(U,H)，接駁車輛在tp時(shí)刻，從車場p出發(fā)，接n個(gè)預(yù)定用戶需求點(diǎn)w，去機(jī)場e。其中：U為接駁車輛路徑集，接駁車輛在預(yù)排班方案Y中接駁路徑u∈U；H為用戶出發(fā)時(shí)刻集，w用戶的出發(fā)時(shí)刻tw∈H。

在預(yù)排班方案Y和時(shí)變路網(wǎng)RN=(V,E,M,C)的基礎(chǔ)上，對已出發(fā)接駁車輛和實(shí)時(shí)新增用戶需求進(jìn)行匹配，判斷接駁車輛能否滿足，并生成接駁車輛-用戶實(shí)時(shí)共享方案，如圖1 所示。其中，新增用戶需求w*是在接駁車輛出發(fā)以后，隨機(jī)出現(xiàn)的；V是道路節(jié)點(diǎn)集，路網(wǎng)中任意節(jié)點(diǎn)i∈V；E是道路路段集，(i,j)∈E；時(shí)間間隔集M={0,1,2,…,m}，任意m表示間隔長度為 Δm的時(shí)間間隔[t,t+Δm](如：將10:20-11:20，按每10 分鐘，間隔離散，t=0 對應(yīng)10:20-10:30)；C為路段時(shí)間阻抗集，路網(wǎng)中任意路段時(shí)間阻抗∈C，表示在m間隔內(nèi)，路段(i,j)的時(shí)間阻抗值；U*是共享路徑集，接駁車輛在實(shí)時(shí)共享方案；中的共享路徑中用戶出發(fā)時(shí)刻集。

從圖1 可以看出，當(dāng)4 節(jié)點(diǎn)隨機(jī)產(chǎn)生實(shí)時(shí)新增用戶需求w*時(shí)，接駁車輛已行駛到(p,1)路段上。在保證原有預(yù)定用戶準(zhǔn)時(shí)到達(dá)機(jī)場e的情況下，需要快速地判斷此接駁車輛能否滿足w*需求，并送其到達(dá)機(jī)場。既找到一條考慮原有用戶航班時(shí)間以及接駁車輛空余資源等約束，且能滿足w*需求的共享路徑u*。

圖1 時(shí)變路網(wǎng)圖Fig. 1 Time-varying network diagram

其中，to為路徑中共享起點(diǎn)的出發(fā)時(shí)刻；為乘客登機(jī)緩沖時(shí)間；為用戶需求點(diǎn)的隨行人數(shù)；Q為車輛容量；Qu為路徑u的總?cè)藬?shù)；為車輛繞行系數(shù)；為用戶需求點(diǎn)w在tw時(shí)刻自行出發(fā)到機(jī)場的最小旅行時(shí)間；Lmax為最大停靠次數(shù)；Tmax為乘客最大候機(jī)時(shí)間閾值；N0為已過節(jié)點(diǎn)集，接駁車輛在新增用戶需求出現(xiàn)前已過的節(jié)點(diǎn)i∈N0；N為未過節(jié)點(diǎn)集，N=V?N0；W：用戶需求點(diǎn)集，為車輛從p出發(fā)的時(shí)刻；為在m間隔內(nèi)路段(i,j)的時(shí)間阻抗；tw為w用戶的出發(fā)時(shí)刻；to為車輛在預(yù)排方案中到達(dá)機(jī)場的時(shí)刻；O為共享路徑的起點(diǎn)；為車輛在共享方案中到達(dá)機(jī)場的時(shí)刻；為實(shí)時(shí)新增用戶需求；tw為用戶的航班時(shí)間。

2 模型建立

為響應(yīng)機(jī)場接駁過程中實(shí)時(shí)出現(xiàn)的新增用戶需求，建立時(shí)變路網(wǎng)下共享式機(jī)場接駁車輛-用戶選擇模型，并使用該模型對機(jī)場接駁車輛路徑進(jìn)行優(yōu)化。

2.1 假設(shè)條件

為方便建立模型和求解，假設(shè)：①每個(gè)預(yù)約用戶的出發(fā)位置和航班時(shí)刻表等信息，可在終端獲得。②所有用戶的登機(jī)緩沖時(shí)間相同。③乘客上車時(shí)間忽略不計(jì)，即接駁車輛到達(dá)w節(jié)點(diǎn)的時(shí)間就是乘客的出發(fā)時(shí)間。④若接駁車輛在t時(shí)刻位于路段(i,j)∈u之間，即ti＜t≤tj，則規(guī)定j節(jié)點(diǎn)為重新規(guī)劃的共享起點(diǎn)O。⑤假設(shè)系統(tǒng)一次只能判斷一個(gè)用戶需求點(diǎn)，是否可以共享，且判斷時(shí)間忽略不計(jì)；⑥所有路段任意間隔內(nèi)的時(shí)變阻抗已獲得，在m間隔內(nèi)，路段阻抗是相同的。

2.2 目標(biāo)函數(shù)與決策變量

為了快速響應(yīng)機(jī)場接駁過程中實(shí)時(shí)出現(xiàn)的新增用戶需求，以接駁車輛總運(yùn)行時(shí)間最小為目標(biāo)函數(shù)，考慮在滿足約束條件的情況下，對機(jī)場接駁車輛路徑進(jìn)行優(yōu)化，生成實(shí)時(shí)共享路徑方案。其目標(biāo)函數(shù)公式為：

2.3 約束條件

1) 流量守恒約束

起終點(diǎn)約束：接駁車輛運(yùn)營從起點(diǎn)出發(fā)，到終點(diǎn)機(jī)場結(jié)束，需滿足節(jié)點(diǎn)進(jìn)、出次數(shù)約束。

其中，i=0 表示變量x的起點(diǎn)；i=e表示變量x,y的終點(diǎn)；i=w表示y的起點(diǎn)。

中間節(jié)點(diǎn)約束：車輛到達(dá)中間節(jié)點(diǎn)，提供接駁服務(wù)后，又離開中間節(jié)點(diǎn)，需滿足節(jié)點(diǎn)進(jìn)出守恒。

必經(jīng)節(jié)點(diǎn)約束：系統(tǒng)中未上車的原有預(yù)定用戶需求必須被滿足。

2) 車輛繞行約束

為使乘客有較好的服務(wù)體驗(yàn)感，乘客接受服務(wù)的時(shí)間，不能超過其自行出發(fā)最小旅行時(shí)間的(1+ε)倍，本研究ε=1.4。w乘客接受服務(wù)的時(shí)間為Tw。

3) 容量限制約束

在提供接駁服務(wù)的過程中，車內(nèi)的乘客數(shù)不能超過車輛的容量。

4) 航班信息約束

空余時(shí)間約束：已出發(fā)車輛還有空余時(shí)間共享給新增用戶。

用戶航班約束：不能讓w的候機(jī)時(shí)間過長，Tmax是已經(jīng)在車上用戶最大候機(jī)時(shí)間的μ倍，本研究中μ=1.5。

5) 最大?？看螖?shù)約束

為保證接駁服務(wù)的質(zhì)量，接駁車輛在途中?？康拇螖?shù)不宜過多，本研究最大停靠次數(shù)Lmax=10。

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

根據(jù)約束規(guī)劃和分枝定界算法設(shè)計(jì)，相應(yīng)求解算法，對新增用戶需求進(jìn)行實(shí)時(shí)共享判斷。通過將分枝定界算法中的分枝策略，運(yùn)用到計(jì)算過程中，從而達(dá)到減少存儲空間和加快求解速度的目的。其算法流程圖如圖2 所示。

圖2 算法流程Fig. 2 Algorithm flow diagram

4 算例分析

設(shè)有13 個(gè)提前預(yù)約用戶，向機(jī)場接駁需求響應(yīng)系統(tǒng)發(fā)送請求，提前預(yù)約用戶需求信息見表1；設(shè)置2 組實(shí)時(shí)預(yù)約用戶組，每組4 個(gè)實(shí)時(shí)預(yù)約用戶，多組實(shí)時(shí)預(yù)約用戶需求信息見表2。機(jī)場接駁車輛采用10座車，從辦理登機(jī)牌到登機(jī)的緩沖時(shí)間最少45 min，即 Δt=45 min。時(shí)變路網(wǎng)中所有路段的阻抗值是由10:20~12:30 以10 min 為間隔，13 個(gè)隨機(jī)離散值組成的。13 個(gè)提前預(yù)約用戶預(yù)排班方案Y見表3，在Y中，只有路徑u2，可對表2 中的實(shí)時(shí)預(yù)約用戶進(jìn)行共享，因此，對u2進(jìn)行重點(diǎn)分析。實(shí)時(shí)預(yù)約用戶為1 組時(shí)，路徑u2的實(shí)時(shí)共享方案圖如圖3 所示。

多組實(shí)時(shí)預(yù)約用戶共享對比見表4，預(yù)約用戶2 組通過機(jī)場接駁需求響應(yīng)系統(tǒng)，拒絕6,10 節(jié)點(diǎn)的預(yù)約請求，得到u2共享路徑為p→2→7→15→18→13→14→G→e。

由表4 可知，通過對1,2 組實(shí)時(shí)預(yù)約用戶共享進(jìn)行比較，車輛的滿載率均從70%增加到100%，機(jī)場接駁系統(tǒng)對用戶請求響應(yīng)率均增加15.3%，候機(jī)時(shí)間利用率分別提高了66.7%和 58.9%。表明：該共享模型可靠，增加了車輛滿載率，減少了運(yùn)營成本，提高了接駁效率和用戶滿意度。該模型和算法能處理機(jī)場接駁需求響應(yīng)系統(tǒng)中實(shí)時(shí)新增用戶需求的動(dòng)態(tài)車輛路徑優(yōu)化，具有良好的適用性。

表1 提前預(yù)約用戶需求信息表Table 1 Demand information of advance booking user

表2 多組實(shí)時(shí)預(yù)約用戶需求信息表Table 2 Demand information of Multi-group real-time booking user

表3 預(yù)排班機(jī)場接駁方案Table 3 Pre-scheduling of airport feeder

圖3 實(shí)時(shí)共享方案Fig. 3 Real-time shared diagram

表4 多組實(shí)時(shí)預(yù)約用戶共享對比表Table 4 Multi-group real-time booking user sharing comparison

5 結(jié)論

根據(jù)機(jī)場接駁響應(yīng)系統(tǒng)，建立了共享式機(jī)場接駁車輛-用戶選擇模型，對實(shí)時(shí)新增用戶需求進(jìn)行響應(yīng)，并設(shè)計(jì)相應(yīng)的算例進(jìn)行分析。得到的結(jié)論為：

1) 在機(jī)場接駁預(yù)排班的基礎(chǔ)上，建立了時(shí)變路網(wǎng)下共享式機(jī)場接駁車輛-用戶選擇模型，及時(shí)快速的響應(yīng)了實(shí)時(shí)新增用戶需求，實(shí)現(xiàn)了有限資源的共享，提高了接駁效率和用戶滿意度。

2) 根據(jù)約束規(guī)劃和分枝定界算法，設(shè)計(jì)了模型求解方法，對車輛路徑進(jìn)行了優(yōu)化，滿足了新增用戶需求的實(shí)時(shí)共享。以期為構(gòu)建智慧化民航接駁運(yùn)輸系統(tǒng)提供參考。