任禹謀，張 琦，袁志明，王 濤，丁舒忻，李 智

(1.中國鐵道科學研究院 研究生部，北京 100081；2.中國鐵道科學研究院集團有限公司 通信信號研究所，北京 100081)

現(xiàn)有鐵路運輸體系中，大型高速鐵路車站作業(yè)交叉干擾是限制列車運行圖能力的重要因素，其中到發(fā)線資源對此尤為敏感。編制高水平到發(fā)線運用計劃能夠滿足列車正點出發(fā)和車站作業(yè)不沖突的要求，提高設(shè)備資源的利用率和抗干擾性，為車站調(diào)度員提供決策支持，具有重要的實際意義。

到發(fā)線運用優(yōu)化問題是一個典型的半結(jié)構(gòu)化問題，模型構(gòu)建繁瑣，且與到發(fā)線相連的咽喉區(qū)進路結(jié)構(gòu)錯綜復雜，進一步加劇了問題的求解難度[1]。Cacchiani等[2]從列車到發(fā)時間和到發(fā)線選擇兩個角度詳細闡述車站作業(yè)問題，并為之提供通用模型和解決方案。Cardillo等[3]首次提出采用增量約束著色圖模型解決列車到發(fā)時間不能改變的車站徑路使用問題。Sels等[4]為了解決無法排列全部列車進路的情況，在構(gòu)建的到發(fā)線模型中提出了虛擬站臺的概念并應(yīng)用于比利時鐵路系統(tǒng)，最大限度地增加了可以在無沖突站臺通行的列車數(shù)量。Petering等[5]構(gòu)建了列車時刻表和到發(fā)線作業(yè)組合優(yōu)化的混合整數(shù)規(guī)劃模型，并采用CPLEX求解器求解實際問題進行驗證。近年，國內(nèi)學者更多地考慮現(xiàn)場因素，并將啟發(fā)式算法應(yīng)用于求解過程，降低問題的求解難度[6]。Zhang等[7]對車站到發(fā)線時空資源進行微觀描述，并建立數(shù)學規(guī)劃模型后用模擬退火算法進行求解。趙鵬等[8]將到發(fā)線和咽喉區(qū)進路作為整體問題綜合研究，完善了到發(fā)線運用模型。魯工圓等[9]以進路沖突圖為基礎(chǔ)構(gòu)建賦時有色Petri網(wǎng)仿真模型解決車站作業(yè)計劃建模過程復雜的問題，有效提高了建模效率。也有部分學者從客運服務(wù)質(zhì)量[10]、車站作業(yè)計劃魯棒性[11]、到發(fā)線利用均衡程度[12-13]等角度出發(fā)，詳細分析車站的優(yōu)化方向以解決到發(fā)線運用問題。

既有研究在解決到發(fā)線運用優(yōu)化問題時，通常采用加權(quán)的方式將多個優(yōu)化目標合并為單個優(yōu)化目標求解，并未以多目標的視角考慮不同方案的適用性，并且在現(xiàn)實中幾乎不可能精確測定各優(yōu)化目標的先驗權(quán)重。因此，到發(fā)線運用優(yōu)化問題的解應(yīng)該是一組從不同角度計算分析得出的Pareto解，供調(diào)度員決策備用。同時既有研究在目標制定過程中，往往忽略了列車到發(fā)分布特征的影響，采用固定化的優(yōu)化目標，這樣難以有針對性地解決車站通過能力與魯棒性之間存在的矛盾。因此，在滿足列車安全運行約束的條件下，針對列車到發(fā)分布特征，提出一種基于分時段多目標的到發(fā)線運用整數(shù)規(guī)劃模型，并設(shè)計改進的NSGA-Ⅱ算法求解，為車站列車調(diào)度工作提供策略支持。

1 問題描述與建模

1.1 問題描述

到發(fā)線運用優(yōu)化問題可以描述為:對于即將進站的列車集合和車站到發(fā)線集合，已知列車的圖定到發(fā)時間和車站站場布置，在滿足多個作業(yè)約束的情況下，求出一個使問題所有目標均盡可能為優(yōu)的合理到發(fā)線分配方案，以達到降低列車晚點傳播風險、提高車站作業(yè)能力和安全運營的目的。高速鐵路車站作業(yè)過程主要包含出段作業(yè)、入段作業(yè)、接車作業(yè)、發(fā)車作業(yè)、通過作業(yè)和折返作業(yè)等，每項作業(yè)對應(yīng)由列車在站內(nèi)走行進路完成，這些進路又可以分為接車進路和發(fā)車進路。在編制到發(fā)線運用計劃時，根據(jù)列車到發(fā)時間、出入段時間和其他作業(yè)時間標準，有序安排到發(fā)線的占用，減少空費時間，并預留一定的時間裕度，便于突發(fā)事件發(fā)生時計劃的調(diào)整[14]。同時合理利用咽喉區(qū)的列車進路，避免作業(yè)間的沖突，保證車站的作業(yè)效率和安全性。

1.2 模型假設(shè)

1)假設(shè)列車到發(fā)時間和車站站場布置均為已知條件；

2)假設(shè)車站作業(yè)過程完成時間均嚴格參照作業(yè)時間標準；

3)假設(shè)列車在接發(fā)車時只選擇基本進路，且所有到發(fā)線均能?？苛熊嚕?/p>

4)不考慮列車進路的分段解鎖，只采用一次性解鎖；

5)假設(shè)折返列車不變更到發(fā)線，并采用順接反發(fā)的進出站方式。

1.3 符號定義

1)集合。I為到站列車集合，i和h為列車的序號，n為到站列車的總數(shù)；J為車站到發(fā)線集合，j和l為到發(fā)線的序號，m為到發(fā)線的總數(shù)；Rj為連接到發(fā)線j的接車進路集合，rjs為集合中的接車進路，s為集合中接車進路的序號，a為集合中包含的接車進路總數(shù)；Pj為連接到發(fā)線j的發(fā)車進路集合，pjg為集合中的發(fā)車進路，g為集合中發(fā)車進路的序號，d為集合中包含的發(fā)車進路總數(shù)。

3)決策變量。xij為0-1決策變量，當xij=1時表示列車i占用到發(fā)線j，否則xij=0；yijs為0-1決策變量，當yijs=1時表示列車i占用到發(fā)線j選擇第s條接車進路，否則yijs=0；zijg為0-1決策變量，當zijg=1時表示列車i占用到發(fā)線j選擇第g條發(fā)車進路，否則zijg=0。

1.4 到發(fā)線運用分時段優(yōu)化模型構(gòu)建

高速鐵路車站接發(fā)列車的分布特征較為明顯，分為高峰時段和平峰時段，從定量的角度可以界定兩類時段對應(yīng)的列車密集程度，進而制定差異化的優(yōu)化目標。定義車站接發(fā)列車的分布特征參數(shù)為θ，設(shè)車站一天中單個小時最大接發(fā)列車數(shù)為M,則高峰和平峰時段對應(yīng)的接發(fā)列車數(shù)量范圍分別為[0,θM]和(θM,M]。平峰時段，在保證到發(fā)線作業(yè)魯棒性的同時，仍需考慮到發(fā)線固定作業(yè)方式等多方面影響因素；高峰時段，不僅要滿足到發(fā)線作業(yè)魯棒性的要求，更要提升到發(fā)線的利用效率。對于到發(fā)線運用優(yōu)化問題的魯棒性[15]，首先引入“沖突系數(shù)”的概念，即相鄰兩列車占用相同到發(fā)線時間間隔的倒數(shù)，用列車總沖突系數(shù)描述魯棒性；到發(fā)線利用效率可通過到發(fā)線占用時間方差衡量；到發(fā)線固定作業(yè)方式和乘客便捷乘降等影響因素折算成到發(fā)線占用費用來表征。到站列車分布特征與優(yōu)化目標的關(guān)系見圖1。

圖1 列車分布特征與優(yōu)化目標關(guān)系Fig.1 Relation between train distribution characteristics and optimization objectives

模型為：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

uskρih(yijs+yhlk)≤1,?i,h∈I;j,l∈J;s∈Rj;k∈Rl

(10)

ugqρih(zijg+zhlq)≤1,?i,h∈I;j,l∈J;g∈Pj;q∈Pl

(11)

usqρih(yijs+zhlq)≤1,?i,h∈I;j,l∈J;s∈Rj;q∈Pl

(12)

(13)

xij,yijs,zijg∈{0,1}

(14)

式(1)針對高峰時段到站列車，表示最小化到發(fā)線占用時間方差；式(2)針對所有時段的到站列車，表示列車總沖突系數(shù)；式(3)針對平峰時段到站列車，表示最小化到發(fā)線占用費用；式(4)為到發(fā)線指派的唯一性約束；式(5)和式(6)為接發(fā)車進路指派的唯一性約束；式(7)和式(8)為到發(fā)線和咽喉區(qū)進路的連通性約束；式(9)為同一到發(fā)線的占用時間間隔約束；式(10)～(12)為咽喉區(qū)進路沖突約束，分別表示接車進路之間、發(fā)車進路之間以及接發(fā)車進路之間在時間和空間上不能存在共同的交集；式(13)為列車折返約束。

2 算法設(shè)計

到發(fā)線運用問題是典型的多目標約束優(yōu)化問題，采用進化多目標優(yōu)化算法可以求出一組Pareto最優(yōu)解集供決策者針對不同的條件制定對應(yīng)的方案。進化算法中的NSGA-Ⅱ可以有效解決多目標優(yōu)化問題，但其在進行支配排序時僅通過適應(yīng)度函數(shù)選擇，并未考慮解的可行性，如果在進化全過程周期中加入約束限制則會導致解的搜索區(qū)域急劇減小，最后陷入局部最優(yōu)[16]。因此在進化的后期加入約束準則改進NSGA-Ⅱ算法中的個體選擇策略，既能在進化前期保持種群的多樣性，又能在進化后期提高種群的收斂性?；静襟E如下：

Step1編碼。采用自然數(shù)編碼方式，染色體長度等于研究時段內(nèi)到站列車的數(shù)目，基因位置代表列車到站的順序，基因所對應(yīng)內(nèi)容則為到發(fā)線編號。

Step2種群初始化。隨機生成一組規(guī)模為N的初始種群作為初代父代種群E(s)，s=0，s為迭代次數(shù)。

Step3非支配排序。針對已經(jīng)生成的種群，計算每個個體對應(yīng)不同目標函數(shù)的值，然后根據(jù)個體間是否存在支配關(guān)系對種群內(nèi)所有個體進行分層，層級越小的解越優(yōu)秀，再對同一層內(nèi)的解計算擁擠距離，計算公式如下

(15)

Step4約束準則排序。引入約束違反度[17]概念，并根據(jù)約束支配原則對種群內(nèi)個體進行排序，有效改善NSGA-Ⅱ進化后期可行解不足的問題。定義如果以下任何一個條件成立，則種群中任意兩個解比較時解1約束支配解2。

1)解1為可行解，解2為不可行解；

2)解1和解2都是不可行解，但解1的約束違反度小；

3)解1和解2都為可行解，且解1優(yōu)于解2，使用Step 3中擁擠距離的計算規(guī)則來解決。

約束違反度值計算公式如下

(16)

式中：G(X)為約束違反度，X為決策向量，ge(X)為模型中的10個約束條件。當ge(X)≤0，〈ge(X)〉返回其絕對值，否則返回0。由此可知當X為可行解時約束違反度值為0，當X為不可行解時，約束違反度值大于0。

Step5遺傳操作。將父代種群E(s)執(zhí)行傳統(tǒng)遺傳算法中的交叉和變異操作，生成一個規(guī)模為N的子代種群F(s)。

3 算例分析

3.1 數(shù)據(jù)準備

以京滬高速鐵路某車站為例進行仿真驗證。車站從3個方向接發(fā)列車，并與一個動車所相連通，站型圖見圖2，站內(nèi)共有10個到發(fā)線，48條基本接發(fā)車進路，8條入段進路和8條出段進路，車站作業(yè)時間標準見表1。對該站某日全天接發(fā)列車數(shù)量進行統(tǒng)計，單小時最大接發(fā)車數(shù)量M為20，到站列車的分布特征參數(shù)θ取0.85，則平峰和高峰時段對應(yīng)的接發(fā)列車數(shù)量范圍分別為[0,17]和(17,20]。綜合考慮方便旅客乘降和到發(fā)線固定作業(yè)方式的影響，制定到發(fā)線占用費用矩陣，見表2。選取16:00～18:00內(nèi)的進站列車作為研究對象，16:00～17:00接發(fā)列車16列，處于平峰時段，17:00～18:00接發(fā)列車20列，處于高峰時段，取種群大小N=200，最大進化代數(shù)Smax=300，交叉概率為0.9，變異概率為0.2，分別對兩種列車分布狀態(tài)下的到發(fā)線運用問題進行建模計算。

表1 作業(yè)時間標準Tab.1 Operating time standard min

表2 到發(fā)線占用費用矩陣Tab.2 Occupancy cost matrix of train platform

圖2 某高速鐵路車站平面站型Fig.2 Layout of a high-speed railway station

3.2 仿真結(jié)果驗證

16:00～17:00平峰時段，計算結(jié)果在進化至220代時逐漸收斂于Pareto前沿，共得到5組解，方案見表3。列車總沖突系數(shù)與到發(fā)線占用費用見圖3?？梢钥闯觯桨钢g均不存在支配關(guān)系，且列車總沖突系數(shù)的減少需要以增加到發(fā)線占用費用為代價。全部可行方案中列車總沖突系數(shù)最低至0.007 4，到發(fā)線占用費用最小為44。該時段到站列車數(shù)量未達峰值，從客運服務(wù)角度來看，優(yōu)先滿足旅客乘降便捷和客運員固定到發(fā)線接發(fā)列車，則選擇方案2，對比原計劃方案，總沖突系數(shù)降低了12.62%，到發(fā)線占用費用降低了16.98%；從車站調(diào)度安全角度來看，優(yōu)先提升到發(fā)線作業(yè)魯棒性，選擇方案1，進一步考慮同一到發(fā)線相鄰列車最小間隔時間可能成為限制計劃強壯性的瓶頸因素，驗證方案1的最小間隔時間為11 min，該值同樣是5個方案中的最大值，符合要求，對比原計劃方案，總沖突系數(shù)降低了33.82%，到發(fā)線占用費用降低了5.66%。

圖3 16:00～17:00到發(fā)線運用方案的Pareto解分布Fig.3 Pareto front distribution in train platform utilization scheme during 16:00—17:00

表3 16:00～17:00平峰時段到發(fā)線分配方案Tab.3 Train platform utilization scheme during normal peak period 16:00—17:00

17:00～18:00高峰時段，仿真計算共得到4組Pareto解，種群進化至250代時趨于收斂，限于篇幅，只展示各方案中列車分配不同的到發(fā)線，見表4。各方案目標函數(shù)對比結(jié)果見圖4。與平峰時段分配方案對比發(fā)現(xiàn)，4個方案中只有40%列車分配的到發(fā)線有區(qū)別，說明到站列車密集，滿足約束的可行性方案不多，同時各方案的最小間隔時間均為3 min，且該瓶頸時間位于列車19和24之間。方案1到發(fā)線使用效率最高，到發(fā)線占用時間方差104.85，比原計劃方案降低48.57%，總沖突系數(shù)也降低了18.71%，明顯提高了車站設(shè)備的利用效率；方案4在總沖突系數(shù)比原計劃方案降低了29.81%的同時，到發(fā)線使用效率基本與方案1持平，既保證了車站的通過效率，又提高了到發(fā)線運用計劃的魯棒性。

圖4 17:00～18:00到發(fā)線運用方案的Pareto解分布Fig.4 Pareto front distribution in train platform utilization scheme during 17:00—18:00

表4 17:00～18:00高峰時段到發(fā)線分配方案(部分)Tab.4 Train platform utilization scheme during rush hour 17:00—18:00 (part)

與此同時，為了研究分時段優(yōu)化與傳統(tǒng)優(yōu)化方法的區(qū)別，本文對全部研究時間段內(nèi)36列列車的三目標整數(shù)規(guī)劃模型進行計算生成了整體優(yōu)化方案，從解的Pareto前沿中均勻選取與分時段優(yōu)化方案等量的解進行對比，見圖5，方法1和方法2分別代表本文方法和整體優(yōu)化方法。可以看出，平峰時段整體優(yōu)化和分時段優(yōu)化方法在到發(fā)線占用費用方面比較接近，但列車總沖突系數(shù)方面卻明顯降低，兩種方法同一到發(fā)線相鄰列車間隔時間的最小差值為19 min，說明在車站作業(yè)不緊張時分時段優(yōu)化方案能夠在保證到發(fā)線合理選擇的同時有效提高到發(fā)線作業(yè)的魯棒性；高峰時段，整體優(yōu)化方法中到發(fā)線占用時間方差和列車總沖突系數(shù)均有較大波動，且兩個目標函數(shù)值變化趨勢相同，分時段優(yōu)化方法則情況相反，分析原因可知，整體優(yōu)化主要考慮了到發(fā)線空間上的運用均衡性，分時段優(yōu)化則進一步將分段時間內(nèi)的到發(fā)線占用時間均勻分布，使得列車總沖突系數(shù)也可以保持在較低水平。當突發(fā)事件發(fā)生,導致列車晚點時，同一到發(fā)線列車間的時間間隔越長表示吸收晚點時間的能力越強，說明分時段優(yōu)化方法能夠增強車站的抗干擾能力，具有一定的優(yōu)越性。

圖5 全部研究時段整體和分時段優(yōu)化方法結(jié)果對比Fig.5 Comparison of results of overall and segment optimization methods throughout the period of study

為檢驗改進算法的求解效率和質(zhì)量，以高峰時段2 h車站數(shù)據(jù)為例，將改進算法與文獻[6]中標準NSGA-Ⅱ算法進行對比實驗，結(jié)果見表5。實驗結(jié)果表明本文的改進NSGA-Ⅱ算法可以獲得更多的可行解，目標值有一定程度的優(yōu)化，同時改進算法的求解時間降低了48.17%。改進后NSGA-Ⅱ算法在解的質(zhì)量和求解效率方面均有提升，說明該算法具有良好的適應(yīng)性和有效性。

表5 本文算法與對比算法的比較結(jié)果Tab.5 Comparison of results of the proposed algorithm and the comparison algorithm

4 結(jié) 論

在考慮列車到發(fā)分布特征，分時段差異化制定目標的基礎(chǔ)上，構(gòu)建了一種到發(fā)線運用多目標優(yōu)化模型，并設(shè)計了包含約束處理的改進NSGA-Ⅱ算法進行求解。與整體優(yōu)化方法相比，分時段優(yōu)化方法從車站資源利用的角度增加了目標的針對性和多樣性，引入列車總沖突系數(shù)加強了到發(fā)線運用計劃的抗干擾性。實驗結(jié)果表明，相比整體優(yōu)化方法，分時段優(yōu)化方法的目標值有大幅降低，說明該方法有更好的魯棒性和有效性，同時本文算法在解的質(zhì)量和求解效率方面比NSGA-Ⅱ算法均有所提升，說明該模型和算法可以適用于不同時段車站到發(fā)線運用計劃制定過程，對提升車站的抗干擾能力和客運服務(wù)質(zhì)量具有重要意義。