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

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

0 引言

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

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

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

1 問題描述

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

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

圖1 靈活接駁線路

2 優(yōu)化模型

2.1 模型假設(shè)

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

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

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

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

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

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

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

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

表2 模型決策變量定義

2.3 模型

為提高應(yīng)急公交車輛的救援效率，本研究將車輛調(diào)度與線路規(guī)劃整合為一個模型，以應(yīng)急公交車輛的疏運成本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)急公交車輛疏運成本最小；式(2)為平均乘客延誤最小；式(3)為乘客總延誤的計算方法；式(4)每輛車被派遣到中斷站的行駛時間；式(5)為每輛車在中斷站間載客的行駛時間；式(6)為每輛車在執(zhí)行任務(wù)期間的空駛時間；式(7)為每輛車的行駛時間；式(8)為車輛疏運完乘客返回停車場的空駛時間；式(9)為第lt次疏運車輛的累積空駛時間；式(10)為第lt次疏運車輛的累積載客時間；式(11)為服務(wù)某一OD的總車次數(shù)；式(12)為任一OD對均有車輛為其服務(wù)；式(13)為應(yīng)急公交車輛疏運能力約束；式(14)為應(yīng)急車輛的救援時間約束。

3 優(yōu)化算法

3.1 NSGA-Ⅱ算法

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

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

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

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

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

(17)

3.3 算法步驟

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

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

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

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

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

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

4 案例分析

4.1 案例背景

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

表3 中斷站點的乘客需求

表4 各派車點的派車信息

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

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

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

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

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

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

4.3 算法分析

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

圖2 算法效果對比

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

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

4.4 靈敏度分析

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

圖3 疏運成本-車型比例

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

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

5 結(jié)論

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

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

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