樹枝形專用線非直達(dá)車流取送的三階段綜合協(xié)調(diào)優(yōu)化

李 冰 李明向 軒 華

(鄭州大學(xué) 管理工程學(xué)院,河南 鄭州 450001)

0 引言

鐵路樞紐是龐大而復(fù)雜的系統(tǒng),在列流、車流和貨流相互交匯的鐵路端點、工業(yè)中心和大都市區(qū)往往會形成鐵路樞紐。樞紐內(nèi)集中配置有數(shù)量眾多的專用車站(編組站和裝卸站)和鐵路線路,通過對這些設(shè)備的合理運用,來完成列流、車流和貨流集散與中轉(zhuǎn)任務(wù)。

鐵路樞紐利用編組站解體到達(dá)列車、編組始發(fā)列車,實現(xiàn)“列流”向“車流”轉(zhuǎn)變。除此之外,樞紐內(nèi)分布有大量為城市、居民和倉庫區(qū)服務(wù)的公共貨運站,為工礦企業(yè)或工礦區(qū)服務(wù)的工業(yè)站,主要承擔(dān)貨物裝卸功能,故稱為裝卸站。公共貨運站或工業(yè)站等裝卸站主要負(fù)責(zé)貨物的裝車和卸車工作,完成“車流”和“貨流”的轉(zhuǎn)換。

鐵路樞紐的貨流由通過流和本地流組成,其中通過流僅需辦理有調(diào)和無調(diào)中轉(zhuǎn)作業(yè),而本地流則除此之外還要辦理面向裝卸站的作業(yè)車取送。據(jù)我國幾大樞紐所在鐵路局的貨流統(tǒng)計數(shù)據(jù),本地流作業(yè)量占到貨流總量的比例均達(dá)到一半以上。

小運轉(zhuǎn)作業(yè)系統(tǒng)是樞紐內(nèi)本地貨物運轉(zhuǎn)的主要運輸動力,承擔(dān)著樞紐編組站與裝卸站之間的“列流-車流-貨流”轉(zhuǎn)變過程中發(fā)揮著橋梁和紐帶作用。其任務(wù)核心是安排樞紐小運轉(zhuǎn)列車,將編組站解體后的本地作業(yè)車送往裝卸站,并將完成裝卸工作的本地作業(yè)車取回編組站。小運轉(zhuǎn)貨物作業(yè)系統(tǒng)在樞紐貨車集結(jié)和疏散過程中發(fā)揮著不可替代的作用,直接影響樞紐運送貨物的時效性。

鐵路貨物運輸組織的相關(guān)研究較多聚焦在服務(wù)通過流的路網(wǎng)干線大運轉(zhuǎn)列車,而服務(wù)本地流的樞紐小運轉(zhuǎn)列車因為等級低、服務(wù)性強等原因,造成相關(guān)研究工作開展不足。面向鐵路樞紐地方貨物流的小運轉(zhuǎn)作業(yè)系統(tǒng)受多種因素影響,最顯著的特點是到達(dá)車流隨機性大、可控性小,列車編組和機車運用靈活,貨車在樞紐內(nèi)作業(yè)次數(shù)多、停留時間長,加上小運轉(zhuǎn)列車等級低、為其它列車的服務(wù)性強,從而給小運轉(zhuǎn)作業(yè)系統(tǒng)的組織工作造成不利影響。同時,這也為小運轉(zhuǎn)作業(yè)系統(tǒng)研究工作開展的迫切性提出了更為緊迫的要求。

針對貨物作業(yè)車取送優(yōu)化,Guo 等[1]以調(diào)車機車的運行和等待時間最小化為目標(biāo),研究了貨物作業(yè)點取送車作業(yè)優(yōu)化問題,設(shè)計了模擬退火算法進行求解。Li 等[2]利用Arena平臺構(gòu)仿真模擬了不同鐵路專用線作業(yè)車取送-調(diào)移策略,并進行了對比分析。Yan 等[3]研究了海鐵聯(lián)運模式下的集裝箱取送問題。Hu 等[4]研究了鐵路樞紐內(nèi)的貨物取送徑路優(yōu)化問題,設(shè)計了一種動態(tài)滾動平面算法進行求解。Otto等[5]研究了技術(shù)站列車分配站場時的列車運行優(yōu)化問題,以不同站場作業(yè)調(diào)車數(shù)量最少為目標(biāo)構(gòu)建線性混合整數(shù)規(guī)劃模型。Lubbecke 等[6]研究了工廠內(nèi)鐵路專用線取送車調(diào)度優(yōu)化問題,以取送車作業(yè)時間總和最少為目標(biāo)構(gòu)建混合整數(shù)規(guī)劃模型,并采用分支定價算法對模型進行求解。王旭坪等[7]研究了多行程帶補貨時間窗的成品油配送問題,引入行程池的概念,設(shè)計了包含內(nèi)外兩層循環(huán)的啟發(fā)式算法。葛顯龍等[8]研究了跨區(qū)域多配送中心多車型開放式動態(tài)聯(lián)合送貨問題,建立考慮車載率的開放式車輛路徑模型,給出“初始優(yōu)化+實時優(yōu)化”的兩階段求解策略。Bettinelli 等[9]研究了城市物流系統(tǒng)中帶客戶和中間設(shè)施時間窗要求的多程分離式貨物取送問題,并提出了分支-切割-價格算法。Alyasiry等[10]研究了帶時間窗和后進先出裝載要求的貨物取送問題,并構(gòu)建了一個松弛網(wǎng)絡(luò)流模型,并設(shè)計了一個精確求解算法。Sun 等[11]研究了以碳排量最小化為目標(biāo)函數(shù)的多車型車隊貨物取送問題,提出了基于集劃分模型的精確求解算法。Gyorgyi 等[12]研究了動態(tài)隨機貨物取送問題,分析了不同客戶間貨物取送作業(yè)發(fā)生的概率,并提出了一種基于概率分析的啟發(fā)式求解算法。Zhang 等[13]等研究了面向快時尚零售商的多品種貨物同步取送問題,構(gòu)建了問題模型,并提出了一種元啟發(fā)式算法。Boysen 等[14]研究了一類轉(zhuǎn)運場鐵路專用線取送車調(diào)度問題,提出一種啟發(fā)式算法和分支定界算法。Chen 等[15]建立了一種基于Petri 網(wǎng)絡(luò)的仿真網(wǎng)絡(luò)模型,分析了多場站間鐵路專用線的不同列車取送作業(yè)環(huán)節(jié)。Adlbrecht 等[16]針對調(diào)車場專用線取送車徑路選擇問題,建立了一種自動化決策系統(tǒng),并通過仿真過程進行了效果驗證。唐春林等[17]研究了一類樹枝形鐵路專用線直達(dá)貨物列車動態(tài)取送問題,以取送車走行時間和等待時間之和最小為目標(biāo)建立數(shù)學(xué)模型。程磊等[18]針對鐵路樹枝型專用線取送車問題,以調(diào)車取送作業(yè)總走行時間最小為目標(biāo)構(gòu)建0-1 規(guī)劃模型,并提出一種基于元胞自動機的改進蟻群算法。李冰等[19,20]以調(diào)機作業(yè)成本和貨車運營成本最小化為目標(biāo),研究了不同環(huán)境下鐵路樞紐樹枝形鐵路專用線取送車問題,并設(shè)計了啟發(fā)式求解算法。

現(xiàn)有研究工作主要集中在基于汽車運輸?shù)呢浳锶∷蛦栴}。面向鐵路樞紐地方貨物流的小運轉(zhuǎn)列車取送研究相對較少,且多為單調(diào)機作業(yè)、先送后取模式。本文研究一類多調(diào)機、同步取送環(huán)境下的樹枝形鐵路專用線網(wǎng)絡(luò)非直達(dá)車流取送車優(yōu)化問題。以調(diào)機運營、貨車運營和貨車待送待取總費用最小化為目標(biāo),構(gòu)建數(shù)學(xué)模型,并設(shè)計一種三階段融合求解策略(Integrated approach with three stage,簡稱IA-TS)。第一階段,首先隨機生成初始取送作業(yè)順序集合,進而利用模型起作用約束組進行更新;第二階段,提出IBH-GA 啟發(fā)式迭代尋優(yōu)過程,完成對取送作業(yè)順序集合的進一步優(yōu)化;第三階段,給出利用基于走行時長-批次時間窗的調(diào)機自適應(yīng)分配策略,實現(xiàn)取送作業(yè)批次劃分與調(diào)機分配。最后設(shè)計多組實驗場景進行方法測試和結(jié)果分析。

1 問題建模

1.1 問題描述

本文研究一類小運轉(zhuǎn)列車在樹枝形鐵路專用線網(wǎng)絡(luò)中進行貨物取送的問題。以調(diào)機運營成本、貨車運營成本、貨車編組站待送成本和貨車裝卸站待取空費成本等各項費用最小化為目標(biāo),考慮取送順序、裝卸能力、調(diào)機牽引定數(shù)、車組取回-掛運列車匹配、調(diào)機走行、取送作業(yè)時間間隔、調(diào)機-作業(yè)匹配、作業(yè)-批次匹配等限制條件,確定合理的取送批次、順序與調(diào)機分配方案。本地貨物作業(yè)車取送作業(yè)如圖1所示。

圖1 本地貨物作業(yè)車取送過程Figure 1 Process of taking-out and placing-in local wagons

結(jié)合鐵路樞紐小運轉(zhuǎn)貨物作業(yè)工作實際,對問題進行如下約定:多臺調(diào)機并行作業(yè),各調(diào)機的牽引定數(shù)均相同;每個取送批次既包含取車作業(yè)也包含送車作業(yè);樞紐內(nèi)專用線和裝卸站分布、裝卸站間調(diào)機走行時間和各車組的裝卸時間均已知。

1.2 符號變量

為構(gòu)建模型,研究引入以下參量與變量:

(1)集合

I:鐵路樞紐內(nèi)裝卸站集合,記為I=,i=0 時表示編組站,時表示裝卸站,為鐵路樞紐內(nèi)裝卸站總數(shù)。

G:陸續(xù)到達(dá)編組站的車組編號集合,記為G={g∣g=1,2,…,},表示車組總數(shù)。

M:陸續(xù)到達(dá)編組站的車組的貨車數(shù),記為M={m(g)∣g=1,2,…,}。

K:調(diào)機編號集合,記為K={k∣k=1,2,…,},為調(diào)機總數(shù)。

U:取送批次編號集合,記為U={u∣u=1,2,…,},為取送批次總數(shù)。

R:陸續(xù)到達(dá)編組站的列車編號集合,記為R={r∣r=1,2,…,},其中為貨物列車的總數(shù);

H:取送作業(yè)性質(zhì)集合,記為H={h∣h=1,2},h=2 表示送車,h=1 表示取車。

W:取送作業(yè)集合。用自然碼標(biāo)記G中各車組的送車和取車作業(yè),記為W={w∣w=1,2,…,},為取送作業(yè)總數(shù)。

ζ(w):作業(yè)w的屬性標(biāo)記集合,記為ζ(w)={wI,wG,wM,wK,wU,wR,wH}。wI為作業(yè)w的目的裝卸站i,wG為作業(yè)w對應(yīng)車組的編號g,wM為作業(yè)w對應(yīng)車組g的貨車數(shù)m,wK為作業(yè)w分派的調(diào)機編號k,wU為作業(yè)w所處的批次編號u,wR為作業(yè)w對應(yīng)車組到達(dá)編組站所跟隨的貨物列車r,wH為作業(yè)w的取送性質(zhì)h。

(2)參數(shù)

hcl:調(diào)機牽引定數(shù)。

Tk:調(diào)機k的最長走行時間。

psti:裝卸站i的裝卸能力。

c1:單位時間調(diào)機使用成本。

c2:單位時間貨車運行成本。

c3:單位時間貨車等待成本。

tij:裝卸站i到裝卸站j的走行時間。

tw:車組wG在目的裝卸站完成裝卸作業(yè)所需時間。

(3)狀態(tài)變量

qu:第u批次的貨車總數(shù)量。顯然qu=。

τu:第u批作業(yè)的取送總時間。

(4)決策變量

yuk:批次-調(diào)機匹配變量。yuk=1 表示第u批次由調(diào)機k服務(wù),否則yuk=0。

zuw:批次-作業(yè)匹配變量。zuw=1 表示作業(yè)w屬于第u批次,否則zuw=0。

(5)取送順序表述

S(W):取送位次集合,記為S(W)={s(w)∣s(1),s(2),…,},s(w)表示作業(yè)w的取送位次。

X(W):取送順序集合。根據(jù)取送位次S(W)的先后順序重新排列作業(yè)W形成取送順序集合,記為X(W)={w∣w∈W}。

1.3 模型構(gòu)建

以調(diào)機運營成本、貨車運營成本、貨車待送待取成本最小化為目標(biāo)函數(shù),考慮取送順序、裝卸能力、調(diào)機牽引能力、車組取回-掛運列車匹配、調(diào)機走行、取送作業(yè)時間間隔、調(diào)機-作業(yè)匹配、作業(yè)-批次匹配等實際約束,建立數(shù)學(xué)模型:

式(1)表示在站停留車小時費用和調(diào)機取送費用之和最小;式(2)表示同一組貨車要先送后取;式(3)表示一個裝卸站內(nèi)同時作業(yè)的貨車數(shù)量不能超過裝卸站的容車能力;式(4)表示同批次貨車數(shù)不能高于調(diào)機牽引定數(shù);式(5)表示車組取回時間時刻必須在掛運列車最晚編組時刻前;式(6)同批次總作業(yè)時間不能高于調(diào)機最大作業(yè)時間;式(7)表示車組送車時刻和取車時刻的時間差要大于車組裝卸時間;式(8)表示每批作業(yè)只能由一臺調(diào)機來完成;式(9)表示每項作業(yè)不能分割,僅能劃歸同一批次;式(10)～(12)為變量取值約束。

2 優(yōu)化求解策略

該模型為混合整數(shù)規(guī)模模型(Mixed integer programming model,簡稱MIP 模型),直接求解較為困難,設(shè)計取送順序集合生成-取送順序集合優(yōu)化-調(diào)機自適應(yīng)分配三階段融合求解策略(Integrated approach with three stage,簡稱IA-TS)。具體步驟如下。

2.1 基于起作用約束組的初始取送作業(yè)順序生成

首先將編組站中某一時間段內(nèi)到達(dá)的車組依次用自然碼進行編排,進而選取模型中制約取送作業(yè)順序式(2)～(6)組建起作用約束組,并按照先順序、后批次的更新策略對取送順序進行更新,從而形成初始取送作業(yè)順序集合?；诳尚屑s束的初始取送作業(yè)順序集合生成過程如圖2 所示。

圖2 基于起作用約束組的初始取送作業(yè)順序集合生成Figure 2 Generating initial placing-in and taking out wagons sequence set using active constraint group

Stage1初始取送作業(yè)順序構(gòu)造

Step1.1生成初始本地車組序列。將編組站中某一時間段內(nèi)到達(dá)的車組依次用自然碼進行編排,記為G={1,2,…,},表示車組總數(shù)。

Step1.2生成初始取送作業(yè)順序。由于各個車組在裝卸站內(nèi)的作業(yè)分為取車和送車兩種,故用自然碼對其進行編號,記為W={w∣w=1,2,…,},為取送作業(yè)總數(shù)。利用車組的初始編號生成初始取送位次集合S(W),進而得到初始取送作業(yè)順序X(W)。初始取送順序如圖3 所示。

圖3 初始取送作業(yè)順序的構(gòu)造Figure 3 Setting up initial placing-in and taking out wagons sequence

Stage2取送作業(yè)順序更新調(diào)整

對初始取送順序依據(jù)先送后取順序限制-裝卸能力限制再進行更新調(diào)整。

Step2.1基于先送后取約束的初始取送作業(yè)順序更新

依據(jù)同一車組的不同作業(yè)先送后取的順序限制對取送順序進行更新,對同一車組不同取送作業(yè)w1和w2,要求取送位次s(w1)＜s(w2),進而保證同一車組的送車作業(yè)一定在取車作業(yè)前面。

Step2.2基于裝卸能力約束的取送作業(yè)順序更新

利用式(3)對取送作業(yè)進行順序調(diào)整。首先依次對各個裝卸站的裝卸能力psti進行檢驗,鎖定不滿足裝卸能力約束的兩項作業(yè),分為兩種情況:

情況一:若某一車組的送車作業(yè)與另一車組的取車作業(yè)相連,則將該車組的送車作業(yè)和該車組送取車作業(yè)順序進行互換。

情況二:若為相鄰兩項送車作業(yè),則將前一車組的取車作業(yè)與后一車組的送車作業(yè)順序互換,得到局部調(diào)整方案。

Stage3調(diào)機開行批次劃分

通過對初始取送作業(yè)順序的調(diào)整,尚不能保證滿足調(diào)機牽引定數(shù)、貨車取回時刻和調(diào)機走行時長的限制,需要按照要求再進行批次更新,形成可行的取送作業(yè)順序方案。

Step3.1基于調(diào)機牽引定數(shù)約束的批次劃分

利用式(4)進行批次的劃分,首先將作業(yè)按照順序進行編排,若到某個作業(yè)順序編號,牽引量達(dá)到調(diào)機的牽引定數(shù),則在此位置后面插入0 進行標(biāo)記,形成批次。依次對所有取送作業(yè)順序的標(biāo)記,完成批次劃分。

Step3.2基于取回時間窗約束的批次更新

根據(jù)急用先送先取得原則,利用式(5)對取送作業(yè)順序進行更新,根據(jù)批次的發(fā)車時間以及走行時間進行計算,對于不滿足取回時間窗約束取車作業(yè),往前提一個位置,再進行判斷,直至滿足取回時間窗的約束,依次完成批次更新。

Step3.3基于調(diào)機走行時長約束的批次更新

利用式(6)對批次進行再更新。首先統(tǒng)計第u批次的任務(wù)總的運行時間,若第u批次任務(wù)的總運行時間大于調(diào)機的走行時間,則此方案不滿足條件,返回step3.1 再次進行批次的劃分。反之,接受此方案,完成一個取送作業(yè)順序的批次劃分。

Stage4取送作業(yè)順序集合生成

Step4.1設(shè)定取送作業(yè)順序集合中的取送作業(yè)順序數(shù)為π。

Step4.2重復(fù)上述步驟,產(chǎn)生π個取送作業(yè)順序。

Step4.3對重復(fù)得到的取送作業(yè)順序進行基于作業(yè)編號的調(diào)整,從而生成初始取送作業(yè)順序集合X,表示為X=[x1,…,xπ]T,xi為一個取送作業(yè)順序解。

2.2 基于IBH-GA 的取送作業(yè)順序集合優(yōu)化

設(shè)計嵌入遺傳機制的改進蝙蝠啟發(fā)式迭代尋優(yōu)過程(Improved bat heuristic with genetic algorithm,簡稱IBH-GA)。該過程在每次迭代中,先基于蝙蝠算法更新機制對初始取送作業(yè)順序進行改進。為防止陷入局部最優(yōu),引入遺傳算法中的精英交叉機制,以提高算法全局搜索能力,最后利用終止規(guī)則完成循環(huán)迭代,得到最佳取送作業(yè)順序,IBH-GA 算法過程如圖4 所示。具體步驟如下:

圖4 IBH-GA 算法流程圖Figure 4 Flowchart of IBH-GA algorithm

Step1蝙蝠群初始參數(shù)設(shè)置

將初始取送作業(yè)順序集合中π個取送作業(yè)順序作為蝙蝠個體,形成初始種群xbat,并設(shè)置參數(shù)初始蝙蝠脈沖發(fā)射響度Vti、蝙蝠脈沖速率ri、蝙蝠脈沖搜索范圍[fmin,fmax],最大迭代次數(shù)nc_max。

Step2最優(yōu)蝙蝠個體搜索

根據(jù)適應(yīng)度值函數(shù)計算出初始蝙蝠群中所有個體的適應(yīng)度值,選擇最小的適應(yīng)度值作為初始種群中最優(yōu)蝙蝠個體記為x*,其適應(yīng)度值為。

Step3蝙蝠群參數(shù)更新

蝙蝠脈沖頻率、速度以及位置的更新公式分別為:

式(13)中的fi為蝙蝠個體i的搜索脈沖頻率,fmax和fmin分別為其最大和最小取值,β為脈沖頻度增強系數(shù),其取值區(qū)間為[0,1];別表示第t次和t-1 次迭代過程中,第i個蝙蝠個體的速度信息;分別表示第t次和t-1次迭代過程中,第i個蝙蝠個體的位置信息。

Step4基于最優(yōu)蝙蝠個體的局部搜索

生成一個均勻分布隨機數(shù)ρ,若ρ＞ri,則利用式(16)對最優(yōu)解x*的進行局部搜索,產(chǎn)生新解記為xnew。

其中,ε為隨機數(shù)且ε∈[-1,1]。根據(jù)蝙蝠種群更新特點,若fitness(xnew)＜fitness(x*),則更新最優(yōu)解xbest=xnew。

Step5基于GA 的蝙蝠群再更新

蝙蝠群的更新機制使得其易陷入局部最優(yōu)陷阱,為改善此種情況,引入遺傳算法的交叉機制,豐富種群的多樣性。交叉方式如下:

隨機取出最優(yōu)蝙蝠個體xbest中一段基因,并將初始蝙蝠群中所有個體做基因沖突檢測,并把這段基因插入蝙蝠群中每一個個體后面,完成交叉操作,形成新的蝙蝠群xbat1。

計算新的蝙蝠群xbat1的適應(yīng)度值,找出最優(yōu)的解,記為xcross。

Step6輸出最佳蝙蝠個體

生成一個隨機數(shù),記為ρ1,若ρ1＜Vi且fitness(xbest)＜fitness(xcross),接受新解xcross為最優(yōu)解,再根據(jù)式(17)和式(18)對xcross更新頻率ri和響度的信息:

式(16)中α和λ分別為脈沖音強衰減系數(shù)和脈沖頻率增強系數(shù),α、λ∈[0,1]。

Step7迭代終止條件

返回Step3,重復(fù)迭代。若迭代次數(shù)達(dá)到nc_max,則停止迭代,輸出最優(yōu)解及對應(yīng)最佳取送作業(yè)順序,并記錄隨迭代次數(shù)的變化曲線。

2.3 基于批次時間窗-走行時長的調(diào)機自適應(yīng)分配

鐵路樞紐內(nèi)的取送作業(yè)往往需要多臺調(diào)機共同完成,從而給出調(diào)機自適應(yīng)配置過程(Engine Adaptive allocation procedure,簡稱EAAP)。該過程以取送時間窗限制及最小化調(diào)機數(shù)為基本原則,對IBH-GA 得到的最佳取送作業(yè)順序,計算每批次的時間窗,為每批次取送任務(wù)配置一臺調(diào)機。當(dāng)前調(diào)機無法滿足取送批次時間窗要求或達(dá)到調(diào)機最長走行時間限制時增加新調(diào)機,從而實現(xiàn)樞紐內(nèi)的調(diào)機對取送作業(yè)的動態(tài)配置。基于批次時間窗-走行時長的調(diào)機自適應(yīng)分配流程如圖5 所示。

圖5 基于批次時間窗-走行時長的調(diào)機自適應(yīng)分配Figure 5 Flowchart of engine adaptive allocation procedure considering batch time windows and engine running time

Step1參數(shù)設(shè)定。

調(diào)機最長走行時間為Tk,調(diào)機編號集合K={k∣k=1,2,…,},其中為調(diào)機總數(shù),取送作業(yè)批次編號集合U={u∣u=1,2,…,},其中為取送作業(yè)批次總數(shù)。

Step2取送批次時間窗計算

根據(jù)IBH-GA 優(yōu)化得到取送順序批次方案的發(fā)車時間、返回編組站時間,并設(shè)立時間窗。其中表示第u批次取送作業(yè)的發(fā)車時刻,表示第u批次取送作業(yè)返回編組站時刻。

Step3基于批次時間窗的調(diào)機自適應(yīng)分配

依據(jù)批次分配方案進行調(diào)機分配,調(diào)機分配策略:首先對批次u=1 的任務(wù)分配編號為k=1 的調(diào)機,再對批次u=2的任務(wù)進行調(diào)機的分配,此時要判斷調(diào)機k=1 是否已經(jīng)回到編組站,若調(diào)機k=1 沒有回到編組站則啟用調(diào)機k=2。依次對所有批次進行調(diào)機的分配,直至完成所有的批次任務(wù)。

Step4基于走行時長的調(diào)機自適應(yīng)分配更新

對滿足時間窗約束的調(diào)機k再基于調(diào)機走行限制進行更新。τu表示第u批次完成取送所需要的時間,τu=。若k=1 滿足時間窗,但(τ1+τ2)＞T1,那么啟用調(diào)機k=2 完成下一批次的取送任務(wù);若k=1 滿足時間窗,但(τ1+τ2)＜T1,分配調(diào)機k=1 完成下一批次的取送任務(wù)。

Step5輸出調(diào)機分配方案

依次完成所有批次的取送任務(wù),得到調(diào)機分配方案,完成調(diào)機自適應(yīng)分配。

3 實驗驗證及結(jié)果分析

3.1 實驗場景

(1)樹枝形鐵路專用線網(wǎng)絡(luò)

設(shè)計一個樹枝形鐵路專用線網(wǎng)絡(luò),其中0 表示編組站,1～12 表示裝卸站,如圖6 所示。各裝卸站間的調(diào)機走行時間如表1 所示。

表1 各裝卸站之間的調(diào)機走行時間(單位:分鐘)Table 1 Running time of shunting engine between handling stations in railway terminal (Unit:min)

圖6 鐵路樞紐樹枝形專用線Figure 6 Branch-shaped siding in railway terminal

(2)樞紐內(nèi)車流到達(dá)信息

在編組站內(nèi),陸續(xù)有4 列貨物列車到達(dá),根據(jù)貨車的目的地不同將貨車分為16 個車組,由于各車組在裝卸站中作業(yè)方式包含取車作業(yè)和送車作業(yè),將16 個車組分為32 個取送作業(yè)并用自然碼進行編號,記為W={w∣w=1,2,…,32}。車流數(shù)據(jù)如表2 所示。

表2 作業(yè)車取送信息表Table 2 Data of arrival train and wagon flow in railway terminal

(3)裝卸站的裝卸能力信息

12 個裝卸站由于貨物線長度限制,每個裝卸站都有最大裝卸能力,網(wǎng)絡(luò)內(nèi)所有的裝卸站以及裝卸能力信息如表3所示。

表3 裝卸站裝卸能力Table 3 Handling station capacity

3.2 IA-TS 主要參數(shù)的調(diào)試

IA-TS 采用試算法來確定主要參數(shù)值。利用Matlab R2014a 對 IA-TS 求解算法進行編程,在Windows 7 作為系統(tǒng),處理器為Intel(R) Core(TM) i5-4200 M CPU @ 2.50 GHz 微機上運行,選取IA-TS 中對結(jié)果影響較大的蝙蝠脈沖發(fā)射響度V和蝙蝠脈沖頻率r兩個參數(shù)進行測試。測試方法為固定其中一個參數(shù),調(diào)整另一個參數(shù),基于多種參數(shù)組合進行嘗試,找出最優(yōu)參數(shù)組合。

根據(jù)以往參考文獻(xiàn)數(shù)據(jù),設(shè)定調(diào)機單位分鐘運營成本c1=16、貨車單位分鐘運營成本c2=1.2、貨車單位分鐘待取待送成本c3=8、調(diào)機最大牽引定數(shù)hcl=40、調(diào)機最大行駛時間Tk=300 min。設(shè)定IA-TS 算法中的固定頻率f_min=0、f_max=1、α=0.9、λ=0.9,蝙蝠群數(shù)量π為10,交叉概率取0.9,最大迭代次數(shù)nc_max=300,給出蝙蝠脈沖發(fā)射響度V和蝙蝠脈沖頻率r參數(shù)取值如表4 所示。

表4 IA-TS 求解算法的參數(shù)設(shè)置Table 4 Parameter setting for IATS approach

根據(jù)參數(shù)設(shè)置,生成25 組參數(shù),分別測試每組參數(shù)對運營成本及CPU 運行時間的影響,每組參數(shù)測試十次并將結(jié)果取平均值,不同參數(shù)組合下求得運營成本和CPU 運行時間如表5 所示。

從表5 中可以看出:蝙蝠脈沖發(fā)射響度V對于營運成本和CPU 運行時間的影響沒有呈現(xiàn)出一定的規(guī)律性,這說明蝙蝠脈沖發(fā)射響度V對解的影響具有隨機性。蝙蝠脈沖頻率r的增大會減少CPU 運行時間,但對解的質(zhì)量影響沒有呈現(xiàn)規(guī)律性。通過結(jié)果的對比,選取V=0.95、r=0.3 為最優(yōu)參數(shù)組合。

表5 不同參數(shù)組合下IA-TS 求解算法運行結(jié)果對比Table 5 Comparing results for IA-TS under different parameters setting

3.3 算法比對方案設(shè)計

在解決排序問題上,遺傳算法GA 和蝙蝠算法BA 相較傳統(tǒng)算法表現(xiàn)出更為突出的性能優(yōu)勢。故引入此兩種算法作為比對,以驗證本文所提出的IA-TS 方法的計算性能。

又因GA 和BA 僅能優(yōu)化取送作業(yè)順序,無法進一步完成調(diào)機指派,從而引入文本提出的調(diào)機自適應(yīng)配置過程(EAAP)來實現(xiàn)。故將此兩種比對算法簡寫為GA-EAAP 和BA-EAAP。

3.4 過程驗證

按照3.2 節(jié)得到的最優(yōu)參數(shù)組合對IA-TS 算法進行配置:固定頻率f_min=0,f_max=1,α=0.9,λ=0.9,蝙蝠群數(shù)量π為10,交叉概率取0.9,最大迭代次數(shù)nc_max=300,蝙蝠脈沖發(fā)射響度V=0.95,蝙蝠脈沖頻度r=0.3;BA-EAAP 算法的參數(shù)與IA-TS 求解算法的保持一致;GA-EAAP 算法交叉概率取0.9,變異概率取0.05。算法運行結(jié)果如表6 所示。

利用表6 中取送位次s(w)的順序,我們可以得到取送作業(yè)順序。例如表6 中GA-EAAP 算法中作業(yè)w的取送位次:s(w)={s(1)=1,s(7)=2,s(5)=3,…,s(6)=32},可以得到取送順序x={1,7,5,…,6},再根據(jù)得到的取送順序以及表6 中的批次信息、表1 的裝卸站間的調(diào)機走行時長和表2 的取送車組作業(yè)信息表可以得到作業(yè)所屬批次、批次的發(fā)車時刻和各個批次取送作業(yè)的總時長,以批次的發(fā)車時刻和完成時刻設(shè)置時間窗,并基于批次時間窗和調(diào)機走行時長進行調(diào)機的自適應(yīng)分配,得到調(diào)機的分配方案。

對表6 的實驗仿真對比結(jié)果進行分析,分析結(jié)果如下:

表6 IA-TS、GA-EAAP 和BA-EAAP 的運行計算結(jié)果Table 6 Results for IA-TS,GA-EAAP and BA-EAAP applied to the test

IA-TS 求解結(jié)果為0-1-0-9-3-5-0-13-15-10-11-20-0-21-0-19-7-17-0-4-0-14-23-8-0-27-0-29-31-28-25-0-22-30-24-0-2-16-32-6-0-12-18-26-0,調(diào)機走行時間為 1314 min,總營運成本為50091.2 元,調(diào)機分配方案[{u=1,k=1},{u=2,k=2},{u=3,k=3},{u=4,k=1},{u=5,k=4},{u=6,k=5},{u=7,k=6},{u=8,k=7},{u=9,k=8},{u=10,k=2},{u=11,k=9},{u=12,k=1}]。

GA-EAAP 求解結(jié)果為0-1-7-0-5-11-0-8-15-3-13-0-9-23-0-19-21-0-10-20-0-12-17-0-27-31-25-0-4-0-2-28-22-29-16-0-24-32-26-0-14-0-18-30-6-0,調(diào)機走行時間為1477 min,總營運成本為61496 元,調(diào)機分配方案[{u=1,k=1},{u=2,k=2},{u=3,k=3},{u=4,k=4},{u=5,k=5},{u=6,k=6},{u=7,k=1},{u=8,k=2},{u=9,k=7},{u=10,k=8},{u=11,k=4},{u=12,k=5},{u=13,k=6}]。

BA-EAAP 求解結(jié)果為0-3-1-9-0-7-13-0-4-15-0-8-11-21-0-19-12-10-26-0-5-25-23-0-17-30-28-6-18-0-20-31-0-14-0-29-27-16-24-0-32-22-2-0,調(diào)機走行時間為1442 min,總營運成本為91182.4 元,調(diào)機分配方案[{u=1,k=1},{u=2,k=2},{u=3,k=3},{u=4,k=5},{u=5,k=5},{u=6,k=6},{u=7,k=7},{u=8,k=2},{u=9,k=8},{u=10,k=3},{u=11,k=8}]。

三種算法調(diào)運成本隨迭代次數(shù)的收斂曲線對比如圖7所示。從圖中也可以明顯的看出:IA-TS 算法比GA-EAAP 和BA-EAAP 算法得到的解的質(zhì)量更好,運營成本比較結(jié)果為IA-TS＜GA-EAAP＜BA-EAAP。

圖7 三種算法調(diào)運成本隨迭代次數(shù)收斂曲線對比圖Figure 7 Comparison for shunting cost with iteration number for three algorithms

3.5 實驗測試對比與性能評估

為了對IA-TS 算法進行性能測試和評估,本文利用圖6 的樹枝形專用線網(wǎng)絡(luò)和表2 的車流信息表數(shù)據(jù),分別設(shè)計12項取送作業(yè)、32 項取送作業(yè)和64 項取送作業(yè)等三組不同取送作業(yè)數(shù)量的實驗,測試IA-TS、GA-EAAP 和BA-EAAP 算法的性能。三種被測算法的參數(shù)設(shè)置如表7 所示。

表7 三種算法的參數(shù)設(shè)置Table 7 Parameter setting for the three algorithms

本文設(shè)置迭代次數(shù)nc_max為300 次,將其作為IA-TS、GA-EAAP 和BA-EAAP 算法測試的停止條件。對每組參數(shù){π,hcl}測試10 次,取平均目標(biāo)函數(shù)值Fava、平均計算機運行時間和算法改進率RAC 作為比對參考指標(biāo)。RAC 為比對算法的平均Fava之差與IA-TS 算法平均Fava的比值。RAC1為IA-TS 相對于GA-EAAP 的改進率,RAC2為IA-TS 相對于BA-EAAP 的改進率,即

RAC1=(GA -EAAPC-(IA-TSC))/IA-TSC×100%

RAC2=(BA -EAAPC-(IA-TSC))/IA-TSC×100%

測試結(jié)果如表8、表9 和表10 所示。

表8 三種算法在10 項取送作業(yè)問題中的性能測試比對Table 8 Performance for IA-TS、GA-EAAP and BA-EAAP applied to the problem with 10 placing-in and taking-out wagons

表9 三種算法在32 項取送作業(yè)問題中的性能測試比對Table 9 Performance for IA-TS、GA-EAAP and BA-EAAP applied to the problem with 32 placing-in and taking-out wagons

表10 三種算法在64 項取送作業(yè)問題中的性能測試比對Table 10 Performance for IA-TS、GA-EAAP and BA-EAAP applied to the problem with 64 placing-in and taking-out wagons

可得到如下結(jié)論:

(1)對于不同規(guī)模問題,三種算法在解的表現(xiàn)上有所差異,其中BA-EAAP 算法CPU 運行時間較短,求解質(zhì)量較差;IA-TS 算法的CPU 運行時間較長,但求解質(zhì)量最好。

在10 項取送作業(yè)問題中,IA-TS 算法的解的質(zhì)量分別平均高于GA-EAAP 算法14%和BA-EAAP 算法19%;在32 項取送作業(yè)問題中,IA-TS 算法的解的質(zhì)量分別平均高于GAEAAP 算法17%和BA-EAAP 算法51%;在64 項取送作業(yè)問題中,IA-TS 算法的解的質(zhì)量分別平均高于GA-EAAP 算法24%和BA-EAAP 算法69%。IA-TS 相較與BA-EAPP 和GAEAAP 的改進率如表11 所示。

表11 IA-TS 算法相較于BA-EAAP 和GA-EAAP 的改進率Table 11 Improvement rate of IA-TS comparing with BA-EAAP and GA-EAAP

根據(jù)不同取送作業(yè)數(shù)量下改進率RAC1和 RAC2的平均值結(jié)果對比,隨著取送作業(yè)數(shù)量的增加,改進率RAC1和RAC2是呈上升的趨勢,說明作業(yè)數(shù)量增加的情況下,IA-TS算法相對于GA-EAAP 算法和BA-EAAP 算法優(yōu)勢更加明顯。

(2)對于不同參數(shù),可以看到在不同種群數(shù)量下,種群數(shù)量π=20 時的計算機運行時間要明顯高于π=10 時候,但求解質(zhì)量并沒有得到明顯改善,有的更是沒有改善,說明增加種群數(shù)量會增加計算機運行時間,并不能提高解的質(zhì)量。

3.6 求解質(zhì)量與算法迭代次數(shù)的相關(guān)性

選用3.5 節(jié)的三組實驗,選取3.2 節(jié)中參數(shù)調(diào)試結(jié)果中的較優(yōu)參數(shù)組合{V=0.95,r=0.3}。測試算法求解質(zhì)量與迭代次數(shù)的相關(guān)性,如圖8 所示。由此可以看出,隨著迭代次數(shù)的增加,IA-TS 算法的優(yōu)勢更為明顯。

圖8 求解質(zhì)量與算法迭代次數(shù)的演進關(guān)系Figure 8 Comparison for solution quality with iteration number of algorithms under different size problems

4 結(jié)論

鐵路樞紐小運轉(zhuǎn)作業(yè)系統(tǒng)承擔(dān)著本地貨流運轉(zhuǎn)的重要任務(wù),其核心工作就是編排小運轉(zhuǎn)列車完成樞紐內(nèi)編組站與裝卸站間的本地作業(yè)車取送。本文以調(diào)機運營成本、貨車運營成本、貨車待送待取成本最小化為目標(biāo)函數(shù),考慮取送順序、裝卸能力、調(diào)機牽引能力、車組取回-掛運列車匹配、調(diào)機走行、取送作業(yè)時間間隔、調(diào)機-作業(yè)匹配、作業(yè)-批次匹配等實際約束,建立樹枝形專用線非直達(dá)車流取數(shù)學(xué)模型。鑒于直接求解較為困難,本文故設(shè)計取送順序集合生成-取送順序集合優(yōu)化-調(diào)機自適應(yīng)分配的三階段融合求解策略。該策略在第一階段,隨機生成初始取送作業(yè)順序集合并利用模型起作用約束組進行更新;第二階段,利用IBH-GA 啟發(fā)式完成裝卸站間貨車取送作業(yè)順序優(yōu)化;第三階段,利用基于批次時間窗-走行時長的EAAP 過程實現(xiàn)取送作業(yè)批次劃分與調(diào)機分配。最后,設(shè)計多組實驗場景進行方法測試和結(jié)果分析。

鐵路樞紐專用線網(wǎng)絡(luò)主要有放射形、樹枝形和混合形三種形式,本文研究了樹枝形鐵路專用線取送車優(yōu)化問題,作業(yè)車均為單重作業(yè)車,沒有考慮作業(yè)車在樞紐內(nèi)不同裝卸站間的調(diào)移問題。未來研究工作將聚焦更為復(fù)雜的混合形鐵路專用線取送車優(yōu)化,并考慮帶調(diào)移的雙重作業(yè)車取送問題。