時變路網下機場接駁車輛-用戶共享路徑優化

歐陽瑞祥，周和平，劉靜波，郭權

(長沙理工大學 交通運輸工程學院，湖南 長沙 410114)

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

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

1 問題描述及符號注明

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

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

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

圖1 時變路網圖Fig. 1 Time-varying network diagram

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

2 模型建立

為響應機場接駁過程中實時出現的新增用戶需求，建立時變路網下共享式機場接駁車輛-用戶選擇模型，并使用該模型對機場接駁車輛路徑進行優化。

2.1 假設條件

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

2.2 目標函數與決策變量

為了快速響應機場接駁過程中實時出現的新增用戶需求，以接駁車輛總運行時間最小為目標函數，考慮在滿足約束條件的情況下，對機場接駁車輛路徑進行優化，生成實時共享路徑方案。其目標函數公式為：

2.3 約束條件

1) 流量守恒約束

起終點約束：接駁車輛運營從起點出發，到終點機場結束，需滿足節點進、出次數約束。

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

中間節點約束：車輛到達中間節點，提供接駁服務后，又離開中間節點，需滿足節點進出守恒。

必經節點約束：系統中未上車的原有預定用戶需求必須被滿足。

2) 車輛繞行約束

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

3) 容量限制約束

在提供接駁服務的過程中，車內的乘客數不能超過車輛的容量。

4) 航班信息約束

空余時間約束：已出發車輛還有空余時間共享給新增用戶。

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

5) 最大停靠次數約束

為保證接駁服務的質量，接駁車輛在途中停靠的次數不宜過多，本研究最大停靠次數Lmax=10。

3 算法設計

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

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

4 算例分析

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

多組實時預約用戶共享對比見表4，預約用戶2 組通過機場接駁需求響應系統，拒絕6,10 節點的預約請求，得到u2共享路徑為p→2→7→15→18→13→14→G→e。

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

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

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

表3 預排班機場接駁方案Table 3 Pre-scheduling of airport feeder

圖3 實時共享方案Fig. 3 Real-time shared diagram

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

5 結論

根據機場接駁響應系統，建立了共享式機場接駁車輛-用戶選擇模型，對實時新增用戶需求進行響應，并設計相應的算例進行分析。得到的結論為：

1) 在機場接駁預排班的基礎上，建立了時變路網下共享式機場接駁車輛-用戶選擇模型，及時快速的響應了實時新增用戶需求，實現了有限資源的共享，提高了接駁效率和用戶滿意度。

2) 根據約束規劃和分枝定界算法，設計了模型求解方法，對車輛路徑進行了優化，滿足了新增用戶需求的實時共享。以期為構建智慧化民航接駁運輸系統提供參考。