基于改進(jìn)差分算法的高速列車運行調(diào)整研究＊

曹巖，孟學(xué)雷

（1.蘭州交通大學(xué) 電子與信息工程學(xué)院，甘肅 蘭州730070；2.蘭州交通大學(xué) 交通運輸學(xué)院，甘肅 蘭州730070）

鐵路區(qū)段內(nèi)列車運行計劃的制定與調(diào)整是鐵路行車調(diào)度指揮工作中的核心，決定著區(qū)段內(nèi)行車組織工作的質(zhì)量。因此，鐵路行調(diào)指揮的自動化是近年來研究的熱點。隨著我國高速鐵路網(wǎng)絡(luò)的不斷完善，我國鐵路發(fā)展進(jìn)入了一個嶄新的歷史時期，在新形勢下如何確定高速列車運行調(diào)整方案，既滿足乘客與貨主的運輸需求，又提高線路車站的使用效率，是一個亟待解決的問題。目前，許多計算模型和智能算法逐步被應(yīng)用到解決列車運行計劃制定與調(diào)整問題的研究上來。對于列車運行調(diào)整問題相關(guān)學(xué)者展開了諸多研究。Cacchiani等［1］建立了列車鋪畫的線性規(guī)劃模型，以最多的列車數(shù)量為運行圖該模型的優(yōu)化目標(biāo)。Meng等［2］建立了以總晚點時間最少為目標(biāo)的非線性列車運行調(diào)整模型并設(shè)計了一種新的粒子群算法進(jìn)行求解。Castillo等［3］以總的旅行時間最少建立了列車運行調(diào)整模型并設(shè)計了兩段法策略進(jìn)行求解。Min等［4］針對列車運行沖突的消解是NP－h(huán)ard問題，設(shè)計了基于column－generation的列車運行調(diào)整算法。Almodovar等［5］基于離散事件仿真模型建立了一種實時的列車運行調(diào)整系統(tǒng)，并設(shè)計了貪婪算法進(jìn)行求解。Lamorgese等［6］設(shè)計了一種列車運行調(diào)整的分解算法。Albrecht等［7］設(shè)計了“問題空間搜索”方法求解列車運行調(diào)整問題。Wang等［8］設(shè)計了高速鐵路運行調(diào)整的雙層規(guī)劃模型。黃鑒等［9］建立了以列車總旅行時間、運行圖均衡性目標(biāo)一級區(qū)間服務(wù)頻率偏差為目標(biāo)的列車運行圖優(yōu)化模型，并設(shè)計模擬退火優(yōu)化算法求解。近年來，差分算法以其優(yōu)秀的算法性能得到了關(guān)注，也應(yīng)用到了列車運行調(diào)整及控制問題的求解中。韓蕙心等［10］利用差分算法求解其建立的基于多目標(biāo)的列車運行控制問題。嚴(yán)細(xì)輝等［11］建立了高速列車運行操縱多目標(biāo)優(yōu)化模型并利用差分算法進(jìn)行求解。本文在研究經(jīng)典種群算法的基礎(chǔ)上，引入多策略的種群尋址模式和多子群協(xié)同進(jìn)化機(jī)制，并將改進(jìn)的算法應(yīng)用于高速列車運行調(diào)整模型的求解中，得到了一種高速列車運行調(diào)整新的解決方法。

1 高速鐵路運行調(diào)整模型

當(dāng)列車運行受到干擾，產(chǎn)生列車晚點時，通過適當(dāng)?shù)卣{(diào)整列車的運行計劃，即改變各列車在車站的到、停時分及在區(qū)間的運行時間，使列車的運行最終回到計劃運行圖上，是列車運行調(diào)整的目的。高速鐵路列車運行調(diào)整是一項十分復(fù)雜的工作，其直接關(guān)系到鐵路行車安全，所以高速鐵路列車運行調(diào)整問題亟待研究。一般地，高速鐵路列車運行狀況調(diào)整的主要措施有：

（1）增加列車的停車站。

（2）延長列車在停車站的停車時分。

（3）選擇合理的會讓站、越行站，加速放行列車。

（4）組織列車進(jìn)行快速、平行作業(yè)，縮短列車在站作業(yè)時間。

（5）充分利用列車運行的最大允許速度，縮短列車區(qū)間運行時分。

（6）其他方法：如組織反方向行車，組織列車合并運行等。

這些措施的實施最終體現(xiàn)在對高速列車到站／離站及通過車站的調(diào)整。

設(shè)研究的區(qū)段內(nèi)共有N列車，M個車站，所謂車計劃就是指某列車在區(qū)段內(nèi)從始站到終站的各站的到發(fā)時分及作業(yè)性質(zhì)。則列車i在車站k的計劃為1個三元組［12］?？梢悦枋鰹椋?/p>

其中aik，dik分別為列車i的到達(dá)時分和發(fā)車時分，PRik表明列車i在車站k的預(yù)定作業(yè)類型，

那么，實際運行狀況可以由各列車經(jīng)過各站的到發(fā)時分來表征，因而可以由N×M個點計劃來描述［12］，即

由于Pik是1個三元組，于是OG可以分解成為到達(dá)矩陣GA，出發(fā)矩陣GD和作業(yè)標(biāo)志矩陣PR：

既定運行圖的列車到達(dá)時分矩陣。

又令SL＝ ｛slk｝（k＝1，2，…，M），表示車站k的到發(fā)線的數(shù)量，TO＝ ｛toik｝（k＝1，2，…，M）表示列車i在站k的技術(shù)作業(yè)時間。進(jìn)入調(diào)整的每一列車都有一個最早接入時間hk，最早發(fā)車時間fk和最晚開出區(qū)段或到達(dá)終點的時間gk，對應(yīng)列車在指定時間段［hk，gk］內(nèi)，應(yīng)該結(jié)束在本調(diào)度區(qū)段內(nèi)的運行。

那么，根據(jù)以上約定，以總晚點時間最少的列車運行調(diào)整問題的數(shù)學(xué)模型如下：目標(biāo)函數(shù)

滿足約束

式（8）表示列車i在站k的停車時間必須大于等于技術(shù)作業(yè)所需的時間；

式（9）表示追蹤列車占用區(qū)間的開始時刻晚于前行列車占用同一區(qū)間的結(jié)束時刻；

式（10）列車運行的區(qū)間順序約束，表明列車必須按時間順序依次通過各個區(qū)間，I為追蹤列車間隔時間；

式（11）表示同一列車開始占用到發(fā)線的開始時刻早于結(jié)束時刻；

式（12）表示所有列車的發(fā)車時刻晚于最早發(fā)車時間；

式（13）表示所有列車占用某區(qū)間的開始時間晚于最早接入時間；

式（14）為車站到發(fā)線能力約束，即該方向某種列車數(shù)和列車總數(shù)不能超過相應(yīng)的車站線路數(shù)；式中N（aik＋t?！躣ik）表示已到達(dá)車站k但并沒有離開車站k的列車數(shù)；

式（15）～（16）表示不能辦理同時接發(fā)同方向列車的車站，兩車間隔應(yīng)滿足不同時發(fā)到間隔時間τ發(fā)到和不同時到發(fā)間隔時間τ到發(fā)。

2 差分進(jìn)化算法及其改進(jìn)策略

2.1 基本差分進(jìn)化算法

差分進(jìn)化算法（DE）是一種用于優(yōu)化問題的啟發(fā)式算法。本質(zhì)上說，它是一種基于實數(shù)編碼的具有保優(yōu)思想的貪婪遺傳算法 。同遺傳算法一樣，差分進(jìn)化算法包含變異和交叉操作，但同時相較于遺傳算法的選擇操作，差分進(jìn)化算法采用一對一的淘汰機(jī)制來更新種群。由于差分進(jìn)化算法在連續(xù)域優(yōu)化問題的優(yōu)勢已獲得廣泛應(yīng)用，并引發(fā)進(jìn)化算法研究領(lǐng)域的熱潮。差分進(jìn)化算法由Storm以及Price提出，算法的原理采用對個體進(jìn)行方向擾動，以達(dá)到對個體的函數(shù)值進(jìn)行下降的目的，同其他進(jìn)化算法一樣，差分進(jìn)化算法不利用函數(shù)的梯度信息，因此對函數(shù)的可導(dǎo)性甚至連續(xù)性沒有要求，適用性很強(qiáng)。同時，算法與種群優(yōu)化有相通之處，但因為差分進(jìn)化算法在一定程度上考慮了多變量間的相關(guān)性，因此相較于種群優(yōu)化在變量耦合問題上有很大的優(yōu)勢。

基本差分算法的步驟是：

（1）初始化種群。隨機(jī)產(chǎn)生L個染色體，其中，每一個染色體由P個基因構(gòu)成。初始種群xi（0），i＝1，2，…，L，其中，xi（0）由P個基因構(gòu)成，為xi1（0），xi2（0），…，xiP（0）。

（2）變異。利用差分策略對染色體的基因進(jìn)行變異。差分策略有多種，常用的一種是隨機(jī)選取種群中2個染色體，然后求出兩者的向量差，乘以縮放因子得到一個新的向量，將該向量與待變異的向量相加，得到新的染色體。

其中，λ為縮放因子。xi（k）表示第k代種群中第i個個體。

（3）交叉。以一定的概率進(jìn)行交叉操作。為了保證變異中間染色體的基因傳給下一代，強(qiáng)制要求將變異中間染色體的一個基因抽取并植入下一代的染色體中。

其中，RandomCross是介于0與1之間的一個隨機(jī)數(shù)。

（4）選擇。差分算法采用貪婪算法選擇進(jìn)入下一代種群的個體。

2.2 基于三角形差分策略的差分進(jìn)化算法

不難發(fā)現(xiàn)，基本差分算法的差分策略較簡單，其優(yōu)點是在設(shè)計算法時易于實現(xiàn)，算法速度又能得到保證。但是，過于簡單的差分策略帶來的風(fēng)險是染色體的變異特征不能充分在子代中體現(xiàn)，可能會導(dǎo)致求解結(jié)果早熟，陷于局部最優(yōu)。所以，本文設(shè)計了一種新的差分策略，充分考慮不同變異染色體的特征，使染色體更優(yōu)。

本策略中，在本代染色體中，隨機(jī)選擇包含已經(jīng)變異的染色體xr1（g），xr2（g），xr3（g），運用這3條染色體，產(chǎn)生新一代染色體。新一代染色體的計算公式為：

其中，

可見，新一代染色體的規(guī)則充分考慮了上一代染色體的特征，避免了列車運行調(diào)整計算時出現(xiàn)早熟從而影響列車運行調(diào)整方案質(zhì)量的現(xiàn)象。

2.3 針對高速鐵路運行調(diào)整模型的差分算法設(shè)計

2.3.1 種群規(guī)模的設(shè)計

設(shè)計種群的規(guī)模，以較為恰當(dāng)?shù)姆N群規(guī)模進(jìn)行計算。針對列車運行調(diào)整問題，設(shè)計種群的規(guī)模介于20～50之間，在保證高速列車運行調(diào)整迭代計算的速度基礎(chǔ)上，防止運行調(diào)整的計算結(jié)果陷入局部最優(yōu)。

2.3.2 染色體設(shè)計

列車的數(shù)量為N，其經(jīng)過的車站數(shù)量為M，那么徑路上存在M－1個區(qū)間。因為某列車在每個車站的到達(dá)時刻和出發(fā)時刻對應(yīng)2個決策變量，那么，決策變量的數(shù)量是2×N×M個。每一個變量代表一個時刻。又因為全天24h是1 440 min，所以將染色體視為一個用二進(jìn)制表示的數(shù)字，數(shù)字的大小表示該時刻與0∶00之間的分鐘數(shù)。如8∶30距離0∶00有510min，則表示為0001 1111 1110。

2.3.3 計算停止條件

在高速列車運行調(diào)整計算中，迭代計算停止的條件設(shè)計有2種。一種通過設(shè)定種群算法的迭代次數(shù)上限控制循環(huán)次數(shù)。另一種通過控制計算結(jié)果與目標(biāo)結(jié)果之間的差距控制循環(huán)次數(shù)。本文采用第2種方法，設(shè)計相當(dāng)簡便，當(dāng)?shù)螖?shù)設(shè)置較合理時，能夠得到較理想的計算結(jié)果。

2.3.4 計算步驟

設(shè)計針對列車運行調(diào)整的計算步驟為：

第1步：設(shè)置計算結(jié)果與目標(biāo)結(jié)果之間的允許差值；

第2步：初始化種群。設(shè)置粒子種群的規(guī)模是Ngen。每一粒子的位置向量由2×N×M×Ngen個變量構(gòu)成。根據(jù)列車晚點情況，設(shè)置每一個變量的初始值；

第3步：計算適應(yīng)度函數(shù)的值Z。將各粒子的最優(yōu)位置進(jìn)行記錄，并記錄使得適應(yīng)度函數(shù)的值最小的染色體；

第4步：變異，交叉，選擇：根據(jù)上述設(shè)計的變異、交叉、選擇規(guī)則進(jìn)行染色體變異、交叉、選擇；

第5步：計算適應(yīng)度值，并求得計算結(jié)果與目標(biāo)結(jié)果之間的差值，若小于等于第1步設(shè)置的允許差值，則根據(jù)種群中最優(yōu)粒子的最優(yōu)位置，給出高速列車運行調(diào)整后各列車在車站的到達(dá)和出發(fā)時刻；否則，轉(zhuǎn)第3步。

3 計算實例與分析

選取京廣高速鐵路廣州南至衡陽東的上行列車運行數(shù)據(jù)作為實驗數(shù)據(jù)。如表1所示，在8∶00～11∶00之間，京廣鐵路的上行方向，有 G280，G1108，G832，G1002，G1110，G6102，G276，D7802，G1112，G1004，G6104，G542，G1006，G532及G822共15個車次的列車在該區(qū)段上運行。其具體的列車運行時刻見表1。

表1 京廣高速鐵路廣州南至衡陽東8∶00至11∶00原列車時刻表Table 1 The original timetable between Guangzhounan and Hengyangdong of Beijing－Guangzhou high speed railway from 8∶00to 11∶00

假設(shè)某日由于鐵路設(shè)備故障，使得部分高速列車出現(xiàn)晚點，即G1108到達(dá)郴州西時晚點10 min、G1002到達(dá)韶關(guān)時晚點13min，G1112，G6104，G542，G1006到達(dá)廣州北時晚點10min?？梢?，初始總晚點時間已經(jīng)達(dá)到了63min，考慮列車晚點傳播的影響，根據(jù)上述設(shè)置的求解步驟，首先設(shè)置目標(biāo)總晚點值控制在150min內(nèi)，而允許的計算結(jié)果與目標(biāo)結(jié)果之間的允許差值為5min，即計算結(jié)果的值在155min以內(nèi)，就結(jié)束循環(huán)計算。

根據(jù)上述設(shè)計的求解步驟，設(shè)計粒子群的規(guī)模為20，那么位置向量由2×15×8×20＝4 800個變量構(gòu)成。

根據(jù)上述設(shè)計的列車運行調(diào)整的改進(jìn)的差分算法，計算得到結(jié)果。然后將計算結(jié)果還原為如表2所示的新的列車時刻表。調(diào)整后的列車運行圖如圖1所示。

表2 京廣高速鐵路廣州南至衡陽東8∶00～11∶00調(diào)整后列車時刻表Table 2 Rescheduled timetable between Guangzhounan and Hengyangdong of Beijing－Guangzhou high speed railway from 8∶00to 11∶00

圖1 京廣高速鐵路廣州南至衡陽東8∶00～11∶00調(diào)整后列車運行圖Fig.1 Rescheduled operation chart between Guangzhounan and Hengyangdong of Beijing－Guangzhou high speed railway from 8∶00to 11∶00

圖1中，虛線為原列車運行計劃線，但是由于設(shè)備故障不能兌現(xiàn)。點畫線為新調(diào)整后的列車運行線。從圖1及表2中的數(shù)據(jù)可知，本文設(shè)計的方法可以得到合理可行的列車運行計劃。最后求得的適應(yīng)度值即總晚點時間為153min，小于目標(biāo)值155min，與目標(biāo)值150min只差3min，達(dá)到了算法中對于計算精度的要求。

具體而言，G1108由于在郴州西站晚點，在郴州西至耒陽西及耒陽西至衡陽東2個區(qū)間趕點，但由于區(qū)間最小運行時分的限制，列車在到達(dá)衡陽東時仍然晚點2min。G1002晚點13min，而要保證在韶關(guān)停站2min，8：39才能從韶關(guān)站出發(fā)。此時，若考慮G1110不晚點通過韶關(guān)站，又要滿足列車之間的追蹤間隔，勢必造成G1002在韶關(guān)站被G1110越行，由于等級相同，G1002不能越行G1110，所以最后將造成G1002嚴(yán)重晚點，所以，此時采取的策略是將G1110到達(dá)韶關(guān)站的時間推遲2min，G1002仍然運行在G1110前方，并進(jìn)行趕點，使其在郴州西恢復(fù)按圖運行。G1006與G532之間的情況同理。G1112和G6104趕點，在郴州西恢復(fù)按圖運行，G542在韶關(guān)恢復(fù)按圖運行?？梢?，本文設(shè)計的模型和算法，在考慮列車運行約束的基礎(chǔ)上，使得列車運行調(diào)整的方案更合理。

4 結(jié)論

（1）建立的高速鐵路運行調(diào)整模型較完整地描述了高速列車行調(diào)工作問題。模型考慮高速列車停站時間、追蹤間隔時間、到發(fā)線數(shù)量約束、高速列出的接入調(diào)整區(qū)段時間、不同時到發(fā)間隔時間與不同時發(fā)到間隔時間等約束，為得到合理的高速鐵路列車運行調(diào)整方案奠定了基礎(chǔ)。

（2）設(shè)計的基于三角差分策略的高速鐵路列車運行調(diào)整差分算法適合求解本文所建立的列車運行調(diào)整模型，由計算結(jié)果還原而成的列車運行計劃合理。

（3）所提出的高速鐵路列車運行的模型和算法是切實可行的，可為我國新一代的鐵路列車運行調(diào)度系統(tǒng)建設(shè)提供一種可借鑒的建模與算法方案。

［1］Cacchiani V，Caprara A，Toth P.Scheduling extra feight trains on railway networks［J］.Transportation Research Part B，2010，44（2）：215－231.

［2］Meng X L，Jia L M，Qin Y.Train timetable optimizing and rescheduling based on improved particle swarm algorithm［J］，Transportation Research Record，2010，2197：71－79.

［3］Castillo E，Gallego I，Urena J M，et al.Timetabling optimization of a mixed double－and single－tracked railway network［J］.Applied Mathematical Modelling，2011，35（2）：859－878.

［4］Min Y H，Park M J，Hong S P，et al.An appraisal of a column－generation－based algorithm for centralized train－conflict resolution on a metropolitan railway network［J］.Transportation Research Part B，2011，45（2）：409－429.

［5］Almodóvar M，García－Ródenas R.On－line reschedule optimization for passenger railways in case of emergencies［J］.Computers ＆ Operations Research ，2013，40（3）：725－736.

［6］Lamorgese L，Mannino C.The track formulation for the train dispatching problem［J］.Electronic Notes in Discrete Mathematics，2013，41：559－566.

［7］Albrecht A R，Panton D M，Lee D H.Rescheduling rail networks with maintenance disruptions using problem space search［J］.Computers ＆ Operations Research，2013，40（3）：703－712.

［8］Wang L，Mo W T，Qin Y，et al.Optimization based high－speed railway train rescheduling with speed restriction［J］.Discrete Dynamics in Nature and Society，2014，Article ID 934369，http：／／dx.doi.org／10.1155／2014／934369.

［9］黃鑒，彭其淵.基于分時客運需求的客運專線列車運行圖優(yōu)化［J］.鐵道科學(xué)與工程學(xué)報，2012，9（6）：66－71.

HUANG Jian，PENG Qiyuan.Train diagram optimization of passenger dedicated line based on passenger transport demand in different time［J］.Journal of Railway Science and Engineering，2012，9（6）：66－71.

［10］韓蕙心，吳鵬，吳杰，等.基于多目標(biāo)差分進(jìn)化算法的列車惰行控制［J］.計算機(jī)應(yīng)用，2013，33（A02）：286－289.

HAN Huixin，WU Peng，WU Jie，et al.Coast control of urban train based on multi－objective differential evolution algorithm［J］.Journal of Computer Applications，2013，33（A02）：286－289.

［11］嚴(yán)細(xì)輝，蔡伯根，寧濱，等.基于差分進(jìn)化的高速列車運行操縱的多目標(biāo)優(yōu)化研究［J］.鐵道學(xué)報，2013，35（9）：65－71.

YAN Xihui，CAI Bogen，NING Bin，et al.Research on multi－objective high－speed train operation optimization based on differential evolution［J］.Journal of the China railway Society，2013，35（9）：65－71.

［12］賈利民.模糊控制與決策及其在鐵路自動化中的應(yīng)用［D］.北京：中國鐵道科學(xué)研究院，1991：107－113.

JIA Limin.Fuzzy control and deciding and its application in railway automatization［D］.Beijing：China Academy of Railway Sciences，1991：107－113.