鐵路貨物快運服務(wù)網(wǎng)絡(luò)魯棒性優(yōu)化方案

劉欣萌

(西安航空學(xué)院經(jīng)濟管理學(xué)院，陜西 西安 710077)

?

【交通運輸】

鐵路貨物快運服務(wù)網(wǎng)絡(luò)魯棒性優(yōu)化方案

劉欣萌

(西安航空學(xué)院經(jīng)濟管理學(xué)院，陜西 西安 710077)

針對計劃期間貨運需求的波動情況，構(gòu)建了鐵路貨物快運服務(wù)網(wǎng)絡(luò)設(shè)計魯棒優(yōu)化模型。通過對比傳統(tǒng)鐵路貨物快運服務(wù)網(wǎng)絡(luò)設(shè)計基礎(chǔ)模型，以總運輸成本最小為目標(biāo)，決策內(nèi)容隱含車流的中轉(zhuǎn)方案和摘掛方案、列車編組計劃、運到期限等運輸服務(wù)約束，采用和聲搜索算法對模型求解，循環(huán)迭代至獲取較優(yōu)結(jié)果。研究結(jié)果表明，魯棒優(yōu)化模型對運輸需求變動的適應(yīng)性較強，且運到期限增大，總成本減少。

貨物快運；列車服務(wù)網(wǎng)絡(luò)設(shè)計；魯棒性；和聲搜索

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

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

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

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

1 鐵路貨物快運服務(wù)網(wǎng)絡(luò)設(shè)計魯棒模型的分析

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

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

圖1 鐵路貨物快運服務(wù)網(wǎng)絡(luò)模型決策思路流程圖Fig.1 Decision flow chart of railway freight transportation service network model

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

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

1.2 建模思路

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

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

(1)

其中

(2)

2 鐵路貨物快運服務(wù)網(wǎng)絡(luò)設(shè)計魯棒模型的建模與求解

2.1 符號定義

(1)集合

(2)參量

(3)決策變量

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

2.2 模型構(gòu)建

(3)

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

(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)為運到期限約束，運輸時間和途中作業(yè)時間的總和應(yīng)小于等于運到期限；(9～10)為開行列車數(shù)冗余范圍約束，開行的班列數(shù)大于需求的最小值，小于需求的最大值；(11)為各個場景下的運能約束：任意路段上的流量之和不超過服務(wù)區(qū)段的最大編成輛數(shù)；(12～15)為變量取值約束。

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

3 求解算法

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

Step 1 和聲編碼

貨物快運服務(wù)網(wǎng)絡(luò)設(shè)計魯棒優(yōu)化模型的編碼和決策變量相關(guān)。每個和聲的編碼形式如下：

(17)

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

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

Step 3 生成新的和聲

進行音調(diào)微調(diào)操作后，多場景需求變動下鐵路貨物快運服務(wù)網(wǎng)絡(luò)設(shè)計的魯棒優(yōu)化模型需要檢驗結(jié)果是否滿足約束條件，如滿足則進行下一步操作，如不滿足則按照可行解的生成辦法重新生成新和聲。

Step 4 更新和聲記憶庫

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

Step 5 算法終止條件

不斷更新和聲記憶庫中的可行解與最優(yōu)目標(biāo)函數(shù)，直到迭代次數(shù)達到規(guī)定的最大迭代次數(shù)，則算法終止，認(rèn)為此時算法已經(jīng)收斂到最優(yōu)，并輸出最優(yōu)解與最優(yōu)函數(shù)值。

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

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

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

3 算例分析

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

圖4 鐵路運輸網(wǎng)結(jié)構(gòu)圖Fig.4 Railway transport network structure diagram

節(jié)點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-

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

表2 各參量取值

注：以上數(shù)據(jù)依據(jù)鐵路貨物快運的統(tǒng)計值和運輸付費清算標(biāo)準(zhǔn)，以及參考文獻[10-11]中對于參數(shù)取值的情況等進行估值。

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

經(jīng)過多次計算，在運到期限1時，經(jīng)過3 106次收斂，收斂值為27 121 152元，也就是總成本和總偏離程度的加權(quán)值，其中總成本5 806 423元，總偏離程度21 314 729元；運到期限2時，經(jīng)過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條車流，經(jīng)過車流組合，部分車流在途中進行了中轉(zhuǎn)和摘掛作業(yè)。運到期限限制1條件下實際開行列車11條，如表3所示。車流合并情況如圖6所示。運到期限限制2同理，在此不再贅述。規(guī)律顯示，運到期限增大，模型的總成本減小。結(jié)果表明，當(dāng)運到期限減小時，會導(dǎo)致某些開車的長車流因為不能滿足開行條件而不能開車，因此在一定程度上增加了開行列數(shù)，也進一步導(dǎo)致開行成本的增加。

表3 貨物快運服務(wù)網(wǎng)絡(luò)魯棒優(yōu)化模型求解結(jié)果(運到期限1)

4 結(jié)語

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

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

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

[3]許旺土. 綜合快捷貨運服務(wù)網(wǎng)絡(luò)運輸能力計算方法研究[D]. 北京:北京交通大學(xué), 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]劉杰, 何世偉, 宋瑞,等. 鐵路既有繁忙干線貨運產(chǎn)品布局優(yōu)化模型及算法[J]. 北京交通大學(xué)學(xué)報, 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]李婷婷, 宋瑞. 國家層面綜合客運樞紐分層布局魯棒優(yōu)化模型[J]. 東南大學(xué)學(xué)報(自然科學(xué)版), 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]郭玉華, 何世偉, 王保華. 鐵路中轉(zhuǎn)班列開行方案優(yōu)化研究[J]. 鐵道學(xué)報, 2011, 33(5):8-13.

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

[14]王瑩, 劉軍. 鐵路行包快運專列開行方案優(yōu)化編制方法的研究[J]. 交通運輸系統(tǒng)工程與信息, 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]許越. 集裝化運輸模式下快捷貨運服務(wù)網(wǎng)絡(luò)優(yōu)化設(shè)計研究[D]. 北京:北京交通大學(xué), 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

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

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

U292.3

A

1002-4026(2017)03-0065-08