城市軌道交通列車運行自動調整的優化模型及算法研究

孫少軍 王慧芳

（上海中鐵通信信號國際工程有限公司，上海 200436）

1 概述

城市軌道交通具有運量大、速度快、安全便捷、可靠性高的特點，已經成為緩解城市交通壓力的主要運輸方式。正常運行情況下，列車是嚴格按照運行圖來運行的。但是，城市軌道交通系統列車以隨機匯集的城市居民及流動人口客流為運輸對象[1]的這一特點，決定了城市軌道交通運輸組織的復雜性，運行過程中必然會產生許多隨機因素的干擾，導致列車的實際運行偏離計劃運行圖的情況發生。因此需要對列車的運行進行調整使其恢復按計劃有序運行。尤其是基于通信的列車運行控制（CBTC）系統實現了移動閉塞技術，打破了傳統的固定閉塞對于追蹤間隔的限制，使得列車的追蹤間隔明顯減小，大大增加了行車密度，同時也增加了列車運行調整的難度。因此，對城市軌道交通系統中列車運行調整的研究是非常必要和重要的。

本文在參考國內外已有相關文獻的基礎上，結合城市軌道交通列車運行的特點，建立列車運行調整的優化模型，采用改進的遺傳算法求解該模型，完成了列車自動調整的仿真測試。

2 列車運行自動調整模型

正常運行情況下，列車嚴格按照列車計劃運行圖運行，許多隨機因素的干擾使得列車難免偏離計劃運行圖，造成行車紊亂。因此需要對列車的運行進行調整，使其盡可能恢復按計劃有序運行。采用如下具有廣泛意義的列車運行調整模型[2，3]。

式中，G(j)為j時刻列車實際運行狀態，T是由列車運行調整決策而決定的狀態轉移算子。

列車運行自動調整問題模型的建立主要分成兩部分：一個是模型目標函數的確定；另一個是約束條件的確定。

2.1 目標函數

城市軌道交通列車運行自動調整問題實質就是根據線路上列車運行情況重新確定運行計劃，使實際運行圖不斷逼近計劃運行圖，最終達到差異最小化的過程。運輸部門在編制列車計劃運行圖時，已充分考慮了旅客平均等待時間、區間通過能力等因素，因此在重新確定運行計劃時，只需考慮如何使得調整后的運行計劃盡可能地接近原運行計劃。在調整過程中需考慮以下兩個因素。

1）列車總晚點時間

傳統的城市軌道交通列車運行調整模型通常會將出發總晚點時間忽略，這對于采用移動閉塞方式的城市軌道交通系統列車運行調整的模型建立來說是很不嚴謹的。因為移動閉塞使得追蹤列車之間沒有固定的閉塞長度，后行列車的運行會受到前行列車運行狀況的制約，前車的發車時間直接影響到后車的進站和離站時間。

這里的總晚點時間指的是列車運行到達總晚點和發車總晚點時間之和。

式中，n為列車總數，m為列車停站總數，dik和d｀ik分別為列車i在車站k的計劃和實際到站時間，fik和f｀ik分別為列車i在車站k的計劃和實際發車時間。

2）列車總晚點數目

同上，這里的總晚點數目指的是列車運行到達總晚點和發車總晚點列車數目之和。

式中，符號定義同公式（2）。

以列車總晚點時間和列車總晚點數目為綜合優化目標，具體的優化目標Z可寫成：

式中，ω1，ω2分別為Z1，Z2對應的權重因子。

2.2 約束條件

采用固定閉塞城市軌道交通系統的列車在運行調整時，主要考慮以下約束。

1）發車時間約束

列車實際發車時間不能早于計劃發車時間。

即：列車實際發車時間不能早于計劃發車時間。

2）最小停站時間約束

為了保證一定的載客量，規定了最小停站時間。列車實際停站時間不能小于本站最小停站時間。

式中，TkDmin是第k站最小停站時間。

3）區間運行時間約束

由于車輛的技術狀態，線路限速等的影響，以及為了保證旅客的舒適度，必須保證一個最小的區間運行時間。

式中，TkTmin是第k站到k+1站的最小區間運行時間。

4）追蹤間隔約束

為了保證行車的安全，列車的追蹤間隔不能小于規定的列車追蹤間隔。

式中ΔT為列車的最小行車間隔。

3 模型求解

由上述分析可知，城市軌道交通列車運行調整問題是一個多目標、多約束的組合優化問題，是一個典型的NP問題。應用傳統的分枝定界或逐步尋優方法進行求解時，在求解結果和收斂速度上都無法令人滿意。隨著智能技術的不斷發展，特別是遺傳算法成功解決了TSP、JobShop等組合優化問題以后，越來越多的學者把目光投向了它[3-5]，不過這些研究多是針對干線鐵路或高速鐵路的，真正針對移動閉塞下的城市軌道交通的運行調整的研究還非常少。本文采用改進的遺傳算法來求解城市軌道交通中列車運行調整的問題。

3.1 染色體編碼及種群初始化

列車運行調整問題實質上是重新確定列車時刻表的過程，變量均為列車的到發時間。采用整數編碼的方式，對所有需要調整的列車到發時間進行編碼。

以第一列列車當天開始運營從第一站的發站時間為零時刻，對時間偏移量以秒為單位進行整數編碼。比如說第一列列車投入運營在首站的發車站時間為6:00:00，則6:00:30被編碼為30。具體的染色體編碼可以表示為：

n為列車總數，m為列車停站總數，dik表示到站時間，fik表示發站時間，m×n×2表示一條染色體上的基因總數，也即到發站時間數據的總個數。一條完整的染色體也就表示了在一段時間內的完整列車運行圖。因為本文設計遺傳算法求解的目的是得到預計的列車到發站時間，從而進行列車運行調整。

種群的初始化采用控制育種范圍的初始化方式，根據調整計劃相對于原計劃的滯后性來控制育種邊界，使初始化染色體對應位置的時間不小于原計劃時間、不大于總晚點時間。

3.2 適應度函數的確定

適應度函數是對染色體適應環境能力的評價函數，一個染色體的適應度值越大，表明該染色體的適應環境的能力越強，即性能越好。本文建立的模型中的目標函數為最小化目標函數，因此需要進行變換。設計如下適應度函數：

由于所有約束條件均為硬約束，在計算適應度函數之前，需在遺傳算法的實現中對7項約束進行檢驗，若有某項不滿足，則該個體即遭淘汰，以此保證解的可行性。

3.3 種群演變策略

1）選擇：按照個體在當前種群中的適應度值為繁殖概率進行個體選擇。設種群中個體總數為C，則某一個體被選擇的概率為：

2）交叉：使種群中不同的個體按一定概率Po進行染色體交叉。

3）變異：以概率Pm對染色體進行變異操作，即隨機改變某個染色體的某一位值，以防止初始種群隨機產生一些重要信息的缺失。

針對城市軌道交通列車運行調整的特點，為了加快收斂速度和獲得有效的最優解，采用一些策略對遺傳算法進行了改進。

*在遺傳算法尋優過程中，初始化的染色體隨機生成，收斂的速度很慢，難以達到列車運行計劃實時調整的目的。如果初始化的染色體本身已經比較接近可行解，則經過交叉和變異，達到可行解的概率會大大增加。因此本文設計一種模式分類的方法，使得優化算法在初始化時，可以利用歷史求解的結果作為初值，加快收斂速度。

*為防止找不到最優解的情況發生，本代中適應度最高的個體被保留，不經過染色體交叉直接復制到下一代，以避免破壞某些優良基因。

進行迭代尋優，當迭代次數達到最大迭代數后退出運算。選取適應度最高的個體作為最優解，即為調整后的運營計劃。最大迭代次數的確定通過大量實驗的方法來確定。

4 仿真驗證

調整算法的仿真是在MATLAB7.0環境下應用英國謝菲爾德大學推出的遺傳算法工具箱實現的。本文以北京地鐵4號線為背景，進行列車運行調整的仿真實驗。

選用從西單到中關村的12個站為調整區段，早8：00-9：00的時間為調整時間段。在線運行的列車數目為15。

列車在各區間對應的最小運行時間(單位：s)矩陣為：

TTmin=[150,150,150,150,150,150,90,120,120,90,120,120]

列車在各站對應的最小停站時間(單位：s)矩陣為：

TDmin=[40,40,40,40,30,30,40,30,40,40,40,40]

列車最小追蹤間隔(單位：s)為：ΔT=150

經過多次的實驗與分析，本實例中遺傳算法的參數?。悍N群規模：100；遺傳代數：50；交叉概率：0.6；變異概率：0.001。

初始狀態設為第6列列車在第2站晚點120 s?？偼睃c時間420 s。進行列車運行自動調整仿真分析。

從仿真結果可以明顯看到，經過運行調整，隨著到發時間線以及站序的推移，各站的總晚點時間不斷減少，直至被消除從而恢復按計劃運行圖運行，如圖1，2所示。從而證明，論文提出的優化模型的設計方案及求解算法對于城市軌道交通環境下列車的運行調整是有效性和可行的。

5 結論

本文通過分析采用移動閉塞技術的城市軌道交通列車運行的特點，建立了城市軌道交通列車的運行調整優化模型，并采用改進的遺傳算法對該模型進行求解。以北京地鐵4號線為背景進行仿真測試，模擬列車晚點情況，按本文所設計模型及求解方法進行自動運行調整。結果表明，本文建立的優化模型和采用的求解方法是合理的，可以滿足列車正常運營自動調整的需求。

[1]吳洋．晚點情況下地鐵列車實時運行調整及速度控制模式研究[D]．成都：西南交通大學，2004.

[2]張亦南．基于GA的列車自動調整算法在CBTC系統中的應用研究[D]．北京：北京交通大學，2018.

[3]李平，賈利民．遺傳算法在列車運行調整中的應用研究[C].2001年中國智能自動化會議論文集，2001.

[4]章優仕，金煒東．基于遺傳算法的單線列車運行調整體系[J].西南交通大學學報，2005,40(2):147-152.

[5]張文修，粱怡．遺傳算法的數學基礎[M].西安：西安交通大學出版社，1999.

[6]郭廓．現代有軌電車中央行車指揮系統研究[D]．北京：北京交通大學．2011.