考慮預(yù)警機(jī)制和開行方案的多車站客流控制問題

李妍峰 ，何金昆，彭釗

(1. 西南交通大學(xué) 經(jīng)濟(jì)管理學(xué)院，四川 成都 610031；2. 服務(wù)科學(xué)與創(chuàng)新四川省重點實驗室，四川 成都 610031)

隨著城市軌道交通的快速發(fā)展，出行者數(shù)量越來越多。據(jù)《城市軌道交通2019年度統(tǒng)計和分析報告》顯示[1]，2019年內(nèi)城市軌道交通客運(yùn)量237.1億人次，同比增長12.5%，高峰時段斷面客流最高高達(dá)6.32萬人次，這給城市軌道交通運(yùn)營造成了極大的壓力。很多城市(北京、上海、深圳、成都等)均采取了客流控制手段來緩解高峰時段城市軌道交通擁擠問題[2]。城市軌道交通客流控制問題可描述為：車站管理人員控制客流進(jìn)站速度，避免出現(xiàn)列車超載、站臺擁堵等現(xiàn)象，讓部分站臺外乘客有序排隊等候，提高列車運(yùn)輸效率[3]。目前相關(guān)學(xué)者對該問題進(jìn)行了研究。在模型構(gòu)建方面，客流控制模型的目標(biāo)函數(shù)包含最小乘客等待時間、最大服務(wù)乘客、最小乘客平均延誤時間、最大企業(yè)運(yùn)營成本等；模型中的決策變量有列車到發(fā)時間、發(fā)車間隔、上車乘客數(shù)量及上述幾種的組合。劉曉華等[4]考慮客流需求不均衡的特點，提出以限、控、封等方式減少下游車站客流擁擠，并進(jìn)行了相鄰車站的客流控制特性分析。WANG等[5]以分散擁擠車站壓力為目的對過飽和線路進(jìn)行發(fā)車間隔及列車最大運(yùn)輸能力設(shè)計。LI等[6]提出了列車時刻表與發(fā)車間隔偏差的優(yōu)化模型，模型中乘客進(jìn)出站數(shù)量影響列車停站時間。XU等[7]考慮不同需求場景下的車站服務(wù)能力，并引入數(shù)據(jù)包絡(luò)分析研究了動態(tài)客流需求下的控制問題。在此基礎(chǔ)上，SHI等[8]提出地鐵網(wǎng)絡(luò)層面的客流控制問題，以提高車站運(yùn)輸效率與車站累積乘客安全。XU等[9]基于對數(shù)的隨機(jī)客流分配原則，調(diào)整進(jìn)站和換乘的乘客數(shù)量。MENG等[10]構(gòu)建了以列車時刻表為導(dǎo)向的時空網(wǎng)絡(luò)模型。HUAN等[11]等研究了乘客乘車偏好對客流控制的影響，以適應(yīng)潛在的客流需求變化。ZHANG等[12]為提高不同乘客OD的乘車公平性，構(gòu)建了以上車乘客數(shù)量最大化為目標(biāo)的優(yōu)化模型。此外，客流控制與列車開行方案的結(jié)合也是研究的熱點。JIANG等[13]將列車跳停策略與客流控制相結(jié)合，構(gòu)建了基于效用理論的客源站選擇模型。陳維亞等[14]提出了列車大小交路與客流控制的整數(shù)規(guī)劃模型，并對小交路開行頻率進(jìn)行特性分析。在求解算法方面，大多數(shù)研究者采用啟發(fā)式算法求解，如粒子群算法、遺傳算法、局部搜索算法等。皮雁南等[15]設(shè)計了混合粒子群算法求解換乘乘客客流控制問題。唐祿林等[16]為匹配乘客出行需求，設(shè)計了遺傳算法求解列車停站方案。SHI等[17]基于地鐵自動售檢票系統(tǒng)(AFC)，提出了改進(jìn)局部搜索算法。綜上，現(xiàn)有城市軌道交通客流控制問題的研究中缺乏考慮站臺客流安全的情形。此外，實際地鐵線路中存在不同的列車大小交路及不同的列車運(yùn)力情況。因此，本文在前人研究的基礎(chǔ)上，考慮列車開行方案、車站客流控制及乘客上下車過程等約束，以進(jìn)站乘客數(shù)量和車站平均限流時間為決策變量，建立最小化乘客出行時間成本的優(yōu)化模型，并設(shè)計混合禁忌搜索算法進(jìn)行求解。

1 問題描述及模型建立

1.1 問題描述

考慮預(yù)警機(jī)制和開行方案的多車站客流控制問題描述如下：在一條共有|V|個車站的城市軌道交通線路中，控制時段T內(nèi)共計m輛列車運(yùn)營，時間粒度為t0。在已知單向客流OD情形下，乘客到達(dá)車站后，根據(jù)客流預(yù)警等級決定乘客是否進(jìn)入站臺。以車站i為例，用Li，0，Li，1，Li，2，Li，3分別表示客流預(yù)警等級為安全(0)，不安全(1)，危險(2)，極度危險(3)的累積乘客數(shù)量上限[18]。

本文提出的客流控制問題還具有以下特點：

1) 乘客刷卡數(shù)據(jù)已知，且遵循“先到先走，先下后上”乘車原則；

2) 各次列車的始發(fā)、終到站已知，列車之間的運(yùn)行順序已知，不考慮列車越行；

3) 列車在固定交路上運(yùn)行，交路之間互不影響；

4) 乘客能夠快速進(jìn)出站，不考慮乘客從刷卡到站臺的走行時間和進(jìn)出站乘客對站臺的瞬時影響；

5) 當(dāng)客流需求無法滿足時，假定乘客不改變行程，即客流需求恒定。

圖1是列車大小交路運(yùn)行示例。(1,|V|)表示大交路始發(fā)站和終到站；(s,s” )表示小交路始發(fā)站和終到站。當(dāng)乘客乘坐小交路列車時，車內(nèi)直達(dá)乘客可直接離開車站，其余乘客在車站s” 成為小交路換乘乘客。

圖1 列車大小交路Fig. 1 train short turning strategy

1.2 符號說明

為構(gòu)建模型，引入以下符號。

1) 集合

K：列車集合。

V：車站集合。

T：統(tǒng)計時段集合。

Z：預(yù)警等級集合。

2) 參數(shù)

t0：時間粒度。

Ni：車站i客流總需求。

Xij(t)：時段t到達(dá)車站i目的地為j站的乘客數(shù)量。

Aij(t)：時段t內(nèi)到達(dá)車站i目的地為j站的累積乘客數(shù)量

3)Ci站臺i的容納能力

Li，z：車站i等級z的累積乘客數(shù)量上限。

d：閘機(jī)最大通過能力。

Or/Dr：列車運(yùn)營始發(fā)站和終點站。

a：相鄰時段進(jìn)站乘客數(shù)量相差限度。

，：列車k到達(dá)/離開車站i的時刻。

hk：列車k的載客量。

Δ：允許的客流預(yù)警等級。

M：足夠大的正數(shù)。

w：站最大平均限流時間權(quán)值。

4) 中間變量：

(t)：時段t進(jìn)入站臺i目的地為j站的累積乘客數(shù)量。

(t)：時段t在車站i目的地為j的限流乘客數(shù)量。

Wk，ij：站臺i等候列車k目的地為j站的乘客數(shù)量。

Rk，ij：站臺i未乘坐列車k目的地為j站的滯留乘客數(shù)量。

Gk，ij：站臺i乘坐列車k目的地為j的上車乘客數(shù)量。

ηk，i，i+1：列車k在區(qū)間(i,i+1)的車內(nèi)乘客數(shù)量。

Ek，j：乘坐列車k目的地為j站的乘客數(shù)量。

Uk，Dk，j：乘坐列車k目的地為j小交路換乘乘客數(shù)量。

tdelayi：車站i的延誤時間。

φ：平均延誤時間。

ρmax：車站最大平均限流時間。

：0-1變量，列車k在車站i的客流預(yù)警等級。

5) 決策變量：

Yij(t)：t時段進(jìn)入站臺i目的地為j的乘客數(shù)量。

1.3 模型建立

目標(biāo)函數(shù)(1)表示最小化乘客出行時間成本，包括平均延誤時間和車站最大平均限流時間；約束(2)表示進(jìn)站累積乘客數(shù)量，由時刻1至?xí)r刻t進(jìn)站乘客數(shù)量累加；約束(3)和(4)表示客流控制過程，限流乘客數(shù)量為t時段到站累積乘客與t時段進(jìn)站累積乘客之差；約束(5)表示單位時間進(jìn)站乘客數(shù)量不超過車站閘機(jī)刷卡限制；約束(6)表示相鄰時段進(jìn)站乘客數(shù)量限制，避免單位時間進(jìn)站客流過大對站臺造成的瞬時影響；約束(7)表示進(jìn)站客流平衡，即所有到站乘客進(jìn)入站臺候車；約束(8)表示站臺等候列車的乘客數(shù)量，由進(jìn)站乘客、小交路換乘乘客、滯留乘客組成；約束(9)表示因列車剩余容量導(dǎo)致的站臺滯留乘客數(shù)量；約束(10)表示客流預(yù)警等級線性化；約束(11)表示上車乘客數(shù)量為車內(nèi)剩余容量與站臺候車乘客數(shù)量的最小值；約束(12)表示列車載客量。當(dāng)列車在運(yùn)營起點時，列車載客量即為首站上車人數(shù)。在其他站點，列車載客量由上車乘客數(shù)量、下車乘客數(shù)量及前一站列車載客量組成；約束(13)和約束(14)分別表示小交路換乘乘客數(shù)量與離站乘客數(shù)量與上車乘客數(shù)量的關(guān)系；約束(15)表示離站客流平衡，即站臺候車客流全部乘車到達(dá)目的地；約束(16)表示車站i的乘客延誤時間，包括站外客流控制時間與站臺乘客滯留時間；約束(17)和(18)分別表示平均延誤時間和平均限流時間計算；約束(19)表示車站最大平均限流時間不小于各車站的平均限流時間；約束(20)表示站臺客流預(yù)警等級不超過允許客流預(yù)警等級；約束(21)表示0-1變量。

2 算法設(shè)計

在城市軌道交通運(yùn)營過程中，客流控制問題是一類NP-hard問題[10]，本文結(jié)合列車大小交路、列車編組及站臺客流預(yù)警，因此也是NP-hard問題，且更難求解。在已有文獻(xiàn)中，禁忌搜索算法的性能較為依賴初始解的質(zhì)量。因此，本文設(shè)計了一種混合禁忌搜索算法。結(jié)合本問題特性，按列車發(fā)車間隔隨機(jī)生成乘客進(jìn)站方案。由于上一時刻未進(jìn)站客流會直接影響下一時刻進(jìn)站客流，因此在產(chǎn)生進(jìn)站客流方案時，每時刻的進(jìn)站乘客數(shù)量需依賴上一時刻的客流需求；然后根據(jù)模型特征，本文設(shè)計了7種領(lǐng)域算子；最后通過解的相似度保證解的多樣性，進(jìn)一步提高解的質(zhì)量。算法框架如下所示：

?

2.1 解的表示

2.2 初始解

由于各車站客流需求相互獨(dú)立，該問題的解由各時段進(jìn)站客流決定，采用整數(shù)編碼的方式，依照先后時刻順序排列。以車站i，控制時段|T|=10為例，解的編碼方式如圖2所示。

圖2 解的表示Fig. 2 Description of solution

本節(jié)采用“隨機(jī)”策略獲得初始解。首先各車站根據(jù)列車發(fā)車間隔生成|K|集合，集合中到站乘客順序隨機(jī)打亂，其次隨機(jī)生成進(jìn)站客流方案，具體算法框架如下：

Input 客流需求、列車及車站設(shè)施信息Step 1 所有乘客按列車發(fā)車間隔隨機(jī)打亂，設(shè)列車集合為K，k∈K；Step 2 初始化，令k=1；Step 3 隨機(jī)生成進(jìn)站客流方案，若滿足約束(12)，轉(zhuǎn)入Step 4；否則重新生成進(jìn)站客流方案，直至滿足約束(12)。k=k+1;Step 4 若k＜|K| 時，轉(zhuǎn)入Step 3；否則轉(zhuǎn)入Step 5；Step 5 若不滿足約束(15)，轉(zhuǎn)入Step 2；否則，結(jié)束得到初始解。

2.3 鄰域算子

為了獲得更好的搜索解空間，本文設(shè)定了7種鄰域算子，分別是單點插入算子、單點移除算子、子序列插入算子、子序列移除算子、兩點交換算子、子序列交換算子、兩子序列交換算子，如圖3所示。

圖3 領(lǐng)域算子Fig. 3 Field operator

1) 單點插入算子：隨機(jī)選擇一點，并隨機(jī)插入限流乘客數(shù)量；

2) 單點移除算子：隨機(jī)選擇一點，并隨機(jī)移除站臺乘客數(shù)量；

3) 子序列插入算子：隨機(jī)選擇一條子序列，并隨機(jī)插入限流乘客數(shù)量；

4) 子序列移除算子：隨機(jī)選擇一條子序列，并隨機(jī)移除站臺乘客數(shù)量；

5) 兩點交換算子：隨機(jī)選擇兩點，重新分配乘客數(shù)量；

6) 子序列交換算子：隨機(jī)選擇一條子序列，重新分配乘客數(shù)量；

7) 兩子序列交換算子：隨機(jī)選擇兩條子序列，重新分配乘客數(shù)量。

2.4 解的評價

本節(jié)提出的混合禁忌搜索算法為擴(kuò)大搜索范圍，允許違背約束(7)。當(dāng)違反客流進(jìn)站平衡限制時，將|T|時段的限流乘客時間作為懲罰值進(jìn)行度量。

2.5 禁忌表和藐視準(zhǔn)則

在迭代過程中，若某次移動改進(jìn)了當(dāng)前最優(yōu)解，則該移動被禁忌θ代，本文選取基于評價函數(shù)的藐視準(zhǔn)則對優(yōu)良解實施解禁。當(dāng)某個候選解的評價函數(shù)能改進(jìn)當(dāng)前最優(yōu)解時，則該移動被特赦并繼續(xù)迭代。

2.6 多樣化策略

為避免算法陷入局部最優(yōu)，本文的多樣化策略基于精英解集合[19]。精英解集合是算法在運(yùn)行過程中不斷加入新的高質(zhì)量解所構(gòu)成的，其多樣性是通過不斷刪除集合中的解來實現(xiàn)的。被刪除解的選擇基于解之間的相似度[20]，考慮以下2種情況：1) 當(dāng)精英解集合未達(dá)到規(guī)模上限，刪除集合中所有相似度ΔY(Ybest，Y)≥(|V|-2)*|T|的解；2) 當(dāng)精英解集合達(dá)到規(guī)模上限，以當(dāng)前最好解替換集合中相似度最高的解。

3 數(shù)值實驗

為驗證模型及算法的有效性，4.1節(jié)首先通過小規(guī)模算例對權(quán)值及客流預(yù)警等級進(jìn)行靈敏度分析。4.2節(jié)將混合禁忌搜索算法與CPLEX運(yùn)行結(jié)果相比較，測試算法性能。4.3節(jié)應(yīng)用實際案例對優(yōu)化結(jié)果進(jìn)行分析。本文算法使用C#進(jìn)行編碼，考慮到目前沒有針對本問題的標(biāo)準(zhǔn)算例，參考SHI等[18]提出的算例生成方法，客流需求通過正態(tài)分布產(chǎn)生。取時間粒度t0=30 s，控制時刻|T|=120。為簡化研究，站臺容納量統(tǒng)一取400人，閘機(jī)最大通過能力150人，相鄰時段進(jìn)站乘客數(shù)量最大相差為30人。列車相鄰區(qū)間運(yùn)行時間為4t0，停留時間為t0，每節(jié)列車編組定員為310人，精英集合規(guī)模設(shè)置為10，程序運(yùn)行100代終止。

3.1 小規(guī)模算例

以5個車站為例，記為V={A, B, C, D, E}。在實際乘車過程中，前方車站客流需求往往高于后方車站，所以假設(shè)車站A和B的客流需求為1 500人，車站C和車站D為1 000人，如表1所示。

表1 小算例客流需求Table 1 Small example passenger flow demand

為探討權(quán)重系數(shù)w的不同取值對平均限流時間的影響，固定站臺客流預(yù)警等級為2，其余信息與上文相同。表2為CPLEX求解得結(jié)果，依次列出目標(biāo)值、平均延誤時間、最大平均限流時間、車站平均限流時間。同時給出w=1時車站B(車站最大平均限流時間)的乘客進(jìn)站動態(tài)過程，如圖4所示。

表2 不同權(quán)重系數(shù)的目標(biāo)值Table 2 Target values of different weight coefficients

圖4 車站B的乘客進(jìn)站動態(tài)Fig. 4 Passenger boards at station B

由表2可知，隨著權(quán)重系數(shù)的逐漸增大，目標(biāo)值與平均延誤時間也逐漸增加，增大的幅度對各站平均限流時間產(chǎn)生不同程度的影響。當(dāng)僅考慮平均延誤時間(w=0)時，各車站平均限流時間呈現(xiàn)極大的不均衡性，其中車站A最小為37.6 s，車站B最大為117.3 s；當(dāng)w在一定的范圍內(nèi)變化時(0

為清楚體現(xiàn)站臺客流預(yù)警等級的設(shè)置對乘客出行時間成本的影響，固定權(quán)重系數(shù)w=1，其計算結(jié)果如圖5所示。隨著客流預(yù)警等級的增大，平均延誤時間由141.5 s縮減至77.4 s，車站最大平均限流時間由132.2 s縮減至72.6 s，分別減少45.3%和45.1%。這是因為站臺可容納乘客數(shù)量增多，擁擠程度變高。因此，地鐵運(yùn)營商可設(shè)置合理的預(yù)警等級來滿足乘客出行的舒適體驗，提高運(yùn)營服務(wù)質(zhì)量。

圖5 不同客流預(yù)警等級的目標(biāo)值Fig. 5 Target values of different passenger flow warning levels

3.2 算法性能分析

為測試本文所提禁忌搜索算法的求解效率，本節(jié)將使用精確算法求解器CPLEX對模型進(jìn)行精確求解，并將所得結(jié)果與混合禁忌搜索算法求解結(jié)果最比較，驗證模型及算法的正確性。隨著數(shù)據(jù)規(guī)模的增加，CPLEX不能求解大規(guī)模數(shù)據(jù)，實驗過程中設(shè)置CPLEX的最長運(yùn)行時間為7 200 s。本文算例生成方式與上文相同，為不失一般性，相同車站數(shù)量設(shè)置不同的客流需求，求解結(jié)果如表3所示。表3依次列出了CPLEX求解時間time(s)，求解下界(LB)，求解上界(LB)及求解Gap%，混合禁忌搜索算法計算20的平均目標(biāo)值(Avg.obj)，平均gap(Avg.gap%)，最好解(Best.obj)，最好解gap(Best.gap%)，平均求解時間Avg.time(s)，混合禁忌搜索算法與CPLEX的相對偏差(Related.gap%)。

表3 CPLEX與混合禁忌搜索算法比較Table 3 Comparison of CPLEX and hybrid tabu search algorithms

由表3可以看出，CPLEX在問題規(guī)模較小時(|V|=7)可求得模型的最優(yōu)解，這表明本文所提模型的正確性。隨著問題規(guī)模的擴(kuò)大(|V|=9,11)，CPLEX在規(guī)定時間(7 200 s)內(nèi)無法求解最優(yōu)解，且解得質(zhì)量也隨之下降(最大gap為26.5%)。當(dāng)問題規(guī)模繼續(xù)變大時(|V|=13)，CPLEX已無法求得可行解，這表明CPLEX可求得本問題小規(guī)模算例的最優(yōu)解，對于大規(guī)模算例求解存在一定程度的局限性。

由表3還可以看出，混合禁忌搜索算法可獲得所有算例的可行解。實驗發(fā)現(xiàn)在問題規(guī)模較小時(|V|=7, 9)可快速求得最好解，平均計算時間Avg.time<30 s，且Related.gap<3%；當(dāng)問題規(guī)模繼續(xù)擴(kuò)大到車站數(shù)|V|=11時，Related.gap均為負(fù)值，充分表明本文算法良好的求解效果；直至車站數(shù)|V|=13時，混合禁忌搜索算法仍能在較短時間(120 s)內(nèi)求得可行解。這表明本文所設(shè)計的混合禁忌搜索算法在大規(guī)模問題中有更優(yōu)的求解質(zhì)量和求解效率。

3.3 實際案例

本節(jié)以重慶地鐵6號線某日早高峰(8:00～9:00)為例，車站集合V={V1，V2，…，V28}，小交路運(yùn)營區(qū)間為(V1，V23)，各車站客流需求如表4所示，其余信息與上文相同。為清楚體現(xiàn)列車大小交路與小交路列車編組設(shè)置對求解結(jié)果的影響，假設(shè)列車編組與發(fā)車頻率如表5所示，其求解結(jié)果如表6所示。

表4 地鐵6號線客流需求Table 4 Passenger flow demand of Metro Line 6

表5 列車編組、發(fā)車頻率Table 5 Train size and departure frequency

由表6可知，在相同編組(8A)情形下考慮列車大小交路比不考慮列車大小交路，平均延誤時間節(jié)約15.2%，車站最大平均限流時間節(jié)約12.7%，且列車大交路平均滿載率相應(yīng)增加13.9%。這是因為小交路乘客提前乘坐列車離開，進(jìn)而影響列車平均滿載率與出行時間成本。所以從地鐵運(yùn)營的角度來講，采取大小交路模式可以解決客流需求的時空不均衡性，達(dá)到緩解車站擁擠的目的。

表6 不同開行方案、列車編組指標(biāo)對比Table 6 Comparison of different operating schemes and train grouping indexes

當(dāng)?shù)罔F運(yùn)營商采用大小交路模式時，小交路列車編組6A比8A出行時間成本更低，乘客能更快完成行程，其平均滿載率增高15.8%，乘客平均延誤時間與車站最大平均限流時間分別節(jié)約7.3%和6.1%，這說明在列車大小交路模式中采用“大交路大編組、小交路小編組”可以提高列車平均滿載率，以減少運(yùn)力浪費(fèi)。

4 結(jié)論

1) 考慮車站平均限流時間可有效提高線路乘車公平性，避免局部客流積壓嚴(yán)重。

2) 合理的站臺客流預(yù)警等級能有效緩解車站擁塞，減少乘客安全風(fēng)險。

3) 列車大小交路模式及小交路小編組可有效提高運(yùn)營服務(wù)質(zhì)量，節(jié)約企業(yè)成本。

4) 本文所設(shè)計的混合禁忌搜索算法表現(xiàn)出了良好的求解性能和質(zhì)量。后續(xù)研究可考慮列車跳停策略及列車時刻表優(yōu)化等問題，也可進(jìn)一步優(yōu)化混合禁忌搜索算法，設(shè)置更加有效的初始解獲得方案。