基于改進TRG方法的管內零散貨物快運列車開行方案研究

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

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

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

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

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

1 LPRSEC模型

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

1.1 模型假設

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

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

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

1.2 模型構建

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

表1 路網信息變量符號及含義

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

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

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

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

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

表4 其他變量符號及含義

1.2.1 上層規劃模型

(1)目標函數：運營成本最小化。主要考慮列車運行成本與中轉作業成本，即

(1)

(2)

(3)

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

(2)徑路與節點的服務關系約束。

(4)

(5)

(6)

(7)

(8)

(9)

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

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

(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)貨物運輸時間約束。貨物運輸應滿足運到期限的要求。由于實際運營中存在一些較難避免的時間延誤，故在貨物運輸時間中預留延誤時間。

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

(17)

(18)

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

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

Gu≤a1u?u∈U

(19)

1.2.2 下層規劃模型

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

(20)

(21)

(22)

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

fk·bk≥Ek?k∈K

(23)

(24)

(25)

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

(26)

fk≥1且為整數 ?k∈K

(27)

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

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

(28)

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

(29)

下層規劃模型中fk、bk均為需要求解的變量。由于上層規劃目標含(fk·bk)且追求最小化，為實現模型求解，式(23)應實現fk·bk→Ek。考慮fk、bk的整數特性，構建fk、bk與Ek的關系為

bk=「Ek/fk? ?k∈K

(30)

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

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

(31)

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

Ek/m1≤fk

(32)

綜上，下層規劃可轉化為決策變量是fk的整數線性規劃。目標函數為式(20)，約束條件為式(28)、式(29)、式(32)。

2 改進的TRG方法

2.1 改進TRG方法思路

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

圖1 改進的TRG方法思路

圖2 車站并入徑路示意

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

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

(33)

在這個環節中，當節點r0作為服務點并入徑路k*，一方面會增加部分OD的備選直達方案，另一方面由于徑路延長使得原經由徑路k*直達的運輸方案可能不再是最優方案。因此，分析貨運方案可能會發生變化的OD如下：

(1)節點r0到徑路k*上原貨運方案為中轉送達的節點。這一類OD的貨運方案由中轉變為徑路k*直達。

(2)節點r0到徑路k*上原貨運方案經由其他徑路直達的節點。這一類OD因備選直達方案的增加，最優方案可能會發生變化。

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

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

搜索上述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對服務點能否并入徑路存在關鍵作用。

2.2 TRG新徑路方案模型

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

表5 新增變量符號及含義

圖3 插入點與前后節點位置關系示意

(34)

(35)

(36)

(37)

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

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

(38)

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

(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新的直達、中轉方案。k′為X2、X3中OD最優直達方案的經由徑路，u′為X4中OD最優中轉方案的中轉站。式(55)、式(56)為新貨運方案下任意OD的運距。式(57)表示X2、X3中OD選擇最短用時的徑路k′直達。其中，X2中OD僅需比較經由原徑路l1i,j與新徑路k*所需的直達運輸時間，X3中OD需比較經由其他徑路與新徑路k*的直達運輸時間。式(58)為X4中OD選擇運輸時間最短方案對應的中轉站u′中轉。

計算新貨運方案下減少的貨物中轉量Q*。只有X1中OD由中轉變為直達，不再耗費中轉作業成本，即

(59)

2.4 改進TRG算法步驟

改進TRG算法的主要步驟如下：

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

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

(60)

將PS(0)中的所有途經點賦予服務點屬性。

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

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

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

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

3 LPRSEC模型求解與算例分析

3.1 求解算法

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

圖4 編碼方式

PS

(3)

(61)

(62)

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

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

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

據此，LPRSEC模型求解算法步驟如下：

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

Step2迭代終止判斷：迭代次數t大于或等于規定次數則輸出結果，否則轉Step3。

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

3.2 算例分析

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

圖5 管內零散貨物快運網絡(n=15)

表6 中轉站作業能力a1

表7 車站接發車能力a2

表8 區間通過能力a3

表9 參數取值

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

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

表10 不同m取值的模型最優解

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

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

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

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

4 結束語

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

綜上，論文研究成果對于管內零散貨物快運的運輸組織優化具有一定的理論意義和應用價值。此外，研究還可進一步改進：結合零散貨物到達發站的時間分布規律，可引入服務時間窗屬性，以實現日常運營中更好的車流與貨流配合。這是論文后續的研究方向。