考慮車輛到達(dá)時(shí)間窗的應(yīng)急公交調(diào)度優(yōu)化模型

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

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

0 引 言

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

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

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

1 問題的提出

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

1.1 調(diào)度過程

應(yīng)急公交車輛調(diào)度指在軌道交通中斷期間從應(yīng)急公交停車場調(diào)度車輛，為軌道交通中斷區(qū)間上、下行滯留的乘客提供往返疏運(yùn)服務(wù)。由于不同的停車場往往存在不同車型的車輛，如果不能對(duì)應(yīng)急公交車輛的車型進(jìn)行科學(xué)合理的選取，很可能會(huì)浪費(fèi)現(xiàn)有的應(yīng)急車輛資源。因此，在進(jìn)行應(yīng)急調(diào)度時(shí)需要考慮車型的因素，選取軌道交通中斷站點(diǎn)作為應(yīng)急公交臨時(shí)停靠站，令中斷車站為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 時(shí)間窗

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

(1)

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

2.1 問題描述

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

2.2 建模分析

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

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

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

(2)

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

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

(3)

2.2.3 約束條件

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

(4)

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

(5)

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

(6)

(7)

(8)

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

minZ=αZ1+βZ2

(9)

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

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

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

(10)

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

(11)

應(yīng)急公交車輛運(yùn)力的限制如式(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ī)模比較大時(shí)，搜索解的空間難度也不斷增加，通常使用傳統(tǒng)的精確求解方法很難求解實(shí)際規(guī)模問題的解。因此，筆者根據(jù)模型的特點(diǎn)設(shè)計(jì)了遺傳算法對(duì)優(yōu)化模型進(jìn)行求解。

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

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

3.2 遺傳算法的步驟

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

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

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

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

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

4 算例分析

4.1 算例背景

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

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

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

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

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

利用改進(jìn)的遺傳算法對(duì)模型求解，同時(shí)根據(jù)文獻(xiàn)[16]固定其它參數(shù)不變，權(quán)值取[0,1]區(qū)間進(jìn)行靈敏度分析，以0.1為步長，均分為11組進(jìn)行計(jì)算。結(jié)果發(fā)現(xiàn)，當(dāng)應(yīng)急公交疏運(yùn)時(shí)間成本權(quán)重為0.5、車輛投入成本權(quán)重為0.5時(shí)，優(yōu)化效果較佳。因此選取該組數(shù)據(jù)作為優(yōu)化結(jié)果進(jìn)行分析。利用MATLAB2018a 軟件，通過大量的參數(shù)計(jì)算，最終選取種群規(guī)模為100、最大迭代次數(shù)為1 000 次、交叉概率為0.8、變異概率為0.05對(duì)優(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輛；通過對(duì)車輛到達(dá)時(shí)間窗的限制，可以有效剔除停車場1和停車場3對(duì)線路末站派車、停車場5和停車場6對(duì)線路首站派車，因?yàn)檫@些停車場到發(fā)車點(diǎn)的時(shí)間費(fèi)用較大。

4.3 算法對(duì)比分析

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

圖3 算法效果對(duì)比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%，驗(yàn)證了改進(jìn)的遺傳算法具有較高的收斂精度和搜索能力。

5 結(jié) 論

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

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

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