考慮預警機制和開行方案的多車站客流控制問題

李妍峰 ，何金昆，彭釗

(1. 西南交通大學 經濟管理學院，四川 成都 610031；2. 服務科學與創新四川省重點實驗室，四川 成都 610031)

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

1 問題描述及模型建立

1.1 問題描述

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

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

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

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

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

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

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

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

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

1.2 符號說明

為構建模型，引入以下符號。

1) 集合

K：列車集合。

V：車站集合。

T：統計時段集合。

Z：預警等級集合。

2) 參數

t0：時間粒度。

Ni：車站i客流總需求。

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

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

3)Ci站臺i的容納能力

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

d：閘機最大通過能力。

Or/Dr：列車運營始發站和終點站。

a：相鄰時段進站乘客數量相差限度。

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

hk：列車k的載客量。

Δ：允許的客流預警等級。

M：足夠大的正數。

w：站最大平均限流時間權值。

4) 中間變量：

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

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

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

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

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

ηk，i，i+1：列車k在區間(i,i+1)的車內乘客數量。

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

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

tdelayi：車站i的延誤時間。

φ：平均延誤時間。

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

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

5) 決策變量：

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

1.3 模型建立

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

2 算法設計

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

?

2.1 解的表示

2.2 初始解

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

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

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

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

2.3 鄰域算子

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

圖3 領域算子Fig. 3 Field operator

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

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

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

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

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

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

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

2.4 解的評價

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

2.5 禁忌表和藐視準則

在迭代過程中，若某次移動改進了當前最優解，則該移動被禁忌θ代，本文選取基于評價函數的藐視準則對優良解實施解禁。當某個候選解的評價函數能改進當前最優解時，則該移動被特赦并繼續迭代。

2.6 多樣化策略

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

3 數值實驗

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

3.1 小規模算例

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

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

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

表2 不同權重系數的目標值Table 2 Target values of different weight coefficients

圖4 車站B的乘客進站動態Fig. 4 Passenger boards at station B

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

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

圖5 不同客流預警等級的目標值Fig. 5 Target values of different passenger flow warning levels

3.2 算法性能分析

為測試本文所提禁忌搜索算法的求解效率，本節將使用精確算法求解器CPLEX對模型進行精確求解，并將所得結果與混合禁忌搜索算法求解結果最比較，驗證模型及算法的正確性。隨著數據規模的增加，CPLEX不能求解大規模數據，實驗過程中設置CPLEX的最長運行時間為7 200 s。本文算例生成方式與上文相同，為不失一般性，相同車站數量設置不同的客流需求，求解結果如表3所示。表3依次列出了CPLEX求解時間time(s)，求解下界(LB)，求解上界(LB)及求解Gap%，混合禁忌搜索算法計算20的平均目標值(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在問題規模較小時(|V|=7)可求得模型的最優解，這表明本文所提模型的正確性。隨著問題規模的擴大(|V|=9,11)，CPLEX在規定時間(7 200 s)內無法求解最優解，且解得質量也隨之下降(最大gap為26.5%)。當問題規模繼續變大時(|V|=13)，CPLEX已無法求得可行解，這表明CPLEX可求得本問題小規模算例的最優解，對于大規模算例求解存在一定程度的局限性。

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

3.3 實際案例

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

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

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

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

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

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

4 結論

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

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

3) 列車大小交路模式及小交路小編組可有效提高運營服務質量，節約企業成本。

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