多階段空車(chē)調(diào)整方法在車(chē)流推算系統(tǒng)中的應(yīng)用研究

單 武

（國(guó)家鐵路局 信息中心，北京 100891）

多階段空車(chē)調(diào)整方法在車(chē)流推算系統(tǒng)中的應(yīng)用研究

單 武

（國(guó)家鐵路局 信息中心，北京 100891）

本文所研究的空車(chē)調(diào)整模型屬于鐵路運(yùn)輸信息集成平臺(tái)下的車(chē)流推算系統(tǒng)。車(chē)流推算模型能夠比較準(zhǔn)確地給出在多階段路網(wǎng)中車(chē)站空車(chē)的需求量和提供量。針對(duì)鐵路網(wǎng)絡(luò)空車(chē)調(diào)整問(wèn)題的動(dòng)態(tài)變化特性，建立了多階段動(dòng)態(tài)空車(chē)調(diào)整模型，模型的目標(biāo)函數(shù)考慮了與時(shí)間因素相關(guān)的空車(chē)滯留費(fèi)用和需求未滿(mǎn)足懲罰費(fèi)用等相關(guān)費(fèi)用，設(shè)計(jì)了模擬退火的啟發(fā)式算法并進(jìn)行了求解。對(duì)一個(gè)簡(jiǎn)單的路網(wǎng)進(jìn)行了驗(yàn)證，結(jié)果表明，該模型及算法能夠較好地解決動(dòng)態(tài)變化環(huán)境下的空車(chē)調(diào)整問(wèn)題。

鐵路運(yùn)輸；多階段空車(chē)調(diào)整；時(shí)空服務(wù)網(wǎng)絡(luò)；鐵路路網(wǎng)；模擬退火算法；車(chē)流推算系統(tǒng)

由于鐵路貨物運(yùn)輸供需關(guān)系的不平衡性，導(dǎo)致鐵路網(wǎng)（簡(jiǎn)稱(chēng)：路網(wǎng)）中有些車(chē)站的裝車(chē)大于卸車(chē)，而有些車(chē)站的卸車(chē)大于裝車(chē)。卸車(chē)大于裝車(chē)的車(chē)站會(huì)產(chǎn)生多余的空車(chē)，而裝車(chē)大于卸車(chē)的車(chē)站則需要空車(chē)，為了平衡運(yùn)輸資源，加快貨源的流通，充分利用路網(wǎng)，需要將多余的空車(chē)調(diào)配到需要空車(chē)的車(chē)站。

空車(chē)調(diào)整是車(chē)流推算中一個(gè)相對(duì)復(fù)雜的問(wèn)題，國(guó)內(nèi)外很多的學(xué)者對(duì)其進(jìn)行了深入的研究。文獻(xiàn)[1]考慮了能力約束條件下的空車(chē)調(diào)配問(wèn)題，建立了空車(chē)調(diào)配數(shù)學(xué)模型，并設(shè)計(jì)分步優(yōu)化迭代算法進(jìn)行求解。文獻(xiàn)[2]考慮了滯留費(fèi)用對(duì)于空車(chē)調(diào)配問(wèn)題的影響，作者構(gòu)建了基于貨物滯留費(fèi)用的鐵路空車(chē)調(diào)配多品類(lèi)整數(shù)規(guī)劃模型。文獻(xiàn)[3]研究了考慮時(shí)間因素的空車(chē)調(diào)配優(yōu)化問(wèn)題。國(guó)外空車(chē)調(diào)整的研究主要解決的是車(chē)輛規(guī)模的問(wèn)題（fleet sizing problem），研究的方法主要有線(xiàn)性規(guī)劃算法、隨機(jī)優(yōu)化算法和模擬仿真算法等。文獻(xiàn)[4]構(gòu)建了多階段鐵路貨運(yùn)車(chē)輛規(guī)模模型，并采用模擬退火算法進(jìn)行求解。文獻(xiàn)[5]同時(shí)研究了需求不確定的情況下考慮了車(chē)隊(duì)規(guī)模和貨物車(chē)輛分配問(wèn)題，采用了兩階段優(yōu)化算法對(duì)隨機(jī)模型進(jìn)行了求解。文獻(xiàn)[6]假設(shè)在未來(lái)需求不確定的情況下，考慮包含多種車(chē)輛類(lèi)型的車(chē)輛規(guī)模問(wèn)題，作者設(shè)計(jì)了動(dòng)態(tài)規(guī)劃和黃金分割相結(jié)合的算法進(jìn)行求解。本文較以往研究不同，問(wèn)題的提出是基于實(shí)際的車(chē)流推算應(yīng)用，且采用了多階段的空車(chē)調(diào)配模型，相對(duì)于以往單一階段的分配模型，空車(chē)調(diào)配的時(shí)間更精確，符合了鐵路未來(lái)精細(xì)化管理的方向。

1 空車(chē)調(diào)整模型輸入和輸出介紹

為了實(shí)現(xiàn)鐵路運(yùn)輸精細(xì)化管理，提高信息化水平，鐵路建設(shè)了鐵路運(yùn)輸信息集成平臺(tái)。該平臺(tái)通過(guò)與既有信息系統(tǒng)交換數(shù)據(jù)以及處理站段報(bào)告事件，整合列車(chē)、車(chē)輛、貨物等數(shù)據(jù)，匯集形成面向貨運(yùn)領(lǐng)域的集中數(shù)據(jù)環(huán)境。

車(chē)流推算系統(tǒng)（CFCS）正是在集成平臺(tái)數(shù)據(jù)環(huán)境下的開(kāi)發(fā)應(yīng)用，而車(chē)流推算過(guò)程中又不可避免的需要研究空車(chē)調(diào)整問(wèn)題。CFCS采集集成平臺(tái)的數(shù)據(jù)，通過(guò)推算模型并結(jié)合次日承認(rèn)車(chē)計(jì)劃能夠比較準(zhǔn)確地預(yù)測(cè)次日時(shí)間段內(nèi)車(chē)站的空車(chē)提供量或者車(chē)站的空車(chē)需求量，為空車(chē)調(diào)整提供輸入條件。

車(chē)流推算模型與空車(chē)調(diào)整模型的關(guān)系如圖1所示。集成平臺(tái)提供的數(shù)據(jù)經(jīng)過(guò)車(chē)流推算模型處理后為空車(chē)調(diào)整模型提供必要的輸入條件：（1）路網(wǎng)中車(chē)站的空車(chē)供給量；（2）路網(wǎng)中車(chē)站的空車(chē)需求量；（3）鐵路網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)；（4）計(jì)劃的時(shí)間階段。空車(chē)調(diào)整模型主要輸出結(jié)果為：（1）每個(gè)階段空車(chē)調(diào)整的數(shù)量；（2）空車(chē)提供站的空車(chē)滯留數(shù)量；（3）空車(chē)需求站的空車(chē)延誤數(shù)量。

圖1 空車(chē)調(diào)整模型的輸入輸出內(nèi)容

2 空車(chē)調(diào)整模型

2.1 問(wèn)題描述

空車(chē)調(diào)整問(wèn)題就是在鐵路運(yùn)輸系統(tǒng)中將空車(chē)從空車(chē)多余車(chē)站合理分配到空車(chē)需求車(chē)站的問(wèn)題。空車(chē)調(diào)整可以考慮單車(chē)種或者多車(chē)種，如果考慮多種類(lèi)型的空車(chē)，那么就需要考慮空車(chē)提供與需求的車(chē)種匹配以及車(chē)種替代等問(wèn)題，本文僅考慮單種空車(chē)類(lèi)型。車(chē)輛在兩個(gè)車(chē)站之間的運(yùn)行時(shí)間需要根據(jù)路網(wǎng)的徑路結(jié)構(gòu)來(lái)決定。

2.2 數(shù)學(xué)模型

2.2.1 變量定義

N1：網(wǎng)絡(luò)中所有的空車(chē)提供站點(diǎn)集合；

N2：網(wǎng)絡(luò)中所有的空車(chē)需求站點(diǎn)集合；

T：多階段（時(shí)間階段）集合， t=0,1,…,Te；

Cj：空車(chē)需求站單位空車(chē)滿(mǎn)足所得收益，j∈N2；

ECij：?jiǎn)蝹€(gè)空車(chē)單位距離走行的價(jià)值，i∈N1，j∈N2；

Lij：空車(chē)提供站i到空車(chē)需求站j的距離，i∈N1,j∈N2；

HCi：?jiǎn)蝹€(gè)空車(chē)在一個(gè)時(shí)間階段內(nèi)的滯留費(fèi)用；

PCj：空車(chē)需求站點(diǎn)未滿(mǎn)足需求的懲罰值，j∈N2；

ttij：從空車(chē)提供點(diǎn)i運(yùn)行到空車(chē)需求點(diǎn)j的運(yùn)行時(shí)間；

Pi(t)：在時(shí)間階段t內(nèi)空車(chē)提供點(diǎn)i提供的空車(chē)數(shù)量；

Di(t)：在時(shí)間階段t內(nèi)空車(chē)需求點(diǎn)j需要的空車(chē)數(shù)量；

αij(τ,t)：空車(chē)從起點(diǎn)出發(fā)的時(shí)間階段為τ，到達(dá)終點(diǎn)的時(shí)間階段為t，且τ≤t，則該值為1，否則為0；

χij(t)：表示時(shí)間階段t的空車(chē)調(diào)配的量；

vi(t)：表示時(shí)間階段t末空車(chē)產(chǎn)生站剩余的空車(chē)；

ωi(t)：表示時(shí)間階段t的空車(chē)滯留的量；

σi(t)：表示時(shí)間階段t的空車(chē)不滿(mǎn)足的量。

2.2.2 數(shù)學(xué)模型

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

約束條件：

目標(biāo)函數(shù)（1）：表示空車(chē)調(diào)配計(jì)劃的綜合收益，為多目標(biāo)決策函數(shù)，包含空車(chē)調(diào)配的純收益最大化，調(diào)配的費(fèi)用支出的最小化，費(fèi)用包含：空走費(fèi)用、滯留費(fèi)用和需求未滿(mǎn)足的懲罰費(fèi)用。約束條件（2）：表示任意空車(chē)需求站在任意時(shí)間段內(nèi)未滿(mǎn)足的需求數(shù)量。約束條件（3）：表示任意空車(chē)提供站在任意的時(shí)間段末所剩余的空車(chē)數(shù)量。約束條件（4）：表示任意空車(chē)提供站在任意的時(shí)間段內(nèi)所滯留的空車(chē)數(shù)量，它是由上一個(gè)階段剩余的空車(chē)數(shù)量減去本階段調(diào)配的空車(chē)數(shù)量得出的，也就是說(shuō)在上一個(gè)階段剩余的空車(chē)如果在本階段內(nèi)還沒(méi)有被調(diào)配就認(rèn)為這些空車(chē)在本階段內(nèi)出現(xiàn)了滯留。約束條件（5）：表示決策變量和中間變量的非負(fù)性質(zhì)。

3 算法

由于該問(wèn)題復(fù)雜程度隨著網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模和時(shí)間階段規(guī)模增長(zhǎng)呈指數(shù)級(jí)的增長(zhǎng)，較難得到多項(xiàng)式求解算法，因此采用模擬退火算法。模擬退火算法（SA，Simulated Annealing）是基于Monte-Carlo迭代求解策略的一種隨機(jī)尋優(yōu)算法，其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過(guò)程與一般組合優(yōu)化問(wèn)題之間的相似性。模擬退火算法是通過(guò)賦予搜索過(guò)程一種時(shí)變且最終趨于零的概率突跳性，從而可有效避免陷入局部極小并最終趨于全局最優(yōu)的串行結(jié)構(gòu)的優(yōu)化算法。空車(chē)調(diào)整問(wèn)題也是一般性的組合優(yōu)化問(wèn)題，因此可以利用模擬退火算法進(jìn)行優(yōu)化求解。

3.1 初始解

用貪心的局部?jī)?yōu)化算法取得模擬退火算法的初始解。

3.2 鄰域解

鄰域解的產(chǎn)生是根據(jù)隨機(jī)選擇空車(chē)調(diào)整量χij(t)，然后在此量的基礎(chǔ)上隨機(jī)浮動(dòng)Δχij(t)，浮動(dòng)量位于區(qū)間[0.3·χij(t)，-0.3·χij(t)]。

3.3 冷卻策略

每次迭代溫度采用下面的函數(shù)進(jìn)行控制：

接受函數(shù)采用下面的隨機(jī)函數(shù)確定：

從公式（7）可以看出，較差解可以接受的概率由當(dāng)前循環(huán)設(shè)置的溫度T和目標(biāo)值的變差量ΔZ共同決定，在溫度較高時(shí)，較差解被接受的概率較高；溫度較低時(shí)，較差解被接受的概率較低。

3.4 終結(jié)條件

算法的終結(jié)條件為迭代時(shí)的溫度下降到設(shè)定溫度時(shí)或者迭代到一定的次數(shù)時(shí)目標(biāo)函數(shù)還沒(méi)有得到優(yōu)化。

4 算例

考慮簡(jiǎn)單的路網(wǎng)結(jié)構(gòu)，并假定路網(wǎng)中節(jié)點(diǎn)S1～S4為空車(chē)提供點(diǎn)，S6～S9為空車(chē)需求點(diǎn)，具體信息如表1～表3所示，其中，表2及表3中的空車(chē)需求量和提供量都為經(jīng)驗(yàn)假設(shè)模擬數(shù)據(jù)。需求節(jié)點(diǎn)考慮的時(shí)間階段從T2開(kāi)始，因?yàn)樘峁┕?jié)點(diǎn)的時(shí)間階段從T1開(kāi)始，加上兩點(diǎn)間的運(yùn)輸時(shí)間，因此空車(chē)到需求點(diǎn)最早也要到T2階段。

表1 路網(wǎng)中車(chē)站之間的最短運(yùn)行時(shí)間

表2 空車(chē)需求點(diǎn)在多階段的空車(chē)需求量

表3 空車(chē)提供點(diǎn)在多階段的空車(chē)提供量

4.1 輸入條件參數(shù)

目標(biāo)函數(shù)中所涉及的費(fèi)用參數(shù)：?jiǎn)挝豢哲?chē)每小時(shí)走行費(fèi)用為500元；單位空車(chē)需求滿(mǎn)足后，所產(chǎn)生的效益為10 000元；單位空車(chē)單個(gè)時(shí)間階段的空車(chē)滯留費(fèi)用為500元；單位空車(chē)單個(gè)時(shí)間階段的空車(chē)未滿(mǎn)足需求的費(fèi)用為1 000元。每個(gè)時(shí)間階段的時(shí)長(zhǎng)為3 h。模擬退火算法的參數(shù)設(shè)置如表4所示，參數(shù)值的設(shè)置根據(jù)經(jīng)驗(yàn)值得到，并結(jié)合算例本身進(jìn)行了驗(yàn)算修正。

表4 模擬退火算法參數(shù)設(shè)置

4.2 計(jì)算結(jié)果

通過(guò)Java程序?qū)崿F(xiàn)了模擬退火算法。模擬退火算法迭代優(yōu)化結(jié)果如圖2所示。從圖中可以看出，前100次迭代目標(biāo)值收斂的速度較快，100～150次迭代目標(biāo)收益有緩慢增長(zhǎng)，而從150～350次的迭代中，收益穩(wěn)定維持在7.55 千萬(wàn)元左右，并沒(méi)有明顯的增加，因此，可以認(rèn)為在150次迭代后的空車(chē)調(diào)配方案已經(jīng)達(dá)到了優(yōu)化解，可以作為優(yōu)化的空車(chē)調(diào)整方案。

圖2 模擬退火算法的迭代優(yōu)化圖

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

在車(chē)流推算研究的大背景下，本文建立了多階段空車(chē)調(diào)整優(yōu)化模型，該模型能夠?qū)⒍嚯A段的空車(chē)調(diào)整綜合優(yōu)化，比較符合鐵路實(shí)際生產(chǎn)中多階段計(jì)劃的綜合調(diào)優(yōu)，并采用模擬退火算法進(jìn)行優(yōu)化，結(jié)果表明，該模型在車(chē)流推算系統(tǒng)中能較好地處理空車(chē)調(diào)整的問(wèn)題。

[1]林柏梁，喬國(guó)會(huì).基于線(xiàn)路能力約束下的鐵路空車(chē)調(diào)配迭代算法[J].中國(guó)鐵道科學(xué)，2008，29（1）：93-96.

[2]曹學(xué)明，林柏梁.基于滯留費(fèi)用的空車(chē)調(diào)配優(yōu)化方法[J].鐵道學(xué)報(bào)，2007，29（4）：18-22.

[3]程學(xué)慶，陸一新，尹傳忠，等.基于時(shí)間窗的鐵路空車(chē)調(diào)配優(yōu)化模型及求解[J].中國(guó)鐵道科學(xué)，2007，28（6）：113-116.

[4]Hamid Reza Sayarshad,Keivan Ghoseiri.A simulated annealing approach for the multi-periodic rail-car feet sizing problem[J].Computers &Operations Research,36 (2009):1789-1799.

[5]Hamid Reza Sayarshad ,Reza Tavakkoli-Moghaddam.Solving a multi periodic stochastic model of the rail-car feet sizing by two-stage optimization formulation[J].Applied Mathematical Modelling,34 (2010):1164-1174.

[6]Ryan Loxton ,Qun Lin,Kok Lay Teo.A stochastic fleet composition problem[J].Computers &Operations Research,39 (2012):3177-3184.

責(zé)任編輯 付 思

Railway multi-stage empty car adjustment method applied to Car Flow Estimation System

SHAN Wu
( Information Center,National Railway Administration of People’s Republic of China,Beijing 100891,China)

Empty car adjustment model researched in this paper was part of Car Flow Estimation System.The car fow estimation model could be used to calculate the demand and availability of empty car precisely on different time periods.According to the dynamic change characteristics of empty car adjustment problem of railway network,a dynamic multi-stage empty car adjustment model was set up.The empty car stranded costs and unsatisfed demand penalty costs related to time factor were considered in the object function.The Heuristic Algorithm of simulated annealing was designed to solve the function.Finally,a simple network was taken to verify the model,and the results indicated that the model could handle the empty car adjustment problem under dynamic environment.

railway transportation;multi-stage empty car adjustment;service network of time and space;railway network;Heuristic Algorithm;Car Flow Estimation System

U292∶TP39

A

1005-8451（2016）06-0005-04

2015-12-20

單 武，高級(jí)工程師。