查偉雄，馮 濤，嚴(yán)利鑫

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

0 引 言

近年來，隨著我國城市軌道交通的快速發(fā)展，軌道交通在城市交通出行中越來越重要，一旦發(fā)生突發(fā)事件，將會對整個城市的公共交通系統(tǒng)產(chǎn)生嚴(yán)重的影響。因此高效的應(yīng)急公交調(diào)度方案成了學(xué)者們研究的熱點。

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

上述研究主要從線路選址和疏運時間的角度，對應(yīng)急公交調(diào)度模型進(jìn)行研究。因此筆者在滿足乘客出行需求情況下，綜合考慮應(yīng)急公交疏運時間以及車輛調(diào)度數(shù)量，構(gòu)建了多車型下帶有車輛到達(dá)時間窗的應(yīng)急公交調(diào)度優(yōu)化模型。

1 問題的提出

當(dāng)城市軌道交通發(fā)生較嚴(yán)重故障時，僅通過系統(tǒng)內(nèi)部調(diào)整列車調(diào)度計劃已不能滿足滯留乘客的出行需求，因此應(yīng)考慮在軌道交通中斷區(qū)間開設(shè)應(yīng)急公交疏散滯留乘客，從而保障系統(tǒng)的安全、穩(wěn)定運行。在滿足整體客流需求的條件下，筆者主要從調(diào)度過程和時間窗兩個角度對應(yīng)急資源進(jìn)行配置。

1.1 調(diào)度過程

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

圖1 應(yīng)急公交調(diào)度示意Fig. 1 Emergency bus dispatching diagram

1.2 時間窗

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

(1)

2 應(yīng)急公交調(diào)度模型

2.1 問題描述

因軌道交通系統(tǒng)內(nèi)部結(jié)構(gòu)復(fù)雜，一旦發(fā)生事故使線路運營中斷，若不能快速有效地疏散滯留的乘客，往往會對軌道交通系統(tǒng)產(chǎn)生重大影響，造成城市交通網(wǎng)絡(luò)局部擁堵甚至癱瘓等嚴(yán)重后果。地面公交因運量較大、響應(yīng)迅速、調(diào)度靈活等優(yōu)點成為疏散中斷區(qū)間滯留乘客的最佳選擇。因此選取地面公交車輛對滯留乘客進(jìn)行疏散，從而保障公共交通網(wǎng)絡(luò)安全高效地運營，并根據(jù)實際情況做出如下假設(shè)：①不考慮客流的動態(tài)變化，僅考慮滿足客流需求的運力問題；②不同的停車場具有不同車型的車輛，且額定載客量為定值；③應(yīng)急車輛沿中斷區(qū)間逐站?？?，在折返站清客后直接開始下一次疏運或終止疏運；④不同車型的應(yīng)急車輛具有不同的平均運營速度，且由歷史平均路況確定；⑤不考慮道路上各種突發(fā)事件對應(yīng)急公交車輛造成的影響。

2.2 建模分析

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

2.2.1 應(yīng)急公交疏運時間成本最小

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

(2)

2.2.2 應(yīng)急車輛調(diào)度成本最少

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

(3)

2.2.3 約束條件

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

(4)

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

(5)

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

(6)

(7)

(8)

2.3 應(yīng)急公交組合調(diào)度模型

minZ=αZ1+βZ2

(9)

式中：α為應(yīng)急公交疏運時間成本的權(quán)重；β為車輛投入成本的權(quán)重。

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

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

(10)

應(yīng)急公交車輛的到達(dá)時間限制如式(11)：

(11)

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

(12)

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

(13)

應(yīng)急公交車輛的往返次數(shù)限制如式(14)：

(14)

3 改進(jìn)的遺傳優(yōu)化算法

應(yīng)急公交調(diào)度優(yōu)化模型屬于非線性整數(shù)規(guī)劃問題中的NP-hard問題。當(dāng)問題的規(guī)模比較大時，搜索解的空間難度也不斷增加，通常使用傳統(tǒng)的精確求解方法很難求解實際規(guī)模問題的解。因此，筆者根據(jù)模型的特點設(shè)計了遺傳算法對優(yōu)化模型進(jìn)行求解。

3.1 改進(jìn)的遺傳算法

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

3.2 遺傳算法的步驟

Step 2種群初始化。隨機(jī)產(chǎn)生初始種群。

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

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

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

Step 6收斂判定。當(dāng)個體的適應(yīng)度達(dá)到給定閾值時或最優(yōu)群體適應(yīng)度不再上升時，則迭代過程收斂，算法結(jié)束；否則重復(fù)Step 3，直至最終得到符合條件的染色體為止。

4 算例分析

4.1 算例背景

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

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

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

表2 車輛運營參數(shù)Table 2 Vehicle operation parameters

4.2 優(yōu)化結(jié)果分析

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

表3 優(yōu)化結(jié)果Table 3 Optimized results

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

4.3 算法對比分析

筆者將改進(jìn)的遺傳算法與普通的遺傳算法的優(yōu)化結(jié)果進(jìn)行對比分析，來證明改進(jìn)的遺傳算法具有較高的收斂精度和搜索能力。將兩種算法重復(fù)運行10次對算法效果進(jìn)行對比，如圖3。圖3中，適應(yīng)度指的是每代適應(yīng)度函數(shù)值的自然對數(shù)的平均值。表4為相關(guān)優(yōu)化指標(biāo)。

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

表4 相關(guān)優(yōu)化指標(biāo)Table 4 Related optimization indicators

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

5 結(jié) 論

1)在軌道交通運營中斷條件下，考慮到車輛到達(dá)情況和車型對調(diào)度方案的影響，筆者構(gòu)建了考慮車輛到達(dá)時間窗的應(yīng)急公交調(diào)度優(yōu)化模型，并利用改進(jìn)的遺傳算法對優(yōu)化模型進(jìn)行求解。

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

3)筆者僅研究了固定疏運需求和固定疏運線路下的應(yīng)急公交調(diào)度方案，而目前隨著互聯(lián)網(wǎng)技術(shù)和車聯(lián)網(wǎng)技術(shù)的迅速發(fā)展，實時動態(tài)客流響應(yīng)和動態(tài)網(wǎng)絡(luò)調(diào)度方案將是未來研究的重點，對推動 “互聯(lián)網(wǎng)+交通”具有積極意義。