單 武

（國家鐵路局 信息中心，北京 100891）

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

單 武

（國家鐵路局 信息中心，北京 100891）

本文所研究的空車調(diào)整模型屬于鐵路運(yùn)輸信息集成平臺(tái)下的車流推算系統(tǒng)。車流推算模型能夠比較準(zhǔn)確地給出在多階段路網(wǎng)中車站空車的需求量和提供量。針對(duì)鐵路網(wǎng)絡(luò)空車調(diào)整問題的動(dòng)態(tài)變化特性，建立了多階段動(dòng)態(tài)空車調(diào)整模型，模型的目標(biāo)函數(shù)考慮了與時(shí)間因素相關(guān)的空車滯留費(fèi)用和需求未滿足懲罰費(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)境下的空車調(diào)整問題。

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

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

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

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

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

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

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

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

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

2.1 問題描述

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

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

2.2.1 變量定義

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

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

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

Cj：空車需求站單位空車滿足所得收益，j∈N2；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

約束條件：

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

3 算法

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

3.1 初始解

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

3.2 鄰域解

鄰域解的產(chǎn)生是根據(jù)隨機(jī)選擇空車調(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ù)還沒有得到優(yōu)化。

4 算例

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

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

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

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

4.1 輸入條件參數(shù)

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

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

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

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

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

5 結(jié)束語

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

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

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

[3]程學(xué)慶，陸一新，尹傳忠，等.基于時(shí)間窗的鐵路空車調(diào)配優(yōu)化模型及求解[J].中國鐵道科學(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í)工程師。