祁 航， 周和平， 蘇貞旅

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

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

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

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

1 定制性靈活線路接駁巴士路徑優(yōu)化模型

先建立傳統(tǒng)動態(tài)最短路徑模型，用于計算2站點(diǎn)間的時間成本。該模型不再詳述[8]。對預(yù)約需求和實(shí)時需求建立的2個模型[9]為:模型一是預(yù)排班模型，針對系統(tǒng)中未服務(wù)的預(yù)約需求;模型二是實(shí)時路徑優(yōu)化模型，針對交通路網(wǎng)上的實(shí)時需求。

1.1 相關(guān)變量與參數(shù)

1) 點(diǎn)集

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

2) 決策變量

(1)

(2)

1.2 預(yù)約需求預(yù)排班模型

該階段能夠為即將出發(fā)車輛在發(fā)車前提供初始接駁路徑，系統(tǒng)中有多輛車進(jìn)行服務(wù)，且要滿足預(yù)約需求。通過整體最優(yōu)，得到了當(dāng)前車輛的初始接駁路徑。

1) 目標(biāo)函數(shù)

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

(3)

目標(biāo)函數(shù)共包含3個部分：① 考慮車輛運(yùn)營成本最小；② 考慮乘客的在車時間最??；③ 考慮在站乘客等待時間成本最小。

車輛運(yùn)營的成本為：

(4)

乘客在車時間的成本為：

(5)

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

(6)

2) 約束條件

① 接駁服務(wù)供給約束。這里的需求包含系統(tǒng)中當(dāng)前提前預(yù)約的未被安排服務(wù)的預(yù)約需求，該需求必須滿足。

(7)

② 站點(diǎn)約束。一趟車輛運(yùn)營從起點(diǎn)出發(fā)，到終點(diǎn)結(jié)束，車輛到達(dá)中間站點(diǎn)提供接駁服務(wù)后又離開中間站點(diǎn)，滿足節(jié)點(diǎn)進(jìn)、出守恒。

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

(8)

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

(9)

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

(10)

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

?k∈K-K′(τ)。

(11)

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

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

?k∈K-K′(τ)。

(12)

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

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

?k∈K-K′(τ)。

(13)

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

1.3 實(shí)時需求路徑優(yōu)化模型

實(shí)時需求路徑優(yōu)化模型是動態(tài)實(shí)時需求插入模型。在整個交通路網(wǎng)的運(yùn)行過程中，系統(tǒng)會得到實(shí)時的接駁需求。對于這種需求，需要判斷是否能夠被滿足。在接駁途中的車輛需從當(dāng)前站點(diǎn)出發(fā)，而新派的車輛從車場出發(fā)。對這些車輛上剩余未被服務(wù)的需求和實(shí)時需求進(jìn)行路徑優(yōu)化，得到的結(jié)果就是最優(yōu)的接駁方案。

1) 目標(biāo)函數(shù)

在τ時刻，實(shí)時訂單產(chǎn)生了。此時需要考慮重新安排路網(wǎng)中的接駁車輛，在滿足約束條件的情況下，使得目標(biāo)函數(shù)最優(yōu)。

C3)+C4。

(14)

(15)

式中：σn為動態(tài)請求不被響應(yīng)的懲罰值。

2) 約束條件

實(shí)時需求路徑優(yōu)化模型是從路網(wǎng)中的車輛考慮其未服務(wù)的需求集合，且τ時刻的關(guān)鍵點(diǎn)即虛擬車場不止一個，因此，此時的模型為多車場對單目的地。

① 接駁服務(wù)供給約束。為了使得接駁目標(biāo)函數(shù)最優(yōu)和保證在車乘客能夠按時到達(dá)終點(diǎn)，對于動態(tài)實(shí)時需求，可以選擇不響應(yīng)；而對于已安排接駁而未被服務(wù)的乘客，必須滿足。

(16)

(17)

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

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

(18)

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

(19)

④ 終點(diǎn)時間窗約束。若響應(yīng)動態(tài)需求，車輛運(yùn)行時間會受到影響，從而影響到乘客，因此，要滿足車上所有乘客的終點(diǎn)時間窗約束。

Tmk, ?k∈K′(τ)。

(20)

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

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

(21)

2 算法設(shè)計

對預(yù)約需求預(yù)排班模型進(jìn)行求解時，由于訂單是確定的，因此屬于靜態(tài)車輛路徑問題。而對于實(shí)時需求路徑優(yōu)化模型，引入時間軸和關(guān)鍵點(diǎn)的概念，將求解動態(tài)車輛路徑問題轉(zhuǎn)化為求解一系列基于時間軸的靜態(tài)子問題?？紤]到車輛路徑是多目標(biāo)組合的優(yōu)化，涉及參數(shù)眾多，約束條件繁雜，因此采用改進(jìn)的蟻群算法求解[10]。為了改善蟻群算法的收斂情況，采用2-opt算法，將蟻群算法每次迭代得到的最優(yōu)解路徑進(jìn)行優(yōu)化。

2.1 路徑選擇

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

2.2 信息素更新策略

1) 局部更新

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

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

Δωpq(τ,τ+1)。

(22)

(23)

(24)

2) 全局更新

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

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

(25)

(26)

(27)

式中：ρ為信息素?fù)]發(fā)系數(shù)；C為車輛攜帶的初始信息素量；Lk為螞蟻k搜索所行走的路徑長度，該路徑記為Tk；Lopt為搜索完成后得出的最優(yōu)路徑，該路徑記為Topt；σ為可調(diào)參數(shù)。

2.3 算法步驟

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

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

3) 按照路徑選擇中采用的規(guī)則得到車輛要進(jìn)行服務(wù)的訂單站點(diǎn)，并在禁忌表Tabu中增加這個站點(diǎn)。

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

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

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

7) 利用2-opt算法，對各代的最優(yōu)解進(jìn)行優(yōu)化。

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

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

3 算例分析

3.1 模型參數(shù)輸入

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

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

3.2 算例求解

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

圖2 發(fā)車前預(yù)排班接駁路徑Fig.2 Pre-arrangement schedules

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

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

車輛編號發(fā)車時刻接駁路徑滿載率/%接駁總時間/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 結(jié)果分析

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

4 結(jié)論

1) 針對預(yù)約訂單和實(shí)時訂單，分別建立了優(yōu)化模型。對于系統(tǒng)中的預(yù)約訂單，模型一能夠求解出初始路徑。當(dāng)實(shí)時訂單產(chǎn)生時，模型二能夠通過最小化目標(biāo)函數(shù)判斷是否響應(yīng)該需求。若響應(yīng)，則將該訂單加入系統(tǒng)進(jìn)行路徑再優(yōu)化。2種模型的結(jié)合能夠在保證接駁服務(wù)水平的基礎(chǔ)上滿足接駁需求。

2) 針對所提出模型的特點(diǎn)，設(shè)計改進(jìn)的蟻群算法并對其進(jìn)行求解。該算法將蟻群算法與2-opt算法結(jié)合起來，有效地解決求解時間長的難題，以便該模型能夠適用于實(shí)際運(yùn)營環(huán)境中。

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