江 秀，倪少權(quán)，陳釘均

（1. 西南交通大學 交通運輸與物流學院，四川 成都 610031；2. 西南交通大學 全國鐵路列車運行圖編制研發(fā)培訓中心，四川 成都 610031；3. 西南交通大學 綜合交通運輸智能化國家地方聯(lián)合工程實驗室，四川 成都 610031）

車站到發(fā)線運用計劃是規(guī)定車站某一階段內(nèi)所有到發(fā)列車占用到發(fā)場具體線路和時間的計劃，是車站行車技術(shù)作業(yè)的關(guān)鍵性工作之一[1]。車站到發(fā)線運用計劃的科學與合理，直接關(guān)系到車站的能力?？瓦\站到發(fā)線運用優(yōu)化，不僅能提高車站的行車技術(shù)管理水平和運輸生產(chǎn)效率，而且有助于提高客運站行車技術(shù)作業(yè)自動化水平。客運站到發(fā)線運用優(yōu)化研究綜述主要從模型種類、模型算法、目標函數(shù)與約束條件 3 個方面分析已有研究成果。

1 研究現(xiàn)狀

1.1 模型種類

1.1.1 0-1規(guī)劃模型

目前，到發(fā)線運用優(yōu)化模型中，0-1 規(guī)劃模型應(yīng)用最為廣泛。0-1 規(guī)劃模型還包括一次 0-1 規(guī)劃模型[2-3]、二次 0-1 規(guī)劃模型[4-8]及混合 0-1 規(guī)劃模型[9-14]。

（1）一次 0-1 規(guī)劃模型方面，何林等[2]以方便旅客上下車為目標，建立高速鐵路車站到發(fā)線運用的一次 0-1 規(guī)劃模型，并利用遺傳算法進行求解。陳建鑫等[3]所建模型也為一次 0-1 規(guī)劃模型，所不同是其將到發(fā)線的運用當作指派問題進行研究，采用指派問題常用的匈牙利算法進行求解。

（2）二次 0-1 規(guī)劃模型方面，呂紅霞等[4]采用“時間片”法，以可行性與交叉干擾最小為目標函數(shù)，以 1 列列車只能占用 1 條到發(fā)線，同一時間片內(nèi)的列車不能安排至同一到發(fā)線為約束條件，建立了二次 0-1 規(guī)劃模型，并通過分解，將其化為 2 個簡單的 0-1 規(guī)劃模型進行求解。有關(guān)研究是通過構(gòu)建二次 0-1 規(guī)劃模型研究到發(fā)線的運用優(yōu)化，只是目標函數(shù)、約束條件與求解算法有所不同[5-8]。

（3）混合 0-1 規(guī)劃模型方面，高建等[9]以出發(fā)列車正點、保持到發(fā)線固定使用方案與保證高等級列車優(yōu)先接發(fā)為優(yōu)化目標；以 2 列車占用到發(fā)線的起始時差的關(guān)系不等式來表示時間相沖突的 2 列相鄰列車占用同一到發(fā)線的約束條件 ( 非“時間片”法 )，建立了到發(fā)線運用的混合 0-1 整數(shù)規(guī)劃模型，并采用模擬退火算法進行求解。構(gòu)建混合 0-1規(guī)劃模型研究到發(fā)線運用優(yōu)化[10-14]的研究中，林志安等[10-11]對約束條件的考慮比較全面，如需要進行上水作業(yè)的列車、行郵作業(yè)量大的列車對到發(fā)線的要求；同一站臺兩側(cè)的到發(fā)線最好不要同時安排2 列出發(fā)時刻相近的列車或 1 列出發(fā)和 1 列到達列車等約束。

綜上所述，一次 0-1 規(guī)劃模型的目標函數(shù)單一，約束條件較少，適用于簡略分析；當需要考慮多項目標，約束條件較全面時需要建立二次 0-1 規(guī)劃模型或混合 0-1 規(guī)劃模型才能更貼切地反應(yīng)實際情況。

1.1.2 排序模型

以張貴英、Kroon 為代表的國內(nèi)外學者，利用排隊理論構(gòu)建排序模型研究到發(fā)線運用優(yōu)化問題。張貴英等[15-16]以列車接入的可行性與到發(fā)線運用的均衡性為目標，將到達的列車作為排隊論中的服務(wù)對象，將到發(fā)線作為排隊論中的服務(wù)機構(gòu)，以列車在車站的作業(yè)時間作為排隊論中的服務(wù)時間，以“先到先服務(wù)”原則、“權(quán)重大小”原則與“有限度大小”原則作為排隊論中的服務(wù)原則 ( 選用原則視具體情況而定，可以單原則，也可以多原則組合 ) 建立第 3 類多目標排序模型，并利用啟發(fā)式算法進行求解，得到車站到發(fā)線運用的初始方案。Kroon 等[17]在從安全角度出發(fā)，在研究特定列車的作業(yè)進路時，只考慮該進路是否可行，以及進路只由 1 個路段組成，將車站到發(fā)線運用問題看成具有固定時間窗口的排序問題，從而建立到發(fā)線運用優(yōu)化的排序模型。

1.1.3 其他模型

其他模型主要是指動態(tài)規(guī)劃模型[18]、圖著色模型[19]、可交替圖模型[20]與隨機機會約束規(guī)劃模型[21]，而到發(fā)線運用優(yōu)化采用這些類模型的研究較少。

朱亮等[18]考慮到同一車場內(nèi)t2時刻到發(fā)線狀態(tài)由t1時刻起始狀態(tài)和t1至t2時段內(nèi)接入及發(fā)出的列車決定，提出到發(fā)線運用優(yōu)化問題是一個多層約束條件動態(tài)規(guī)劃問題，以時刻表的刻度作為基本步長λ，建立到發(fā)線運用狀態(tài)轉(zhuǎn)移方程，以到發(fā)線剩余價值 ( 剩余到發(fā)線結(jié)構(gòu)重要度指數(shù)之和，結(jié)構(gòu)重要度由結(jié)構(gòu)重要度分析法確定相應(yīng)權(quán)重值 ) 最大為目標函數(shù)，建立動態(tài)規(guī)劃模型。由于該模型中的動態(tài)轉(zhuǎn)移方程的決策變量僅涉及到發(fā)線數(shù)量，因此利用該模型所求得的解僅是符合功能要求的解，后續(xù)還需要進行到發(fā)線占用沖突檢驗，以及考慮到發(fā)線均衡運用等。

Cardillo 等[19]將列車表示為無向圖的頂點，不能安排至同一到發(fā)線的 2 頂點相連表示為無向圖的邊，采用顏色集合表示到發(fā)線的集合，然后使用顏色集合給無向圖中所有頂點逐一著色，并使任何相鄰頂點所著顏色互不相同，用顏色dj給頂點vi著色表示將列車vi安排到發(fā)線dj，構(gòu)建圖著色模型。所建模型以到發(fā)線使用條數(shù)最少為目標函數(shù)，利用啟發(fā)式算法進行求解。

夏明等[21]考慮到到發(fā)線運用過程中的不確定因素，如旅客上下車延誤、車站作業(yè)等，研究了旅客列車停站時間和接續(xù)時間隨機變動情況下的到發(fā)線運用優(yōu)化問題，以提高車站作業(yè)效率和方便旅客乘降為目標，建立了到發(fā)線運用隨機機會約束規(guī)劃模型。

1.2 目標函數(shù)與約束條件

到發(fā)線合理運用的優(yōu)化目標如表 1 所示。

表1 到發(fā)線合理運用的優(yōu)化目標

在現(xiàn)有研究成果中，大部分所建模型為表中各單目標組合的多目標模型，少部分為單目標模型。這些研究主要包括：以到發(fā)線均衡使用、方便旅客乘降與有利于車站行車技術(shù)作業(yè)的組合為優(yōu)化目標[8，22]，以有利于車站行車技術(shù)作業(yè)與行車作業(yè)交叉干擾最小的組合為優(yōu)化目標[4]，以到發(fā)線均衡使用與列車站內(nèi)走行時間最短的組合為優(yōu)化目標[13]，以有利于行車技術(shù)作業(yè)與列車正點發(fā)車率最大的組合為優(yōu)化目標[9]，以到發(fā)線均衡使用與總誤工數(shù)最小的組合為優(yōu)化目標[15]，以到發(fā)線均衡使用與列車在到發(fā)線上停留時間最短的組合為優(yōu)化目標[23]，以到發(fā)線均衡使用構(gòu)建單目標優(yōu)化模型[24]，以方便旅客乘降構(gòu)建單目標優(yōu)化模型[2-3]等。

到發(fā)線運用優(yōu)化模型所涉及的約束條件主要有以下方面。

（1）1 條到發(fā)線同一時間內(nèi)只能接發(fā) 1 列列車。

（2）1 列列車在同一時間只能占用 1 條到發(fā)線。

（3）到發(fā)線作業(yè)的間隔時間約束。

（4）時間上存在重疊的 2 列車不能接入同一到發(fā)線。

（5）所有可能出現(xiàn)交叉干擾的列車均按平行進路接發(fā)列車。

（6）通過列車安排于正線。

（7）有上水要求的列車必須安排到有上水設(shè)備的到發(fā)線。

（8）有行包、郵政作業(yè)的列車必須安排接入靠近行包、郵政通道口站臺的到發(fā)線。

（9）要求接入基本站臺的列車必須安排靠近基本站臺的到發(fā)線。

（10）存在換乘關(guān)系的 2 列車應(yīng)安排在臨靠相同站臺的到發(fā)線上。

（11）終到站由同一車底擔當?shù)?2 列折返列車要安排在同一到發(fā)線上。

1.3 模型算法

到發(fā)線運用優(yōu)化模型求解目前主要包括分層求解思想和直接求解思想。

分層求解是將目標問題分解成幾個子問題，依次優(yōu)化，分解后的子目標多是線性的，可以直接采用一些常用軟件 ( 如 LINGO )，也可以考慮用運籌學中比較成熟的算法求解，如單純形法[4]、分枝定界法[8]、匈牙利解法[3]等。呂紅霞等[4]將 1 個二次0-1 規(guī)劃模型，分解成 2 個子模型，分別采用分枝定界算法與單純形法求解；雷定猷等[8]將 1 個多目標模型分解為 2 個模型，其中一個為一次 0-1 規(guī)劃模型，采用分枝定界算法求出可行解，在此可行解的基礎(chǔ)上再采用人機交互考慮另一模型。

直接求解即是尋找有效的搜索尋優(yōu)算法直接對所建模型進行求解?？瓦\站到發(fā)線運用優(yōu)化研究所涉及的搜索尋優(yōu)算法主要有：遺傳算法( Genetic Algorithm，GA )、蟻群算法 ( Ant Colony Optimization，ACO )、模擬退火算法 ( Simulation Annealing，SA )、模因演算法 ( Memetic Algorithm，MA )、基于捕食策略的禁忌搜索算法 ( Tabu Search，TS )、克隆算法 ( Immune Clonal Selection Algorithm，ICSA )。基于 CNKI 相關(guān)文獻，統(tǒng)計得出到發(fā)線運用優(yōu)化模型常用算法情況如圖 1 所示，遺傳算法與分枝定界算法在到發(fā)線運用模型中使用頻率較高，而禁忌搜索算法與蟻群算法使用較少，后續(xù)研究者可以嘗試這 2 類算法的探索研究。

圖1 到發(fā)線運用優(yōu)化模型常用算法統(tǒng)計

2 研究評述

2.1 參數(shù) Cij 的確定

在以有利于車站行車技術(shù)作業(yè)為目標的模型中，有些研究使用參數(shù)Cij，這一參數(shù)表示第i列列車由第j條到發(fā)線接發(fā)的權(quán)值。Cij取值描述如表 2 所示。其中，類別 1 中Cij是由歷史數(shù)據(jù)和工作人員的經(jīng)驗得出，但是否符合到發(fā)線固定使用方案，如何得出，憑借什么經(jīng)驗，涉及哪些因素沒有做出明確闡述；類別 2 中Cij的設(shè)定方法是否符合車站實際工作仍有待探討。

2.2 到發(fā)線運用與相關(guān)作業(yè)的綜合考慮

到發(fā)線運用與進路選擇、機車作業(yè)的綜合研究較少，而國外研究主要將到發(fā)線安排與列車作業(yè)進路、運行圖等進行綜合考慮。始發(fā)終到客運站，以及機車換掛站均存在著機車作業(yè)，機車作業(yè)對到發(fā)線的運用具有較大影響，而相關(guān)研究較少，其中提及到發(fā)線相關(guān)作業(yè)包括機車作業(yè)，但是實際所建模型均未考慮機車作業(yè)影響因素[7，22]。鐵路實際生產(chǎn)作業(yè)中，在始發(fā)站，機車需要出段至到發(fā)線或機待線；在終到站，機車需要從到發(fā)線或機待線入段；機車出入庫和機車換掛的作業(yè)進路將占用車站咽喉區(qū)，對車站接發(fā)列車或者其他技術(shù)作業(yè)將產(chǎn)生進路沖突。因此，如果到發(fā)線安排不合理，會導(dǎo)致機車走行時間、占用咽喉時間、列車占用到發(fā)線時間過長，嚴重影響車站接發(fā)列車能力。因此，客運站到發(fā)線運用優(yōu)化模型的后續(xù)研究應(yīng)將機車作業(yè)這一約束加入考慮，使得到發(fā)線的運用方案更好地滿足生產(chǎn)實際要求。

表2 取值描述

2.3 到發(fā)線運用優(yōu)化的研究方向

（1）到發(fā)線權(quán)值的確定。對到發(fā)線權(quán)值設(shè)定的影響因素與取值方法還需要進一步明確研究，只有到發(fā)線的權(quán)值賦值恰當，求得的方案才能客觀合理。

（2）到發(fā)線運用與相關(guān)作業(yè)的協(xié)調(diào)優(yōu)化研究。只有綜合考慮進路、機車等到發(fā)線相關(guān)作業(yè)，才能建立更加符合實際的到發(fā)線運用優(yōu)化模型，進而提高到發(fā)線運用方案的可行性。

（3）求解算法研究。研究更好的模型求解算法，從而保證能更快更準確地得到滿意的解，提高解決實際問題的能力。

3 結(jié)束語

制定科學合理的到發(fā)線運用計劃，優(yōu)化安排列車的接發(fā)順序和位置是應(yīng)對目前客運專線車站接發(fā)旅客列車數(shù)量成倍增長、到發(fā)線能力日趨緊張的狀況，保障行車安全，提高行車效率的關(guān)鍵[22]。以上從模型種類、求解算法、目標函數(shù)與約束條件 3 個方面，對客運站到發(fā)線運用模型的現(xiàn)有研究成果進行的綜合分析，為到發(fā)線運用優(yōu)化的進一步研究提供參考。

[1] 李宇航. 大型客運站高峰期到發(fā)線運用優(yōu)化方案研究[D].北京：北京交通大學，2010.

[2] 何 林，呂紅霞. 高速鐵路車站到發(fā)線運用優(yōu)化研究[J]. 鐵道運輸與經(jīng)濟，2012，34(18)：47-50，66.

[3] 陳建鑫. 高速客運站到發(fā)線運用優(yōu)化安排[J]. 科技論壇，2008(1)：26，73.

[4] 呂紅霞，倪少權(quán)，紀洪業(yè). 技術(shù)站調(diào)度決策支持系統(tǒng)的研究——到發(fā)線的合理使用[J]. 西南交通大學學報，2000，35 (3)：255-258.

[5] 呂紅霞，何大可，陳 韜. 基于蟻群算法的客運站到發(fā)線運用計劃編制方法[J]. 西南交通大學學報，2008，43(2)：153-158.

[6] 郭 莉，呂紅霞，陳煥云. 基于遺傳算法的鐵路本站到發(fā)線運用優(yōu)化研究[J]. 西南交通大學學報，2005，31(1)：28-31.

[7] 郭吉安，石紅國. 客運專線與既有線銜接車站到發(fā)線運用優(yōu)化研究[J]. 交通運輸工程與信息學報，2012，10(2)：132-136.

[8] 雷定猷，王 棟，劉明翔. 客運站股道運用優(yōu)化模型及算法[J]. 交通運輸工程學報，2007，7(5)：84-87.

[9] 高 建. 基于模擬退火算法的客運站到發(fā)線運用優(yōu)化研究[J]. 交通科技與經(jīng)濟，2011(4)：73-75.

[10] 林志安，潘玲巧. 基于 Memetic 算法的客運站到發(fā)線分配問題研究[J]. 蘭州交通大學學報，2008，27(6)：80-82.

[11] 林志安，潘玲巧. 鐵路客運站到發(fā)線分配問題研究[J]. 鐵道運輸與經(jīng)濟，2010，32(10)：58-61.

[12] 喬瑞軍，朱曉寧，張?zhí)靷? 客運專線車站到發(fā)線運用多目標優(yōu)化模型[J]. 北京交通大學學報，2012，36(3)：57-64.

[13] 喬瑞軍. 客運專線車站接發(fā)車進路選擇與調(diào)整問題研究[D]. 北京：北京交通大學，2012.

[14] Biilionnet A. Using Integer Programming to Solve the Train-Piatforming Problem[J]. Transportation Science，2003，37(2)：213-222.

[15] 張英貴，雷定猷，劉明翔. 鐵路車站股道運用排序模型與算法[J]. 中國鐵道科學，2010，31(2)：96-99.

[16] 張英貴. 鐵路客運站股道運用優(yōu)化方法與應(yīng)用研究[D]. 長沙：中南大學，2012.

[17] Kroon L J，Romeijn H E，Zwaneveld P J. Routing Trains Through Railway Stations：Complexity Issues[J]. European Journal of Operational Research，1997，98(1)：458-498.

[18] 朱 亮，周浪雅，諸葛恒英. 大型客運站到發(fā)線運用及進路決策模型研究[J]. 鐵道運輸與經(jīng)濟，2013，35(6)：46-51.

[19] Cardillo D D L，Mione N. k L-list Colouring of Graphs[J].European Journal of Operational Research，1998，106(1)：160-164.

[20] D’Ariano A. Improving Real-Time Train Dispatching Models，Algorithms and Applications[D]. The Netherlands：Delft University of technology，2008.

[21] 夏 明，周磊山，樂逸祥. 客專大站到發(fā)線運用隨機機會約束模型與算法研究[J]. 物流技術(shù)，2010 (4)：54-58.

[22] 李 琦. 高速鐵路大型客運站到發(fā)線運用優(yōu)化研究[D]. 成都：西南交通大學，2012.