基于能力約束的多車種空車動態(tài)調(diào)整方法

張紅斌，董寶田，孫遠運

(1.北京交通大學 交通運輸學院，北京 100044；2.中國鐵路信息技術中心，北京 100844)

?

基于能力約束的多車種空車動態(tài)調(diào)整方法

張紅斌1,2，董寶田1，孫遠運2

(1.北京交通大學 交通運輸學院，北京 100044；2.中國鐵路信息技術中心，北京 100844)

引入空車時空服務網(wǎng)絡來描述鐵路運輸動態(tài)變化特性，同時考慮到實際運輸生產(chǎn)中的能力約束，并據(jù)此建立了基于能力約束的動態(tài)規(guī)劃模型.模型的目標函數(shù)考慮了與時間因素相關的空車滯留費用和需求未滿足時的懲罰費用等相關費用，同時考慮了多個車種之間的替代費用.模型的能力約束條件考慮了網(wǎng)絡弧段的通過能力、空車提供站的發(fā)送空車能力和空車需求站的接收空車能力.考慮網(wǎng)絡徑路繞行的情況，設計了融合K短路算法的模擬退火算法，并采用了兩步法的優(yōu)化策略進行求解.最后對一個簡單的路網(wǎng)進行了驗證，結(jié)果表明融合K短路算法可以在能力約束條件下得到較好的收益.

鐵路運輸；能力約束；多車種空車動態(tài)調(diào)整；時空服務網(wǎng)絡；模擬退火算法

鐵路空車調(diào)整問題是涉及鐵路運輸資源優(yōu)化配置的重要問題，不僅是實際生產(chǎn)中的重要內(nèi)容，同時也是國內(nèi)外很多學者研究的熱點問題.由于空車調(diào)配問題本質(zhì)為一個路網(wǎng)運輸問題，因此需對復雜的網(wǎng)絡進行簡化處理，處理方法主要有區(qū)段中心優(yōu)化法、重心優(yōu)化法和振蕩法等3種[1-3],但是由于路網(wǎng)貨流和區(qū)段能力的動態(tài)變化特性，這些通過固定的方法合并網(wǎng)絡具有一定的不合理性，基于此，多個學者進行了深入研究，林柏梁等[4]通過分布優(yōu)化迭代的算法研究了能力約束條件下的空車調(diào)配問題.溫旭紅等[5]根據(jù)多商品網(wǎng)絡流理論構建鐵路車流分配及徑路優(yōu)化模型，將路徑的合理繞行納入約束體系，使結(jié)果更加符合鐵路運輸實際.曹學明等[6]考慮了滯留費用對于空車調(diào)配問題的影響.程學慶等[7]研究了考慮時間因素的空車調(diào)配優(yōu)化問題，約束條件包括時間窗和區(qū)段空車運輸能力約束.梁棟等[8]采用動態(tài)規(guī)劃方法提出了鐵路局管內(nèi)空車調(diào)配的動態(tài)優(yōu)化模型.王龍等[9]研究了全路空車動態(tài)調(diào)配及路網(wǎng)分界口排空流量測算方法，基于時空網(wǎng)絡的概念建立了動態(tài)調(diào)配優(yōu)化模型.但是這些成果并沒有將多車種和調(diào)配的動態(tài)特性進行統(tǒng)一研究.

國外通常將重車徑路與空車調(diào)配協(xié)同優(yōu)化調(diào)整作為主要的研究方向.Loxton等[10]設計了動態(tài)規(guī)劃和黃金分割相結(jié)合的算法，研究了未來需求不確定的情況下，考慮包含多種車輛類型的車輛規(guī)模問題. Yaghini等[11]采用遺傳算法和模擬退火算法集成的啟發(fā)式算法研究了動態(tài)多階段的車輛規(guī)模問題.然而此類文章研究的側(cè)重點為購買車輛以及車輛的維護費用，這與空車調(diào)整問題研究所關心的費用有所不同，同時研究并沒有涉及車種替代問題.

本文作者在前人研究的基礎上，結(jié)合當前貨改對于精細化調(diào)度指揮的要求，提出了多車種動態(tài)調(diào)整的方法，構建了基于能力約束的空車多車種動態(tài)調(diào)整模型.研究了在路網(wǎng)能力約束的條件下，多種空車在不同的時間階段內(nèi)的有效調(diào)配，以便產(chǎn)生較好的經(jīng)濟效益，更好地適應鐵路部門當前對于調(diào)度精細化管理的需求.

1 問題的描述

鐵路系統(tǒng)的空車調(diào)整問題主要分為排空和配空2種.本文所研究的模型主要用來解決各鐵路局的空車配空計劃的優(yōu)化.在實際的生產(chǎn)過程中，由于多種不確定因素，路網(wǎng)的貨流和車流情況變化比較頻繁，車站生產(chǎn)是通過日班計劃和階段計劃結(jié)合的方式來適應這種動態(tài)變化特性，然而此種方法只是在變化發(fā)生的時候被動調(diào)整，會導致車站裝卸能力使用不均衡；同時，在實際的運輸生產(chǎn)中由于某些路段的運輸任務比較緊張，主要供重車通行(比如大秦線)，空車需要選擇其他的繞行徑路，考慮路段為空車預留的能力約束是實際運輸生產(chǎn)過程中的需求.因此，本文研究在能力約束下的多階段空車調(diào)整方法，同時考慮路網(wǎng)貨流的動態(tài)變化特性.

空車時空服務網(wǎng)絡的概念是專門針對空車調(diào)整模型提出的，如圖1所示.它能夠比較直觀地反映出多階段空車調(diào)整的模式.剩余空車轉(zhuǎn)移弧表示了空車提供點在本階段剩余的空車滯留到下一個階段的轉(zhuǎn)移弧，空車分配轉(zhuǎn)移弧表示了空車從提供點配送到需求點的轉(zhuǎn)移弧，不滿足空車轉(zhuǎn)移弧表示了空車需求點在本階段沒有滿足的空車需求從而累計到下一個階段的轉(zhuǎn)移弧.

圖1展示了4個車站(S1，S2，N1，N2)，2個車輛提供車站(S1，S2)和2個車輛需求車站(N1，N2)，4個時間階段(T1，T2，T3，T4)的一個空車時空服務網(wǎng)絡圖.

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

2.1 模型的假設

空車調(diào)整問題的模型假設有：1)對于空車需求站，此階段不滿足的需求，將會疊加到下一個階段的需求中；2)對于空車提供站，此階段滯留的空車，將會疊加到下一個階段的空車中；3)空車需求站和空車提供站的性質(zhì)在計劃周期內(nèi)不變；4)空車需求站在每個階段提供的空車數(shù)量保持不變，空車提供站在每個階段需求的空車數(shù)量保持不變；5)路網(wǎng)中任意兩車站之間車輛的運行時間固定.

2.2 數(shù)學模型

2.2.1 變量的定義

N表示網(wǎng)絡中所有的站點集合；N1表示網(wǎng)絡中所有的空車提供站點集合；N2表示網(wǎng)絡中所有的空車需求站點集合；A表示網(wǎng)絡中所有的弧段集合；a表示網(wǎng)絡中任意一個弧段；k表示網(wǎng)絡中任意一個徑路；T表示時間階段集合；t表示任意一個時間階段；U表示車種集合；u表示任意一種車種.

2.2.2 數(shù)學模型

(1)

s.t.

?j,t,u

(2)

?i,t,u

(3)

?i,t,u

(4)

?a,t

(5)

(6)

(7)

?i,j,t,k,u,v

(8)

目標函數(shù)(1)為多目標決策函數(shù)，表示空車調(diào)配計劃的綜合收益，包含了空車調(diào)配的純收益最大化，調(diào)配費用支出的最小化.費用包含：空走費用、滯留費用、需求未滿足的懲罰費用和車種替代費用.

式(2)為空車需求站在某時間段內(nèi)未滿足的空車需求，它等于上階段和本階段的未滿足空車數(shù)量之和.

式(3)為空車提供站在某時間階段所剩余的空車數(shù)量，它等于上階段和本階段的空車剩余數(shù)量之和.

式(4)為空車提供站在某時間段內(nèi)所滯留的空車量，它是由上階段剩余的空車數(shù)量減去本階段調(diào)配的空車數(shù)量得出，即在上階段剩余的空車如果在本階段內(nèi)還沒有被調(diào)配就認為這些空車在本階段內(nèi)出現(xiàn)了滯留.

式(5)為弧段能力約束，約束左側(cè)表示在某時間階段內(nèi)通過弧段的車流量，此車流量需要小于等于該弧段在該時間階段的最大通過能力.

式(6)為空車提供站的空車最大發(fā)送能力約束.

式(7)為空車需求站的空車最大接收能力約束.

式(8)為決策變量和中間變量的非負性質(zhì).

3 模擬退火算法求解

空車調(diào)整問題的本質(zhì)為一個組合優(yōu)化問題，本文采用模擬退火算法(Simulated Annealing，SA)進行求解.

求解過程分為兩步.

第一步，在只考慮最短路的情況下，結(jié)合式(1)～式(4)、式(8)，利用模擬退火算法求解，然后考慮式(5)，找出所有不滿足式(5)的弧段，再找到經(jīng)過這些弧段的OD集合，調(diào)用K短路算法，將集合中的OD加入K短路作為鄰域解.

1)初始解.

令所有的空車調(diào)整量初始解都為0.

2)鄰域解.

3)冷卻策略.

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

Tn+1=αTn， 0<α<1

(9)

式中Tn表示第n次迭代時的溫度.

4)接受函數(shù).

較差解可以接受的概率采用下式確定：

P(ΔZ,T)=exp(-ΔZ/T)

(10)

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

5)終止條件.

當?shù)鷷r的溫度下降到設定溫度或迭代到一定的次數(shù)時目標函數(shù)還沒有得到優(yōu)化即算法終止.

4 算例分析

路網(wǎng)的拓撲結(jié)構如圖2所示，路網(wǎng)中每條弧段都為雙向弧段，弧段上的數(shù)字表示弧段的距離,單位為km.設空車在路網(wǎng)中的平均速度為50 km/h，假定路網(wǎng)中節(jié)點S1～S4為空車提供點，S6～S9為空車需求點.

表1和表2分別表示了空車需求點在不同的時間階段對于不同車種的提供量和空車提供點在不同的時間階段的空車需求量，本文中考慮了3種車種c1～c3.不同車種替代費用：c1與c2車種替代費用為5元；其他情況的替代費用較高，值為100元.

4.1 輸入條件參數(shù)

目標函數(shù)中所涉及的費用參數(shù)：單位空車走行費用為50元/h；單位空車需求滿足后，所產(chǎn)生的效益為2 000元；單位空車單個時間階段的空車滯留費用為500元；單位空車單個時間階段的空車未滿足需求的費用為50元.每個時間階段的時長為3 h.

模擬退火算法的參數(shù):初始溫度為500，終止溫度為1，冷卻比例為0.99，固定溫度的迭代次數(shù)為10，次解的最大迭代次數(shù)為100，最大迭代次數(shù)為15 000.

4.2 計算結(jié)果

1)能力無約束.

在能力不受約束的情況下，通過模擬退火算法進行求解，各個弧段的能力利用情況如表3所示.

表1 空車提供點在不同時間階段的空車提供量
Tab.1 Empty car supporting numbers of supporting stations in different time stages 輛

節(jié)點階段1階段2階段3階段4c1c2c3c1c2c3c1c2c3c1c2c3節(jié)點1200200400500200500600300100400500300節(jié)點2300200400100500300200500200500200100節(jié)點3200200400500600600300200400600600200節(jié)點4100200800800700400500600650600300200

表2 空車需求站在不同時間階段的空車需求量
Tab.2 Empty car needing numbers of needing stations in different time stages 輛

節(jié)點階段2階段3階段4階段5c1c2c3c1c2c3c1c2c3c1c2c3節(jié)點6200300100400100200400500100500600100節(jié)點7400400500600600300500900300200100400節(jié)點8400500300700200400600700600300300400節(jié)點9300500600700700300200300200400500200

表3 能力不受限制情況下各弧段能力利用值

Tab.3 Capacity using values of all arcs without capacity constraints 輛

弧段能力利用弧段能力利用弧段能力利用弧段能力利用S5-S85234S6-S94314S2-S42212S4-S74351S1-S21126S1-S61498S3-S58324S5-S4 818S1-S31467S2-S32413S4-S54042S5-S66314

2)能力約束.

現(xiàn)將弧段S3-S5設為能力約束弧，最大能力約束為3 000輛；那么經(jīng)過此弧段的所有OD集合，以及此OD集對應的K短路，如表4所示.

表4 能力限制情況下的受限制OD集合及K短路

將表4的備選徑路加入對應的鄰域集合，得出了在能力約束條件下的空車調(diào)整結(jié)果，此時路網(wǎng)的能力利用如表5所示，從表中可以看出限制弧段S3-S5能力利用值為3 000輛,達到最大.

表5 能力限制條件下各弧段能力利用值
Tab.5 Capacity using values of all arcs with capacity constraints 輛

由于篇幅限制，表6只列出了在階段1時的結(jié)論，表示選擇不同徑路的空車調(diào)整結(jié)果.從表6中可以看出，分配結(jié)果只出現(xiàn)了車種c1和c2互相替換的情況，同時受能力約束影響的OD都選擇了繞行的徑路.

圖3表示了模擬退火能力無約束、能力約束和能力約束且考慮了K短路3種不同情況下的迭代優(yōu)化結(jié)果.從圖中可以看出，3種情況都在迭代8 000次左右時達到了優(yōu)化；第1種情況下調(diào)整的收益最大，第3種情況次之，第2種情況最少，因此,得出結(jié)論:在能力約束條件下采用K短路的方法比采用最短路的收益要高.

表6 階段1時空車調(diào)整結(jié)果Tab.6 Empty car distribution results under stage one 輛

續(xù)表6

K短路節(jié)點節(jié)點6節(jié)點7節(jié)點8節(jié)點9c1c2c3c1c2c3c1c2c3c1c2c3第2短路節(jié)點1節(jié)點2節(jié)點3節(jié)點4c100000012100000c2000000600000c30000000050000c11122000001603700c23411000071110290c3002500000570044c1000144012401110c22706701120290c30033006700250054c1000000000000c2000000000000c3000000000000第3短路節(jié)點1節(jié)點2節(jié)點3節(jié)點4c10000005110000c2000000700000c30000000053000c100000030012110c2215000013001700c3001400000330028c127210101078016210c2140000010002200c300000530064000c1000000000000c2000000000000c3000000000000

5 結(jié)論

本文建立了在能力約束條件下的多車種空車動態(tài)調(diào)整優(yōu)化模型，引入了空車服務網(wǎng)絡，并采用融合K短路算法的模擬退火算法進行優(yōu)化，設計了兩步法優(yōu)化策略，得到了較優(yōu)解.研究了能力無約束采用最短路、能力約束采用最短路和能力約束且考慮了K短路3種不同情況下的迭代優(yōu)化結(jié)果.結(jié)果表明在能力約束的條件下采用K短路的方法能得到相對較好的收益.該模型可以為路網(wǎng)中空車調(diào)整問題的研究提供一定的參考.然而，空車調(diào)整問題在實際生產(chǎn)中需要考慮的因素還很多，如車流運行時間受多種因素影響、列車車次接續(xù)和車站裝卸車能力等都影響空車調(diào)配的效率，這些因素需要在下一步工作中繼續(xù)研究.

[1] 果鵬文，林柏梁，余洋. 大規(guī)模路網(wǎng)上空車調(diào)配的區(qū)段中心優(yōu)化[J]. 中國鐵道科學，2001，22(2)：122-128. GUO Pengwen, LIN Boliang, YU Yang. The section center optimization method of empty car adjustment on large-scale railway network[J]. China Railway Science, 2001, 22(2):122-128.(in Chinese)

[2] 紀嘉倫，林柏梁，李福志，等. 用重心優(yōu)化方法求解鐵路網(wǎng)上空車調(diào)配問題[J]. 鐵道學報，2001，23(3)：109-113. JI Jialun, LIN Boliang, LI Fuzhi, et al. Distribution of empty wagons on railway network by using the center-of-gravity-optimization method[J]. Journal of the China Railway Society, 2001, 23(3): 109-113. (in Chinese)

[3] 果鵬文，褚江，林柏梁. 用振蕩法解大規(guī)模路網(wǎng)上的空車調(diào)配問題[J]. 中國鐵道科學，2002，23(4)：111-117. GUO Pengwen, CHU Jiang, LIN Boliang. Reiterative adjusting method of empty wagon on large-scale railway network[J]. China Railway Science, 2002, 23(4):111-117. (in Chinese)

[4] 林柏梁，喬國會. 基于線路能力約束下的鐵路空車調(diào)配迭代算法[J]. 中國鐵道科學，2008，29(1)：93-96. LIN Boliang, QIAO Guohui. Iterative algorithm of railway network empty cars distribution based on restriction of route capacity[J]. China Railway Science, 2008, 29(1):93-96. (in Chinese)

[5] 溫旭紅,林柏梁,王龍,等.基于多商品網(wǎng)絡流理論的鐵路車流分配及徑路優(yōu)化模型[J].北京交通大學學報,2013,37(3):117-121. WEN Xuhong, LIN Boliang, WANG Long,et al. Optimization model for railway car flow assignment and routing plan based on multi-commodity network flow theory[J]. Journal of Beijing Jiaotong University, 2013,37(3):117-121. (in Chinese)

[6] 曹學明，林柏梁. 基于滯留費用的空車調(diào)配優(yōu)化方法[J]. 鐵道學報，2007，29(4)：18-22. CAO Xueming, LIN Boliang. An optimization method for distribution of empty cars based on stock cost[J]. Journal of the China Railway Society, 2007,29(4):18-22. (in Chinese)

[7] 程學慶，陸一新，尹傳忠,等. 基于時間窗的鐵路空車調(diào)配優(yōu)化模型及求解[J]. 中國鐵道科學，2007，28(6)：113-116. CHENG Xueqing, LU Yixin, YIN Chuanzhong, et al. Optimal model and solution of railway empty wagon distribution with time-window[J]. China Railway Science, 2007,28(6)：113-116. (in Chinese)

[8] 梁棟，林柏梁. 鐵路空車調(diào)配的多階段策略優(yōu)化模型研究[J]. 鐵道學報，2007，29(1)：1-6. LIANG Dong, LIN Boliang. Research on the multi-stage optimization model of empty railcar distribution[J]. Journal of the China Railway Society, 2007，29(1)：1-6. (in Chinese)

[9] 王龍，馬建軍，林柏梁，等.全路空車動態(tài)調(diào)配及路網(wǎng)分界口排空流量測算方法[J].鐵道學報，2015，37(6)：1-9. WANG Long, MA Jianjun, LIN Boliang, et al. Dynamic empty car distribution for the whole rail system and calculation for empty car flow discharged over network boundaries[J]. Journal of the China Railway Society, 2015，37(6)：1-9. (in Chinese)

[10] LOXTON R, LIN Q, TEO K L. A stochastic fleet composition problem[J]. Computers & Operations Research, 2012,39 (12):3177-3184.

[11] YAGHINI M, KHANDAGHABADI Z. A hybrid metaheuristic algorithm for dynamic rail car fleet sizing problem[J]. Applied Mathematical Modelling，2013, 37(6):4127-4138.

Multi-type empty car dynamic distribution method based on capacity constraints

ZHANGHongbin1,2，DONGBaotian1，SUNYuanyun2

(1.School of Traffic and Transportation，Beijing Jiaotong University，Beijing 100044，China； 2.China Railway Information Technology Center，Beijing 100844， China)

Empty car service network of time and space is proposed to cater for the dynamic characteristic of railway transportation system, and the dynamic programming model based on capacity constraints is proposed considering the actual transport capacity constraints in the production. Empty car stranded costs and unsatisfied demand penalty costs related to time factor, car substitution costs are considered in object function. Railway network arc carrying capacity，empty car supporting and needing stations' capacity are all concluded in the restrain conditions of the formulation. A simulated annealing (SA) algorithm integrating K shortest path algorithm is designed, and a two steps optimization strategy is proposed to solve the problem. Finally, a simple network is to verify the model, and the results indicate that the integrating K shortest path algorithm can get preferable revenue under capacity constraints.

railway transportation; capacity constraints; multi-type empty car dynamic distribution; service network of time and space; simulated annealing algorithm

1673-0291(2016)06-0050-07

10.11860/j.issn.1673-0291.2016.06.009

2016-03-01

中國鐵路總公司科技研究開發(fā)計劃項目資助(2014X009-A，2016X006-D)

張紅斌(1981—)，男，河南焦作人，博士.研究方向為鐵路運輸組織現(xiàn)代化.email:zhanghongbin2003@126.com.

U292.4

A