鐵路貨物快運服務網絡魯棒性優化方案

劉欣萌

(西安航空學院經濟管理學院，陜西 西安 710077)

?

【交通運輸】

鐵路貨物快運服務網絡魯棒性優化方案

劉欣萌

(西安航空學院經濟管理學院，陜西 西安 710077)

針對計劃期間貨運需求的波動情況，構建了鐵路貨物快運服務網絡設計魯棒優化模型。通過對比傳統鐵路貨物快運服務網絡設計基礎模型，以總運輸成本最小為目標，決策內容隱含車流的中轉方案和摘掛方案、列車編組計劃、運到期限等運輸服務約束，采用和聲搜索算法對模型求解，循環迭代至獲取較優結果。研究結果表明，魯棒優化模型對運輸需求變動的適應性較強，且運到期限增大，總成本減少。

貨物快運；列車服務網絡設計；魯棒性；和聲搜索

我國鐵路的貨運組織改革，對貨物運輸提出了更高的要求。社會物資品類和結構的細化，又進一步增加和誘發了新的貨運需求[1]。鐵路貨物快運是鐵路貨運產品中以運輸高附加值貨物為主的貨物運輸方案，向貨主承諾貨物運到時間，具有安全、快速、準時、便捷等特點，體現快捷和限時送達等優勢。如何開展貨物快運列車服務網絡優化設計，使貨物列車更好地適應市場發展，滿足貨主需求，同時降低運輸成本、提高運輸收益，已成為該領域亟待解決的問題[2]。

運輸服務網絡通常是指在物理網絡的基礎上，由節點和聯弧組成[3]，運輸主體通過決策確定的運輸服務方案，具體包括車流徑路、場站節點、服務頻率等。國內外學者對此進行了深入的研究，例如在服務網絡研究方面， Maia等[4]針對多通道網絡貨運業務，以普通貨運和公鐵聯運為例，提出了一種創新的分配模型。Bai等[5]設計的隨機服務網絡，主要解決不確定因素對目標函數的影響，提出了一個新的隨機貨運服務網絡設計模型與車輛路徑選擇方法，主要增強了模型的靈活性。Hajiaghaei-Keshteli等[6]針對鐵路運輸的綜合調度問題進行算法對比，模型以總成本最小為目標，得出Keshtel算法(KA)相比于遺傳算法(GA)應用于鐵路綜合調度問題具有更好的求解效果的結論。劉杰等[7]采用節點拆分的方式構建了既有繁忙干線貨運產品網絡。

服務網絡的研究給規劃者提供了規劃依據，可是在實際運輸中，運輸需求會因季節、周期、天氣、政策等各種因素導致運輸中發生不可控的情況。針對不確定因素的研究，比較成熟的方法是魯棒模型[8]，該方法強調的是在優化開始時就考慮模型的不確定性，使優化的結果達到對不確定因素不敏感及性能指標最優的統一，可以有效解決眾多行業對不確定優化問題的需求，因此考慮魯棒性以后的結果被認為是更穩定的，而相對其他模型卻不一定是值最優的。對于魯棒性的研究， Najafi等[9]針對自然災害的應急預案，提出了在地震發生后救援物資的輸送方案。定義救助條件為不確定的，即需求和供給是不確定的，建立了多目標魯棒優化模型。李婷婷等[10]考慮城鎮化發展階段客運需求的不確定性，構建了基于有能力限制的層級選址模型和遺憾魯棒優化模型。

長期以來鐵路運輸需求很難準確預知，也容易受各種因素的影響，給鐵路貨物快運服務網絡設計帶來了諸多不確定的條件。因此，構建多場景需求變動下貨物快運服務網絡設計的魯棒優化模型，可以有效解決目前鐵路貨物快運過程中面臨的問題，對提高經營質量和效益，適應市場、擴大市場，實現可持續發展都具有深遠的意義。現階段魯棒性在服務網絡設計中的應用尚處于空白，本文借鑒魯棒性在樞紐選址[11]、中轉班列開行方案[12]等方面的應用，建立了貨物快運服務網絡設計魯棒優化模型，最后采用和聲搜索算法對模型進行求解。

1 鐵路貨物快運服務網絡設計魯棒模型的分析

鐵路貨物快運服務網絡模型，其核心是確定候選車流集，根據運輸需求、通道能力，運輸時限等，確定開行方案、開行頻度、運行路徑。對所有車流合理合并，可以有效壓縮網絡規模，提高運輸效率。在此基礎上，考慮到實際貨運量和計劃貨運量間存在偏差，會影響基礎模型最終設計的結果，使得所求結果的抗干擾性較差，因此，本文提出了鐵路貨物快運服務網絡設計魯棒優化模型(簡稱魯棒優化模型)。

在魯棒優化模型中，魯棒優化理論中的不確定因素通常對應離散的場景(scenario)或連續的區間范圍[13]，最優解可以使得所有的確定性參數的穩定性最高，從而實現魯棒優化模型的抗干擾性。本文的魯棒優化模型中，選擇場景來表示不同時段的貨運需求量。魯棒優化模型的決策思路流程圖如圖1所示。

圖1 鐵路貨物快運服務網絡模型決策思路流程圖Fig.1 Decision flow chart of railway freight transportation service network model

1.1 確定車流徑路的候選車流集

車流徑路是求解貨物快運服務網絡設計的核心要素[14]，對于貨物快運服務網絡設計而言，為貨流確定可行路徑(即車流徑路)，將貨流分配在其所在路徑上，是編組的首要任務。因此，考慮到實際情況，運輸企業總成本最小，車流需要和其他車流合并運行至終點。提前定義好供流量分配時選擇的候選徑路集，可以提高每個車流的選擇速度。由于貨物快運通常是干線運輸，其運行路徑規定為特定路徑，在這里視為已知。

1.2 建模思路

考慮多場景條件下魯棒優化問題的優化模型的一般形式[15]：

minZ=Z1(X)+Z2(X,S) s.t.X∈Ω ,

(1)

其中

(2)

2 鐵路貨物快運服務網絡設計魯棒模型的建模與求解

2.1 符號定義

(1)集合

(2)參量

(3)決策變量

xf為0-1變量，車流f是否開車，若是則xf=1，否則xf=0。yf為整數變量，表示車流f所開行鐵路貨物快運班列的列數。zf,f′為0-1變量，車流f是否并入f′，若并入zf,f′=1，否則zf,f′=0。yf,s為整數變量，表示場景s下，車流f所開行鐵路貨物快運班列的列數。

2.2 模型構建

(3)

除此以外還需要考慮服務網絡在各個場景下的偏離程度，偏離程度會存在正偏離和負偏離兩種情況，因此在求解的過程中需要取絕對值處理，所以總偏離程度可以理解成是開行列數的波動導致固定成本的變動數額。具體表示為：

(4)

(5)

約束條件如下：

xf+zf,f′≤1 , ?f∈F,f′∈Pf,

(6)

zf,f′≤xf′ , ?f∈F,f′∈Pf,

(7)

(8)

(9)

(10)

(11)

(12)

yf∈N+, ?f∈F ,

(13)

(14)

yf,s∈N+, ?f∈F,s∈S 。

(15)

式(6)為車流合并約束，對于任意一條車流，或者自行開車，或者并入其他車流；(7)為并入條件約束，被并入的車流必須開車且是并入車流的候選徑路集；(8)為運到期限約束，運輸時間和途中作業時間的總和應小于等于運到期限；(9～10)為開行列車數冗余范圍約束，開行的班列數大于需求的最小值，小于需求的最大值；(11)為各個場景下的運能約束：任意路段上的流量之和不超過服務區段的最大編成輛數；(12～15)為變量取值約束。

由于鐵路貨物列車的開行方案是比較長遠期的規劃，因此在優化開行方案的過程中考慮計劃期內各個場景(階段)的預測貨運量更具有實用價值。

3 求解算法

貨物快運服務網絡設計魯棒優化模型為整數規劃模型，智能優化中的和聲搜索算法在求解大規模復雜問題中具有適應度強、編碼簡單、類比清晰、步驟明確等優勢[16]。本文采用該算法進行求解。具體步驟如下：

Step 1 和聲編碼

貨物快運服務網絡設計魯棒優化模型的編碼和決策變量相關。每個和聲的編碼形式如下：

(17)

Step 2 生成初始解和初始化和聲記憶庫

根據以上分析，和聲記憶庫(HM)有保存初始可行解和在迭代過程中獲得較優解的作用。而初始化和聲記憶庫，需要求得初始可行解，由于路網的復雜性，且約束條件較多，使得求解難度增大，可能產生較多不可行解，對求解效果產生影響。因此,本文給出了兩階段的可行解的生成辦法，可以較好地得到初始可行解，如圖2所示。

Step 3 生成新的和聲

進行音調微調操作后，多場景需求變動下鐵路貨物快運服務網絡設計的魯棒優化模型需要檢驗結果是否滿足約束條件，如滿足則進行下一步操作，如不滿足則按照可行解的生成辦法重新生成新和聲。

Step 4 更新和聲記憶庫

利用式(5)對模型生成的新解進行評估，如果其評估結果好于和聲記憶庫中最差的可行解，那么就將新生成的解更新至和聲記憶庫中。

Step 5 算法終止條件

不斷更新和聲記憶庫中的可行解與最優目標函數，直到迭代次數達到規定的最大迭代次數，則算法終止，認為此時算法已經收斂到最優，并輸出最優解與最優函數值。

圖2 初始可行解生成示意圖Fig.2 Schematic diagram of initial feasible solution

圖3給出了和聲搜索算法流程圖。

圖3 和聲搜索算法流程圖Fig.3 Flow chart of harmony search algorithm

3 算例分析

為驗證求解結果的準確性和可行性，使用算例進行分析。構建服務網絡結構，所有節點間均可以雙向服務，鐵路運輸網結構如圖4所示。節點間OD需求量和固定成本見表1，各參量取值見表2。

圖4 鐵路運輸網結構圖Fig.4 Railway transport network structure diagram

節點12345671-20/10850-15/3668040/52369-10/33180210/10850-45/9804420/5236970/15823520/3272515/45806320/3272560/98044-30/3911330/5880020/34020-48/36680-40/39113-20/6545020/3318020/39288515/5236966/15823542/5880020/65450-30/1732540/19425610/4366310/3272512/340208/3318020/17325-10/1522578/3318020/45806-10/3928830/1942520/15225-

注：以上數據滿足遞遠遞減規律，參考運行線始末站間的距離、成本車輛使用費用以及租用運行線的費用等進行估算。

表2 各參量取值

注：以上數據依據鐵路貨物快運的統計值和運輸付費清算標準，以及參考文獻[10-11]中對于參數取值的情況等進行估值。

采用和聲搜索算法對模型求解，算法由C#語言在Visual Studio 2010平臺下實現，在Inter(R)Core(TM)i5-3210M CPU和2 GB內存環境下運行。和聲記憶庫大小取80，記憶庫取值概率取值在0.9，微調概率0.3，經過測試，取最大迭代次數為4 500，場景數選擇12個。為了對比運到期限對模型的影響，選擇運到期限1取值13.8 h，運到期限2取值9.9 h。

經過多次計算，在運到期限1時，經過3 106次收斂，收斂值為27 121 152元，也就是總成本和總偏離程度的加權值，其中總成本5 806 423元，總偏離程度21 314 729元；運到期限2時，經過3 781次迭代收斂，收斂值為29 181 330元，其中總成本5 452 476元，總偏離程度23 728 854元。平均運行時間125 s。收斂圖如圖5所示。

圖5 和聲搜索算法收斂過程示意圖Fig.5 Convergence process of harmony search algorithm

圖6 車流合并情況示意圖(運到期限1)Fig.6 Traffic flow merging situation (shipped to a period of 1)

以運到期限限制1為例作解釋說明，原來的37條車流，經過車流組合，部分車流在途中進行了中轉和摘掛作業。運到期限限制1條件下實際開行列車11條，如表3所示。車流合并情況如圖6所示。運到期限限制2同理，在此不再贅述。規律顯示，運到期限增大，模型的總成本減小。結果表明，當運到期限減小時，會導致某些開車的長車流因為不能滿足開行條件而不能開車，因此在一定程度上增加了開行列數，也進一步導致開行成本的增加。

表3 貨物快運服務網絡魯棒優化模型求解結果(運到期限1)

4 結語

鐵路貨物快運服務網絡設計可以滿足市場對鐵路快運發展的要求，在實際鐵路運輸中，運輸需求往往不能用一個定值去衡量，本文考慮到實際鐵路貨物快運需求的波動性，借鑒魯棒優化思想，構建了鐵路貨物快運服務網絡設計魯棒優化模型，以提高求解結果的適用性，并采用和聲搜索算法對模型進行求解。算例分析表明，本文采用的構模方式可以有效壓縮網絡規模，收斂速度快。本文給出的方法，能夠為貨物快運列車服務網絡設計提供決策支持。但是，由于文中未考慮空車車底的回送可能會增加的運輸成本，在下一步的研究中可以結合鐵路貨物快運服務網絡設計和空車調配的問題進行綜合考慮。

[1]張靜. 我國鐵路快捷貨運班列開行方案研究[D]. 北京:北京交通大學, 2011.

[2]蘭勁棕. 我國鐵路快捷貨物運輸組織相關問題研究[D].成都:西南交通大學, 2011.

[3]許旺土. 綜合快捷貨運服務網絡運輸能力計算方法研究[D]. 北京:北京交通大學, 2010.

[4] MAIA L C, do COUTO A F. An innovative freight traffic assignment model for multimodal networks[J]. Computers in Industry, 2013, 64(2):121-127.

[5] BAI R B, WALLACE S W,LI J P, et al. Stochastic service network design with rerouting[J]. Transportation Research Part B Methodological, 2014, 60:50-65.

[6] HAJIAGHAEI-KESHTELI M, M AMINNAYERI. Solving the integrated scheduling of production and rail transportation problem by Keshtel algorithm[J]. Applied Soft Computing, 2014, 25:184-203.

[7]劉杰, 何世偉, 宋瑞,等. 鐵路既有繁忙干線貨運產品布局優化模型及算法[J]. 北京交通大學學報, 2013, 37(6):91-98.

[8]SOYSTER A L. Convex programming with set-inclusive constraints and applications to inexact linear programming[J]. Operations Research, 1973, 21(5):1154-1157.

[9] NAJAFI M,ESHGHI K,DULLAERT W. A multi-objective robust optimization model for logistics planning in the earthquake response phase[J]. Transportation Research Part E Logistics & Transportation Review, 2013, 49(1):217-249.

[10]李婷婷, 宋瑞. 國家層面綜合客運樞紐分層布局魯棒優化模型[J]. 東南大學學報(自然科學版), 2015, 45(1):189-195.

[11]LIU X C, HE S W, SONG R, et al. Robust optimization model and algorithm for railway freight center location problem in uncertain environment[J]. Computational Intelligence & Neuroscience, 2014, 2014:607159.

[12]郭玉華, 何世偉, 王保華. 鐵路中轉班列開行方案優化研究[J]. 鐵道學報, 2011, 33(5):8-13.

[13]王保華, 何世偉. 不確定環境下物流中心選址魯棒優化模型及其算法[J]. 交通運輸系統工程與信息, 2009, 9(2):69-74.

[14]王瑩, 劉軍. 鐵路行包快運專列開行方案優化編制方法的研究[J]. 交通運輸系統工程與信息, 2007, 7(3):125-129.

[15]KHAN M B, ZHOU X S. Stochastic optimization model and solution algorithm for robust double-track train-timetabling problem[J]. IEEE Transactions on Intelligent Transportation Systems, 2010, 11(1):81-89.

[16]許越. 集裝化運輸模式下快捷貨運服務網絡優化設計研究[D]. 北京:北京交通大學, 2015.

DOI:10.3976/j.issn.1002-4026.2017.03.015

Robustness optimization model for freight express service network design scheme

LIU Xin-meng

(School of Economic Management, Xi′an Aeronautical University, Xi′an 710077, China)

∶As freight demand is prone to volatility during the planning period, robustness optimization model for freight express service network design was constructed in this paper. By comparing the robustness optimization model with the traditional basis model, and aiming at minimizing total transportation cost, the objective function has the implication of transportation services constraints, such as train transfers and train detaching as well as attaching plan, train marshaling plan, and delivery time, etc. The harmony search algorithm was used in this paper to solve the model with loop iteration to get better results. The results reveal that the robustness optimization model is well accustomed to the change in transportation demand, and it can also postpone freight delivery deadline while the transportation cost is reduced.

∶freight express; train service network design; robustness; harmony search

10.3976/j.issn.1002-4026.2017.03.012

2016-08-24

陜西省社會科學基金項目(2016D051)

劉欣萌(1990—)，女，助教，研究方向為交通運輸現代組織管理理論與方法。E-mail：13120872@bjtu.edu.cn

U292.3

A

1002-4026(2017)03-0065-08