城市軌道交通列車運(yùn)行自動調(diào)整的優(yōu)化模型及算法研究

孫少軍 王慧芳

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

1 概述

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

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

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

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

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

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

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

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

1）列車總晚點(diǎn)時(shí)間

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

這里的總晚點(diǎn)時(shí)間指的是列車運(yùn)行到達(dá)總晚點(diǎn)和發(fā)車總晚點(diǎn)時(shí)間之和。

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

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

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

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

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

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

2.2 約束條件

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

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

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

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

2）最小停站時(shí)間約束

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

式中，TkDmin是第k站最小停站時(shí)間。

3）區(qū)間運(yùn)行時(shí)間約束

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

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

4）追蹤間隔約束

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

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

3 模型求解

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

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

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

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

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

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

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

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

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

3.3 種群演變策略

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

2）交叉：使種群中不同的個(gè)體按一定概率Po進(jìn)行染色體交叉。

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

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

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

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

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

4 仿真驗(yàn)證

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

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

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

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

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

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

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

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

初始狀態(tài)設(shè)為第6列列車在第2站晚點(diǎn)120 s。總晚點(diǎn)時(shí)間420 s。進(jìn)行列車運(yùn)行自動調(diào)整仿真分析。

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

5 結(jié)論

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

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

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

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

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

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

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