高鐵站定制性靈活線路接駁巴士路徑優化

祁 航， 周和平， 蘇貞旅

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

客運方式之間的接駁已成為熱點問題，接駁出行正借助于分享經濟模式得到如火如荼的發展，網約專車、順風車、拼車及定制公交等極大地促進了接駁客運的繁榮。針對新時期接駁運輸“高效、公平、低碳、優質”的新要求，定制性靈活線路接駁巴士能有效地實現高鐵接駁運輸。如：Lin[1]等人研究了利用多目標規劃方法的接駁公交路線設計的優化。Tong[2]等人建立聯合優化模型，解決了靈活定制公交服務的車輛容量利用率和時間窗等問題。Qiu[3]等人考慮車輛運營成本和運輸客戶成本，以鹽城湖為例，對靈活路線取代固定路線的可行性進行了探索。Liu[4]等人通過中國30個正在運行或正在建設的定制公交系統，分析了定制公交這種新概念的演變。

定制化靈活線路接駁巴士路徑優化屬于單目的地時變交通信息下開放式帶時間窗的動態車輛路徑優化問題[5]。Barkaoui[6-7]等人針對動態車輛路徑問題，提出了一種新的算法，旨在明確提高客戶滿意度。

在國外，定制公交服務系統模式和線網設計的研究成果較多,但在中國尚處于對其影響因素進行探討的層面，對于定制性靈活線路接駁巴士路徑優化的研究也較少見。作者擬基于動態路網和動態需求，建立高鐵站定制性靈活線路接駁巴士路徑優化模型，以提高接駁的運輸組織效率。

1 定制性靈活線路接駁巴士路徑優化模型

先建立傳統動態最短路徑模型，用于計算2站點間的時間成本。該模型不再詳述[8]。對預約需求和實時需求建立的2個模型[9]為:模型一是預排班模型，針對系統中未服務的預約需求;模型二是實時路徑優化模型，針對交通路網上的實時需求。

1.1 相關變量與參數

1) 點集

定義一個無向網絡圖，G=(V,A)，點集V={s,1,2,…，n,t}，其中：s為起點；t為終點；其他點為乘客的上車點。由于需求是不斷變化的，點集會不斷擴大。點集Vα(τ)∈V為τ時刻未安排服務預約需求上車站點的集合(即車輛發車預排班得到的接駁站點)，是接駁車輛必經站點集合；點集Vβ(τ)∈V為τ時刻已安排服務預約需求上車站點的集合；點集Vδ(τ)∈V為τ時刻已安排服務而未被服務的預約需求上車站點集合；點集Vλ(τ)∈V為τ時刻實時需求上車站點的集合，車輛可選擇是否響應該需求；點集Vc(τ)∈V為τ時刻關鍵點集合；點集Vu(τ)∈V為τ時刻剩余未被服務需求上車站點集合。

2) 決策變量

(1)

(2)

1.2 預約需求預排班模型

該階段能夠為即將出發車輛在發車前提供初始接駁路徑，系統中有多輛車進行服務，且要滿足預約需求。通過整體最優，得到了當前車輛的初始接駁路徑。

1) 目標函數

系統在即將出發車輛發車前的一定時刻為τ時刻(本研究所涉及的時刻與通常的時刻不同，它表示某個時間切片，如：時間范圍8∶00-10∶00，按1 h進行時間切片，則對應2個時刻。系統中未出發的車輛集合為K-K′(τ)(其中：K為系統所有車輛的編號集合，K={1,2,…，k}；K′(τ)為τ時刻發出車輛集合)。考慮此時如何安排接駁車輛在滿足約束條件的情況下使得目標函數最優，從而得到當前τ時刻即將出發車輛的初始接駁路徑。令k=min (K-K′(τ))，Tk為車輛k的處罰時刻，則有：

(3)

目標函數共包含3個部分：① 考慮車輛運營成本最小；② 考慮乘客的在車時間最小；③ 考慮在站乘客等待時間成本最小。

車輛運營的成本為：

(4)

乘客在車時間的成本為：

(5)

在站乘客等待時間的成本為：

(6)

2) 約束條件

① 接駁服務供給約束。這里的需求包含系統中當前提前預約的未被安排服務的預約需求，該需求必須滿足。

(7)

② 站點約束。一趟車輛運營從起點出發，到終點結束，車輛到達中間站點提供接駁服務后又離開中間站點，滿足節點進、出守恒。

?p∈Vα(τ)，k∈K-K′(τ)。

(8)

?q∈Vα(τ),k∈K-K′(τ)。

(9)

?q∈Vα(τ),k∈K-K′(τ)。

(10)

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

?k∈K-K′(τ)。

(11)

式中：C為車輛最大載客量。

④ 終點時間窗約束。通過時間窗的約束限制接駁公交到達高鐵站的時間，要滿足接駁乘客可接受到達高鐵站的最晚時間。

?k∈K-K′(τ)。

(12)

式中：Tmk為車輛k到達高鐵站的可接受最晚時間。

⑤ 車輛路徑有效性約束。通過控制接駁巴士的行駛時間來體現定制化接駁巴士的服務水平。通過該約束條件限制乘客乘坐接駁巴士到達高鐵站的行駛時間不超過其直達行駛時間的(1+θ)倍(其中：θ為最大繞行率)。

?k∈K-K′(τ)。

(13)

式中：Ts為乘客直達行駛的最短時間。

1.3 實時需求路徑優化模型

實時需求路徑優化模型是動態實時需求插入模型。在整個交通路網的運行過程中，系統會得到實時的接駁需求。對于這種需求，需要判斷是否能夠被滿足。在接駁途中的車輛需從當前站點出發，而新派的車輛從車場出發。對這些車輛上剩余未被服務的需求和實時需求進行路徑優化，得到的結果就是最優的接駁方案。

1) 目標函數

在τ時刻，實時訂單產生了。此時需要考慮重新安排路網中的接駁車輛，在滿足約束條件的情況下，使得目標函數最優。

C3)+C4。

(14)

(15)

式中：σn為動態請求不被響應的懲罰值。

2) 約束條件

實時需求路徑優化模型是從路網中的車輛考慮其未服務的需求集合，且τ時刻的關鍵點即虛擬車場不止一個，因此，此時的模型為多車場對單目的地。

① 接駁服務供給約束。為了使得接駁目標函數最優和保證在車乘客能夠按時到達終點，對于動態實時需求，可以選擇不響應；而對于已安排接駁而未被服務的乘客，必須滿足。

(16)

(17)

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

?q∈Vδ(τ),k∈K′(τ)。

(18)

③ 車輛容量約束。優先滿足預約需求。當車輛在路上行駛時，有些訂單的乘客已經在車上了，因此，剩余的需求只能由剩余容量滿足，剩余容量Ck(τ)可以通過第一個模型得到。

(19)

④ 終點時間窗約束。若響應動態需求，車輛運行時間會受到影響，從而影響到乘客，因此，要滿足車上所有乘客的終點時間窗約束。

Tmk, ?k∈K′(τ)。

(20)

⑤ 車輛路徑有效性約束。限制乘客乘坐接駁巴士到達高鐵站的行駛時間不超過其直達行駛時間的(1+θ)倍。

(1+θ)Ts， ?k∈K′(τ)。

(21)

2 算法設計

對預約需求預排班模型進行求解時，由于訂單是確定的，因此屬于靜態車輛路徑問題。而對于實時需求路徑優化模型，引入時間軸和關鍵點的概念，將求解動態車輛路徑問題轉化為求解一系列基于時間軸的靜態子問題。考慮到車輛路徑是多目標組合的優化，涉及參數眾多，約束條件繁雜，因此采用改進的蟻群算法求解[10]。為了改善蟻群算法的收斂情況，采用2-opt算法，將蟻群算法每次迭代得到的最優解路徑進行優化。

2.1 路徑選擇

在求解過程中，每只螞蟻代表1輛車，其經過的路徑為該車可行的接駁方案。構造訂單選擇信息素矩陣ω，并且初始化ω=ones(n,n)(其中：n為訂單所在站點、車場及目的地的總數)。構造啟發信息矩陣η為啟發式期望(可見度)，矩陣η中的元素ηpq=1/Tpq，表示p站點到q站點之間的行駛時間倒數。將τ時刻滿足約束條件的訂單放入可選訂單集allowk中，并選擇訂單。在選擇路徑時，按照特定的轉移概率選擇要服務的下一個站點。

2.2 信息素更新策略

1) 局部更新

當每只螞蟻結束一次路徑搜索、需要更新信息素矩陣時，采用自適應局部更新規則。在迭代的過程中，根據狀態的變化，不斷地調整初始信息素量Q。設經過p站點的車輛數為R，經過(p,q)的車輛數為r，并設Q(τ)=Q·(1-r/R)，當R=0時，Q(τ)=Q，則局部更新計算式為：

ωpq(τ+1)=(1-ρ)·ωpq(τ)+

Δωpq(τ,τ+1)。

(22)

(23)

(24)

2) 全局更新

在一次迭代結束、每輛車對所有訂單完成一次接駁后，選取最優路徑進行信息素的全局更新，更新計算式為：

ωpq(τ+1)=(1-ρ)·ωpq(τ)+Δωpq(τ,

(25)

(26)

(27)

式中：ρ為信息素揮發系數；C為車輛攜帶的初始信息素量；Lk為螞蟻k搜索所行走的路徑長度，該路徑記為Tk；Lopt為搜索完成后得出的最優路徑，該路徑記為Topt；σ為可調參數。

2.3 算法步驟

1) 初始化。包括啟發因子和信息素揮發系數等參數初始化，設置迭代次數N=1和最大迭代次數Nm，初始化信息素矩陣ω=ones(n,n)，將m只螞蟻放到車場s，建立禁忌表Tabu。

2) 根據模型中提到的約束條件，包括時間窗約束等來搜索螞蟻能夠服務的下一個訂單所在q站點，并把符合要求的訂單添加到allowk。

3) 按照路徑選擇中采用的規則得到車輛要進行服務的訂單站點，并在禁忌表Tabu中增加這個站點。

4) 將未被服務的訂單集更新，同時更新可選訂單集allowk。

5) 若allowk不為空，返回3)；否則，繼續。

6) 記錄每只螞蟻所獲得的路徑、總成本及各代的最優解。

7) 利用2-opt算法，對各代的最優解進行優化。

8) 將信息素矩陣更新，迭代次數加1，N←N+1。

9) 若N≤Nm，返回2)，繼續迭代；否則，輸出結果，算法終止。

3 算例分析

3.1 模型參數輸入

設有一個高鐵站定制性靈活線路接駁系統，接駁巴士車場s運營時間為8∶00-22∶00。為了便于計算，將時間進行轉換。令8∶00為時刻τ=0，每小時為1，則22∶00為τ=14，車場內有最大載客量為10人的接駁車輛若干。某天，接駁系統中已有預約訂單20個，后續預約訂單3個，實時訂單2個。各訂單均有接駁時間窗和最晚到達時間限制。各訂單分布位置信息如圖1所示(圖中數字代表訂單所在站點編號，其中，實時預約訂單所在站點為24和25)。在圖1中，接駁起點坐標為(0,0)，接駁終點坐標為(40,0)。假設各參數的取值：單位時間在車等候成本σ0取4元/h；單位距離收益B取1元/km；單位時間在站候車成本σw取6元/h；車輛最大載客量C取10人；車輛行駛單位時間成本σv取100元/h；動態請求不被響應的懲罰值σn取20元/人；最大繞行率θ為0.5。蟻群螞蟻數量m為50；初始信息素量Q為500；信息素衰減系數ρ為0.75；可調參數σ為0.7；最大迭代次數為100。

圖1 訂單位置分布Fig.1 Distribution of order locations

3.2 算例求解

根據所設計的模型和改進蟻群算法，結合已知約束條件，輸入原始數據，運用MATLAB編寫程序。根據初始預約和后續預約訂單，通過計算，得到每輛車發車前的預排班接駁路徑，如圖2所示。

圖2 發車前預排班接駁路徑Fig.2 Pre-arrangement schedules

針對系統中出現的實時訂單，通過計算，判斷訂單是否使原有車輛目標函數最優。若是，則予以響應；否則，不予響應。坐標為(18,2)的第24個訂單被安排至第2輛車時會在滿足約束條件的情況下使得目標函數最優，因此，響應該訂單；而坐標為(33,3)的第25個訂單則不予響應。最終實時路徑優化接駁路徑如圖3所示，最終接駁路徑數據見表1。

圖3 車輛最終接駁路徑Fig.3 Final vehicle access routes

車輛編號發車時刻接駁路徑滿載率/%接駁總時間/h繞行率/%10.23s-2-8-13-18-20-t901.42106.520.43s-3-5-24-12-15-23-16-t1001.5611730.79s-21-4-7-10-11-17-t901.62121.541.59s-1-6-9-22-14-19-t901.80135

3.3 結果分析

在系統出現的25個訂單中，除了第25個實時需求訂單不予響應外，其他均滿足目標最優，給予響應，并給出優化接駁路徑。從表1中可以看出，接駁車輛的滿載率、行駛時間及繞行情況等結果均較好。根據車輛到站時間和乘客時間窗的對比分析，接駁車輛滿足了大部分訂單的接駁時間窗要求，體現了接駁巴士的靈活性和便捷性。

4 結論

1) 針對預約訂單和實時訂單，分別建立了優化模型。對于系統中的預約訂單，模型一能夠求解出初始路徑。當實時訂單產生時，模型二能夠通過最小化目標函數判斷是否響應該需求。若響應，則將該訂單加入系統進行路徑再優化。2種模型的結合能夠在保證接駁服務水平的基礎上滿足接駁需求。

2) 針對所提出模型的特點，設計改進的蟻群算法并對其進行求解。該算法將蟻群算法與2-opt算法結合起來，有效地解決求解時間長的難題，以便該模型能夠適用于實際運營環境中。

3) 通過本研究所提出的模型，采用虛擬交通網絡進行算例求解，驗證了該模型和算法的有效性。