劉欣萌
(西安航空學(xué)院經(jīng)濟(jì)管理學(xué)院,陜西 西安 710077)
?
【交通運(yùn)輸】
鐵路貨物快運(yùn)服務(wù)網(wǎng)絡(luò)魯棒性優(yōu)化方案
劉欣萌
(西安航空學(xué)院經(jīng)濟(jì)管理學(xué)院,陜西 西安 710077)
針對(duì)計(jì)劃期間貨運(yùn)需求的波動(dòng)情況,構(gòu)建了鐵路貨物快運(yùn)服務(wù)網(wǎng)絡(luò)設(shè)計(jì)魯棒優(yōu)化模型。通過(guò)對(duì)比傳統(tǒng)鐵路貨物快運(yùn)服務(wù)網(wǎng)絡(luò)設(shè)計(jì)基礎(chǔ)模型,以總運(yùn)輸成本最小為目標(biāo),決策內(nèi)容隱含車流的中轉(zhuǎn)方案和摘掛方案、列車編組計(jì)劃、運(yùn)到期限等運(yùn)輸服務(wù)約束,采用和聲搜索算法對(duì)模型求解,循環(huán)迭代至獲取較優(yōu)結(jié)果。研究結(jié)果表明,魯棒優(yōu)化模型對(duì)運(yùn)輸需求變動(dòng)的適應(yīng)性較強(qiáng),且運(yùn)到期限增大,總成本減少。
貨物快運(yùn);列車服務(wù)網(wǎng)絡(luò)設(shè)計(jì);魯棒性;和聲搜索
我國(guó)鐵路的貨運(yùn)組織改革,對(duì)貨物運(yùn)輸提出了更高的要求。社會(huì)物資品類和結(jié)構(gòu)的細(xì)化,又進(jìn)一步增加和誘發(fā)了新的貨運(yùn)需求[1]。鐵路貨物快運(yùn)是鐵路貨運(yùn)產(chǎn)品中以運(yùn)輸高附加值貨物為主的貨物運(yùn)輸方案,向貨主承諾貨物運(yùn)到時(shí)間,具有安全、快速、準(zhǔn)時(shí)、便捷等特點(diǎn),體現(xiàn)快捷和限時(shí)送達(dá)等優(yōu)勢(shì)。如何開展貨物快運(yùn)列車服務(wù)網(wǎng)絡(luò)優(yōu)化設(shè)計(jì),使貨物列車更好地適應(yīng)市場(chǎng)發(fā)展,滿足貨主需求,同時(shí)降低運(yùn)輸成本、提高運(yùn)輸收益,已成為該領(lǐng)域亟待解決的問(wèn)題[2]。
運(yùn)輸服務(wù)網(wǎng)絡(luò)通常是指在物理網(wǎng)絡(luò)的基礎(chǔ)上,由節(jié)點(diǎn)和聯(lián)弧組成[3],運(yùn)輸主體通過(guò)決策確定的運(yùn)輸服務(wù)方案,具體包括車流徑路、場(chǎng)站節(jié)點(diǎn)、服務(wù)頻率等。國(guó)內(nèi)外學(xué)者對(duì)此進(jìn)行了深入的研究,例如在服務(wù)網(wǎng)絡(luò)研究方面, Maia等[4]針對(duì)多通道網(wǎng)絡(luò)貨運(yùn)業(yè)務(wù),以普通貨運(yùn)和公鐵聯(lián)運(yùn)為例,提出了一種創(chuàng)新的分配模型。Bai等[5]設(shè)計(jì)的隨機(jī)服務(wù)網(wǎng)絡(luò),主要解決不確定因素對(duì)目標(biāo)函數(shù)的影響,提出了一個(gè)新的隨機(jī)貨運(yùn)服務(wù)網(wǎng)絡(luò)設(shè)計(jì)模型與車輛路徑選擇方法,主要增強(qiáng)了模型的靈活性。Hajiaghaei-Keshteli等[6]針對(duì)鐵路運(yùn)輸?shù)木C合調(diào)度問(wèn)題進(jìn)行算法對(duì)比,模型以總成本最小為目標(biāo),得出Keshtel算法(KA)相比于遺傳算法(GA)應(yīng)用于鐵路綜合調(diào)度問(wèn)題具有更好的求解效果的結(jié)論。劉杰等[7]采用節(jié)點(diǎn)拆分的方式構(gòu)建了既有繁忙干線貨運(yùn)產(chǎn)品網(wǎng)絡(luò)。
服務(wù)網(wǎng)絡(luò)的研究給規(guī)劃者提供了規(guī)劃依據(jù),可是在實(shí)際運(yùn)輸中,運(yùn)輸需求會(huì)因季節(jié)、周期、天氣、政策等各種因素導(dǎo)致運(yùn)輸中發(fā)生不可控的情況。針對(duì)不確定因素的研究,比較成熟的方法是魯棒模型[8],該方法強(qiáng)調(diào)的是在優(yōu)化開始時(shí)就考慮模型的不確定性,使優(yōu)化的結(jié)果達(dá)到對(duì)不確定因素不敏感及性能指標(biāo)最優(yōu)的統(tǒng)一,可以有效解決眾多行業(yè)對(duì)不確定優(yōu)化問(wèn)題的需求,因此考慮魯棒性以后的結(jié)果被認(rèn)為是更穩(wěn)定的,而相對(duì)其他模型卻不一定是值最優(yōu)的。對(duì)于魯棒性的研究, Najafi等[9]針對(duì)自然災(zāi)害的應(yīng)急預(yù)案,提出了在地震發(fā)生后救援物資的輸送方案。定義救助條件為不確定的,即需求和供給是不確定的,建立了多目標(biāo)魯棒優(yōu)化模型。李婷婷等[10]考慮城鎮(zhèn)化發(fā)展階段客運(yùn)需求的不確定性,構(gòu)建了基于有能力限制的層級(jí)選址模型和遺憾魯棒優(yōu)化模型。
長(zhǎng)期以來(lái)鐵路運(yùn)輸需求很難準(zhǔn)確預(yù)知,也容易受各種因素的影響,給鐵路貨物快運(yùn)服務(wù)網(wǎng)絡(luò)設(shè)計(jì)帶來(lái)了諸多不確定的條件。因此,構(gòu)建多場(chǎng)景需求變動(dòng)下貨物快運(yùn)服務(wù)網(wǎng)絡(luò)設(shè)計(jì)的魯棒優(yōu)化模型,可以有效解決目前鐵路貨物快運(yùn)過(guò)程中面臨的問(wèn)題,對(duì)提高經(jīng)營(yíng)質(zhì)量和效益,適應(yīng)市場(chǎng)、擴(kuò)大市場(chǎng),實(shí)現(xiàn)可持續(xù)發(fā)展都具有深遠(yuǎn)的意義?,F(xiàn)階段魯棒性在服務(wù)網(wǎng)絡(luò)設(shè)計(jì)中的應(yīng)用尚處于空白,本文借鑒魯棒性在樞紐選址[11]、中轉(zhuǎn)班列開行方案[12]等方面的應(yīng)用,建立了貨物快運(yùn)服務(wù)網(wǎng)絡(luò)設(shè)計(jì)魯棒優(yōu)化模型,最后采用和聲搜索算法對(duì)模型進(jìn)行求解。
鐵路貨物快運(yùn)服務(wù)網(wǎng)絡(luò)模型,其核心是確定候選車流集,根據(jù)運(yùn)輸需求、通道能力,運(yùn)輸時(shí)限等,確定開行方案、開行頻度、運(yùn)行路徑。對(duì)所有車流合理合并,可以有效壓縮網(wǎng)絡(luò)規(guī)模,提高運(yùn)輸效率。在此基礎(chǔ)上,考慮到實(shí)際貨運(yùn)量和計(jì)劃貨運(yùn)量間存在偏差,會(huì)影響基礎(chǔ)模型最終設(shè)計(jì)的結(jié)果,使得所求結(jié)果的抗干擾性較差,因此,本文提出了鐵路貨物快運(yùn)服務(wù)網(wǎng)絡(luò)設(shè)計(jì)魯棒優(yōu)化模型(簡(jiǎn)稱魯棒優(yōu)化模型)。
在魯棒優(yōu)化模型中,魯棒優(yōu)化理論中的不確定因素通常對(duì)應(yīng)離散的場(chǎng)景(scenario)或連續(xù)的區(qū)間范圍[13],最優(yōu)解可以使得所有的確定性參數(shù)的穩(wěn)定性最高,從而實(shí)現(xiàn)魯棒優(yōu)化模型的抗干擾性。本文的魯棒優(yōu)化模型中,選擇場(chǎng)景來(lái)表示不同時(shí)段的貨運(yùn)需求量。魯棒優(yōu)化模型的決策思路流程圖如圖1所示。
圖1 鐵路貨物快運(yùn)服務(wù)網(wǎng)絡(luò)模型決策思路流程圖Fig.1 Decision flow chart of railway freight transportation service network model
1.1 確定車流徑路的候選車流集
車流徑路是求解貨物快運(yùn)服務(wù)網(wǎng)絡(luò)設(shè)計(jì)的核心要素[14],對(duì)于貨物快運(yùn)服務(wù)網(wǎng)絡(luò)設(shè)計(jì)而言,為貨流確定可行路徑(即車流徑路),將貨流分配在其所在路徑上,是編組的首要任務(wù)。因此,考慮到實(shí)際情況,運(yùn)輸企業(yè)總成本最小,車流需要和其他車流合并運(yùn)行至終點(diǎn)。提前定義好供流量分配時(shí)選擇的候選徑路集,可以提高每個(gè)車流的選擇速度。由于貨物快運(yùn)通常是干線運(yùn)輸,其運(yùn)行路徑規(guī)定為特定路徑,在這里視為已知。
1.2 建模思路
考慮多場(chǎng)景條件下魯棒優(yōu)化問(wèn)題的優(yōu)化模型的一般形式[15]:
minZ=Z1(X)+Z2(X,S) s.t.X∈Ω ,
(1)
其中
(2)
2.1 符號(hào)定義
(1)集合
(2)參量
(3)決策變量
xf為0-1變量,車流f是否開車,若是則xf=1,否則xf=0。yf為整數(shù)變量,表示車流f所開行鐵路貨物快運(yùn)班列的列數(shù)。zf,f′為0-1變量,車流f是否并入f′,若并入zf,f′=1,否則zf,f′=0。yf,s為整數(shù)變量,表示場(chǎng)景s下,車流f所開行鐵路貨物快運(yùn)班列的列數(shù)。
2.2 模型構(gòu)建
(3)
除此以外還需要考慮服務(wù)網(wǎng)絡(luò)在各個(gè)場(chǎng)景下的偏離程度,偏離程度會(huì)存在正偏離和負(fù)偏離兩種情況,因此在求解的過(guò)程中需要取絕對(duì)值處理,所以總偏離程度可以理解成是開行列數(shù)的波動(dòng)導(dǎo)致固定成本的變動(dòng)數(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)為車流合并約束,對(duì)于任意一條車流,或者自行開車,或者并入其他車流;(7)為并入條件約束,被并入的車流必須開車且是并入車流的候選徑路集;(8)為運(yùn)到期限約束,運(yùn)輸時(shí)間和途中作業(yè)時(shí)間的總和應(yīng)小于等于運(yùn)到期限;(9~10)為開行列車數(shù)冗余范圍約束,開行的班列數(shù)大于需求的最小值,小于需求的最大值;(11)為各個(gè)場(chǎng)景下的運(yùn)能約束:任意路段上的流量之和不超過(guò)服務(wù)區(qū)段的最大編成輛數(shù);(12~15)為變量取值約束。
由于鐵路貨物列車的開行方案是比較長(zhǎng)遠(yuǎn)期的規(guī)劃,因此在優(yōu)化開行方案的過(guò)程中考慮計(jì)劃期內(nèi)各個(gè)場(chǎng)景(階段)的預(yù)測(cè)貨運(yùn)量更具有實(shí)用價(jià)值。
貨物快運(yùn)服務(wù)網(wǎng)絡(luò)設(shè)計(jì)魯棒優(yōu)化模型為整數(shù)規(guī)劃模型,智能優(yōu)化中的和聲搜索算法在求解大規(guī)模復(fù)雜問(wèn)題中具有適應(yīng)度強(qiáng)、編碼簡(jiǎn)單、類比清晰、步驟明確等優(yōu)勢(shì)[16]。本文采用該算法進(jìn)行求解。具體步驟如下:
Step 1 和聲編碼
貨物快運(yùn)服務(wù)網(wǎng)絡(luò)設(shè)計(jì)魯棒優(yōu)化模型的編碼和決策變量相關(guān)。每個(gè)和聲的編碼形式如下:
(17)
Step 2 生成初始解和初始化和聲記憶庫(kù)
根據(jù)以上分析,和聲記憶庫(kù)(HM)有保存初始可行解和在迭代過(guò)程中獲得較優(yōu)解的作用。而初始化和聲記憶庫(kù),需要求得初始可行解,由于路網(wǎng)的復(fù)雜性,且約束條件較多,使得求解難度增大,可能產(chǎn)生較多不可行解,對(duì)求解效果產(chǎn)生影響。因此,本文給出了兩階段的可行解的生成辦法,可以較好地得到初始可行解,如圖2所示。
Step 3 生成新的和聲
進(jìn)行音調(diào)微調(diào)操作后,多場(chǎng)景需求變動(dòng)下鐵路貨物快運(yùn)服務(wù)網(wǎng)絡(luò)設(shè)計(jì)的魯棒優(yōu)化模型需要檢驗(yàn)結(jié)果是否滿足約束條件,如滿足則進(jìn)行下一步操作,如不滿足則按照可行解的生成辦法重新生成新和聲。
Step 4 更新和聲記憶庫(kù)
利用式(5)對(duì)模型生成的新解進(jìn)行評(píng)估,如果其評(píng)估結(jié)果好于和聲記憶庫(kù)中最差的可行解,那么就將新生成的解更新至和聲記憶庫(kù)中。
Step 5 算法終止條件
不斷更新和聲記憶庫(kù)中的可行解與最優(yōu)目標(biāo)函數(shù),直到迭代次數(shù)達(dá)到規(guī)定的最大迭代次數(shù),則算法終止,認(rèn)為此時(shí)算法已經(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
為驗(yàn)證求解結(jié)果的準(zhǔn)確性和可行性,使用算例進(jìn)行分析。構(gòu)建服務(wù)網(wǎng)絡(luò)結(jié)構(gòu),所有節(jié)點(diǎn)間均可以雙向服務(wù),鐵路運(yùn)輸網(wǎng)結(jié)構(gòu)如圖4所示。節(jié)點(diǎn)間OD需求量和固定成本見表1,各參量取值見表2。
圖4 鐵路運(yùn)輸網(wǎng)結(jié)構(gòu)圖Fig.4 Railway transport network structure diagram
節(jié)點(diǎn)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ù)滿足遞遠(yuǎn)遞減規(guī)律,參考運(yùn)行線始末站間的距離、成本車輛使用費(fèi)用以及租用運(yùn)行線的費(fèi)用等進(jìn)行估算。
表2 各參量取值
注:以上數(shù)據(jù)依據(jù)鐵路貨物快運(yùn)的統(tǒng)計(jì)值和運(yùn)輸付費(fèi)清算標(biāo)準(zhǔn),以及參考文獻(xiàn)[10-11]中對(duì)于參數(shù)取值的情況等進(jìn)行估值。
采用和聲搜索算法對(duì)模型求解,算法由C#語(yǔ)言在Visual Studio 2010平臺(tái)下實(shí)現(xiàn),在Inter(R)Core(TM)i5-3210M CPU和2 GB內(nèi)存環(huán)境下運(yùn)行。和聲記憶庫(kù)大小取80,記憶庫(kù)取值概率取值在0.9,微調(diào)概率0.3,經(jīng)過(guò)測(cè)試,取最大迭代次數(shù)為4 500,場(chǎng)景數(shù)選擇12個(gè)。為了對(duì)比運(yùn)到期限對(duì)模型的影響,選擇運(yùn)到期限1取值13.8 h,運(yùn)到期限2取值9.9 h。
經(jīng)過(guò)多次計(jì)算,在運(yùn)到期限1時(shí),經(jīng)過(guò)3 106次收斂,收斂值為27 121 152元,也就是總成本和總偏離程度的加權(quán)值,其中總成本5 806 423元,總偏離程度21 314 729元;運(yùn)到期限2時(shí),經(jīng)過(guò)3 781次迭代收斂,收斂值為29 181 330元,其中總成本5 452 476元,總偏離程度23 728 854元。平均運(yùn)行時(shí)間125 s。收斂圖如圖5所示。
圖5 和聲搜索算法收斂過(guò)程示意圖Fig.5 Convergence process of harmony search algorithm
圖6 車流合并情況示意圖(運(yùn)到期限1)Fig.6 Traffic flow merging situation (shipped to a period of 1)
以運(yùn)到期限限制1為例作解釋說(shuō)明,原來(lái)的37條車流,經(jīng)過(guò)車流組合,部分車流在途中進(jìn)行了中轉(zhuǎn)和摘掛作業(yè)。運(yùn)到期限限制1條件下實(shí)際開行列車11條,如表3所示。車流合并情況如圖6所示。運(yùn)到期限限制2同理,在此不再贅述。規(guī)律顯示,運(yùn)到期限增大,模型的總成本減小。結(jié)果表明,當(dāng)運(yùn)到期限減小時(shí),會(huì)導(dǎo)致某些開車的長(zhǎng)車流因?yàn)椴荒軡M足開行條件而不能開車,因此在一定程度上增加了開行列數(shù),也進(jìn)一步導(dǎo)致開行成本的增加。
表3 貨物快運(yùn)服務(wù)網(wǎng)絡(luò)魯棒優(yōu)化模型求解結(jié)果(運(yùn)到期限1)
鐵路貨物快運(yùn)服務(wù)網(wǎng)絡(luò)設(shè)計(jì)可以滿足市場(chǎng)對(duì)鐵路快運(yùn)發(fā)展的要求,在實(shí)際鐵路運(yùn)輸中,運(yùn)輸需求往往不能用一個(gè)定值去衡量,本文考慮到實(shí)際鐵路貨物快運(yùn)需求的波動(dòng)性,借鑒魯棒優(yōu)化思想,構(gòu)建了鐵路貨物快運(yùn)服務(wù)網(wǎng)絡(luò)設(shè)計(jì)魯棒優(yōu)化模型,以提高求解結(jié)果的適用性,并采用和聲搜索算法對(duì)模型進(jìn)行求解。算例分析表明,本文采用的構(gòu)模方式可以有效壓縮網(wǎng)絡(luò)規(guī)模,收斂速度快。本文給出的方法,能夠?yàn)樨浳锟爝\(yùn)列車服務(wù)網(wǎng)絡(luò)設(shè)計(jì)提供決策支持。但是,由于文中未考慮空車車底的回送可能會(huì)增加的運(yùn)輸成本,在下一步的研究中可以結(jié)合鐵路貨物快運(yùn)服務(wù)網(wǎng)絡(luò)設(shè)計(jì)和空車調(diào)配的問(wèn)題進(jìn)行綜合考慮。
[1]張靜. 我國(guó)鐵路快捷貨運(yùn)班列開行方案研究[D]. 北京:北京交通大學(xué), 2011.
[2]蘭勁棕. 我國(guó)鐵路快捷貨物運(yùn)輸組織相關(guān)問(wèn)題研究[D].成都:西南交通大學(xué), 2011.
[3]許旺土. 綜合快捷貨運(yùn)服務(wù)網(wǎng)絡(luò)運(yùn)輸能力計(jì)算方法研究[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]劉杰, 何世偉, 宋瑞,等. 鐵路既有繁忙干線貨運(yùn)產(chǎn)品布局優(yōu)化模型及算法[J]. 北京交通大學(xué)學(xué)報(bào), 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]李婷婷, 宋瑞. 國(guó)家層面綜合客運(yùn)樞紐分層布局魯棒優(yōu)化模型[J]. 東南大學(xué)學(xué)報(bào)(自然科學(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é)報(bào), 2011, 33(5):8-13.
[13]王保華, 何世偉. 不確定環(huán)境下物流中心選址魯棒優(yōu)化模型及其算法[J]. 交通運(yùn)輸系統(tǒng)工程與信息, 2009, 9(2):69-74.
[14]王瑩, 劉軍. 鐵路行包快運(yùn)專列開行方案優(yōu)化編制方法的研究[J]. 交通運(yùn)輸系統(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]許越. 集裝化運(yùn)輸模式下快捷貨運(yùn)服務(wù)網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)研究[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
陜西省社會(huì)科學(xué)基金項(xiàng)目(2016D051)
劉欣萌(1990—),女,助教,研究方向?yàn)榻煌ㄟ\(yùn)輸現(xiàn)代組織管理理論與方法。E-mail:13120872@bjtu.edu.cn
U292.3
A
1002-4026(2017)03-0065-08