鐵路空車調(diào)配的多時點優(yōu)化模型研究

王波，榮朝和，黎浩東*，王保華

（1.北京交通大學(xué)經(jīng)濟管理學(xué)院，北京100044；2.廣鐵集團惠州車務(wù)段，廣東516023；3.IBM中國研究院，北京100193）

鐵路空車調(diào)配的多時點優(yōu)化模型研究

王波1,2，榮朝和1，黎浩東*1，王保華3

（1.北京交通大學(xué)經(jīng)濟管理學(xué)院，北京100044；2.廣鐵集團惠州車務(wù)段，廣東516023；3.IBM中國研究院，北京100193）

空車調(diào)配優(yōu)化直接影響鐵路運用車輛使用效率和市場需求滿足的程度.從實時性優(yōu)化調(diào)整角度，通過定義配空弧與裝運弧，確立了配空和裝運之間的映射關(guān)系，從而形成空車調(diào)配服務(wù)時空網(wǎng)絡(luò).在此基礎(chǔ)上，綜合考慮決策階段內(nèi)收益、成本、服務(wù)能力等因素，以空車調(diào)配收益最大為目標(biāo)，構(gòu)建空車調(diào)配的多時點優(yōu)化模型.最后以粵東地區(qū)空車調(diào)配為案例，對所構(gòu)建模型進行驗證.案例結(jié)果表明，所提出的空車調(diào)配時空網(wǎng)絡(luò)構(gòu)建方法，有助于綜合考慮收益、成本和點線能力等因素，以及降低問題的難度，可為空車調(diào)整策略提供新的思路.

鐵路運輸；空車調(diào)配；服務(wù)時空網(wǎng)絡(luò)；多時點；列車開行

1 引言

無論為適應(yīng)市場發(fā)展采取何種鐵路貨運改革形式，空車調(diào)配始終是鐵路運輸組織中的重要問題之一.國內(nèi)外學(xué)者對空車調(diào)配問題進行了很多研究.在國內(nèi)，從建立模型的策略上看，文獻[1-4]分別從空車調(diào)配多階段優(yōu)化、車種代用情況下空車調(diào)配、車數(shù)最少空車調(diào)配、基于知識約束空車調(diào)配等角度進行優(yōu)化研究；從模型求解上看，文獻[5-8]分別從應(yīng)用重心優(yōu)化方法、遺傳啟發(fā)算法、振蕩法對空車調(diào)配問題進行求解；國外，文獻[9-10]以市場需求的滿足為目標(biāo)，研究了空車調(diào)配隨時間段變化的情況等.在上述建模中，存在著諸如編制方法靜態(tài)局限、排空與配空未統(tǒng)籌兼顧、空車調(diào)配與列車開行計劃及其調(diào)整不協(xié)調(diào)等不足，這可能導(dǎo)致所編制的空車調(diào)配方案難以實施.本文從鐵路運輸調(diào)度實際工作出發(fā)，從實時性優(yōu)化調(diào)整角度，在決策階段內(nèi)綜合考慮收益、成本、服務(wù)、能力等因素，建立鐵路裝卸站時點之間映射關(guān)系，從而形成鐵路多時點空車服務(wù)時空網(wǎng)絡(luò)；在時空網(wǎng)絡(luò)中，節(jié)點的設(shè)置體現(xiàn)各裝卸站點的作業(yè)時間點，協(xié)調(diào)排空和配空關(guān)系；聯(lián)弧則是基于實際列車開行計劃設(shè)置，是空車調(diào)配的具體反映；最后基于時空網(wǎng)絡(luò)，從動態(tài)優(yōu)化角度建立鐵路局（公司）管內(nèi)空車調(diào)配的多時點優(yōu)化模型，并通過具體案例對模型進行驗證.

2 服務(wù)時空網(wǎng)絡(luò)和模型建立

2.1 建立映射關(guān)系

決策階段的時間長短取決于運輸確定性信息的掌握情況，掌握的越好，決策階段時長就越長，否則，不確定因素越多，決策時長就越短.如圖1所示，在A站的A1時點有一組車卸空，在技術(shù)作業(yè)完畢后其中一部分可運送到C1時點進行裝車，裝車后在技術(shù)作業(yè)完畢掛運到B站的B1時點進行卸車，卸車完畢后再經(jīng)裝車等作業(yè)掛運到A站的A3時點；另外一部分，可在本站等到A2時點進行裝車，在相關(guān)作業(yè)完畢后再掛運到C站.在上述過程中，相關(guān)運輸信息可以通過推流、各種作業(yè)標(biāo)準(zhǔn)和列車開行方案等方面取得.在取得決策階段相關(guān)信息、開行計劃后，可通過聯(lián)弧形式建立映射關(guān)系，其中映射關(guān)系是指實際空車組織的實際作業(yè)過程（包括主要的裝卸作業(yè)時間點和空車調(diào)配過程）在時空網(wǎng)絡(luò)中的具體表示.其中時空網(wǎng)絡(luò)中的節(jié)點表示實際的裝卸作業(yè)時間節(jié)點，聯(lián)弧則是基于實際運營計劃設(shè)置的可能空車調(diào)配作業(yè)，包括配空弧和裝運弧兩種.在重車卸空完畢的時點與該車在所裝車站裝車時點之間建立聯(lián)弧，定義為配空弧；在裝車時點與該車在所卸車站卸車完畢時點建立聯(lián)弧，定義為裝運弧，如圖1所示.所有車流運行、等待和作業(yè)狀態(tài)都可以用配空弧和裝運弧來表示.

圖1 配空弧與裝運弧的形成Fig.1 Construction of empty railcar arcs and loaded railcar arcs

以圖2所示網(wǎng)絡(luò)進行說明，其中A方向是進口接重方向，D站是交口排空方向.通過推流，預(yù)計在A站6時（點A6）、B站8時（點B8）、C站12時（點C12），以及E站7時（點E7）有重車卸空；根據(jù)請求車情況，在B站11時（點B11）、C站20時（點C20）、D站12時（點D12）有請求裝車.在計劃開行方案制定后，在所有滿足卸車時間、裝車時間、技術(shù)作業(yè)時間、運行時間等之和最小接續(xù)時間條件的裝車與卸車時點之間，以及滿足車種或車種代用要求的聯(lián)弧之間，建立映射關(guān)系.如圖3所示，L1表示A站6點卸空車流可配空到B站11點裝車的配空??；L2表示A站6點卸空車流可配空到C站20點裝車配空??；L3表示A站6點卸空車流可經(jīng)D站進行排空的配空??；L4表示D站在12點可能的裝車向C站掛運的重車卸空后為20點裝車配空的裝運弧；L5、L6表示C站在20點可能開始裝車掛運而形成的裝運弧，其他弧亦同.設(shè)計算階段為6:00-24: 00，則所有已知裝運時點都應(yīng)包括在該階段內(nèi)，如圖B11、C20、D12；如果卸空站仍有空車在站等待或有空車需排空超出計算階段等情況時，如A站6時A6點的卸空車，對于要等待到下一階段的空車，可在卸空時點和本站計算階段終點間建立配空弧如圖L7，而A24時點的空車又可作為下一計算階段的空車源.對于排空到分界口卻超出計算階段的空車，仍可按建弧要求形成配空弧如L3.這樣，所有配空弧與裝運弧共同構(gòu)成了一種服務(wù)時空網(wǎng)絡(luò)形態(tài).基于列車運營計劃，將空車調(diào)配問題用時空網(wǎng)絡(luò)表示，可將該問題描述為網(wǎng)絡(luò)流問題，有利于將空車調(diào)配與實際列車運營計劃相結(jié)合，進而有利于對問題的描述、模型的構(gòu)建及求解.

圖2 某管內(nèi)車站布局示意圖Fig.2 Yard layout on a main line

圖3 由配空弧與裝運弧構(gòu)成的服務(wù)時空網(wǎng)絡(luò)Fig.3 Time space network based on empty railcar arcs and loaded railcar arcs

2.2 建立優(yōu)化模型

Lk為配空弧集合，Lz為裝運弧集合，i為聯(lián)弧索引，有i∈(Lk?Lz)；N為節(jié)點集合，n為索引；T為時點集合，t為索引.n站t時節(jié)點所連結(jié)的配空弧集合為分別是以此節(jié)點為終點、起點的配空弧集合，有；n站t時節(jié)點所連結(jié)的裝運弧集合為分別是以此節(jié)點為終點、起點的裝運弧集合，是以此節(jié)點為起點的裝運弧集合，有；n站t時節(jié)點卸空車總量為Qnt，裝卸作業(yè)能力為Pnt，請求車總量為Znt；n站t時節(jié)點i配空弧能力為，i裝運弧能力為；fi為i裝車弧單車收益，ci為i配空弧或裝運弧單車成本.決策變量xi為各聯(lián)弧流量，為非負(fù)實型變量.模型表述如下：

（1）節(jié)點流量守恒約束.

對于包含裝運弧N站t時點流進量與流出量相等，有

對于不包含裝運弧N站t時點卸空車總量等于配空弧總流量，有

（2）N站t時的作業(yè)量不大于其裝卸作業(yè)能力，有

（3）配空流量和裝運流量分別小于等于弧能力，有

（4）裝運弧流量小于等于N站t時需求裝車數(shù)，有

以最大化空車調(diào)配的總收益為目標(biāo)，表示如下：

關(guān)于模型的幾點說明：

（1）弧形成的前提是有列車開行計劃，列車開行計劃是根據(jù)決策階段內(nèi)運輸情況編制出來的，開行計劃進一步調(diào)整完善可形成日（班）計劃中的列車工作計劃.

（2）卸空時點和裝運時點的確定，體現(xiàn)了時間約束，在卸空時點之前因沒有卸空，也就不能形成為配空所需的車組；在裝運時點之后不符合開行時間要求，所裝車列要在此點編入計劃車次.

（3）裝車弧收益是指包括運輸收入、裝卸收入、其他服務(wù)性收入在內(nèi)的收費，是鐵路因貨運裝車而帶來的一切收益.

（4）配空弧或裝運弧成本是指車輛走行、裝卸作業(yè)、車輛使用等的費用支出，不同的的車輛走行、裝卸作業(yè)及使用的車輛種類對應(yīng)著不同的配空弧或裝運弧成本.成本可分為可變成本和固定成本，可變成本主要是車輛走行成本、使用成本等組成，走行成本可綜合各種可變費用進行平均分?jǐn)偳蟮?，使用成本可按鐵路總公司車輛使用收費情況獲得；對于固定成本在具體計算時，涉及到各種設(shè)備實施的折舊，計算相當(dāng)復(fù)雜，但考慮到在短時期內(nèi)無論是否計入固定成本都不影響決策目標(biāo)的求取，因而在此可不計入.

（5）配空弧能力是指卸車站與裝車站之間有計劃安排、符合列車編組要求，且滿足最小接續(xù)時間條件的最大輸送能力，或是在站等待作業(yè)時的最大容車數(shù)，裝運弧能力亦同.

（6）對于重點必保的排空或配空任務(wù)要求，在計算時其裝運弧收益取值為較大的實數(shù)，以優(yōu)先保證這部分空車的調(diào)配.

所構(gòu)建的模型為整數(shù)規(guī)劃模型，考慮路局層面空車調(diào)配問題規(guī)模，以及時空網(wǎng)絡(luò)構(gòu)建時對問題的簡化，可采用Cplex等優(yōu)化軟件進行求解.如在所構(gòu)建的時空網(wǎng)絡(luò)中，可通過作業(yè)時間的推算、走行徑路等的分析，剔除明顯不合理的聯(lián)弧，進而壓縮問題的規(guī)模.

3 實例分析

以粵東鐵路配空為例進行測算，各站點如圖4所示，其中東莞東口是接重和空車進入口，龍川北是編組站，定南口是空車排出口，其他各站是貨運作業(yè)站.

圖4 粵東鐵路貨運站點示意圖Fig.4 Yard layout of East Guangdong Railway

在表1中通過推流可預(yù)計各站在所列時間點有重車卸空；按貨運裝車作業(yè)時間標(biāo)準(zhǔn)和開行計劃可確定裝運時間；運輸收入是實際收取的裝車運費，是按貨運品類的貨價率計算求得，再按相關(guān)優(yōu)惠政策執(zhí)行后的最后收費；運行成本是走行成本+車輛使用成本=走行里程×0.8+使用時間×5.7，0.8在本算例中是各種可變費用綜合平均求得，是單車每走行一公里所需費用，使用時間=走行里程/平均旅行速度+裝卸作業(yè)時間.

表1 各站卸空車和請求車情況Table 1Unloading and empty car requirement of each yard

圖5是部分計劃開行列車運行線，貨物列車運行線鋪畫是在旅客列車運行線確定的情況下，根據(jù)運輸能力和生產(chǎn)實際進行鋪畫，圖中鋪畫了部分為配空所開行的計劃線，裝運重車運行線等計劃開行線鋪畫同理.

圖5 計劃開行列車運行圖Fig.5 Timetable of freight trains in of East Guangdong Railway

根據(jù)上述已知條件，可構(gòu)建相應(yīng)的時空網(wǎng)絡(luò)，這里只給出了如表2所示的配空弧信息.其中線的兩端連結(jié)卸車站和裝車站，弧起點時刻是卸空時間，終點時刻是裝運時間，空車總量是卸車站卸空總量，可掛運車次是計劃開行列車可能掛運空車的列車.在配空弧構(gòu)建過程中，根據(jù)走行情況和具體作業(yè)去掉了明顯不合理的聯(lián)弧，如仙塘配空一般由埔前卸車配空，而不由東莞東、陳江卸空調(diào)配.

表2 配空弧構(gòu)建情況Table 2Information of empty arcs

本模型采用IBM ILOG CPLEX 12.2進行求解，計算結(jié)果如表3所示，目標(biāo)函數(shù)值為1 580 394.

表3 配空情況及開行方案Table 3Empty car distribution and trains plan

4 研究結(jié)論

（1）對于列車開行計劃下的多車種、多去向的配空及裝運方式，可采用由配空弧與裝運弧構(gòu)成的服務(wù)時空網(wǎng)絡(luò)形式進行表述，車輛走行、裝卸作業(yè)、車輛使用等成本構(gòu)成配空弧和裝運弧成本，運輸收入、裝卸收入、其他服務(wù)性收入在內(nèi)的收費構(gòu)成裝車弧收益，通過求解按效益最大化為目標(biāo)的函數(shù)，能夠得出實際應(yīng)用的滿意配空方案.

（2）如果按市場開發(fā)及拓展所提出的配空要求，可對模型中的收益進行重新賦值，這時的收益已不是現(xiàn)期收益，而是預(yù)期收益或是潛在收益，通過調(diào)整收益值能夠形成按要求的配空方案，如在案例中對汕頭北的裝車，因?qū)撛谑袌龅拈_發(fā)需要進行裝車時，按市場營銷的預(yù)期收入進行當(dāng)期化處理后，可形成新的滿意配空方案.

（3）在列車開行計劃下的配空方案形成后，需重新調(diào)整列車工作計劃，如由于排空比配空到汕頭北要優(yōu)，配空優(yōu)化結(jié)果沒有往汕頭北配空5個車，所開行的42142/41次列車即到揭陽站截止，又如配空優(yōu)化結(jié)果是40012次列車運行到惠州甩空，因而不會再開行至龍川北，這些都需要重新對列車開行計劃進行優(yōu)化，在此基礎(chǔ)上再對空車調(diào)配計劃進行優(yōu)化，反復(fù)調(diào)整才能形成合理滿意的工作計劃.

[1]梁棟,林柏梁.鐵路空車調(diào)整的多階段策略優(yōu)化模型研究[J].鐵道學(xué)報,2007,29(1):1-6.[LIANG D,LIN B L.Research on the multi-stage optimization model of empty railcar distribution[J].Journal of China Railway Society,2007,29(1):1-6.]

[2]梁棟,林柏梁,嚴(yán)賀祥,等.車種代用情況下的鐵路空車調(diào)配研究[J].鐵道學(xué)報，2005,27(4):1-5.[LIANG D,LIN B L,YAN H X,et al.Study of railway empty car distribution with substitution of empty car types[J]. Journal of China Railway Society,2005，27(4):1-5.]

[3]李文權(quán),杜文,周賢偉.優(yōu)化空車調(diào)配問題[J].西南交通大學(xué)學(xué)報,1998,33(4):383-386.[LI W Q,DU W, ZHOU X W.Optimal assignment of empty cars[J]. Journal of Southwest Jiaotong University,1998,33(4): 383-386.]

[4]張喜,張全壽.基于知識約束的空車調(diào)整優(yōu)化方法研究[J].鐵道學(xué)報,2003,25(6):14-20.[ZHANG X, ZHANG Q S.Study on the optimization method of emptywagondistributionbasedonknowledge constraints[J].Journal of China Railway Society,2003, 25(6):14-20.][5]紀(jì)嘉倫,林柏梁,李福志,等.用重心優(yōu)化方法求解鐵路網(wǎng)上空車調(diào)配問題[J].鐵道學(xué)報,2001,23(3):109-113.[JI J L,LIN B L,LI F Z,et al.Distribution of empty wagons on railway network by using the centerof-gravity-optimization method[J].Journal of China Railway Society,2001,23(3):109-113.]

[6]熊紅云,魯五一,溫紅艷.鐵路空車調(diào)配問題的遺傳啟發(fā)算法[J].中國鐵道科學(xué),2002,23(4):118-121.[XIONG H Y,LU W Y,WEN H Y.Hereditary heuristic algorithm for empty car distribution in railway transportation[J].China Railway Science,2002,23(4): 118-121.]

[7]曾健,周健,張喜.空車調(diào)整專家系統(tǒng)的研究[J].鐵路計算機應(yīng)用,1999,8(4):5-7.[ZENG J,ZHOU J, ZHANG X.Research on empty cars distribution expert system[J].Railway Computer Application,1999,8(4):5-7.]

[8]果鵬文,禇江,林柏梁.用振蕩法解大規(guī)模路網(wǎng)上的空車配送問題[J].中國鐵道科學(xué),2002,23(4): 111-117.[GUO P W,ZHU H,LIN B L.Reiterative adjusting method of empty wagon on large-scale railway network[J].China Railway Science,2002,23(4):111-117.]

[9]Kikuchi S.Empty freight car dispatching model under freight car pool concept[J].Transportation Research Part B,1985,19(2):169-185.

[10]Glickman T S,Sherali H D.Large scale network distribution of pooled empty freight cars over time,with limitedsubstitutionandequitablebenefits[J]. Transportation Research Part B,1985,19(2):85-94.

Multi-time Point Optimization Model for Empty Railcar Distribution

WANG Bo1,2,RONG Chao-he1,LI Hao-dong1,WANG Bao-hua3
（1.School of Economics and Management,Beijing Jiaotong University,Beijing 100044,China;2.Guangzhou Railway(Group) Corporation,Guangdong 16023,China;3.IBM Research-China,Beijing 100193,China）

Optimization of empty railcar distribution helps to improve the railcar service efficiency and meet the transportation demand.This paper defines empty railcar arcs and loaded railcar arcs from the perspective of real-time optimization,the revenue,cost and service capacity can be denoted on those arcs during the plan horizon.A time space service network of empty railcar distribution is present after mapping the relationship of those arcs.Based on the time space network,a multi-time point optimization model is proposed,with the objective of maximizing the total revenue of empty railcar distribution.At last,the model is verified by a real world example of east region of Guangzhou Railway(Group)Corporation.The result shows that the proposed time space service network and the model can reduce the difficult of the real world problem,and provide a new idea for empty railcar distribution.

railway transportation;empty railcar distribution;time space service network;multi-time point;train operation

1009-6744（2015）05-0157-07

U292.3

A

2015-03-18

2015-05-12錄用日期：2015-05-18

國家自然科學(xué)基金項目（41171113）.

王波（1974-），男，黑龍江齊齊哈爾人，博士后. ＊

:lihd@bjtu.edu.cn