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

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

0 引言

地鐵在運(yùn)營期間發(fā)生突發(fā)中斷事件，不僅會(huì)打破本區(qū)段的運(yùn)營秩序，而且還會(huì)將這種影響傳播至軌道交通網(wǎng)絡(luò)，甚至?xí)斐烧麄€(gè)城市的公共交通系統(tǒng)紊亂。因此，許多專家學(xué)者對(duì)地鐵運(yùn)營中斷下的應(yīng)急車輛調(diào)度問題展開了大量的研究。

國內(nèi)外許多專家學(xué)者對(duì)應(yīng)急公交調(diào)度問題進(jìn)行了研究，WANG等[1]設(shè)計(jì)了臨時(shí)應(yīng)急公交橋接網(wǎng)絡(luò)，并實(shí)現(xiàn)了大規(guī)模的蒙特卡洛模擬試驗(yàn)；FENG[2]、GU[3]等提出了應(yīng)急車輛可以靈活地服務(wù)于不同的橋接線路，來構(gòu)建應(yīng)急車輛調(diào)度優(yōu)化模型；YANG等[4]對(duì)軌道交通網(wǎng)絡(luò)在面對(duì)突發(fā)事件時(shí)的魯棒性進(jìn)行了度量，并提出了一種新的加權(quán)綜合指數(shù)；TENG等[5]對(duì)乘客的行為和偏好進(jìn)行了調(diào)查，并建立了一個(gè)多項(xiàng)式logit模型。YANG等[6]通過構(gòu)建城市軌道交通與乘車平臺(tái)之間的博弈模型，來優(yōu)化城市軌道交通的補(bǔ)償決策；WANG等[7]考慮了中斷期間的動(dòng)態(tài)客流，建立了多目標(biāo)應(yīng)急公交調(diào)度優(yōu)化模型；胡華等[8]以完成各中斷站乘客的總疏運(yùn)時(shí)間最短為目標(biāo)，構(gòu)建公交車輛多循環(huán)調(diào)度模型；趙星等[9]以路阻函數(shù)的路徑行程時(shí)間與基于大量歷史交通量數(shù)據(jù)的可靠性為目標(biāo)進(jìn)行路徑規(guī)劃，并且通過指標(biāo)權(quán)重確定最優(yōu)路徑；王勇[10]、呂偉[11]、柴獲等[12]構(gòu)建了考慮時(shí)間窗的車輛路徑規(guī)劃模型，并通過實(shí)例驗(yàn)證了模型的有效性；何民[13]、韓霜等[14]建立了響應(yīng)式定制公交線路規(guī)劃模型，并通過實(shí)例驗(yàn)證了模型和算法的可靠性；趙建有等[15]為提高突發(fā)事件下的救援效率，建立了應(yīng)急物資配送優(yōu)化模型；馬昌喜等[16]針對(duì)疫情防控的要求，建立了突發(fā)事件下應(yīng)急定制公交線路規(guī)劃模型；薛浩楠等[17]提出了一種基于時(shí)空聚類法的定制公交需求響應(yīng)機(jī)制，并通過實(shí)例驗(yàn)證了該響應(yīng)機(jī)制的有效性。

上述研究主要是從固定線路調(diào)度角度出發(fā)，通過應(yīng)急車輛循環(huán)往返疏運(yùn)地鐵中斷站滯留的乘客。由于傳統(tǒng)固定線路疏運(yùn)不能有效地利用車輛自身的運(yùn)能，因此本研究在以往研究的基礎(chǔ)上，首先，從城市軌道交通運(yùn)營中斷下的實(shí)際操作模式出發(fā)，提出多停車場(chǎng)協(xié)同疏運(yùn)以及多車型協(xié)調(diào)調(diào)度的作業(yè)模式。然后，針對(duì)傳統(tǒng)固定線路調(diào)度疏運(yùn)效率低的不足，提出了靈活調(diào)度策略，允許應(yīng)急公交車輛服務(wù)于不同的調(diào)度路徑。將車輛調(diào)度與線路規(guī)劃整合為一個(gè)模型，以平均乘客延誤最小和公交企業(yè)疏運(yùn)成本最小為目標(biāo)，建立了多車型下應(yīng)急公交靈活線路開行方案模型。最后，采用改進(jìn)的NSGA-Ⅱ算法對(duì)應(yīng)急公交開行方案模型進(jìn)行求解，從而高效合理的制定應(yīng)急公交線路開行方案。

1 問題描述

當(dāng)城市地鐵線路發(fā)生較長(zhǎng)時(shí)間的運(yùn)營服務(wù)中斷事件時(shí)，應(yīng)及時(shí)利用地面公交車輛對(duì)地鐵中斷站的乘客進(jìn)行疏散。應(yīng)急預(yù)案為：從距離地鐵中斷區(qū)間兩端向外搜索最近的折返站，組織列車開行臨時(shí)交路，而在中斷區(qū)間內(nèi)組織應(yīng)急車輛來疏散滯留的乘客，同時(shí)選取中斷區(qū)間內(nèi)的站點(diǎn)作為應(yīng)急公交臨時(shí)?？空?。由于往返于中間站內(nèi)的疏運(yùn)需求一般相對(duì)較小，可借助其他交通工具繼續(xù)出行，因此，本論文主要研究往返于折返站和中間站以及往返于折返站之間的待疏運(yùn)客流需求。

應(yīng)急公交線路開行方案問題可描述為：已知某一中斷區(qū)域內(nèi)需要接駁的OD對(duì)集合為W，可供調(diào)度的停車場(chǎng)有s個(gè)，每個(gè)停車場(chǎng)有r輛k型車，每輛車的最大疏運(yùn)次數(shù)為L(zhǎng)，應(yīng)急車輛每次只服務(wù)一個(gè)OD對(duì)，每個(gè)OD對(duì)的待疏運(yùn)需求為Qia，由于疏運(yùn)需求遠(yuǎn)超單輛車的運(yùn)能，因此需要每輛應(yīng)急公交車進(jìn)行多次疏運(yùn)，且可以靈活的服務(wù)不同的OD對(duì)。以企業(yè)疏運(yùn)成本最少和乘客平均延誤最小為目標(biāo)，在所有乘客均被疏散的基礎(chǔ)上，獲取車輛的最佳調(diào)度方案和疏運(yùn)路徑，靈活接駁調(diào)度方案如圖1所示。

圖1 靈活接駁線路

2 優(yōu)化模型

2.1 模型假設(shè)

(1)地鐵中斷站的待疏運(yùn)乘客需求是確定的。

(2)采用多車型協(xié)同調(diào)度，每種車型的額定載客量、車速、固定成本均不相同。

(3)應(yīng)急公交車輛完成疏運(yùn)任務(wù)后需要返回原停車場(chǎng)。

(4)應(yīng)急車輛每次只能接駁1個(gè)OD對(duì)的乘客，期間不允許接駁其他乘客。

(5)不考慮道路上各種突發(fā)事件對(duì)應(yīng)急公交車輛的干擾。

2.2 參數(shù)和變量定義

應(yīng)急公交線路開行方案模型的相關(guān)參數(shù)和決策變量定義見表1和表2。

表1 模型參數(shù)定義

表2 模型決策變量定義

2.3 模型

為提高應(yīng)急公交車輛的救援效率，本研究將車輛調(diào)度與線路規(guī)劃整合為一個(gè)模型，以應(yīng)急公交車輛的疏運(yùn)成本Z1最小和平均乘客延誤Z2最小為目標(biāo)，構(gòu)建了多目標(biāo)應(yīng)急公交線路開行方案模型。優(yōu)化模型及約束條件如下：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

Qia≤GiaPη,

(13)

(14)

式(1)為應(yīng)急公交車輛疏運(yùn)成本最小；式(2)為平均乘客延誤最?。皇?3)為乘客總延誤的計(jì)算方法；式(4)每輛車被派遣到中斷站的行駛時(shí)間；式(5)為每輛車在中斷站間載客的行駛時(shí)間；式(6)為每輛車在執(zhí)行任務(wù)期間的空駛時(shí)間；式(7)為每輛車的行駛時(shí)間；式(8)為車輛疏運(yùn)完乘客返回停車場(chǎng)的空駛時(shí)間；式(9)為第lt次疏運(yùn)車輛的累積空駛時(shí)間；式(10)為第lt次疏運(yùn)車輛的累積載客時(shí)間；式(11)為服務(wù)某一OD的總車次數(shù)；式(12)為任一OD對(duì)均有車輛為其服務(wù)；式(13)為應(yīng)急公交車輛疏運(yùn)能力約束；式(14)為應(yīng)急車輛的救援時(shí)間約束。

3 優(yōu)化算法

3.1 NSGA-Ⅱ算法

應(yīng)急公交企業(yè)與出行乘客之間存在著一種博弈關(guān)系，針對(duì)應(yīng)急突發(fā)事件乘客總是想要以最短的時(shí)間繼續(xù)完成出行任務(wù)，而應(yīng)急公交企業(yè)總是期望以最少的經(jīng)濟(jì)投入完成疏運(yùn)任務(wù)，乘客與應(yīng)急公交企業(yè)之間是相互競(jìng)爭(zhēng)的，為了權(quán)衡不同目標(biāo)之間的利益關(guān)系，需要得到一組Pareto解集。由于傳統(tǒng)算法通常將多目標(biāo)轉(zhuǎn)化為單目標(biāo)進(jìn)行求解，常常存在算法早熟、局部最優(yōu)以及權(quán)重不好確定等缺點(diǎn)。而快速非支配排序遺傳算法(NSGA-Ⅱ)，雖然相對(duì)復(fù)雜，但計(jì)算精度、優(yōu)化效果較好。其搜索過程具有自組織、自學(xué)習(xí)性且運(yùn)行一次能夠得到一組互不支配的Pareto解集，因此選用NSGA-Ⅱ算法對(duì)應(yīng)急公交線路開行方案模型進(jìn)行求解。

3.2 NSGA-Ⅱ算法的改進(jìn)

3.2.1 正態(tài)分布交叉算子

由于普通NSGA-Ⅱ算法通常使用單點(diǎn)交叉，為了提升算法的搜索能力，在NSGA-II 算法中引入正態(tài)分布交叉算子[18]。令p1，p2為父代，利用正態(tài)分布算子產(chǎn)生x1，x2子代，其中|N(0,1)|為正態(tài)分布隨機(jī)變量，t為t∈(0,1)內(nèi)的隨機(jī)數(shù)。

(1)若t≤0.5

(15)

(2)若t>0.5

(16)

3.2.2 差分局部搜索策略

由于普通NSGA-Ⅱ算法通常使用多項(xiàng)式變異策略，為了提高算法的局部搜索能力，采用差分變異策略對(duì)個(gè)體的進(jìn)化過程進(jìn)行干預(yù)，利用差分向量作為變異算子[18]。種群p的同一層級(jí)中相鄰的父代個(gè)體{pa，pb}∈p，其子代個(gè)體p′i可通過差分變異算子獲取，r為相鄰個(gè)體對(duì)變異方向的影響程度r∈[0,1]，r越大影響越大。

p′i=rpa+(1-r)pb。

(17)

3.3 算法步驟

Step 1：參數(shù)設(shè)置：輸入算法相關(guān)參數(shù)，同時(shí)輸入應(yīng)急公交線路開行方案的相關(guān)參數(shù)。

Step 2：編碼與解碼：采用分段編碼，獲取每類車的使用數(shù)量、執(zhí)行任務(wù)次數(shù)、優(yōu)先級(jí)以及每次任務(wù)的優(yōu)先級(jí)。解碼，依據(jù)車輛的優(yōu)先級(jí)安排每輛車執(zhí)行任務(wù)的路徑，依據(jù)當(dāng)前車輛對(duì)于每個(gè)任務(wù)的優(yōu)先級(jí)和執(zhí)行任務(wù)次數(shù)，選擇優(yōu)先級(jí)高的任務(wù)作為本車的任務(wù)。

Step 3：隨機(jī)生成初始種群，對(duì)于NSGA-II算法設(shè)計(jì)的初始種群，將其轉(zhuǎn)為約束條件，再把約束條件轉(zhuǎn)換成邊界條件，并在規(guī)定的邊界中隨機(jī)產(chǎn)生初始種群。

Step 4：使用錦標(biāo)賽選擇法對(duì)初始種群進(jìn)行選擇操作，并利用正態(tài)分布交叉算子和差分變異算子進(jìn)行交叉和變異操作，從而形成子代個(gè)體。

Step 5：將父代和新產(chǎn)生的子代個(gè)體進(jìn)行合并，依據(jù)擁擠度比較算子挑出新個(gè)體，并通過快速非支配排序以及擁擠度的計(jì)算產(chǎn)生新種群。

Step 6：算法終止條件判斷，滿足則終止運(yùn)算，否則重復(fù)Step 3～Step 5。

4 案例分析

4.1 案例背景

南昌地鐵1號(hào)線是江西省南昌市首條開通運(yùn)營的線路，途徑經(jīng)開區(qū)、紅谷灘新區(qū)、東湖區(qū)、青山湖區(qū)、高新區(qū)，橫跨贛江兩岸，地理位置較獨(dú)特，線路全長(zhǎng)28.84 km，共修建24座車站，若彭家橋站-艾溪湖東站區(qū)段發(fā)生突發(fā)事件使線路雙向運(yùn)營中斷，中斷時(shí)間為2 h，涉及4個(gè)中間站和2個(gè)折返站，調(diào)用周邊區(qū)域4個(gè)停車場(chǎng)來完成疏運(yùn)任務(wù)。根據(jù)文獻(xiàn)[8]的方法獲取中斷站的待疏運(yùn)乘客需求如表3所示，表4為派車點(diǎn)的派車信息，表5為車輛運(yùn)營參數(shù)信息。

表3 中斷站點(diǎn)的乘客需求

表4 各派車點(diǎn)的派車信息

表5 車輛相關(guān)運(yùn)營參數(shù)

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

固定線路調(diào)度方案指應(yīng)急公交車輛從派車場(chǎng)出發(fā)前往中斷站點(diǎn)，沿中斷站行駛到折返站，且在折返站清客后直接空駛返回原中斷站進(jìn)行下一次疏運(yùn)或停止疏運(yùn)返回原停車場(chǎng)。利用改進(jìn)的NSGA-Ⅱ算法對(duì)應(yīng)急公交車輛固定調(diào)度模型與靈活調(diào)度模型進(jìn)行求解，并采用隸屬度函數(shù)求解出最大滿意度的Pareto解，從而得到應(yīng)急公交開行方案的最優(yōu)折衷解。表6為不同調(diào)度方案對(duì)比結(jié)果，表7為靈活調(diào)度方案的優(yōu)化結(jié)果。

表6 不同調(diào)度方案對(duì)比

表7 靈活調(diào)度方案的優(yōu)化結(jié)果

表6、表7結(jié)果表明：應(yīng)急公交車輛在每次完成疏運(yùn)任務(wù)后，能夠就近或者直接服務(wù)包含本次疏運(yùn)任務(wù)終點(diǎn)的其他OD對(duì)，能夠彌補(bǔ)傳統(tǒng)固定線路調(diào)度回程空駛返回原起點(diǎn)不載客的不足；靈活調(diào)度方案相比固定調(diào)度方案平均乘客延誤降低了5.20%,應(yīng)急公交疏運(yùn)成本降低了35.85%，參與調(diào)度的車輛數(shù)降低了31.91%；同時(shí)，也驗(yàn)證應(yīng)急公交靈活線路調(diào)度方案的優(yōu)越性。

4.3 算法分析

為了驗(yàn)證改進(jìn)的NSGA-Ⅱ算法與普通NSGA-Ⅱ算法以及多目標(biāo)粒子群算法(MOPSO)的收斂精度和搜索能力，在相同試驗(yàn)數(shù)據(jù)的條件下進(jìn)行試驗(yàn)，來對(duì)比3種算法的優(yōu)化效果，表8為優(yōu)化結(jié)果，圖2為優(yōu)化效果對(duì)比圖。

圖2 算法效果對(duì)比

表8 算法優(yōu)化結(jié)果對(duì)比

圖2、表8結(jié)果表明：改進(jìn)NSGA-II算法相比普通NSGA-II算法具有較高的計(jì)算精度和搜索能力，且求得的Pareto 最優(yōu)解集分布更均勻；同時(shí)，NSGA-Ⅱ算法相比MOPSO算法具有較高的計(jì)算精度和搜索能力。

4.4 靈敏度分析

對(duì)應(yīng)急公交車輛的車型比例(B型車數(shù)量/總車數(shù)量)進(jìn)行靈敏度分析，研究B型車數(shù)量的變化對(duì)應(yīng)急公交線路開行方案的影響，圖3、圖4分別為應(yīng)急公交疏運(yùn)成本和平均乘客延誤隨車型比例的變化情況。

圖3 疏運(yùn)成本-車型比例

圖4 平均乘客延誤-車型比例

圖3、圖4結(jié)果表明：在一定范圍內(nèi)應(yīng)急公交疏運(yùn)成本、平均乘客延誤隨車型比例的增加而下降車，車型比例對(duì)應(yīng)急公交調(diào)度方案具有顯著影響。

5 結(jié)論

(1)在地鐵運(yùn)營中斷條件下，考慮到傳統(tǒng)固定線路調(diào)度方案疏運(yùn)效率低的問題，本研究將車輛調(diào)度與線路規(guī)劃問題集成一個(gè)模型，構(gòu)建了多車型下的應(yīng)急公交線路開行方案模型，并利用改進(jìn)的NSGA-Ⅱ算法對(duì)開行方案模型求解。

(2)以南昌地鐵1號(hào)線為例進(jìn)行分析，研究結(jié)果表明：靈活調(diào)度方案相比傳統(tǒng)固定調(diào)度方案，平均乘客延誤降低了5.20%，應(yīng)急公交疏運(yùn)成本降低了35.85%，參與調(diào)度的車輛數(shù)降低了31.91%；同時(shí)對(duì)車型比例進(jìn)行靈敏度分析，發(fā)現(xiàn)車型比例對(duì)調(diào)度方案具有顯著影響。

(3)論文僅研究了單條地鐵線路運(yùn)營中斷下的應(yīng)急公交線路開行方案，而目前各大城市地鐵網(wǎng)絡(luò)迅速發(fā)展，研究大型中斷網(wǎng)絡(luò)下的應(yīng)急公交線路開行方案將是接下來研究的重點(diǎn)。