多階段空車調整方法在車流推算系統中的應用研究

單 武

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

多階段空車調整方法在車流推算系統中的應用研究

單 武

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

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

鐵路運輸；多階段空車調整；時空服務網絡；鐵路路網；模擬退火算法；車流推算系統

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

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

1 空車調整模型輸入和輸出介紹

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

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

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

圖1 空車調整模型的輸入輸出內容

2 空車調整模型

2.1 問題描述

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

2.2 數學模型

2.2.1 變量定義

N1：網絡中所有的空車提供站點集合；

N2：網絡中所有的空車需求站點集合；

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

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

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

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

HCi：單個空車在一個時間階段內的滯留費用；

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

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

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

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

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

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

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

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

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

2.2.2 數學模型

目標函數：

約束條件：

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

3 算法

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

3.1 初始解

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

3.2 鄰域解

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

3.3 冷卻策略

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

接受函數采用下面的隨機函數確定：

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

3.4 終結條件

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

4 算例

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

表1 路網中車站之間的最短運行時間

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

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

4.1 輸入條件參數

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

表4 模擬退火算法參數設置

4.2 計算結果

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

圖2 模擬退火算法的迭代優化圖

5 結束語

在車流推算研究的大背景下，本文建立了多階段空車調整優化模型，該模型能夠將多階段的空車調整綜合優化，比較符合鐵路實際生產中多階段計劃的綜合調優，并采用模擬退火算法進行優化，結果表明，該模型在車流推算系統中能較好地處理空車調整的問題。

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

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

[3]程學慶，陸一新，尹傳忠，等.基于時間窗的鐵路空車調配優化模型及求解[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

單 武，高級工程師。