孫少軍 王慧芳

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

1 概述

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

本文在參考國內(nèi)外已有相關(guān)文獻(xiàn)的基礎(chǔ)上，結(jié)合城市軌道交通列車運行的特點，建立列車運行調(diào)整的優(yōu)化模型，采用改進的遺傳算法求解該模型，完成了列車自動調(diào)整的仿真測試。

2 列車運行自動調(diào)整模型

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

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

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

2.1 目標(biāo)函數(shù)

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

1）列車總晚點時間

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

這里的總晚點時間指的是列車運行到達(dá)總晚點和發(fā)車總晚點時間之和。

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

2）列車總晚點數(shù)目

同上，這里的總晚點數(shù)目指的是列車運行到達(dá)總晚點和發(fā)車總晚點列車數(shù)目之和。

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

以列車總晚點時間和列車總晚點數(shù)目為綜合優(yōu)化目標(biāo)，具體的優(yōu)化目標(biāo)Z可寫成：

式中，ω1，ω2分別為Z1，Z2對應(yīng)的權(quán)重因子。

2.2 約束條件

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

1）發(fā)車時間約束

列車實際發(fā)車時間不能早于計劃發(fā)車時間。

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

2）最小停站時間約束

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

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

3）區(qū)間運行時間約束

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

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

4）追蹤間隔約束

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

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

3 模型求解

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

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

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

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

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

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

3.2 適應(yīng)度函數(shù)的確定

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

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

3.3 種群演變策略

1）選擇：按照個體在當(dāng)前種群中的適應(yīng)度值為繁殖概率進行個體選擇。設(shè)種群中個體總數(shù)為C，則某一個體被選擇的概率為：

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

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

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

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

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

進行迭代尋優(yōu)，當(dāng)?shù)螖?shù)達(dá)到最大迭代數(shù)后退出運算。選取適應(yīng)度最高的個體作為最優(yōu)解，即為調(diào)整后的運營計劃。最大迭代次數(shù)的確定通過大量實驗的方法來確定。

4 仿真驗證

調(diào)整算法的仿真是在MATLAB7.0環(huán)境下應(yīng)用英國謝菲爾德大學(xué)推出的遺傳算法工具箱實現(xiàn)的。本文以北京地鐵4號線為背景，進行列車運行調(diào)整的仿真實驗。

選用從西單到中關(guān)村的12個站為調(diào)整區(qū)段，早8：00-9：00的時間為調(diào)整時間段。在線運行的列車數(shù)目為15。

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

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

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

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

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

經(jīng)過多次的實驗與分析，本實例中遺傳算法的參數(shù)取：種群規(guī)模：100；遺傳代數(shù)：50；交叉概率：0.6；變異概率：0.001。

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

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

5 結(jié)論

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

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

[2]張亦南．基于GA的列車自動調(diào)整算法在CBTC系統(tǒng)中的應(yīng)用研究[D]．北京：北京交通大學(xué)，2018.

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

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

[5]張文修，粱怡．遺傳算法的數(shù)學(xué)基礎(chǔ)[M].西安：西安交通大學(xué)出版社，1999.

[6]郭廓．現(xiàn)代有軌電車中央行車指揮系統(tǒng)研究[D]．北京：北京交通大學(xué)．2011.