考慮車輛到達時間窗的應急公交調度優化模型

查偉雄，馮 濤，嚴利鑫

(華東交通大學 交通運輸與物流學院，江西 南昌 330013)

0 引 言

近年來，隨著我國城市軌道交通的快速發展，軌道交通在城市交通出行中越來越重要，一旦發生突發事件，將會對整個城市的公共交通系統產生嚴重的影響。因此高效的應急公交調度方案成了學者們研究的熱點。

國內外許多學者對軌道交通中斷條件下的應急公交調度問題進行了研究。Y.B.WANG等[1]考慮到有限的應急資源以及城市交通狀況,設計了臨時應急公交橋接網絡，并基于復合泊松過程理論建立了需求模型；I.AKGUEN等[2]利用故障樹分析的方法計算了需求點脆弱性，并創新地將其融入到所建立的優化模型中；J.G.JIN 等[3]考慮中斷區間通勤者的出行需求，建立了動態響應需求的應急線路優化模型；J.G. SHI等[4]從脆弱性的角度分析了城市軌道交通網絡的可持續性，從時空角度量化網絡攻擊下網絡效率和結構完整性的變化，并對城市軌道交通網絡脆弱性進行評估；L.J.KANG等[5]探討了軌道交通網絡環境下的最后一班列車與公交橋接服務的問題，并建立了混合整數規劃橋接模型，用于解決末班列車乘客午夜滯留問題；Z.YANG 等[6]以網約車、網約車平臺和滯留乘客組成的系統為研究對象，建立了以城市軌道交通為主的軌道交通與網約車平臺之間的博弈模型；Y.WANG等[7]在考慮疏散優先權的前提下，建立了城軌運營中斷條件下的應急公交線路規劃模型；王起全等[8]提出了地鐵火災疏散路線的規劃及對策， 并建立多套消防救援方案；黃家駿等[9]針對動態不確定環境下的乘客初始狀態、疏散行為以及全局疏散路徑不確定等問題，提出了基于Agent的疏散行為動態切換模型；張勇等[10]基于隨機生滅過程理論建立了救援車輛的聯合排隊模型，并得到了救援狀態平衡方程；趙淑芝等[11]、張思林等[12]為有效緩解固定發車間隔造成的資源浪費和過度擁擠，建立了常規公交線路多車型配置優化模型；鄭玉靖等[13]建立兩階段優化模型，一階段以管理部門角度最小化疏散時間為目標,二階段以乘客角度降低乘客延誤為目標；王佳冬等[14]以總疏散時間以及乘客平均延誤最小為目標，建立了應急公交車輛調度優化模型。

上述研究主要從線路選址和疏運時間的角度，對應急公交調度模型進行研究。因此筆者在滿足乘客出行需求情況下，綜合考慮應急公交疏運時間以及車輛調度數量，構建了多車型下帶有車輛到達時間窗的應急公交調度優化模型。

1 問題的提出

當城市軌道交通發生較嚴重故障時，僅通過系統內部調整列車調度計劃已不能滿足滯留乘客的出行需求，因此應考慮在軌道交通中斷區間開設應急公交疏散滯留乘客，從而保障系統的安全、穩定運行。在滿足整體客流需求的條件下，筆者主要從調度過程和時間窗兩個角度對應急資源進行配置。

1.1 調度過程

應急公交車輛調度指在軌道交通中斷期間從應急公交停車場調度車輛，為軌道交通中斷區間上、下行滯留的乘客提供往返疏運服務。由于不同的停車場往往存在不同車型的車輛，如果不能對應急公交車輛的車型進行科學合理的選取，很可能會浪費現有的應急車輛資源。因此，在進行應急調度時需要考慮車型的因素，選取軌道交通中斷站點作為應急公交臨時停靠站，令中斷車站為i∈I,j∈J；s為應急公交車輛的停車場，s∈S；p為應急公交線路的首末站，p∈P，p=1為應急公交線路首站，p=2為應急公交線路末站；k為車型，k=1為大型公交車，k=2為中型公交車，k∈K。應急公交調度過程示意如圖1。

圖1 應急公交調度示意Fig. 1 Emergency bus dispatching diagram

1.2 時間窗

因為軌道交通突發事件具有隨機性和緊急性，所以應急公交車輛難以準確無誤地按照應急管理部門的時間要求到達站點，因此應急管理部門允許公交車輛的到達時間存在一定的波動范圍，筆者稱之為車輛到達時間窗。如果應急公交車輛到達應急線路首末站的時間超過了應急響應時限，則應該對該停車場予以剔除。對于晚到的公交車輛實行懲罰機制，如果公交車輛晚到，則相當于公交車輛多運行了一定的時間，以此增大目標函數值。令λ為獎懲時間，Tmin為懲罰車輛到達時間的上限(車輛到達時超過這個時間限度開始實行懲罰機制)，f(λ)為“懲罰系數函數”,χ,γ為懲罰參數：

(1)

2 應急公交調度模型

2.1 問題描述

因軌道交通系統內部結構復雜，一旦發生事故使線路運營中斷，若不能快速有效地疏散滯留的乘客，往往會對軌道交通系統產生重大影響，造成城市交通網絡局部擁堵甚至癱瘓等嚴重后果。地面公交因運量較大、響應迅速、調度靈活等優點成為疏散中斷區間滯留乘客的最佳選擇。因此選取地面公交車輛對滯留乘客進行疏散，從而保障公共交通網絡安全高效地運營，并根據實際情況做出如下假設：①不考慮客流的動態變化，僅考慮滿足客流需求的運力問題；②不同的停車場具有不同車型的車輛，且額定載客量為定值；③應急車輛沿中斷區間逐站?？浚谡鄯嫡厩蹇秃笾苯娱_始下一次疏運或終止疏運；④不同車型的應急車輛具有不同的平均運營速度，且由歷史平均路況確定；⑤不考慮道路上各種突發事件對應急公交車輛造成的影響。

2.2 建模分析

以往研究[15]主要集中在對“應急公交車輛的疏運時間”進行優化，從而構建了城市軌道交通運營中斷下的應急公交調度模型。但是在實際公交體系中不僅存在多種車型，而且在實際調度過程中還要遵循“就近調配車輛”的原則。因此筆者綜合考慮“多車型”和“車輛到達時間窗”對調度方案的影響，構建了多車型下考慮車輛到達時間窗的應急公交調度模型，因此推導出目標函數和約束條件。

2.2.1 應急公交疏運時間成本最小

應急公交車輛調度問題主要包含兩個過程：一是從停車場派遣車輛到應急線路的首末站；二是應急車輛在應急線路之間進行往返疏運。建模目的是為了在滿足客流出行需求的同時，減少應急公交在中斷區間的疏運時間。因此選取應急公交車輛疏運時間進行優化，應急公交疏運時間成本Z1如式(2)：

(2)

2.2.2 應急車輛調度成本最少

因為城市軌道交通發生突發事件時可供調度的應急車輛是有限的，所以應急管理部門更多考慮的是在滿足客流需求的前提下，盡可能地減少應急車輛的使用數量。應急車輛調度成本指參與調度的所有應急車輛所花費的成本。應急公交車輛調度成本Z2如式(3)：

(3)

2.2.3 約束條件

1)應急公交車輛的救援時間限制。令T為中斷運營時間：

(4)

2)應急公交車輛的到達時間限制。盡管應急公交停車場很多，但是可供使用的停車場數量有限。因此必須通過車輛到達的時間窗，來剔除距離應急公交線路首末站距離較遠(運營時間費用較大)的停車場。令Tmax為應急管理部門規定車輛到達的時間上限：

(5)

3)疏運需求的限制。令maxQi為最大斷面疏運需求，Bk為k型公交車的額定載客量：

(6)

(7)

(8)

2.3 應急公交組合調度模型

minZ=αZ1+βZ2

(9)

式中：α為應急公交疏運時間成本的權重；β為車輛投入成本的權重。

應急公交車輛的救援時間限制如式(10)：

先人說過“以身作則”，做任何事先自己做好，才能要求別人那樣做，教學也是一樣的。想要更有效的教學方式，教師作為學生的引路人，想要學生能學好，教師首先就要樹立起有效“課題學習”的教學理念。

(10)

應急公交車輛的到達時間限制如式(11)：

(11)

應急公交車輛運力的限制如式(12)：

(12)

停車場的最大派車數量限制如式(13)：

(13)

應急公交車輛的往返次數限制如式(14)：

(14)

3 改進的遺傳優化算法

應急公交調度優化模型屬于非線性整數規劃問題中的NP-hard問題。當問題的規模比較大時，搜索解的空間難度也不斷增加，通常使用傳統的精確求解方法很難求解實際規模問題的解。因此，筆者根據模型的特點設計了遺傳算法對優化模型進行求解。

3.1 改進的遺傳算法

由于傳統遺傳算法存在計算量大、收斂速度慢等缺點，筆者在交叉操作上進行改進，引入線性交叉算子，來增強算法的全局搜索能力，避免程序陷入局部最優，同時與傳統交叉方法進行對比分析。

3.2 遺傳算法的步驟

Step 2種群初始化。隨機產生初始種群。

Step 3選擇操作。使用輪盤賭法，選擇適應度較高的優秀個體遺傳給下一代。適應度用來評估個體的優劣程度，從而決定其遺傳機會的大小。

Step 4交叉操作。采用線性交叉算子。交叉操作指把兩個父代個體的部分結構加以替換重組而生成新的個體的運算。交叉的目的是為了在下一代產生新的個體。交叉操作在遺傳算法中起核心作用。

Step 5變異操作。使新個體的基因以一定的概率出錯，增強算法的局部隨機搜索能力和維持種群多樣性防止早熟現象。

Step 6收斂判定。當個體的適應度達到給定閾值時或最優群體適應度不再上升時，則迭代過程收斂，算法結束；否則重復Step 3，直至最終得到符合條件的染色體為止。

4 算例分析

4.1 算例背景

南昌地鐵2號線，全長31.51 km，共建設28座車站，西起南路站，途經新建區、東湖區、西湖區和青山湖區，東止辛家庵站，且經過南昌站、南昌西站兩個鐵路樞紐站，線路橫跨贛江兩岸，地理位置較獨特，局部線路如圖2。如果翠苑路站—學府大道站區段發生供電故障，中斷運營時間為1.5 h，導致雅苑路站、地鐵大廈站、翠苑路站、學府大道站、前湖大道站、嶺北站共6個車站運營中斷。同時在中斷區間附近選取下正街、省體育館、文教路、紅都大市場、老福山立交橋、辛家庵6個公交停車場進行車輛調配。停車場配車信息如表1，車輛運營參數如表2。

圖2 南昌市軌道交通2號線局部線路Fig. 2 Partial route map of Nanchang Rail Transit Line 2

表1 停車場配車信息Table 1 Parking dispatching information

表2 車輛運營參數Table 2 Vehicle operation parameters

4.2 優化結果分析

利用改進的遺傳算法對模型求解，同時根據文獻[16]固定其它參數不變，權值取[0,1]區間進行靈敏度分析，以0.1為步長，均分為11組進行計算。結果發現，當應急公交疏運時間成本權重為0.5、車輛投入成本權重為0.5時，優化效果較佳。因此選取該組數據作為優化結果進行分析。利用MATLAB2018a 軟件，通過大量的參數計算，最終選取種群規模為100、最大迭代次數為1 000 次、交叉概率為0.8、變異概率為0.05對優化模型進行求解。表3為改進遺傳算法的優化結果。

表3 優化結果Table 3 Optimized results

表3表明：派往應急公交首站大型車13輛、中型車3輛，派往應急公交末站大型車17輛、中型車2輛；通過對車輛到達時間窗的限制，可以有效剔除停車場1和停車場3對線路末站派車、停車場5和停車場6對線路首站派車，因為這些停車場到發車點的時間費用較大。

4.3 算法對比分析

筆者將改進的遺傳算法與普通的遺傳算法的優化結果進行對比分析，來證明改進的遺傳算法具有較高的收斂精度和搜索能力。將兩種算法重復運行10次對算法效果進行對比，如圖3。圖3中，適應度指的是每代適應度函數值的自然對數的平均值。表4為相關優化指標。

圖3 算法效果對比Fig. 3 Contrast map of algorithm effect

表4 相關優化指標Table 4 Related optimization indicators

圖3、表4表明：改進的遺傳算法相比普通遺傳算法，總目標降低了16.87%，車輛滿載率提高了18.49%，驗證了改進的遺傳算法具有較高的收斂精度和搜索能力。

5 結 論

1)在軌道交通運營中斷條件下，考慮到車輛到達情況和車型對調度方案的影響，筆者構建了考慮車輛到達時間窗的應急公交調度優化模型，并利用改進的遺傳算法對優化模型進行求解。

2)以南昌軌道交通1號線為例進行分析，研究結果表明：通過時間窗的獎懲機制可以使距離首末站較近的停車場優先服務，同時剔除不滿足時間窗約束的停車場；改進的遺傳算法相比普通遺傳算法，總目標降低了16.87%，車輛滿載率提高了18.49%。

3)筆者僅研究了固定疏運需求和固定疏運線路下的應急公交調度方案，而目前隨著互聯網技術和車聯網技術的迅速發展，實時動態客流響應和動態網絡調度方案將是未來研究的重點，對推動 “互聯網+交通”具有積極意義。