考慮空車調(diào)配協(xié)調(diào)的貨物列車開(kāi)行方案優(yōu)化研究

劉曉偉，晏啟鵬，倪少權(quán)*，呂苗苗，呂紅霞

(1.西南交通大學(xué)，a.交通運(yùn)輸與物流學(xué)院，b.綜合交通運(yùn)輸智能化國(guó)家地方聯(lián)合工程實(shí)驗(yàn)室，c.綜合交通大數(shù)據(jù)應(yīng)用技術(shù)國(guó)家工程實(shí)驗(yàn)室，成都610031；2.四川旅游學(xué)院，成都610100)

0 引言

目前，國(guó)內(nèi)鐵路貨運(yùn)組織方法，存在一定的局限性，即列車編組計(jì)劃與運(yùn)行圖等基本計(jì)劃編制是以計(jì)劃車流為基礎(chǔ)，而計(jì)劃車流無(wú)法反映基于貨運(yùn)營(yíng)銷與動(dòng)態(tài)需求確定的日常動(dòng)態(tài)車流，使得在日常調(diào)度中按基本計(jì)劃要求為日常車流分段規(guī)劃的運(yùn)送方案尚需優(yōu)化，加之運(yùn)送方案規(guī)劃未考慮運(yùn)到期限要求，受動(dòng)態(tài)車流及列車滿軸開(kāi)行要求影響兌現(xiàn)困難，導(dǎo)致車流掛線不確定，規(guī)劃方案難以適應(yīng)貨主動(dòng)態(tài)需求和運(yùn)到期限要求。因此，文獻(xiàn)[1]借鑒客運(yùn)組織理念提出動(dòng)態(tài)規(guī)劃型運(yùn)輸組織思想，即依據(jù)基本計(jì)劃與貨運(yùn)營(yíng)銷，基于近期(周、日)動(dòng)態(tài)車流與運(yùn)到期限要求，調(diào)整編組方案與安排運(yùn)行線等資源，制定車流全程運(yùn)送方案，滾動(dòng)編制貨物列車開(kāi)行方案、列車運(yùn)行計(jì)劃、機(jī)車車輛運(yùn)用計(jì)劃等動(dòng)態(tài)運(yùn)輸計(jì)劃，作為日常調(diào)度依據(jù)，實(shí)現(xiàn)按圖行車。加拿大等國(guó)外鐵路以分組列車形式為主的規(guī)劃型運(yùn)輸組織方法[2]，不完全適應(yīng)國(guó)內(nèi)以單組列車形式為主的運(yùn)營(yíng)特點(diǎn)。

貨物列車開(kāi)行方案是基于動(dòng)態(tài)車流進(jìn)行編組計(jì)劃調(diào)整與列車運(yùn)行方案綜合優(yōu)化，確定列車徑路與編組內(nèi)容、開(kāi)行頻率及時(shí)段，為后續(xù)安排運(yùn)行線確定列車運(yùn)行計(jì)劃提供依據(jù)，屬于動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題[3]；列車運(yùn)行方案是在基本運(yùn)行圖架構(gòu)[4]中為列車挑選合適區(qū)段線。實(shí)際中，空車調(diào)配及時(shí)與否直接影響貨物裝卸取送作業(yè)、車流開(kāi)始集結(jié)時(shí)段及列車集結(jié)過(guò)程，其合理性也將影響貨物列車開(kāi)行方案優(yōu)劣，要求兩者協(xié)調(diào)優(yōu)化。

既有研究主要集中于空車調(diào)配、列車開(kāi)行方案優(yōu)化問(wèn)題，較少涉及兩者綜合優(yōu)化研究。國(guó)內(nèi)學(xué)者基于多階段[5]、多時(shí)點(diǎn)[6]優(yōu)化策略，國(guó)外學(xué)者考慮市場(chǎng)動(dòng)態(tài)需求[7-8]、基于列車時(shí)刻表[9-10]研究空車調(diào)配問(wèn)題。關(guān)于列車開(kāi)行方案的研究成果，可參考文獻(xiàn)[4]分析，其考慮車流改編方案唯一性與樹(shù)形改編要求、運(yùn)到期限等約束，優(yōu)化列車開(kāi)行方案，但未考慮空車調(diào)配協(xié)調(diào)問(wèn)題。兩者綜合優(yōu)化研究較少，HAGHANI[11]以美國(guó)鐵路為例，研究列車徑路、編組計(jì)劃與空車分布的綜合優(yōu)化；ANDERSEN 等[12]以歐盟鐵路為例，考慮多類型車輛周轉(zhuǎn)的貨運(yùn)服務(wù)網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題，但國(guó)外鐵路較少考慮車流不可拆分與樹(shù)形改編要求。文獻(xiàn)[13]針對(duì)國(guó)內(nèi)鐵路，考慮車輛周轉(zhuǎn)設(shè)計(jì)鐵路動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)，未考慮車流樹(shù)形改編要求、車站能力限制以及節(jié)點(diǎn)與區(qū)段不對(duì)流空車約束。本文以單組列車形式為主，考慮空車調(diào)配協(xié)調(diào)研究貨物列車開(kāi)行方案優(yōu)化問(wèn)題；以文獻(xiàn)[4]為基礎(chǔ)，在目標(biāo)中考慮空車配送費(fèi)用，結(jié)合配空與裝卸取送、集編發(fā)的時(shí)間接續(xù)要求、節(jié)點(diǎn)與區(qū)段不對(duì)流空車要求，進(jìn)行重空車流組織優(yōu)化。

為避免引入空車調(diào)配因素導(dǎo)致車流組織方案數(shù)量激增和求解復(fù)雜度增加的問(wèn)題，基于車流時(shí)空服務(wù)徑路構(gòu)建弧路模型；借鑒文獻(xiàn)[14]中k短路算法快速搜索重車、空車流時(shí)空服務(wù)徑路可行集，減小問(wèn)題規(guī)模。結(jié)合重車或空車配空的時(shí)間接續(xù)要求，將不同的k短路重車流方案與空車配空方案相關(guān)聯(lián)，改進(jìn)文獻(xiàn)[4]的可行解構(gòu)造方法，設(shè)計(jì)混合差分進(jìn)化求解算法。

1 基于時(shí)空網(wǎng)絡(luò)的重車、空車流動(dòng)態(tài)組織過(guò)程分析

為分析空車調(diào)配對(duì)動(dòng)態(tài)車流組織過(guò)程的影響，根據(jù)文獻(xiàn)[6]配空與裝運(yùn)關(guān)系描述，拓展文獻(xiàn)[4]中基于離散時(shí)空網(wǎng)絡(luò)方法構(gòu)建的貨運(yùn)時(shí)空服務(wù)網(wǎng)絡(luò)，結(jié)合基本運(yùn)行圖架構(gòu)與車流徑路，確定網(wǎng)絡(luò)結(jié)構(gòu)，引入貨場(chǎng)時(shí)空節(jié)點(diǎn)，重車裝取與送卸弧及空車取送弧，刻畫(huà)配空與裝卸取送、集編發(fā)的時(shí)間接續(xù)關(guān)系，分析各重車、空車流在網(wǎng)絡(luò)中尋路過(guò)程，將車流按一定規(guī)則分配到合理時(shí)空服務(wù)弧上，確定重車流時(shí)空服務(wù)徑路與空車配送方案，新增集合和參數(shù)如表1所示，重車、空車動(dòng)態(tài)組織過(guò)程如圖1所示。

表1 時(shí)空網(wǎng)絡(luò)與車流的集合與參數(shù)Table 1 Sets and parameters of space-time service network and wagon-flow

圖1中，i1,i2,…,i8,i9為不同時(shí)空節(jié)點(diǎn)，假定裝卸車、取送車等四項(xiàng)作業(yè)時(shí)長(zhǎng)均為1 個(gè)時(shí)段，可依據(jù)實(shí)際情況調(diào)整；假設(shè)長(zhǎng)途車流在S3站改編，當(dāng)空車充足，其與短途車流分別選擇第2,2,6 時(shí)段開(kāi)始集結(jié)，車流時(shí)空運(yùn)送方案為；當(dāng)S3站空車不足，裝車將受影響，一方面，選擇開(kāi)行空車直達(dá)列車為S3站提供空車，則各車流方案不變，空車調(diào)配費(fèi)用隨之增加；另一方面，利用到站車流完成卸車，進(jìn)行重車配空，將在第9時(shí)段開(kāi)始集結(jié)，方案變?yōu)椋嚵骷Y(jié)等待費(fèi)用隨之增加。顯然，考慮空車調(diào)配協(xié)調(diào)，決策配空方案，對(duì)作業(yè)車流配合中轉(zhuǎn)車流集結(jié)編組及時(shí)掛線產(chǎn)生重要影響。

圖1 貨運(yùn)時(shí)空服務(wù)網(wǎng)絡(luò)與車流時(shí)空服務(wù)徑路Fig.1 Car space-time path in freight transportation space-time service network

2 模型構(gòu)建

2.1 模型假設(shè)

(1)快運(yùn)、裝車地直達(dá)列車編組方案和運(yùn)行線安排已確定，空車直達(dá)列車方案未知，主要研究空車直達(dá)列車、技術(shù)直達(dá)列車和相鄰編組站間的列車編組方案與運(yùn)行線安排綜合優(yōu)化。

(2)車流OD量、運(yùn)到期限要求、車流徑路已知；車流起運(yùn)時(shí)段未知，即開(kāi)始集結(jié)時(shí)段未知，需根據(jù)重車、空車流組織和時(shí)間窗要求進(jìn)行決策。

(3)基本運(yùn)行圖架構(gòu)已確定，按時(shí)段描述區(qū)段通過(guò)能力；根據(jù)實(shí)際數(shù)據(jù)，采用單元時(shí)段換算，近似描述各弧時(shí)長(zhǎng)。

(4)實(shí)際中車流不允許拆分且需滿足改編方案唯一性，可以假定車流需要滿足時(shí)空服務(wù)徑路唯一性要求。另外，不考慮空車車種和重空混編方式，假定車站裝卸取送作業(yè)能力充足。

2.2 決策變量與中間變量

xp∈{0,1} 為重車流d∈D是否選擇時(shí)空服務(wù)徑路p∈Pd運(yùn)送；xd,a∈{0,1} 為車流d是否選擇列車運(yùn)行弧a；xE,i,j∈{0,1} 為節(jié)點(diǎn)i,j∈N之間是否開(kāi)行空車直達(dá)列車；yE,at為選擇時(shí)段t內(nèi)時(shí)空弧at的空車流量；fat∈Z0+,fE,at∈Z0+為時(shí)段t∈T內(nèi)運(yùn)行時(shí)空弧at∈AR上開(kāi)行重車流、空車流列車的頻率，Z0+為正整數(shù)集；∈{0,1} 為相同到站車流的樹(shù)形運(yùn)輸決策變量[4]，若終點(diǎn)為n站的車流d，在同一技術(shù)站n′∈改編后，選擇列車運(yùn)行弧，即n′站(na,+站)的后續(xù)改變站為na,-站時(shí)，1；否則，0。其中，為終點(diǎn)為n站的車流d的車流徑路，顯然為所含車站集。

2.3 模型建立

式(1)為動(dòng)態(tài)車流組織優(yōu)化模型目標(biāo)，使規(guī)劃期內(nèi)重車流徑路費(fèi)用、空車走行費(fèi)用、列車開(kāi)行費(fèi)用的廣義總費(fèi)用最??；a′t∈AR、a″t∈AR均為運(yùn)行時(shí)空弧，Ta″t為a″t∈AR上列車運(yùn)行時(shí)長(zhǎng)，單位列車開(kāi)行費(fèi)用α為單位列車固定開(kāi)行費(fèi)用(元·車-1)；指運(yùn)行時(shí)空弧a″t∈AR上單位列車每運(yùn)行1 時(shí)段的燃油費(fèi)用(元·時(shí)段-1)。式(2)為重車流時(shí)空服務(wù)徑路唯一性約束。式(3)、式(4)為車流改編徑路唯一性約束與樹(shù)形改編約束。式(5)為重車流選擇列車運(yùn)行弧與時(shí)空服務(wù)徑路的關(guān)聯(lián)約束，當(dāng)車流d選擇運(yùn)行弧a時(shí)，才能選擇包含a對(duì)應(yīng)的運(yùn)行時(shí)空弧at∈AR(a)的時(shí)空服務(wù)徑路式(6)、式(7)為節(jié)點(diǎn)與區(qū)段不對(duì)流空車約束，節(jié)點(diǎn)h∈N不允許同時(shí)存在到達(dá)、出發(fā)空車流，且區(qū)段v∈V不允許同時(shí)存在正向、反向空車流。式(8)為空車流選擇列車運(yùn)行弧與運(yùn)行時(shí)空弧的關(guān)聯(lián)約束，當(dāng)節(jié)點(diǎn)i,j∈N允許開(kāi)行空車直達(dá)列車，空車流才可選擇nat,+∈NT,OUT(i),nat,-∈NT,IN(j)的運(yùn)行時(shí)空弧at∈AR。式(9)為重車、空車流轉(zhuǎn)換關(guān)聯(lián)約束[11]，是時(shí)段t內(nèi)n站的空車分配決策，左側(cè)為空車供應(yīng)，即時(shí)段t內(nèi)n站空車存量、到達(dá)空車量與完成卸車的到站重車流量三者之和；右側(cè)為空車需求，即時(shí)段t+1 內(nèi)n站空車存量、時(shí)段t內(nèi)n站為其他站配送的空車量與開(kāi)始裝車的重車流量三者之和。式(10)、式(11)為列車運(yùn)行時(shí)空弧的運(yùn)輸能力約束，ηmat,ηmE,at分別為at∈AR上單位列車最小重車或空車編組輛數(shù)；d:p∈Pd為車流d通過(guò)時(shí)空服務(wù)徑路p,即兩者相關(guān)聯(lián)。式(12)、式(13)為區(qū)段通過(guò)能力約束，指列車運(yùn)行弧a若需正向或反向途經(jīng)區(qū)段v，其通過(guò)v的后方全部區(qū)段所需時(shí)長(zhǎng)；Cv,t,Cvˉ,t指時(shí)段t內(nèi)區(qū)段v的正向、反向通過(guò)能力(列)。式(14)～式(16)為技術(shù)站能力約束，依次指改編作業(yè)能力、到發(fā)線與分類線數(shù)約束。

3 算法設(shè)計(jì)

通過(guò)表2建模特點(diǎn)分析可知，本文模型引入的空車調(diào)配約束較復(fù)雜，既有算法[4,13]均難以快速有效處理，故本文結(jié)合重車或空車配空的時(shí)間接續(xù)要求，通過(guò)k短路搜索與可行解構(gòu)造，將退火機(jī)制引入差分進(jìn)化算法(DE)進(jìn)行求解。

表2 本文建模特點(diǎn)分析Table 2 Model characteristic of this paper

(1)k短路搜索與可行解構(gòu)造

借鑒文獻(xiàn)[14]中k短路算法搜索重車、空車流時(shí)空服務(wù)徑路可行集，以減小問(wèn)題規(guī)模。并結(jié)合重車或空車配空的時(shí)間接續(xù)要求，將不同的k短路重車流方案與空車配空方案相關(guān)聯(lián)，引入貪婪策略、退火策略，改進(jìn)文獻(xiàn)[4]的可行解構(gòu)造方法，可行解構(gòu)造流程如圖2所示。

圖2 可行解構(gòu)造流程Fig.2 Flow diagram of constructing feasible solution

①基于貪婪策略的關(guān)聯(lián)與配空方案初選

當(dāng)k值確定，若基點(diǎn)或關(guān)聯(lián)車流dl起點(diǎn)站空車充足，則根據(jù)不同時(shí)空徑路序號(hào)q值，分別以φk,q,dl為起點(diǎn)，按重車流約束與合并開(kāi)行要求，以關(guān)聯(lián)方案費(fèi)用增長(zhǎng)最小、列車開(kāi)行費(fèi)用節(jié)省最大為原則，依次篩選關(guān)聯(lián)車流dl,RD，確定關(guān)聯(lián)方案tpk,q,dl；否則，按配空要求，以重車配空優(yōu)先、空車配空次之的原則和配空方案費(fèi)用排序，為各配空方案設(shè)置配空策略編碼k′dl∈Kdl，選擇k′dl最小的配空方案ECk,q,dl。

②基于退火策略的關(guān)聯(lián)與配空方案比選

以相同k值，不同q值的車流dl方案φk,q,dl為起點(diǎn)，形成不同關(guān)聯(lián)方案tpk,q,dl與配空方案ECk,q,dl，即方案ICk,q,dl，以概率選擇較優(yōu)方案ICk,q,dl，其中，ζk,q,dl,ζmin為各方案ICk,q,dl權(quán)值與最小權(quán)值，δ為當(dāng)前溫度。

(2)編碼與初始種群

根據(jù)可行解構(gòu)造中車流di運(yùn)送方案φk,q,dl,(k=0,1,2,…,K;q=1,2,3,…,I)的時(shí)空徑路序號(hào)q以及配空策略編碼k′dl∈Kdl，設(shè)計(jì)個(gè)體實(shí)數(shù)編碼方案：，其中，I+1 為虛擬徑路方案，Kdl+1 表示不需要配空，并以概率ψk,q,dl隨機(jī)選擇方案ICk,q,dl，獲得規(guī)模為Nps的初始種群。

(3)算子設(shè)計(jì)與算法流程

算法流程如圖3所示。

圖3 混合差分進(jìn)化算法(HYDE)的算子設(shè)計(jì)與流程Fig.3 Operator design and framework of hybrid differential evolution algorithm

采用常用的DE/best/1 變異策略及交叉、選擇策略，GM為最大迭代次數(shù)，計(jì)算式為

式中：χr1,G,χr2,G為規(guī)模為Nps的種群中兩個(gè)不同個(gè)體；變異率F=0.7；rand 表示隨機(jī)數(shù)；D表示車流集合；交叉率CR=0.1 ；χτ,l,G,γτ,l,G,Uτ,l,G分別為個(gè)體χτ,G中對(duì)應(yīng)第l支車流運(yùn)送方案與配空方案的l列原始、變異、交叉后編碼。

當(dāng)變異交叉新個(gè)體χτ,G不滿足約束，需先根據(jù)χτ,G編碼確定車流dl改編調(diào)整方案和配空策略k′dl，按可行解構(gòu)造方法獲得新解；當(dāng)配空策略k′dl無(wú)效時(shí)，則選k′dl最小的可行配空方案。由于可行解構(gòu)造引入退火策略，故該策略將影響DE算法。

4 案例分析

以我國(guó)東北地區(qū)某局部鐵路網(wǎng)為例[4]，對(duì)本文模型及算法進(jìn)行驗(yàn)證。路網(wǎng)中有19 個(gè)站，主要參數(shù)詳見(jiàn)文獻(xiàn)[4]與圖4，車流徑路與區(qū)段通過(guò)能力、車流OD 量與車站初始空車存量，限于篇幅不予羅列。 規(guī)劃期設(shè)為T=72 h ；θ=50元·車·h-1；α=3000元·列-1；m=50車 ；mE=60車；500元·h-1；FPdv=1000元·車-1；η=0.9；βn=200車·條-1；γn=0.8。路網(wǎng)結(jié)構(gòu)及相關(guān)參數(shù)如圖4所示。

圖4 路網(wǎng)結(jié)構(gòu)及相關(guān)參數(shù)Fig.4 Structure schematic diagram of railway network and relevant parameters

(1)空車調(diào)配影響分析

以線路{1,2,6,10,13,14} 和{7,8,10,11,12} 組成的“十字”子路網(wǎng)為例，根據(jù)表3的車流量，假定所有車流的最晚到達(dá)時(shí)段t′d為16，分別求解空車充足與空車不足情景下的優(yōu)化方案。若空車充足，優(yōu)化方案目標(biāo)值為283500，如圖5所示。

表3 子路網(wǎng)的車流OD量Table 3 Wagon-flow volume in sub-network

若空車不足，假定空車存量及裝卸取送作業(yè)時(shí)間如表4所示，則需空車調(diào)配和調(diào)整圖5的方案，引起部分列車開(kāi)行時(shí)段變化及車流集結(jié)等待時(shí)間增加，優(yōu)化方案如圖6所示，目標(biāo)值增加18150。

圖5 空車充足情形下的優(yōu)化方案Fig.5 Optimization planning without considering empty car distribution

表4 子路網(wǎng)各站初始空車存量及裝卸取送作業(yè)時(shí)間Table 4 Empty car distribution and relevant parametersin sub-network

圖6 空車不足情形下的優(yōu)化方案Fig.6 Optimization planning when considering empty car distribution

配空方案如下：

②采用重車配空，由于空車直達(dá)列車1，占用區(qū)段1 →2 在時(shí)段1 的能力，列車需時(shí)段2 出發(fā)，時(shí)段5到達(dá)車站6；車流占用車站6的40輛空車存量，與中轉(zhuǎn)車流組成列車發(fā)出；而到站車流經(jīng)送卸車作業(yè)，為車流提供空車，使得車流在時(shí)段11才能完成集結(jié)，故中轉(zhuǎn)車流需要多集結(jié)等待1個(gè)時(shí)段，與其組成列車發(fā)出。

若未考慮空車調(diào)配與列車開(kāi)行方案協(xié)調(diào)，比如車站1在時(shí)段2發(fā)出空車直達(dá)列車1，將無(wú)法及時(shí)滿足列車裝車需求，導(dǎo)致其中一列延誤發(fā)車，增加額外等待費(fèi)用。將兩者綜合優(yōu)化，有助于合理安排配空方案，減少空車走行費(fèi)用，及時(shí)滿足裝車需求，有效保證作業(yè)車流配合中轉(zhuǎn)車流集結(jié)編組及時(shí)掛線，提高方案可實(shí)施性。

(2)算法效果分析

HYDE 算法采用C＃編程，其中：K=10,Kdi=20,I=30,Nps=20,CR=0.1,F=0.7，在CPU 為Intel Core E6550,2.33 GHz×2,8 G 內(nèi)存的PC 機(jī)上運(yùn)行，算法求解性能如表5所示。

表5 算法求解性能分析Table 5 Performance analysis of algorithms

當(dāng)算例規(guī)模較小時(shí)，CPLEX、SA及HYDE算法均可獲得全局最優(yōu)解。當(dāng)算例規(guī)模擴(kuò)大時(shí)，CPLEX算法無(wú)法在限定時(shí)間求得全局最優(yōu)解；SA 算法收斂速度快，但易于陷入局部最優(yōu)；HYDE 算法收斂較快，求解質(zhì)量更優(yōu)。

基于算例Ⅳ的SA、HYDE算法收斂對(duì)比如圖7所示。

圖7 基于算例Ⅳ的SA、HYDE算法收斂對(duì)比Fig.7 Convergence curve of algorithm

不考慮節(jié)點(diǎn)與區(qū)段不對(duì)流空車約束，目標(biāo)值減小，表明該要求對(duì)優(yōu)化方案造成重要影響；HYDE算法能有效處理該約束，獲得更切實(shí)際的優(yōu)化方案。

5 結(jié)論

為實(shí)現(xiàn)空車調(diào)配與列車開(kāi)行方案協(xié)調(diào)優(yōu)化，本文考慮配空與裝卸取送、集編發(fā)的時(shí)間接續(xù)要求、節(jié)點(diǎn)與區(qū)段不對(duì)流空車要求，構(gòu)建切合實(shí)際的整數(shù)規(guī)劃弧路模型，同時(shí)決策列車徑路與編組內(nèi)容、開(kāi)行時(shí)段與頻率及空車調(diào)配方案等。依據(jù)重車、空車流方案的關(guān)聯(lián)性與編碼設(shè)計(jì)，設(shè)計(jì)混合差分進(jìn)化求解算法，有效平衡種群多樣性與收斂速度。算例結(jié)果表明，模型和算法有效，有助于減少空車走行費(fèi)用，及時(shí)滿足裝車需求，協(xié)調(diào)車流組織各環(huán)節(jié)，提高方案可實(shí)施性，保證流線結(jié)合與運(yùn)到期限。