客運(yùn)站到發(fā)線運(yùn)用優(yōu)化研究綜述

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

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

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

1 研究現(xiàn)狀

1.1 模型種類

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

目前，到發(fā)線運(yùn)用優(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]以方便旅客上下車為目標(biāo)，建立高速鐵路車站到發(fā)線運(yùn)用的一次 0-1 規(guī)劃模型，并利用遺傳算法進(jìn)行求解。陳建鑫等[3]所建模型也為一次 0-1 規(guī)劃模型，所不同是其將到發(fā)線的運(yùn)用當(dāng)作指派問(wèn)題進(jìn)行研究，采用指派問(wèn)題常用的匈牙利算法進(jìn)行求解。

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

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

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

1.1.2 排序模型

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

1.1.3 其他模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（6）通過(guò)列車安排于正線。

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

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

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

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

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

1.3 模型算法

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

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

直接求解即是尋找有效的搜索尋優(yōu)算法直接對(duì)所建模型進(jìn)行求解。客運(yùn)站到發(fā)線運(yùn)用優(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)文獻(xiàn)，統(tǒng)計(jì)得出到發(fā)線運(yùn)用優(yōu)化模型常用算法情況如圖 1 所示，遺傳算法與分枝定界算法在到發(fā)線運(yùn)用模型中使用頻率較高，而禁忌搜索算法與蟻群算法使用較少，后續(xù)研究者可以嘗試這 2 類算法的探索研究。

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

2 研究評(píng)述

2.1 參數(shù) Cij 的確定

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

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

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

表2 取值描述

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

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

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

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

3 結(jié)束語(yǔ)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[16] 張英貴. 鐵路客運(yùn)站股道運(yùn)用優(yōu)化方法與應(yīng)用研究[D]. 長(zhǎng)沙：中南大學(xué)，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] 朱 亮，周浪雅，諸葛恒英. 大型客運(yùn)站到發(fā)線運(yùn)用及進(jìn)路決策模型研究[J]. 鐵道運(yùn)輸與經(jīng)濟(jì)，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] 夏 明，周磊山，樂(lè)逸祥. 客專大站到發(fā)線運(yùn)用隨機(jī)機(jī)會(huì)約束模型與算法研究[J]. 物流技術(shù)，2010 (4)：54-58.

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