易晨陽，查偉雄，李 劍，張清雅，石俊剛

(1.華東交通大學(xué) 交通運輸工程學(xué)院，江西 南昌 330013；2.廣深鐵路股份有限公司 廣州車務(wù)段，廣東 廣州 510000)

2014年我國鐵路開辦了零散貨物快運業(yè)務(wù)，是鐵路新型零擔(dān)運輸產(chǎn)品，定位于高附加值但運量小的競爭性白貨，采用區(qū)別于其他鐵路快捷貨運產(chǎn)品的新型運輸組織模式，主要特點如下：①采用客車化的運輸組織模式，貨運列車具有固定的車次、徑路與編組等，在沿線各站裝卸；②零散貨物快運由兩部分構(gòu)成，一個是將管內(nèi)全部快運站與中心站相連的管內(nèi)零散貨物快運系統(tǒng)，另一個是將各路局中心站相連的直通零散貨物快運系統(tǒng)，兩個系統(tǒng)列車開行相對獨立；③路局一般設(shè)1個中心站，在各中心站間開行點到點直達(dá)班列，實現(xiàn)貨物直通運輸，以中心站為絕大部分快運列車的首末站，在管內(nèi)開行常態(tài)化的環(huán)線列車，實現(xiàn)貨物管內(nèi)運輸。

目前，國內(nèi)外與管內(nèi)零散貨物快運具有相似運輸組織模式的列車開行方案編制研究極少。大宗貨物運輸以優(yōu)化編組去向[1-4]為主，有大量成熟研究。Xiao等[1]研究單組與雙組列車的編組計劃優(yōu)化模型，并提出一種將遺傳算法和禁忌搜索相結(jié)合的混合求解算法。在基于點對點開行模式的貨物快運列車開行方案研究中：易晨陽等[5]研究列車開行方案與貨運方案的協(xié)同優(yōu)化，模型借鑒編組去向的優(yōu)化方法；李蒞等[6]構(gòu)建貨運動車組列車開行方案優(yōu)化模型。部分貨物快運列車在運行途中設(shè)有停站，相關(guān)列車開行方案的編制研究主要采用構(gòu)建備選集的方式；夏陽等[7]基于備選集構(gòu)建快速集裝箱列車開行方案的編制模型；郭玉華等[8]基于備選班列集合優(yōu)化鐵路中轉(zhuǎn)班列開行方案；金偉等[9]采用列生成算法獲得列車徑路與停站方案的備選集，基于備選集來求解貨流與列車流的耦合問題。備選集能有效縮小可行解范圍，提升模型求解效率。然而，管內(nèi)零散貨物快運的起終點多為中心站，環(huán)線列車的可選徑路多樣，備選徑路的篩選相對困難。無論是優(yōu)化編組去向還是構(gòu)建備選集，常用的列車開行方案優(yōu)化方法難以直接用于管內(nèi)零散貨物快運。

考慮管內(nèi)零散貨物運輸組織模式的特殊性，文獻(xiàn)[10]借鑒車輛路徑問題(Vehicle Routing Problem, VRP)的路徑搜索方法，在此基礎(chǔ)上提出列車徑路組合生成 (Train Route Generation, TRG) 方法求解列車開行方案。VRP在國內(nèi)外有大量成熟的研究，并發(fā)展出帶服務(wù)時間窗、同時取送貨等研究場景的VRP衍生問題[11-13]。但VRP主要解決貨物配送問題，基本不考慮客戶間的貨運需求。而TRG方法是列車服務(wù)網(wǎng)絡(luò)從滿足中心站與快運站之間貨運需求向快運站與快運站之間貨運需求的延伸。文獻(xiàn)[10]未考慮車站作業(yè)能力、線路通過能力等方面的限制，本文針對管內(nèi)零散貨物快運開行方案問題，構(gòu)建考慮能力約束、大貨流OD服務(wù)頻率的新模型，其中，大貨流OD服務(wù)頻率的設(shè)計有利于提高列車運行計劃在時變貨流條件下的穩(wěn)定性；同時改進(jìn)TRG方法，將貨運成本作為節(jié)點并入徑路的判斷依據(jù)，最終實現(xiàn)模型的高效求解。

1 LPRSEC模型

本文將構(gòu)建的管內(nèi)零散貨物快運列車開行方案編制模型稱為LPRSEC (Line Plan for Regional Scattered Freight Express with Capacity Constrains) 模型。LPRSEC模型需要解決的問題為：在管內(nèi)零散貨物快運網(wǎng)絡(luò)上，以中心站為起終點，找到m條列車開行徑路覆蓋管內(nèi)全部快運站，以區(qū)間通過能力、車站作業(yè)能力、貨物運到期限等為約束，在運營成本最小的條件下實現(xiàn)最大的大貨流OD服務(wù)頻率，滿足貨物運輸需求。

1.1 模型假設(shè)

(1)管內(nèi)路網(wǎng)僅設(shè)有1個中心站，其為全部列車開行徑路的首末站。

(2)貨物僅在具備中轉(zhuǎn)條件的快運站中轉(zhuǎn)，且最多只能中轉(zhuǎn)1次。

(3)相同OD貨物有且只有一種運輸方案，為可選的最短用時運輸方案。

1.2 模型構(gòu)建

(1)(V,L,U)為路網(wǎng)信息，變量符號及含義見表1。

表1 路網(wǎng)信息變量符號及含義

(2)(K,P,S,H,A,F,B)為徑路方案，變量符號及含義見表2。

表2 徑路方案變量符號及含義

(3)(Y1,Y2,L1,L2)為貨運方案，變量符號及含義見表3。

表3 貨運方案變量符號及含義

(4)其他符號釋義見表4。

表4 其他變量符號及含義

1.2.1 上層規(guī)劃模型

(1)目標(biāo)函數(shù)：運營成本最小化。主要考慮列車運行成本與中轉(zhuǎn)作業(yè)成本，即

(1)

(2)

(3)

式中：fk、bk由下層規(guī)劃模型輸出。

(2)徑路與節(jié)點的服務(wù)關(guān)系約束。

(4)

(5)

(6)

(7)

(8)

(9)

式(4)表示中心站為任意徑路的起終點。式(5)表示中心站為任意徑路的服務(wù)點。式(7)表示任意快運站至少被一條徑路服務(wù)。式(8)表示除中心站外，任意徑路至少服務(wù)一個快運站。式(9)表示徑路上的途經(jīng)點可不均為服務(wù)點。

(3)貨運方案與運輸時間的關(guān)系約束。

(10)

?i,j∈Vu∈U

(11)

(12)

(13)

?i,j∈Vk∈K

(14)

?k∈Kr=1,2,…,N2(k)-1

(15)

?k∈Kr=1,2,…,N2(k)-1

(16)

(4)貨物運輸時間約束。貨物運輸應(yīng)滿足運到期限的要求。由于實際運營中存在一些較難避免的時間延誤，故在貨物運輸時間中預(yù)留延誤時間。

ti,j+d1≤di,j?i,j∈V

(17)

(18)

式(17)表示貨物運輸時間與延誤時間之和不超過貨物運到期限。式(18)表示貨運方案與運輸時間具有唯一性。

(5)中轉(zhuǎn)能力約束。車站u的中轉(zhuǎn)作業(yè)量不大于該站的中轉(zhuǎn)作業(yè)能力，即

Gu≤a1u?u∈U

(19)

1.2.2 下層規(guī)劃模型

零散貨運計劃性不強，采用隨到隨辦、敞開受理的方式，容易產(chǎn)生日常貨流與列流不匹配的現(xiàn)象。OD服務(wù)頻率表示OD間每日平均開行的列車數(shù)，是評價列車開行方案服務(wù)水平的重要指標(biāo)。在能力約束的條件下，OD服務(wù)頻率越大，列車運行計劃在時變貨流條件下的穩(wěn)定性越好。鐵路部門長期重視大宗、穩(wěn)定貨流，開展零散貨物快運業(yè)務(wù)也重視保障大貨流節(jié)點的運輸需求。因此，設(shè)定下層規(guī)劃目標(biāo)為大貨流OD服務(wù)頻率最大，即

(20)

(21)

(22)

(1)貨運需求與供給約束。

fk·bk≥Ek?k∈K

(23)

(24)

(25)

bk=m2,m2+1，…，m1-1，m1?k∈K

(26)

fk≥1且為整數(shù) ?k∈K

(27)

式(23)表示徑路上實際開行的棚車數(shù)不小于需開行的棚車數(shù)。式(24)表示徑路上需開行的棚車數(shù)取決于徑路上的最大斷面貨流量。式(25)表示徑路上各區(qū)段的貨流量由徑路貨流分配獲得。式(26)表示列車編組存在上下限。式(27)表示徑路上每日至少開行一趟車。

(2)接發(fā)列車能力約束。車站接發(fā)列車的數(shù)量不大于其接發(fā)列車能力，即

(28)

(3)區(qū)段通過能力約束。區(qū)段通過的列車數(shù)量不大于其區(qū)段通過能力，即

(29)

下層規(guī)劃模型中fk、bk均為需要求解的變量。由于上層規(guī)劃目標(biāo)含(fk·bk)且追求最小化，為實現(xiàn)模型求解，式(23)應(yīng)實現(xiàn)fk·bk→Ek。考慮fk、bk的整數(shù)特性，構(gòu)建fk、bk與Ek的關(guān)系為

bk=「Ek/fk? ?k∈K

(30)

由于「x?=x+γ,γ∈[0,1)，故式(26)結(jié)合式(30)可轉(zhuǎn)化為

Ek/(m1-γ)≤fk≤Ek/(m2-γ) ?k∈K

(31)

由于有Ek/m1≤Ek/(m2-γ)

Ek/m1≤fk

(32)

綜上，下層規(guī)劃可轉(zhuǎn)化為決策變量是fk的整數(shù)線性規(guī)劃。目標(biāo)函數(shù)為式(20)，約束條件為式(28)、式(29)、式(32)。

2 改進(jìn)的TRG方法

2.1 改進(jìn)TRG方法思路

TRG是實現(xiàn)列車服務(wù)網(wǎng)絡(luò)從滿足快運站—中心站貨運需求向快運站—快運站貨運需求延伸的重要手段。改進(jìn)TRG方法思路見圖1，具體過程是：①通過快運站排序搜索初始徑路組合PS(0)(P,S)，使m條徑路串聯(lián)起所有快運站，且任意快運站僅被1條徑路服務(wù)，其保證了每個快運站均能直達(dá)中心站；②在PS(0)基礎(chǔ)上，根據(jù)直達(dá)優(yōu)先原則，將徑路上的車站均臨時賦予服務(wù)點屬性，獲得PS(1)；③在PS(1)的基礎(chǔ)上，對任意不在徑路上的快運站進(jìn)行服務(wù)點并入判斷，若允許并入則進(jìn)一步擴展徑路的服務(wù)點、途經(jīng)點序列，見圖2，獲得PS(2)；④根據(jù)PS(2)及其貨運方案(Y1,Y2,L1,L2)，刪除徑路上未被貨流使用的服務(wù)點，獲得最終徑路組合PS(3)。

圖1 改進(jìn)的TRG方法思路

圖2 車站并入徑路示意

當(dāng)管內(nèi)零散貨物快運網(wǎng)絡(luò)中只存在直通零散貨運需求時，初始徑路組合PS(0)即可滿足運輸需求，無需計算PS(1)～PS(3)；當(dāng)管內(nèi)零散貨物快運網(wǎng)絡(luò)中同時存在直通與管內(nèi)零散貨運需求時，通過“服務(wù)點并入判斷”，使管內(nèi)零散貨物的直達(dá)方案被逐步添加到貨運方案集合中，實現(xiàn)最優(yōu)徑路組合的快速搜索。

因此，由服務(wù)點并入獲得PS(2)是改進(jìn)的TRG方法的關(guān)鍵環(huán)節(jié)。服務(wù)點并入判斷的依據(jù)是其對運營成本(上層規(guī)劃目標(biāo))的影響。LPRSEC模型上層規(guī)劃目標(biāo)函數(shù)的求解需要進(jìn)行配流、求解下層規(guī)劃，若每一次服務(wù)點并入判斷均要求解上層規(guī)劃目標(biāo)值，則計算規(guī)模太大，耗時過長。故考慮簡化的運營成本判斷方法，為

(33)

在這個環(huán)節(jié)中，當(dāng)節(jié)點r0作為服務(wù)點并入徑路k*，一方面會增加部分OD的備選直達(dá)方案，另一方面由于徑路延長使得原經(jīng)由徑路k*直達(dá)的運輸方案可能不再是最優(yōu)方案。因此，分析貨運方案可能會發(fā)生變化的OD如下：

(1)節(jié)點r0到徑路k*上原貨運方案為中轉(zhuǎn)送達(dá)的節(jié)點。這一類OD的貨運方案由中轉(zhuǎn)變?yōu)閺铰穔*直達(dá)。

(2)節(jié)點r0到徑路k*上原貨運方案經(jīng)由其他徑路直達(dá)的節(jié)點。這一類OD因備選直達(dá)方案的增加，最優(yōu)方案可能會發(fā)生變化。

(3)原貨運方案由徑路k*直達(dá)，且r0的插入位置在裝車站、卸車站之間的OD。這一類OD可能會由于徑路k*延長使其用時最短直達(dá)方案發(fā)生變化，且其裝、卸車站在新徑路上的位置編號發(fā)生改變。

(4)原貨運方案經(jīng)由徑路k*中轉(zhuǎn)運輸，且r0的插入位置在裝車站→中轉(zhuǎn)站或中轉(zhuǎn)站→卸車站之間的OD。這一類OD可能會因徑路k*延長導(dǎo)致用時最短的中轉(zhuǎn)方案發(fā)生變化。

搜索上述4類OD，并置于集合X1、X2、X3、X4?？赏浦旱?、2類OD有ΔCr0,k*≤0,?(i,j)∈X1∪X2；第3、4類OD有ΔCr0,k*≥0,?(i,j)∈X3∪X4。故第1、2類OD對服務(wù)點能否并入徑路存在關(guān)鍵作用。

2.2 TRG新徑路方案模型

新增變量的符號及含義見表5。

表5 新增變量符號及含義

圖3 插入點與前后節(jié)點位置關(guān)系示意

(34)

(35)

(36)

(37)

節(jié)點r0的插入位置要使徑路k*的長度增長最少，即

r=2,3,…,N2(k*)

(38)

新徑路上列車離開r0站及前方車站的時刻，為上一站的離站時刻加上新增的列車區(qū)間運行時間與停站時間，即

(39)

(40)

新徑路上列車離開r0站及前方車站時的累計運行里程，是在上一站的累計運行里程加上新增的路徑距離，即

(41)

(42)

2.3 TRG新貨運方案模型

?i∈sk*

(43)

?i∈sk*

(44)

?i,j∈sk*

(45)

?i,j∈V且i,j≠r0

(46)

?i,j∈Vk∈K

(47)

?i,j∈Vk∈K

(48)

(49)

(50)

(51)

?i,j∈V

(52)

(53)

(54)

?i,j∈V

(55)

(56)

?i,j∈V

(57)

?(i,j)∈X4u∈Uk1=l1i,uk2=l1u,j

(58)

式(53)、式(54)分別為4類OD新的直達(dá)、中轉(zhuǎn)方案。k′為X2、X3中OD最優(yōu)直達(dá)方案的經(jīng)由徑路，u′為X4中OD最優(yōu)中轉(zhuǎn)方案的中轉(zhuǎn)站。式(55)、式(56)為新貨運方案下任意OD的運距。式(57)表示X2、X3中OD選擇最短用時的徑路k′直達(dá)。其中，X2中OD僅需比較經(jīng)由原徑路l1i,j與新徑路k*所需的直達(dá)運輸時間，X3中OD需比較經(jīng)由其他徑路與新徑路k*的直達(dá)運輸時間。式(58)為X4中OD選擇運輸時間最短方案對應(yīng)的中轉(zhuǎn)站u′中轉(zhuǎn)。

計算新貨運方案下減少的貨物中轉(zhuǎn)量Q*。只有X1中OD由中轉(zhuǎn)變?yōu)橹边_(dá)，不再耗費中轉(zhuǎn)作業(yè)成本，即

(59)

2.4 改進(jìn)TRG算法步驟

改進(jìn)TRG算法的主要步驟如下：

(1)初始徑路組合PS(0)生成。詳見3.1。

(2)服務(wù)點擴充，生成PS(1)。擴充方法為

(60)

將PS(0)中的所有途經(jīng)點賦予服務(wù)點屬性。

(3)服務(wù)點并入判斷，生成PS(2)。

Step1基于PS(1)計算原貨運方案(Y1,Y2,L1,L2) (詳見文獻(xiàn)[10])，轉(zhuǎn)Step2。

Step4判斷是否遍歷了全部徑路k，否則轉(zhuǎn)Step2，是則結(jié)束運算并輸出PS(2)。

(4)服務(wù)點刪除判斷，生成PS(3)。

3 LPRSEC模型求解與算例分析

3.1 求解算法

LPRSEC模型采用結(jié)合改進(jìn)TRG方法的單親遺傳算法求解。種群個體的編碼方式見圖4。x基因段為不重復(fù)的快運站編號排序(不含中心站)，y基因段為PS(0)中各徑路上的服務(wù)點數(shù)量。種群個體解碼可獲得PS(0)：①在被y基因分隔的x基因段首末加上中心站編號，例如：已知n=5,m=2，中心站編號為“0”，個體基因為“124331”，可將其分解為 “0-1-2-4-0”與“0-3-0”；②用Dijkstra算法求取以上相鄰節(jié)點間的最短路徑，組成完整徑路，獲得PS(0)。之后通過改進(jìn)的TRG方法將PS(0)轉(zhuǎn)化為PS(3)。

圖4 編碼方式

PS

(3)

(61)

(62)

式中：Z1為上層規(guī)劃的目標(biāo)函數(shù)值；ρ為下層規(guī)劃解的輸出形式，ρ=1為下層規(guī)劃模型無可行解，反之ρ=0；κ為懲罰系數(shù)(κ>0)，取極大值M。

式(62)表示當(dāng)下層規(guī)劃模型有可行解時，輸出(fk,bk)并計算Z1；無可行解時Z1=M。

根據(jù)適應(yīng)值對種群個體(對應(yīng)PS(0))進(jìn)行繁殖與基因重組操作[14]。其中，父代采用雜草算法繁殖機制[14]，子代基因根據(jù)IPGA重組方式生成[15]。

據(jù)此，LPRSEC模型求解算法步驟如下：

Step1種群初始化[10]，計算ξi,j與初代種群P(t=0)適應(yīng)度，轉(zhuǎn)Step2。

Step2迭代終止判斷：迭代次數(shù)t大于或等于規(guī)定次數(shù)則輸出結(jié)果，否則轉(zhuǎn)Step3。

Step3對種群P(t)開展繁殖與基因重組操作，獲得新一代種群P(t+1)，計算新種群適應(yīng)度。t=t+1，轉(zhuǎn)Step2。

3.2 算例分析

以南昌局管內(nèi)路網(wǎng)為參照，構(gòu)建管內(nèi)零散貨物快運網(wǎng)絡(luò)，見圖5。圓圈內(nèi)數(shù)字為車站編號，連接邊括號內(nèi)的數(shù)字表示站間距離，km，括號外的數(shù)字表示從左至右、從上到下的區(qū)段編號，例如區(qū)段“1-3”、“3-1”的編號分別為“1”和“-1”。節(jié)點1為中心站，中轉(zhuǎn)站集合U={1,5,7,11}，能力參數(shù)a1～a3見表6～表8，其他參數(shù)見表9。隨機生成測試貨流集合{Qi,j}，貨流量總計6 386 t/d。

圖5 管內(nèi)零散貨物快運網(wǎng)絡(luò)(n=15)

表6 中轉(zhuǎn)站作業(yè)能力a1

表7 車站接發(fā)車能力a2

表8 區(qū)間通過能力a3

表9 參數(shù)取值

目前各路局管內(nèi)零散貨物快運的列車開行徑路數(shù)量為2～6條，平均4條。據(jù)此，測試m分別取{3,4,5,6}時的運算結(jié)果，并判定最優(yōu)的列車開行方案。算法用MATLAB R2019a實現(xiàn)，下層規(guī)劃采用其內(nèi)置函數(shù)intprog求解。測試種群規(guī)模與迭代次數(shù)，發(fā)現(xiàn)取種群規(guī)模200、迭代200次時運算結(jié)果相對穩(wěn)定，能較快、較好地趨近最優(yōu)解。測試不同列車開行徑路數(shù)量m條件下的模型最優(yōu)解，每組經(jīng)15次運算測試，獲得不同m條件下最優(yōu)解的收斂情況，見圖6，計算結(jié)果見表10所示。當(dāng)m=5時，管內(nèi)零散貨物快運的運營成本最小，為141.68萬元；m=4,6時，運營成本與其相近，分別為143.03、144.75萬元。但m=5,6時，大貨流OD服務(wù)頻率最小，為1.6；m=4時，大貨流OD服務(wù)頻率較大，為1.97。

圖6 不同m取值的收斂曲線圖

表10 不同m取值的模型最優(yōu)解

綜合上、下層目標(biāo)函數(shù)值，取m=4為最優(yōu)方案，見表11。徑路全長最大2 662 km，最小1 158 km。由于管內(nèi)零散貨物快運為棚車編組，可加掛宿營車，故該列車徑路長度是可行的。徑路1、2的列車開行數(shù)量為3列/d，編組分別為7車/列、6車/列；徑路3、4的列車開行數(shù)量為2列/d，編組分別為6車/列、9車/列。部分徑路列車開行數(shù)量較小是受區(qū)間通過能力較小、大貨流OD較少等因素的綜合限制。

表11 管內(nèi)零散貨物快運列車開行方案(m=4)

列車開行徑路與區(qū)段流量(m=4)見圖7。圖中連接邊旁的數(shù)字為線路區(qū)段上的貨流量，t，括號外為編號是正數(shù)的區(qū)段流量，括號內(nèi)為編號是負(fù)數(shù)的區(qū)段流量。其中，1—11、11—1、1—5、5—1、5—7為最繁忙區(qū)段，這是因為大量貨物在中心站集散，進(jìn)而呈現(xiàn)出貨流向中心站聚集或由中心站向路網(wǎng)發(fā)散的特點。節(jié)點5、11作為介值較大、具有中轉(zhuǎn)站屬性的節(jié)點，也承擔(dān)了大量貨物的集散工作。

圖7 列車開行徑路與區(qū)段流量示意圖(m=4)

4 結(jié)束語

本文主要研究工作如下：①在LPRSE模型的基礎(chǔ)上，新增了區(qū)間通過能力、車站接發(fā)列車能力、中轉(zhuǎn)作業(yè)能力三種能力約束，以管內(nèi)零散貨物快運的運營成本最小為上層目標(biāo)，大貨流OD服務(wù)頻率最大為下層目標(biāo)構(gòu)建了LPRSEC模型。大貨流OD服務(wù)頻率的設(shè)計，有利于減少零散貨流到站時間分布不均衡帶來的負(fù)面影響，提高列車運行計劃在時變貨流條件下的穩(wěn)定性。②設(shè)計改進(jìn)的TRG方法，通過判斷服務(wù)點并入徑路前后對貨運成本的影響，使管內(nèi)零散貨物的直達(dá)方案被逐步添加到貨運方案集合中，最終實現(xiàn)最優(yōu)徑路組合的快速搜索，提高了模型求解效率。同時，通過刪除徑路上未被OD使用的服務(wù)點，減少徑路上的服務(wù)點數(shù)量，實現(xiàn)列車停站優(yōu)化。③將下層規(guī)劃轉(zhuǎn)化為整數(shù)線性規(guī)劃，將解的形式融入適應(yīng)值函數(shù)，結(jié)合改進(jìn)的TRG方法與單親遺傳算法，設(shè)計LPRSEC模型求解算法。④以南昌局管內(nèi)零散貨物快運網(wǎng)絡(luò)為參照進(jìn)行算例分析，分別測試了不同列車開行徑路數(shù)量條件下的運算結(jié)果，得到了最優(yōu)的列車開行方案。

綜上，論文研究成果對于管內(nèi)零散貨物快運的運輸組織優(yōu)化具有一定的理論意義和應(yīng)用價值。此外，研究還可進(jìn)一步改進(jìn)：結(jié)合零散貨物到達(dá)發(fā)站的時間分布規(guī)律，可引入服務(wù)時間窗屬性，以實現(xiàn)日常運營中更好的車流與貨流配合。這是論文后續(xù)的研究方向。