趙 軍，張煜婷，張思宇

鐵路技術(shù)站作業(yè)計(jì)劃綜合編制的優(yōu)化模型研究

趙 軍，張煜婷，張思宇

（1. 西南交通大學(xué)，交通運(yùn)輸與物流學(xué)院，成都 611756；2. 綜合交通運(yùn)輸智能化國(guó)家地方聯(lián)合工程實(shí)驗(yàn)室，成都 611756）

本文探討鐵路技術(shù)站作業(yè)計(jì)劃中三個(gè)重要子計(jì)劃，即車流推算、調(diào)機(jī)運(yùn)用和調(diào)車線運(yùn)用計(jì)劃的綜合編制問題。首先，以給定的時(shí)間精度將計(jì)劃時(shí)段離散化為有限個(gè)時(shí)刻，并采用累積流思想刻畫車輛占用調(diào)車線的情況。進(jìn)而，以車輛在站總停留時(shí)間和對(duì)調(diào)車線占用總懲罰最小為目標(biāo)，將該綜合問題建立為整數(shù)非線性規(guī)劃模型。根據(jù)模型特點(diǎn)，利用既有線性化技術(shù)，將該模型轉(zhuǎn)換為整數(shù)線性規(guī)劃模型。最后，計(jì)算分析結(jié)果表明，所提出的線性模型可正確刻畫技術(shù)站作業(yè)計(jì)劃綜合編制的特點(diǎn)和要求，采用合理的時(shí)間精度設(shè)置，該模型可在合理時(shí)間內(nèi)找到高質(zhì)量的解。

鐵路運(yùn)輸；作業(yè)計(jì)劃；數(shù)學(xué)優(yōu)化；技術(shù)站；綜合編制

0 引 言

技術(shù)站是鐵路貨物列車的生產(chǎn)場(chǎng)所，其工作組織的質(zhì)量對(duì)鐵路貨物運(yùn)輸組織的各個(gè)環(huán)節(jié)產(chǎn)生影響。在現(xiàn)場(chǎng)，技術(shù)站的日常工作通過編制各種類型的作業(yè)計(jì)劃來組織。階段計(jì)劃是技術(shù)站重要的作業(yè)計(jì)劃之一，主要解決3~4 h計(jì)劃時(shí)段內(nèi)的車流推算、調(diào)機(jī)運(yùn)用、到發(fā)線運(yùn)用和調(diào)車線運(yùn)用等子問題，其中前兩個(gè)子問題常合稱為配流問題。各子問題相互聯(lián)系和影響，共同決定技術(shù)站階段計(jì)劃的可行性。研究作業(yè)計(jì)劃綜合編制的優(yōu)化方法，同時(shí)解決多個(gè)關(guān)聯(lián)的子問題，對(duì)于提高技術(shù)站作業(yè)計(jì)劃編制質(zhì)量、保證技術(shù)站工作組織效率具有重要意義。

國(guó)外對(duì)技術(shù)站作業(yè)計(jì)劃編制開展了一定研究。早期的研究主要關(guān)注作業(yè)計(jì)劃中各子問題的優(yōu)化。例如，對(duì)于車流推算問題，Bektas[1]引入時(shí)間窗，建立了空車流重配的0-1線性規(guī)劃模型。Boysen[2]研究了基本車流推算問題，提出三種車流分配策略，并設(shè)計(jì)定向搜索算法求解。針對(duì)調(diào)車線運(yùn)用問題，Bohlin[3]以二次解體車輛數(shù)最少為目標(biāo)，分別建立了基于生成列和弧索引的整數(shù)線性規(guī)劃模型。Gestrelius[4]進(jìn)一步約束出發(fā)列車按站順編組，提出了基于生成列的整數(shù)規(guī)劃模型。近來，國(guó)外對(duì)技術(shù)站作業(yè)計(jì)劃的集成編制進(jìn)行了探討。Gestrelius[5]對(duì)技術(shù)站車流推算與調(diào)車線運(yùn)用進(jìn)行綜合優(yōu)化，以最小化二次編組車數(shù)和股道占用成本為目標(biāo)，建立了整數(shù)規(guī)劃模型。Haahr[6]提出了啟發(fā)式求解框架，綜合優(yōu)化技術(shù)站解體排序、編組排序和調(diào)車線運(yùn)用三個(gè)子問題。對(duì)于相同問題，Raut[7]建立了混合整數(shù)線性規(guī)劃模型，并提出了滾動(dòng)時(shí)域求解算法。

國(guó)內(nèi)針對(duì)技術(shù)站作業(yè)計(jì)劃編制中的各子問題開展了許多工作。對(duì)于配流問題，薛鋒[8]設(shè)計(jì)了GAAA算法，首先生成解體方案的集合，其次以蟻群算法對(duì)以上解集進(jìn)行檢驗(yàn)，得到配流成功車數(shù)最多的配流方案。黎浩東[9]考慮不同滿軸約束條件，以階段內(nèi)配流代價(jià)最小為目標(biāo)，建立混合整數(shù)線性規(guī)劃模型，并設(shè)計(jì)和聲搜索算法進(jìn)行求解。趙軍[10]以車流在站總停留時(shí)間最小為目標(biāo)，構(gòu)造多解多編運(yùn)營(yíng)條件下的混合整數(shù)線性規(guī)劃模型，并設(shè)計(jì)基于隨機(jī)鍵編碼的有偏遺傳算法求解。馬亮[11]將問題分為初步和二次配流兩部分，首先采用混合算法獲取初步配流方案，然后設(shè)計(jì)貪婪算法對(duì)配流方案進(jìn)行優(yōu)化。對(duì)于調(diào)車線運(yùn)用問題，黎浩東[12]以最小化整理線數(shù)量和出發(fā)列車總連掛鉤數(shù)為目標(biāo)，構(gòu)建0-1線性規(guī)劃模型。馬亮[13]定義股道活用原則，基于此建立了使調(diào)車場(chǎng)股道混亂度最小和占用優(yōu)先級(jí)最大的整數(shù)優(yōu)化模型，并設(shè)計(jì)啟發(fā)式回溯算法求解。同時(shí)，國(guó)內(nèi)對(duì)技術(shù)站作業(yè)計(jì)劃綜合編制也開展了一定工作。薛鋒[14]建立綜合考慮配流、到發(fā)線運(yùn)用和取送車作業(yè)的混合整數(shù)非線性規(guī)劃模型，并采用ECGACO算法求解。Shi[15]對(duì)配流和調(diào)車線運(yùn)用綜合問題，提出了以最小化車輛在站停留時(shí)間為目標(biāo)函數(shù)的混合整數(shù)規(guī)劃模型，并設(shè)計(jì)啟發(fā)式算法確定解體順序。

綜上，國(guó)內(nèi)外主要關(guān)注技術(shù)站作業(yè)計(jì)劃編制中的個(gè)別子問題，對(duì)作業(yè)計(jì)劃綜合編制的探討不多。在既有的作業(yè)計(jì)劃綜合優(yōu)化研究中，國(guó)外采用的優(yōu)化方案不適用我國(guó)實(shí)際，國(guó)內(nèi)的相關(guān)工作通常把調(diào)車線運(yùn)用規(guī)則進(jìn)行簡(jiǎn)化處理。然而，實(shí)際技術(shù)站工作中，各技術(shù)作業(yè)間存在強(qiáng)的時(shí)空因果關(guān)系，忽略這種關(guān)系將會(huì)給模型在現(xiàn)場(chǎng)的運(yùn)用帶來影響。Shi[15]建立的配流與調(diào)車線運(yùn)用綜合模型對(duì)本文有所啟發(fā)，但仍有可提升的空間。文中規(guī)定各去向的車流只能嚴(yán)格按照固定的方案使用調(diào)車線，不允許調(diào)車線靈活運(yùn)用。固定調(diào)車線運(yùn)用方案固然可減輕模型的建模難度并便于現(xiàn)場(chǎng)實(shí)施，但與此同時(shí)可能丟掉調(diào)車線運(yùn)用的靈活性，影響作業(yè)計(jì)劃的質(zhì)量，還有可能因調(diào)車線能力緊張，使得作業(yè)計(jì)劃不可行。

結(jié)合技術(shù)站作業(yè)計(jì)劃編制的特點(diǎn)和要求，本文以車輛作為車流推算的最小單元，對(duì)文獻(xiàn)[10]中的配流模型進(jìn)行拓展；考慮調(diào)車線固用與活用相結(jié)合，根據(jù)文獻(xiàn)[7]提出的累積流思想刻畫車輛占用調(diào)車線情況；進(jìn)而以車輛在站總停留時(shí)間和對(duì)調(diào)車線占用懲罰最小為目標(biāo)函數(shù)，提出技術(shù)站車流推算、調(diào)機(jī)運(yùn)用和調(diào)車線運(yùn)用綜合問題的整數(shù)非線性規(guī)劃模型，并借助既有線性化技術(shù)將該模型轉(zhuǎn)換為線性模型；最后設(shè)計(jì)算例對(duì)模型的正確性進(jìn)行驗(yàn)證。

1 問題描述

本文對(duì)具有一套改編系統(tǒng)的技術(shù)站在給定計(jì)劃時(shí)間內(nèi)的作業(yè)計(jì)劃綜合編制問題進(jìn)行研究。車輛在站按到達(dá)場(chǎng)—駝峰—調(diào)車場(chǎng)—出發(fā)場(chǎng)的順序依次流動(dòng)，列車到達(dá)車站后根據(jù)安排好的接車進(jìn)路進(jìn)入到達(dá)場(chǎng)指定股道等待后續(xù)技術(shù)檢查。列檢完畢的到達(dá)列車由空閑解體調(diào)機(jī)推上駝峰進(jìn)行解體，在解體溜放過程中，脫鉤的車輛溜入指定調(diào)車線，與后續(xù)進(jìn)入線路的車輛集結(jié)成列。待完成集結(jié)作業(yè)后，空閑編組調(diào)機(jī)按一定順序連掛調(diào)車線上集結(jié)完成的車輛以編成出發(fā)列車，再轉(zhuǎn)至出發(fā)場(chǎng)指定線路，等待進(jìn)行出發(fā)技術(shù)檢查作業(yè)及發(fā)車作業(yè)。

在現(xiàn)場(chǎng)，技術(shù)站通過編制作業(yè)計(jì)劃來指導(dǎo)日常運(yùn)輸生產(chǎn)，需解決幾個(gè)優(yōu)化決策問題。其中，車流推算確定到發(fā)列車間的車流接續(xù)方案，調(diào)機(jī)運(yùn)用解決調(diào)車機(jī)車的解體、編組等調(diào)車作業(yè)計(jì)劃，到發(fā)線運(yùn)用確定到發(fā)列車對(duì)到發(fā)線的占用方案，調(diào)車線運(yùn)用解決車輛對(duì)調(diào)車線的占用方案。由車輛在站技術(shù)作業(yè)過程可知，車流推算和調(diào)機(jī)運(yùn)用決策在很大程度上決定了技術(shù)站對(duì)車輛的中轉(zhuǎn)效率和作業(yè)計(jì)劃的質(zhì)量。同時(shí)，到發(fā)線運(yùn)用和調(diào)車線運(yùn)用決策又限制了車流推算和調(diào)機(jī)運(yùn)用決策的可行性，相比于到發(fā)線，調(diào)車線是供車輛在解體完成后和編組開始前可能長(zhǎng)時(shí)間停留的場(chǎng)所，其運(yùn)用決策對(duì)車流推算和調(diào)機(jī)運(yùn)用決策的影響更為顯著。因此，本文具體研究技術(shù)站含車流推算、調(diào)機(jī)運(yùn)用和調(diào)車線運(yùn)用綜合問題的優(yōu)化方法。

綜上，本文解決的技術(shù)站作業(yè)計(jì)劃綜合編制問題可描述為：給定到達(dá)列車、到達(dá)車輛、出發(fā)列車、解體調(diào)機(jī)、編組調(diào)機(jī)和調(diào)車線等信息，以車輛在站總停留時(shí)間和對(duì)調(diào)車線占用總懲罰最小為目標(biāo)，確定到發(fā)列車車流推算方案、列車解編方案和車輛-調(diào)車線占用方案，并滿足所有的運(yùn)營(yíng)和安全規(guī)則。

2 模型構(gòu)建

2.1 符號(hào)說明

本節(jié)模型使用的集合和參數(shù)見表1，變量見表2。

表1 集合、參數(shù)定義

表2 變量定義

Tab.2 Definitions of variables

續(xù)表2

符 號(hào)含 義 當(dāng)出發(fā)列車滿長(zhǎng)時(shí)取1，否則取0 當(dāng)出發(fā)列車在時(shí)間上可接續(xù)車輛時(shí)為1，否則為0 當(dāng)出發(fā)列車經(jīng)調(diào)機(jī)kk在時(shí)刻開始編組作業(yè)時(shí)取1，否則取0 當(dāng)時(shí)，若出發(fā)列車先于出發(fā)列車編組結(jié)束取1，否則取0 出發(fā)列車的編組開始時(shí)刻 當(dāng)車輛占用調(diào)車線時(shí)取1，否則取0 從計(jì)劃時(shí)段初至?xí)r刻，累積占用調(diào)車線的車輛的總長(zhǎng)度 從計(jì)劃時(shí)段初至?xí)r刻，累積釋放調(diào)車線的車輛的總長(zhǎng)度

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

由問題描述，本文考慮車輛在站總停留時(shí)間和調(diào)車線占用總懲罰最小的目標(biāo)。一方面，技術(shù)站的運(yùn)營(yíng)目的是快速中轉(zhuǎn)車輛，給定計(jì)劃時(shí)段內(nèi)，站內(nèi)改編設(shè)備及能力有限，為加快車輛周轉(zhuǎn)速度，首要目標(biāo)應(yīng)最小化車輛在站總停留時(shí)間。另一方面，現(xiàn)場(chǎng)一般按固用與活用相結(jié)合的原則為車輛安排調(diào)車線，在能力允許的情況下，優(yōu)先為車輛安排固用的調(diào)車線，若能力不足，也應(yīng)對(duì)固定使用方案做最小調(diào)整。為反映現(xiàn)場(chǎng)的調(diào)車線運(yùn)用特點(diǎn)，引入車輛-調(diào)車線占用懲罰，并以車輛對(duì)調(diào)車線占用總懲罰最小作為次要目標(biāo)?；诖?，目標(biāo)函數(shù)表達(dá)如下：

需說明的是，在目標(biāo)函數(shù)（1）中，第二項(xiàng)次要目標(biāo)的值遠(yuǎn)小于第一項(xiàng)主要目標(biāo)的值，式（1）將這兩項(xiàng)目標(biāo)直接加在一起形成一項(xiàng)目標(biāo)，正好可反映兩個(gè)目標(biāo)的相對(duì)重要性，即在先優(yōu)化第一項(xiàng)目標(biāo)的前提下再優(yōu)化第二項(xiàng)目標(biāo)，也可避免求解多目標(biāo)優(yōu)化問題的困難。

2.3 約束條件

2.3.1 到達(dá)列車解體約束

到達(dá)列車解體約束如下：

式（2）為解體完成時(shí)刻唯一性約束，即各到達(dá)列車必須經(jīng)某臺(tái)解體調(diào)機(jī)在最早解體開始時(shí)刻后的某時(shí)刻完成解體作業(yè)。式（3）為占用調(diào)機(jī)不沖突約束，表示各解體調(diào)機(jī)在計(jì)劃時(shí)段內(nèi)各時(shí)刻至多只能完成一列到達(dá)列車的解體作業(yè)。式（4）定義了到達(dá)列車的解體完成時(shí)刻。式（5）和式（6）為占用溜放線不沖突約束，即相繼進(jìn)行解體技術(shù)作業(yè)的到達(dá)列車，其解體結(jié)束時(shí)刻至少間隔一個(gè)溜放時(shí)間。式（7）和式（8）為變量定義域約束。

2.3.2 車流推算約束

車流推算約束如下：

式（9）為車流推算唯一性約束，表示車輛只能編入一列出發(fā)列車。式（10）~（12）為出發(fā)列車滿軸約束，即未滿足滿軸要求的出發(fā)列車無法開行。式（13）~（14）為車流接續(xù)的時(shí)間約束，表示僅當(dāng)出發(fā)列車編組開始時(shí)刻不早于車輛的解體完成時(shí)刻時(shí)，允許車輛編入該出發(fā)列車。式（15）為車流接續(xù)的去向約束，即當(dāng)出發(fā)列車可吸收去向包含車輛的去向時(shí)，車輛編入出發(fā)列車為可行方案；式（16）~（18）為變量定義域約束。

2.3.3 出發(fā)列車編組約束

出發(fā)列車編組約束如下：

式（19）為編組開始時(shí)刻唯一性約束，即出發(fā)列車必須經(jīng)某臺(tái)編組調(diào)機(jī)在最晚編組開始時(shí)刻前的某時(shí)刻開始編組作業(yè)。式（20）為占用調(diào)機(jī)不沖突約束，表示一臺(tái)編組調(diào)機(jī)在計(jì)劃時(shí)段內(nèi)各時(shí)刻至多只能完成一列出發(fā)列車的編組作業(yè)。式（21）定義了出發(fā)列車的編組開始時(shí)刻。式（22）和式（23）為占用峰尾牽出線不沖突約束，即相繼進(jìn)行編組技術(shù)作業(yè)的出發(fā)列車，其編組結(jié)束時(shí)刻至少間隔一個(gè)轉(zhuǎn)場(chǎng)時(shí)間。式（24）~（26）為變量定義域約束。

2.3.4 調(diào)車線運(yùn)用約束

調(diào)車線運(yùn)用約束如下：

2.4 優(yōu)化模型

綜上，鐵路技術(shù)站作業(yè)計(jì)劃綜合編制問題可構(gòu)建為以下優(yōu)化模型M：

目標(biāo)函數(shù)：式（1）

s.t. 式（2）~（36）

不難看出，約束（28）~（32）中存在幾個(gè)非線性項(xiàng)，使得模型M是1個(gè)非線性模型，顯著增加了求解難度。下節(jié)依次對(duì)這些非線性約束進(jìn)行線性化，進(jìn)而提出技術(shù)站作業(yè)計(jì)劃綜合編制的線性模型。

3 模型線性化

3.1 約束（28）~（30）的線性化

由此，式（28）~（30）可轉(zhuǎn)換為以下線性約束：

3.2 約束（31）的線性化

基于此，式（31）可轉(zhuǎn)換為：

3.3 約束（32）的線性化

3.4 線性模型

綜上，模型M可轉(zhuǎn)換為以下線性模型M′：

目標(biāo)函數(shù)：式（1）

可見，模型M′是1個(gè)整數(shù)線性規(guī)劃模型，其規(guī)模隨著到達(dá)列車、到達(dá)車輛、出發(fā)列車、解體調(diào)機(jī)、編組調(diào)機(jī)、調(diào)車線和離散化時(shí)刻的數(shù)量呈多項(xiàng)式增長(zhǎng)。為求解該模型，對(duì)于小規(guī)模例子，可采用商業(yè)優(yōu)化軟件（例如CPLEX、GUROBI等）直接求解；對(duì)于大規(guī)模例子，模型規(guī)模將變大，商業(yè)軟件可能不再有效，此時(shí)還需要研究另外的求解算法。本文致力于構(gòu)建技術(shù)站作業(yè)計(jì)劃綜合編制問題的整數(shù)線性規(guī)劃模型，通過模型顯示技術(shù)站的車流推算、調(diào)機(jī)運(yùn)用和調(diào)車線運(yùn)用綜合問題可在統(tǒng)一的1個(gè)線性模型下進(jìn)行綜合優(yōu)化。因此，接下來的算例分析中，直接采用商業(yè)優(yōu)化軟件求解模型M′。

4 算例分析

4.1 算例描述與參數(shù)取值

以1個(gè)技術(shù)站0：00~3：00的階段計(jì)劃為例，驗(yàn)證所提出模型的可行性。該技術(shù)站有車流去向10個(gè)，在考慮階段內(nèi)，有到達(dá)列車4列，編號(hào)為A0~A3，其中A0表示計(jì)劃初調(diào)車場(chǎng)現(xiàn)在車，到達(dá)列車信息見表3。到達(dá)車輛185輛，設(shè)定各到達(dá)列車中車輛按去向分組且按去向的編號(hào)遞增排列，假設(shè)各輛車總重80 t，換長(zhǎng)1.1，簡(jiǎn)便起見，省略具體到達(dá)車輛信息。有候選出發(fā)列車4列，編號(hào)為D1~D4，各列車的牽引定數(shù)4240 t（可向下波動(dòng)80 t），總換長(zhǎng)88（可向下波動(dòng)1.1），出發(fā)列車信息見表4，D1、D2和D4為小運(yùn)轉(zhuǎn)列車，允許欠軸開行。解體和編組調(diào)機(jī)各1臺(tái)，列車溜放和轉(zhuǎn)場(chǎng)時(shí)間均為0 min。有調(diào)車線10條，信息見表5。

表3 到達(dá)列車信息

Tab.3 Information of inbound trains

表4 出發(fā)列車信息

Tab.4 Information of outbound trains

表5 調(diào)車線信息

Tab.5 Information of classification tracks

以Intel（R）Core（TM）i7-7700 3.6 GHz CPU和16 GB RAM的個(gè)人電腦為計(jì)算平臺(tái)，采用MATLAB 9.0編程所提出的優(yōu)化方法，并調(diào)用軟件CPLEX 12.8對(duì)線性模型M′同前進(jìn)行求解。

4.2 計(jì)算結(jié)果及分析

車流推算方案見表6，其中，第2列為出發(fā)列車的編組內(nèi)容，由各到達(dá)列車中車輛組成，編組調(diào)機(jī)在編組過程中需將車流推算方案中指定車輛連掛成列。以出發(fā)列車D1為例，編入D1的車輛來自于到達(dá)列車A0、A1和A2，車輛編號(hào)分別是1~5、18~51和75~77。根據(jù)表6可得，所有出發(fā)列車均配流成功，其中出發(fā)列車D3滿軸出發(fā)，其余小運(yùn)轉(zhuǎn)列車欠軸出發(fā)。

到達(dá)列車解體方案見表7，其中，各到達(dá)列車的待解時(shí)間為其解體實(shí)際開始時(shí)刻減去其最早開始時(shí)刻?？梢?，到達(dá)列車解體順序與到達(dá)順序一致，即先到先解；相繼進(jìn)行解體作業(yè)的列車間，前序列車的解體結(jié)束時(shí)刻與后續(xù)列車的解體開始時(shí)刻相同，解體調(diào)機(jī)連續(xù)不間斷進(jìn)行作業(yè)，工作效率高；各到達(dá)列車待解時(shí)間較小，列車完成技檢后快速進(jìn)行解體。

表6 車流推算方案

Tab.6 Wagon-flow allocation plan

表7 到達(dá)列車解體方案

Tab.7 Classification plan of inbound trains

出發(fā)列車編組方案見表8，其中，各出發(fā)列車的待發(fā)時(shí)間等于其編組最晚結(jié)束時(shí)刻減去其實(shí)際結(jié)束時(shí)刻。從表8可看出，出發(fā)列車按出發(fā)順序先后進(jìn)行編組，事實(shí)上，由于最后一列到達(dá)列車A3已于1：20結(jié)束解體，D2、D3和D4采取其他編組順序（例如2、4和3或者3、4和2）也可獲得相同的計(jì)算結(jié)果；相繼進(jìn)行編組作業(yè)的列車間，前序列車的編組結(jié)束時(shí)刻與后續(xù)列車的編組開始時(shí)刻一致，編組調(diào)機(jī)連續(xù)不間斷進(jìn)行作業(yè)，工作效率高。

表8 出發(fā)列車編組方案

Tab.8 Assembly plan of outbound trains

調(diào)車線運(yùn)用方案如圖1所示，圖中，峰尾在右端，縱軸表示調(diào)車線，橫軸表示車輛，對(duì)于各條調(diào)車線，以車輛在線路上?？课恢秒x右端的距離表示其占用該調(diào)車線的先后順序。圖1表明，車輛均按固定使用方案占用調(diào)車線，不存在占用懲罰。例如，D2同時(shí)吸收了去向8的車輛65~74和108~117、及去向9的車輛15~17、118~130和182~185，這兩個(gè)去向的車輛分別在在其固用調(diào)車線S9和S10上集結(jié)，便于后續(xù)編組作業(yè)。此外，由于計(jì)劃時(shí)段內(nèi)不存在優(yōu)先在調(diào)車線S1、S3、S4和S5上集結(jié)的車輛，這些線路上無車輛占用。

圖1 調(diào)車線運(yùn)用方案

統(tǒng)計(jì)結(jié)果見表9，其中第三行和第四行分別為目標(biāo)函數(shù)（1）中第一項(xiàng)和第二項(xiàng)的值，即車輛在站總停留時(shí)間和對(duì)調(diào)車線占用總懲罰，第五行為獲得解的計(jì)算誤差。由表9可知，使用模型M′找到了算例的最優(yōu)解，由于車輛均可在其固用調(diào)車線上集結(jié)，無調(diào)車線占用懲罰，目標(biāo)函數(shù)值等于其第一項(xiàng)的總停留時(shí)間。對(duì)于計(jì)算時(shí)間，模型M′耗費(fèi)不到2 min將算例求解到最優(yōu)。綜上，本文所提出的線性模型可正確描述技術(shù)站作業(yè)計(jì)劃綜合編制問題，并在限制時(shí)間內(nèi)同時(shí)得到了可行的車流推算、調(diào)機(jī)運(yùn)用和調(diào)車線運(yùn)用方案。該模型可避免分步求解可能存在的不可行問題，體現(xiàn)了對(duì)技術(shù)站作業(yè)計(jì)劃進(jìn)行綜合編制是必要且可行的。

表9 統(tǒng)計(jì)結(jié)果

Tab.9 Statistics results

4.3 時(shí)間精度對(duì)結(jié)果的影響

不難看出，時(shí)間精度?對(duì)模型M′的規(guī)模和求解性能具有影響。分別取時(shí)間精度為1、5和10 min，在每個(gè)時(shí)間精度下，限定模型計(jì)算時(shí)間為3 min或求到最優(yōu)。計(jì)算結(jié)果見表10，其中，“解的質(zhì)量”指獲得解與最好解的相對(duì)誤差，該值越小，計(jì)算結(jié)果越好。

表10 時(shí)間精度的影響

Tab.10 Effect of time granularity

根據(jù)表10可知，隨著時(shí)間精度的降低，解的質(zhì)量變差，時(shí)間精度取10 min時(shí)最優(yōu)解的質(zhì)量相對(duì)于取1和5 min時(shí)的解變差1.5%。同時(shí)，時(shí)間精度越低，模型越容易求解，當(dāng)時(shí)間精度取1 min時(shí)，在180 s內(nèi)找不到可行解，此時(shí)需花810 s才能找到最優(yōu)解；當(dāng)時(shí)間精度取5和10 min時(shí)，都能在120 s以內(nèi)收斂。由此可知，時(shí)間精度同時(shí)影響模型的解質(zhì)量和計(jì)算時(shí)間，在實(shí)際實(shí)施時(shí)，應(yīng)合理設(shè)置時(shí)間精度的取值，在滿足決策時(shí)間要求的同時(shí)保證解質(zhì)量。

5 結(jié)束語

本文提出了技術(shù)站集車流推算、調(diào)機(jī)運(yùn)用和調(diào)車線運(yùn)用計(jì)劃綜合編制的優(yōu)化模型，以車輛在站總停留時(shí)間和調(diào)車線占用總懲罰最小為目標(biāo)，構(gòu)建了該綜合問題的整數(shù)非線性規(guī)劃模型，再進(jìn)一步將其轉(zhuǎn)換為整數(shù)線性規(guī)劃模型。根據(jù)算例分析結(jié)果，所提出的優(yōu)化模型可準(zhǔn)確描述技術(shù)站作業(yè)計(jì)劃綜合編制的特點(diǎn)，通過合理的時(shí)間精度設(shè)置，能夠在合理時(shí)間內(nèi)返回高質(zhì)量的計(jì)算結(jié)果。為完整刻畫原問題的要求，文中所提出的綜合優(yōu)化模型含許多時(shí)空和資源約束，使得該模型對(duì)于大規(guī)模的問題可能存在求解困難。因此，在以后的研究中需要分析該模型的特點(diǎn)，設(shè)計(jì)更有效的求解算法，以在解的質(zhì)量和計(jì)算時(shí)間上取得更好的折中效果。

[1] BEKTA? T, CRAINIC T G, MORENCY V. Improving the performance of rail yards through dynamic reassignments of empty cars[J]. Transportation Research Part C: Emerging Technologies, 2009, 17 (3): 259-273.

[2] BOYSEN N, EMDE S, FLIEDNER M. The basic train makeup problem in Shunting yards[J]. OR Spectrum, 2016, 38 (1): 207-233.

[3] BOHLIN M, GESTRELIUS S, DAHMS F, et al. Optimization methods for multistage freight train formation[J]. Transportation Science, 2016, 50 (3): 823-840.

[4] GESTRELIUS S, DAHMS F, BOHLIN M. Optimisation of simultaneous train formation and car sorting at marshalling yards[C]// RailCopenhagen.Copenhagen: Railcopenhagen Press, 2013: 1-17.

[5] GESTRELIUS S, ARONSSON M, JOBORN M, et al. Towards a comprehensive model for track allocation and roll-time scheduling at marshalling yards[J]. Journal of Rail Transport Planning & Management, 2017, 7 (3): 157-170.

[6] HAAHR J T, LUSBY R M. A matheuristic approach to integrate humping and pullout sequencing operations at railroad hump yards[J]. Networks, 2016, 67 (2): 126-138.

[7] RAUT S, SINHA S K, KHADILKAR H, et al. A rolling horizon optimisation model for consolidated hump yard operational planning[J]. Journal of Rail Transport Planning & Management, 2019, 9: 3-21.

[8] 薛鋒, 王慈光, 張展杰. 編組站配流的協(xié)調(diào)優(yōu)化算法[J]. 西南交通大學(xué)學(xué)報(bào), 2010, 45 (6): 932-937.

[9] 黎浩東, 何世偉, 景云, 等. 考慮不同滿軸約束的編組站階段計(jì)劃配流優(yōu)化[J]. 鐵道學(xué)報(bào), 2012, 34 (7): 10-17.

[10] 趙軍, 彭其淵. 單向編組站配流與調(diào)機(jī)運(yùn)用綜合問題[J]. 鐵道學(xué)報(bào), 2012, 34 (11): 1-9.

[11] 馬亮, 郭進(jìn), 陳光偉. 鐵路編組站動(dòng)態(tài)配流分層模型[J]. 中國(guó)鐵道科學(xué), 2015, 36 (2): 87-95.

[12] 黎浩東, 宋瑞, 呼志剛. 鐵路編組站分類線運(yùn)用優(yōu)化研究[J]. 鐵道學(xué)報(bào), 2015, 37 (12): 8-13.

[13] 馬亮, 張曉霞, 郭進(jìn). 基于啟發(fā)式回溯算法的鐵路編組站調(diào)車場(chǎng)調(diào)車線活用研究[J]. 鐵道學(xué)報(bào), 2016, 38 (8): 16-22.

[14] 薛鋒. 鐵路編組站配流協(xié)同優(yōu)化模型與算法[J]. 系統(tǒng)工程理論與實(shí)踐, 2013, 33 (11): 2930-2936.

[15] SHI T, ZHOU X. A mixed integer programming model for optimizing multi-level operations process in railroad yards[J]. Transportation Research Part B: Methodological, 2015, 80: 19-39

Optimization Model for the Integrated Operation Plan at Railway Technical Stations

ZHAO Jun, ZHANG Yu-ting, ZHANG Si-yu

(1. School of Transportation and Logistics, Southwest Jiaotong University, Chengdu 611756, China; 2. National United Engineering Laboratory of Integrated and Intelligent Transportation, Chengdu 611756, China)

This paper investigated the integrated design of three important sub-plans including wagon-flow allocation, engine scheduling and car-to-track assignment in the operation plan of railway technical stations. First, the planning period was discretized into a limited number of time points using a given granularity of time. The cumulative flow-based idea was used to describe the occupation of railcars on classification tracks. Then, the integrated problem was formulated as an integer nonlinear programming model with the objective of minimizing the total dwell time at station and total occupation penalty on classification tracks of railcars. According to the characteristics of the model, it was easily transformed into an integer linear programming model using existing linearization techniques. Finally, computational results show that the proposed linear model can describe correctly the characteristics and requirements for the integrated design of operation plan at technical stations. The model can find high-quality solutions within reasonable time under a reasonable setting of the granularity of time.

railway transportation; operation plan; mathematical optimization; technical station; integrated design

1672-4747（2020）04-0011-12

U292.16

A

10.3969/j.issn.1672-4747.2020.04.002

2020-02-26

中國(guó)國(guó)家鐵路集團(tuán)有限公司科技研究開發(fā)計(jì)劃課題（K2018X004）

趙軍（1986—），男，四川宜賓人，博士，副教授，研究方向?yàn)殍F路運(yùn)輸組織，E-mail：junzhao@swjtu.edu.cn

趙 軍，張煜婷，張思宇. 鐵路技術(shù)站作業(yè)計(jì)劃綜合編制的優(yōu)化模型研究[J]. 交通運(yùn)輸工程與信息學(xué)報(bào)，2020, 18(4): 11-22

（責(zé)任編輯：李愈）