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

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

0 引言

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

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

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

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

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

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

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

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

圖1 貨運(yùn)時空服務(wù)網(wǎng)絡(luò)與車流時空服務(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)時段未知，即開始集結(jié)時段未知，需根據(jù)重車、空車流組織和時間窗要求進(jìn)行決策。

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

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

2.2 決策變量與中間變量

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

2.3 模型建立

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

3 算法設(shè)計

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

表2 本文建模特點分析Table 2 Model characteristic of this paper

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

借鑒文獻(xiàn)[14]中k短路算法搜索重車、空車流時空服務(wù)徑路可行集，以減小問題規(guī)模。并結(jié)合重車或空車配空的時間接續(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值確定，若基點或關(guān)聯(lián)車流dl起點站空車充足，則根據(jù)不同時空徑路序號q值，分別以φk,q,dl為起點，按重車流約束與合并開行要求，以關(guān)聯(lián)方案費(fè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為起點，形成不同關(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)的時空徑路序號q以及配空策略編碼k′dl∈Kdl，設(shè)計個體實數(shù)編碼方案：，其中，I+1 為虛擬徑路方案，Kdl+1 表示不需要配空，并以概率ψk,q,dl隨機(jī)選擇方案ICk,q,dl，獲得規(guī)模為Nps的初始種群。

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

算法流程如圖3所示。

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

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

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

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

4 案例分析

以我國東北地區(qū)某局部鐵路網(wǎng)為例[4]，對本文模型及算法進(jìn)行驗證。路網(wǎng)中有19 個站，主要參數(shù)詳見文獻(xiàn)[4]與圖4，車流徑路與區(qū)段通過能力、車流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á)時段t′d為16，分別求解空車充足與空車不足情景下的優(yōu)化方案。若空車充足，優(yōu)化方案目標(biāo)值為283500，如圖5所示。

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

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

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

表4 子路網(wǎng)各站初始空車存量及裝卸取送作業(yè)時間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 在時段1 的能力，列車需時段2 出發(fā)，時段5到達(dá)車站6；車流占用車站6的40輛空車存量，與中轉(zhuǎn)車流組成列車發(fā)出；而到站車流經(jīng)送卸車作業(yè)，為車流提供空車，使得車流在時段11才能完成集結(jié)，故中轉(zhuǎn)車流需要多集結(jié)等待1個時段，與其組成列車發(fā)出。

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

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

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

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

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

5 結(jié)論

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