單 武

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

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

單 武

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

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

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

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

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

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

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

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

車流推算模型與空車調(diào)整模型的關系如圖1所示。集成平臺提供的數(shù)據(jù)經(jīng)過車流推算模型處理后為空車調(diào)整模型提供必要的輸入條件：（1）路網(wǎng)中車站的空車供給量；（2）路網(wǎng)中車站的空車需求量；（3）鐵路網(wǎng)絡拓撲結構；（4）計劃的時間階段?？哲囌{(diào)整模型主要輸出結果為：（1）每個階段空車調(diào)整的數(shù)量；（2）空車提供站的空車滯留數(shù)量；（3）空車需求站的空車延誤數(shù)量。

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

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

2.1 問題描述

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

2.2 數(shù)學模型

2.2.1 變量定義

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

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

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

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

ECij：單個空車單位距離走行的價值，i∈N1，j∈N2；

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

HCi：單個空車在一個時間階段內(nèi)的滯留費用；

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

ttij：從空車提供點i運行到空車需求點j的運行時間；

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

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

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

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

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

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

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

2.2.2 數(shù)學模型

目標函數(shù)：

約束條件：

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

3 算法

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

3.1 初始解

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

3.2 鄰域解

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

3.3 冷卻策略

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

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

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

3.4 終結條件

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

4 算例

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

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

表2 空車需求點在多階段的空車需求量

表3 空車提供點在多階段的空車提供量

4.1 輸入條件參數(shù)

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

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

4.2 計算結果

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

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

5 結束語

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

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

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

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

責任編輯 付 思

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

單 武，高級工程師。