考慮車輛周轉(zhuǎn)的鐵路動態(tài)貨運服務(wù)網(wǎng)絡(luò)設(shè)計優(yōu)化模型及其分支-定價-切割算法

王保華，何世偉

(1. Amazon Research，北京 100024；2.北京交通大學(xué) 交通運輸學(xué)院，北京 100044)

鐵路貨運服務(wù)網(wǎng)絡(luò)設(shè)計屬于戰(zhàn)術(shù)規(guī)劃層次的決策內(nèi)容，主要目標(biāo)是制定一個貨運列車開行方案，包括列車始發(fā)和終到站(以及甩掛站)、開行頻率、編組內(nèi)容等，力求在一定服務(wù)水平的基礎(chǔ)上滿足客戶的運輸需求。鐵路動態(tài)貨運服務(wù)網(wǎng)絡(luò)設(shè)計在此基礎(chǔ)上進一步引入時間維度，根據(jù)列車開行頻率以及列車間車流接續(xù)關(guān)系規(guī)定了各列車的具體開行時段，可作為列車開行方案與列車運行圖的中間過渡環(huán)節(jié)，為編制列車運行圖奠定良好基礎(chǔ)。貨物列車的組織開行需要充足的動力(機車)和裝載設(shè)備資源(車輛)作保障，二者的合理運用是貨運服務(wù)網(wǎng)絡(luò)能夠高效率、低成本滿足客戶運輸需求的基礎(chǔ)。如果決策者能夠在優(yōu)化設(shè)計貨物服務(wù)網(wǎng)絡(luò)的同時考慮機車車輛資源的合理周轉(zhuǎn)，既可以使當(dāng)前已經(jīng)投入使用的機車和車輛資源發(fā)揮最大效力，也可以避免由于機車、車輛資源不足導(dǎo)致日常運輸組織無法正常開展。

盡管眾多學(xué)者對貨運服務(wù)網(wǎng)絡(luò)設(shè)計進行了廣泛的研究[1-21]，但與鐵路相關(guān)的研究仍然相對較少。文獻[3]把鐵路貨運列車開行方案問題構(gòu)建為一個混合整數(shù)規(guī)劃模型，考慮列車最大編組輛數(shù)和車站中轉(zhuǎn)能力限制等約束，目標(biāo)在于最小化列車開行費用、車小時費用、車輛中轉(zhuǎn)費用。該文給出一種基于Lagrangian的對偶調(diào)整算法用于求解模型，并基于美國鐵路運輸企業(yè)的實際案例對模型和算法進行了測試。文獻[4]基于動態(tài)需求構(gòu)建列車編組和空車調(diào)整綜合優(yōu)化模型，目標(biāo)在于最小化列車開行費用、中轉(zhuǎn)費用以及相關(guān)延誤和懲罰費用。該文給出一種基于分解策略的啟發(fā)式算法，并在由4個車站及5條雙向線路組成的網(wǎng)絡(luò)中進行了測試。文獻[8]以滿足客戶服務(wù)水平為目標(biāo)，研究鐵路貨運列車開行方案問題，并將遺傳算法和禁忌搜索算法結(jié)合起來對模型進行了求解。文獻[17]研究了快捷貨物運輸動態(tài)服務(wù)網(wǎng)絡(luò)的設(shè)計問題，主要以鐵路運輸為例給出了優(yōu)化模型和求解算法，并分析了該模型和算法在公路和航空領(lǐng)域的通用性。文獻[18]以意大利鐵路為背景，將鐵路貨運列車開行方案問題轉(zhuǎn)化為一類費用為凹函數(shù)的多商品網(wǎng)絡(luò)流問題，并給出了一種禁忌搜索算法。

近年來也有若干學(xué)者開始研究考慮相關(guān)設(shè)備資源周轉(zhuǎn)的貨運服務(wù)網(wǎng)絡(luò)設(shè)計問題，這些研究通常引入時間維度來描述資源的循環(huán)過程，在服務(wù)網(wǎng)絡(luò)設(shè)計優(yōu)化時考慮最大化這些資源的利用率。文獻[7]研究公鐵聯(lián)運網(wǎng)絡(luò)中的運輸計劃編制問題，構(gòu)建了時空網(wǎng)絡(luò)用于描述鐵路平車、拖車的周轉(zhuǎn)過程以及貨物的移動過程。該文構(gòu)建整數(shù)規(guī)劃模型并給出求解算法，還進一步考慮了車站作業(yè)能力、機車周轉(zhuǎn)等因素的影響。文獻[14-15]研究了考慮多種資源周轉(zhuǎn)的貨運服務(wù)網(wǎng)絡(luò)設(shè)計問題，該文構(gòu)建了包含聯(lián)弧和循環(huán)設(shè)計變量、聯(lián)弧和徑路貨流變量的多商品網(wǎng)絡(luò)流模型，給出了各類服務(wù)開行時間的確定方法，目標(biāo)在于最小化所有貨物的總運輸時間。該文還考慮了空駛車輛的調(diào)配問題。文獻[19]基于上文的研究給出了一種基于分支-定價的求解框架，提高了模型求解效率。

本文主要研究考慮貨運車輛周轉(zhuǎn)的鐵路動態(tài)服務(wù)網(wǎng)絡(luò)設(shè)計問題。首先拓展傳統(tǒng)的離散時空網(wǎng)絡(luò)為一類超級網(wǎng)絡(luò)，用于描述貨運車輛在網(wǎng)絡(luò)中的流動過程(即所謂車輛流)以及在重、空兩種狀態(tài)中的轉(zhuǎn)換，基于此構(gòu)建混合整數(shù)規(guī)劃模型。動態(tài)服務(wù)網(wǎng)絡(luò)設(shè)計問題由于引入了時間因素，通常會導(dǎo)致網(wǎng)絡(luò)規(guī)模較為龐大，采用商用優(yōu)化模型求解軟件(如IBM ILOG等)無法直接求解，而本文所研究的問題又在網(wǎng)絡(luò)中引入了車輛流的概念，進一步增加了模型的求解難度，故本文給出一種基于分支-定價-切割的求解算法，通過動態(tài)調(diào)整貨流和車輛流的徑路集以減小模型規(guī)劃和計算量。最后通過算例對算法進行驗證。

本文所建的模型不僅適用于某單一特定車型，也適用于更為普遍的多車型場景，而單一車型(如糧食專用車、化學(xué)用品專用罐車等)可以看作是對給出模型的一種簡化。本文給出的方法既可應(yīng)用于中長期計劃的制定，也可以用于周、日計劃乃至階段計劃的編制過程。當(dāng)應(yīng)用于中長期計劃制定時，根據(jù)給定貨流結(jié)構(gòu)、可用車型、各車型車輛數(shù)量和空間分布，可以得到最優(yōu)列車時刻表以及列車編組計劃；當(dāng)用于短期計劃時，編組計劃可作為框架性指導(dǎo)，列車編組內(nèi)容將嚴(yán)格按照編組計劃規(guī)定，這將簡化模型和算法的計算量，但與此同時，問題的優(yōu)化空間也受一定影響。考慮到實際運營中，編組計劃經(jīng)常根據(jù)貨流結(jié)構(gòu)進行微調(diào)，本研究在應(yīng)用于短期計劃編制時，可以考慮適當(dāng)放寬編組計劃，例如只嚴(yán)格規(guī)定重點列車的編組內(nèi)容，而允許對其他列車的編組計劃進行調(diào)整，此時，模型結(jié)果也可以用于編組計劃微調(diào)的參考和依據(jù)。

1 考慮車輛周轉(zhuǎn)的鐵路動態(tài)運輸服務(wù)網(wǎng)絡(luò)設(shè)計模型

在模型構(gòu)建之前，首先對文獻[17]定義的鐵路動態(tài)服務(wù)網(wǎng)絡(luò)進行拓展。該文獻中的鐵路動態(tài)服務(wù)網(wǎng)絡(luò)以離散時空網(wǎng)絡(luò)為基礎(chǔ)，只要合理設(shè)置單位時段的長度，離散時空網(wǎng)絡(luò)足以滿足實際應(yīng)用需要。在運輸服務(wù)網(wǎng)絡(luò)結(jié)構(gòu)已經(jīng)確定的條件下，各類車輛在網(wǎng)絡(luò)中的流轉(zhuǎn)可以看作是車輛流尋路的過程，車輛將按照一定規(guī)則分配到運輸服務(wù)網(wǎng)絡(luò)中的各條運輸服務(wù)聯(lián)弧(也即列車運行線)上去。與普通貨流有所不同的是，車輛流在運輸服務(wù)網(wǎng)絡(luò)上的分配過程要更加靈活，有可能有特定的起點和終點，也有可能有服務(wù)區(qū)域的限制(例如，用于散糧運輸專用的車輛一般都為企業(yè)自購，只能服務(wù)于部分區(qū)域)，并且運輸服務(wù)聯(lián)弧上的車輛流大小應(yīng)與其上的貨流大小相匹配。基于此，根據(jù)車輛的使用區(qū)域范圍對動態(tài)離散時空網(wǎng)絡(luò)進行區(qū)域劃分，每個區(qū)域添加一個超級節(jié)點表示車輛流的虛擬起點，為所有區(qū)域添加一個超級節(jié)點表示車輛流的虛擬終點，不同區(qū)域之間通過運輸服務(wù)聯(lián)弧相連，如圖1所示。圖1中的運輸服務(wù)聯(lián)弧表示貨運列車，其發(fā)車時間、出發(fā)站、到達時間、到達站等信息取決于聯(lián)弧起點和終點的屬性，延遲聯(lián)弧表示車流在同一車站的停留過程，超級聯(lián)弧并沒有實際含義，僅代表車輛的虛擬起點和虛擬終點。車輛不同使用區(qū)域?qū)?yīng)不同的虛擬起點和虛擬終點，車輛將從對應(yīng)區(qū)域的虛擬起點出發(fā)，在該區(qū)域?qū)?yīng)的時空網(wǎng)絡(luò)中(整個時空網(wǎng)絡(luò)的一部分)選擇合理的徑路。

圖1 超級動態(tài)貨運列車服務(wù)網(wǎng)絡(luò)

1.1 參數(shù)定義

1.2 決策變量定義

1.3 模型構(gòu)建

( 1 )

s.t.

?f∈F

( 2 )

( 3 )

( 4 )

( 5 )

?a∈Atrain，e∈E

( 6 )

xa∈{0，1}，?a∈Atrain

( 7 )

( 8 )

( 9 )

式( 1 )為目標(biāo)函數(shù)，表示最小化總成本，包括添加運輸服務(wù)聯(lián)弧的固定成本、貨流在網(wǎng)絡(luò)中流動的成本及車輛流在網(wǎng)絡(luò)中流動的成本；式( 2 )為貨流的流量守恒約束；式( 3 )為車輛流的流量守恒約束；式( 4 )和式( 5 )為運輸服務(wù)聯(lián)弧上車輛流的最小值和最大值約束，其中最大值和最小值即編組計劃規(guī)定的列車最大編組輛數(shù)和最小編組輛數(shù)；式( 6 )表示運輸服務(wù)聯(lián)弧上的總貨流量應(yīng)小于其上車輛流決定的最大流量；式( 7 )～式( 9 )為決策變量的邏輯約束。

2 求解算法

首先討論Benders割的生成方法。基于給定的服務(wù)網(wǎng)絡(luò)設(shè)計變量xa，原模型退化為包含兩類商品流(貨流和車輛流)的多商品網(wǎng)絡(luò)流問題，給出基于列生成的求解算法。

2.1 Benders割的生成方法

令運輸服務(wù)網(wǎng)絡(luò)設(shè)計變量xa(x為其向量形式)為原模型的復(fù)雜變量，τ為人工變量，可定義主問題如下

P2：

s.t.

xa∈{0，1}，?a∈Atrain

τ≥0

令(x*，τ*)表示上述主問題的最優(yōu)解的向量形式。在模型中添加人工變量m和r用于保證子問題總有解。由于服務(wù)網(wǎng)絡(luò)設(shè)計變量x為整數(shù)變量，因此需要考慮該變量的分支過程(該變量只取0或1，因此分支過程較為簡單，本文不再贅述)。給定(x*，τ*)，可構(gòu)建子問題用于獲取Benders割。

s.t.

?f∈F

(13)

(14)

?a∈Atrain

(15)

?a∈Atrain

(16)

m|F|+|L|+2|Atrain|+a+e-n≤0 ?a∈Atrain，e∈E

(17)

(18)

xa∈{0，1}，?a∈Atrain

(19)

(20)

(21)

mj≥0，i=1，2，…，2|Atrain|+

|Atrain||E|+|F|+|L|

(22)

r>0

(23)

以上模型可以用下文介紹的列生成法求解。令(y*，z*，m*，l*)表示子問題的最優(yōu)解，β為式(18)的對偶向量，M表示一個足夠大的正數(shù)，原模型最優(yōu)目標(biāo)函數(shù)值的上界為

原模型最優(yōu)目標(biāo)函數(shù)值的下界為

如果|ωupper-ωlower|≤ε，不需要再向模型中添加Benders割，否則，在上文中的主問題中添加如下Benders割

2.2 求解子模型的列生成算法

上述子問題屬于一類特殊的多商品網(wǎng)絡(luò)流問題，其中車輛流和貨流的可選徑路集大小決定了模型的規(guī)模。當(dāng)網(wǎng)絡(luò)規(guī)模較大時，顯然采用先獲取貨流和車輛流所有徑路，然后再求解模型的方法并不可取。為此，本文給出一種列生成算法，通過不斷求解定價子問題，來增加貨流和車輛流的徑路，此即定價過程。

2.3 算法總體步驟

綜上，求解模型P1的分支-定價-切割算法步驟如下，易知該算法在足夠長的時間內(nèi)可收斂至全局最優(yōu)解，可根據(jù)實際需要設(shè)置算法終止條件，如連續(xù)若干次迭代目標(biāo)函數(shù)值無改進、算法運行時間達到給定標(biāo)準(zhǔn)或算法迭代到一定次數(shù)。

步驟1定義主問題P2，采用分支-定界方法求解；

步驟2采用列生成算法求解給定主問題結(jié)果后退化而得的模型P3，直至貨流和車輛流都不需要再添加新徑路；

步驟3根據(jù)步驟1的結(jié)果生成Benders割，并計算模型P1的上界和下界；

步驟4如果上界和下界的差距在容許范圍內(nèi)，算法結(jié)束，輸出最優(yōu)解；否則，在模型P2中添加Benders割，并采用分支-定界方法求解，轉(zhuǎn)步驟2。

3 算例分析

本章將給出算例對上述模型和算法進行驗證，算法由Java實現(xiàn)，并在操作系統(tǒng)為Redhat Linux 5.6、主頻為Intel Xeon(E5520，2.27 GHz)的IBM System X服務(wù)器上運行。算例中的鐵路物理網(wǎng)絡(luò)如圖2所示，圖2中標(biāo)出了各場站間列車行駛時間，單位為時段，總決策時間長度為12個時段。算例中只考慮棚車一種車輛。

圖2 算例中的鐵路物理網(wǎng)絡(luò)

備選運輸服務(wù)相關(guān)參數(shù)見表1。在網(wǎng)絡(luò)中添加運輸服務(wù)聯(lián)弧的固定費用(也即開行列車的固定費用)主要包括開行列車占用運行線的費用及機車牽引費用，車輛流通過網(wǎng)絡(luò)的費用主要指租用車輛的費用(按使用時間收費)。

表1 備選運輸服務(wù)集合

假設(shè)上述運輸服務(wù)在所有時段都可開行，則可添加到網(wǎng)絡(luò)中的備選運輸服務(wù)聯(lián)弧數(shù)量為130條。算例中所有貨流相關(guān)參數(shù)見表2。

表2 貨流相關(guān)參數(shù)

假設(shè)所有車站都屬于同一區(qū)域，因此只需在離散時空網(wǎng)絡(luò)中添加一個超級節(jié)點。再假設(shè)有1 000輛棚車可以在該區(qū)域使用，這些車輛全部保有在虛擬的超級起點。在本算例的運行環(huán)境下，算法運行2 s后收斂至最優(yōu)解，見表3。注意表3中部分列車實際為重空混編，如序號為2、4和6的列車，這主要是由于模型中規(guī)定了列車最小編組輛數(shù)，由于重車數(shù)量不足，因此用空車補齊，這也是實際運營調(diào)度指揮中經(jīng)常使用的一種策略。

表3 算法運行結(jié)果

在以上算例中，如果假設(shè)鐵路線路D-E連接兩個不同的國家，也即從A、B、C、D站出發(fā)的棚車在決策時間結(jié)束時必須返回A、B、C、D中任意一個車站，而從E、F、G站出發(fā)的棚車在決策時間結(jié)束時也必須返回E、F、G站中任意一個車站。此時，離散時空網(wǎng)路中將添加2個超級起點，分別對應(yīng)于A、B、C、D站和E、F、G站，車輛流也將因此被拆分為兩支。此外，再將E、F、G站可用的棚車數(shù)量降低為30，A、B、C、D站可用的棚車數(shù)量降低為500，以測試本文模型給出的空車調(diào)配方案。在同樣的計算環(huán)境下，算法運行結(jié)果表明，在E、F、G三站間開行的列車編組中包含來自A、B、C、D站的車輛，例如，時段1開行的列車E-F(服務(wù)于貨流13)，時段6開行的列車E-G(服務(wù)于貨流15)和時段9開行的列車E-G(服務(wù)于貨流16)。但這些車輛全部編往一列從G站開往E站的排空列車輸送回A、B、C、D站所屬的區(qū)域。

如果進一步把A、B、C、D站可使用的棚車數(shù)量減少到300，時段6和時段9開行的列車E-G仍由來自A、B、C、D站的車輛組成，但時段1和3開行的列車E-F則由來自E、F、G站的車輛組成。為了滿足車輛使用區(qū)域的約束，時段10和12將開行兩列從G到E的排空列車，時段2將開行從F到E的排空列車，用于時段開行的列車E-F。

4 結(jié)束語

本文研究考慮車輛周轉(zhuǎn)的鐵路動態(tài)運輸服務(wù)網(wǎng)絡(luò)設(shè)計問題，對傳統(tǒng)的離散時空網(wǎng)絡(luò)進行拓展以描述重車和空車之間的轉(zhuǎn)化關(guān)系，建立混合整數(shù)規(guī)劃模型以同時解決列車開行時段、編組內(nèi)容和空車調(diào)配方案等問題。本文給出的方案既可用于進一步編制列車運行圖的框架，同時也可用于估算為滿足運輸需求所需各車種貨車的數(shù)量。文中給出了一種分支-定價-切割算法用于求解模型，該算法可保證收斂至模型的全局最優(yōu)解，并給出了算例以證明模型算法的有效性。算例中還通過調(diào)整模型中的輸入?yún)?shù)以測試不同車輛數(shù)量下排空策略的調(diào)整方案。未來進一步研究可關(guān)注當(dāng)單位時段縮小(如1 h或0.5 h)導(dǎo)致網(wǎng)絡(luò)規(guī)模進一步擴大時，如何改進分支-定價-切割的策略以加快算法收斂速度，滿足實際應(yīng)用的需要。

參考文獻：

[1]MAGNANTI T L,WONG R T.Network Design and Transportation Planning:Models and Algorithms[J].Transportation Science,1984,18(1):1-15.

[2]CRAINIC T G,ROUSSEAU J.Multicommodity,Multimode Freight Transportation:A General Modeling and Algorithmic Framework for the Service Network Design Problem[J].Transportation Research Part B:Methodological,1986,20(3):225-242.

[3]KEATON M H.Designing Optimal Railroad Operating Plans:Lagrangian Relaxation and Heuristic Approaches[J].Transportation Research Part B:Methodological,1989,23(6):415-431.

[4]HAGHANI A.Formulation and Solution of a Combined Train Routing and Makeup,and Empty Car Distribution Model[J].Transportation Research Part B:Methodological,1989,23(6):433-452.

[5]FARVOLDEN J M,POWELL W B.Subgradient Methods for the Service Network Design Problem[J].Transportation Science,1994,28(3):256-272.

[6]AYKIN T.Lagrangian Relaxation Based Approaches to Capacitated Hub-and-spoke Network Design Problem[J].European Journal of Operational Research,1994,79(3):501-523.

[7]NOZICK L K,MORLOK E K.A Model for Medium-term Operations Planning in an Intermodal Rail-truck Service[J].Transportation Research Part A:Policy and Practice,1997,31(2):91-107.

[8]GOEMAN M F.Santa Fe Railway Uses an Operating-plan Model to Improve Its Service Design[J].Interfaces,1998,28(4):1-12.

[9]KIM D,BARNHART C,WARE K,et al.Multimodal Express Package Delivery:A Service Network Design Application[J].Transportation Science,1999,33(4):391-407.

[10]CRAINIC T G.Service Network Design in Freight Transportation[J].European Journal of Operational Research,2000,122(2):272-288.

[11]CHEUNG W,LEUNG L C,WONG Y M.Strategic Service Network Design for DHL Hong Kong[J].Interfaces,2001,31(4):1-14.

[12]BARNHART C,KRISHNAN N,KIM D,et al.Network Design for Express Shipment Delivery[J].Computational Optimization and Applications,2002,21(3):239-262.

[13]AGARWAL R,ERGUN O.Ship Scheduling and Network Design for Cargo Routing in Liner Shipping[J].Transportation Science,2008,42(2):175-196.

[14]ANDERSON J,CRAINIC T G,CHRISTIANSEN M.Service Network Design with Management and Coordination of Multiple Fleets[J].European Journal of Operational Research,2009,192(2):377-389.

[15]ANDERSON J,CRAINIC T G,CHRISTIANSEN M.Service Network Design with Asset Management:Formulations and Comparative Analyses[J].Transportation Research Part C:Emerging Technologies,2009,17(2):197-207.

[16]王保華,何世偉,宋瑞,等.綜合運輸體系下快捷貨運網(wǎng)絡(luò)流量分配優(yōu)化模型及算法[J].鐵道學(xué)報,2009,31(2):12-16.

WANG Baohua,HE Shiwei,SONG Rui,et al.Multi-modal Express Shipment Network Routing Optimization Model and Algorithm[J].Journal of the China Railway Society,2009,31(2):12-16.

[17]王保華,何世偉,宋瑞,等.快捷貨運動態(tài)服務(wù)網(wǎng)絡(luò)設(shè)計優(yōu)化模型及其算法[J].鐵道學(xué)報,2009,31(5):17-22.

WANG Baohua,HE Shiwei,SONG Rui,et al.Optimization Model and Algorithm of Dynamic Express Shipment Service Network Design[J].Journal of the China Railway Society,2009,31(5):17-22.

[18]LULLI G,PIETROPAOLI U,RICCIARDI N.Service Network Design for Freight Railway Transportation:The Italian Case[J].Journal of Operational Research Society,2011,62(12):2107-2119.

[19]ANDERSON J,CHRISTIANSEN M,CRAINIC T G,et al.Branch and Price for Service Network Design with Asset Management Constraints[J].Transportation Science,2011,45(1):33-49.

[20]申永生.綜合運輸體系下貨運服務(wù)網(wǎng)絡(luò)設(shè)計優(yōu)化問題的研究[D].北京:北京交通大學(xué),2012.

[21]王保華,何世偉.綜合運輸體系下快捷貨物運輸網(wǎng)絡(luò)資源配置優(yōu)化模型及算法[J].鐵道學(xué)報,2017,39(2):10-16.

WANG Baohua,HE Shiwei.Resource Planning Optimization Model and Algorithm for Multi-modal Express Shipment Network[J].Journal of the China Railway Society,2017,39(2):10-16.