李 冰 李明向 軒 華

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

0 引言

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

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

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

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

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

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

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

1 問(wèn)題建模

1.1 問(wèn)題描述

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

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

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

1.2 符號(hào)變量

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

(1)集合

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

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

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

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

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

R:陸續(xù)到達(dá)編組站的列車編號(hào)集合,記為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對(duì)應(yīng)車組的編號(hào)g,wM為作業(yè)w對(duì)應(yīng)車組g的貨車數(shù)m,wK為作業(yè)w分派的調(diào)機(jī)編號(hào)k,wU為作業(yè)w所處的批次編號(hào)u,wR為作業(yè)w對(duì)應(yīng)車組到達(dá)編組站所跟隨的貨物列車r,wH為作業(yè)w的取送性質(zhì)h。

(2)參數(shù)

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

Tk:調(diào)機(jī)k的最長(zhǎng)走行時(shí)間。

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

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

c2:單位時(shí)間貨車運(yùn)行成本。

c3:單位時(shí)間貨車等待成本。

tij:裝卸站i到裝卸站j的走行時(shí)間。

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

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

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

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

(4)決策變量

yuk:批次-調(diào)機(jī)匹配變量。yuk=1 表示第u批次由調(diào)機(jī)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)機(jī)運(yùn)營(yíng)成本、貨車運(yùn)營(yíng)成本、貨車待送待取成本最小化為目標(biāo)函數(shù),考慮取送順序、裝卸能力、調(diào)機(jī)牽引能力、車組取回-掛運(yùn)列車匹配、調(diào)機(jī)走行、取送作業(yè)時(shí)間間隔、調(diào)機(jī)-作業(yè)匹配、作業(yè)-批次匹配等實(shí)際約束,建立數(shù)學(xué)模型:

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

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

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

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

首先將編組站中某一時(shí)間段內(nèi)到達(dá)的車組依次用自然碼進(jìn)行編排,進(jìn)而選取模型中制約取送作業(yè)順序式(2)～(6)組建起作用約束組,并按照先順序、后批次的更新策略對(duì)取送順序進(jìn)行更新,從而形成初始取送作業(yè)順序集合?；诳尚屑s束的初始取送作業(yè)順序集合生成過(guò)程如圖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生成初始本地車組序列。將編組站中某一時(shí)間段內(nèi)到達(dá)的車組依次用自然碼進(jìn)行編排,記為G={1,2,…,},表示車組總數(shù)。

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

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

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

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

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

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

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

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

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

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

Stage3調(diào)機(jī)開(kāi)行批次劃分

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

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

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

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

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

Step3.3基于調(diào)機(jī)走行時(shí)長(zhǎng)約束的批次更新

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Step5基于GA 的蝙蝠群再更新

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

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

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

Step6輸出最佳蝙蝠個(gè)體

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

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

Step7迭代終止條件

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

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

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

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

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

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

Step2取送批次時(shí)間窗計(jì)算

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

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

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

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

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

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

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

3 實(shí)驗(yàn)驗(yàn)證及結(jié)果分析

3.1 實(shí)驗(yàn)場(chǎng)景

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

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

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

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

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

在編組站內(nèi),陸續(xù)有4 列貨物列車到達(dá),根據(jù)貨車的目的地不同將貨車分為16 個(gè)車組,由于各車組在裝卸站中作業(yè)方式包含取車作業(yè)和送車作業(yè),將16 個(gè)車組分為32 個(gè)取送作業(yè)并用自然碼進(jìn)行編號(hào),記為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 個(gè)裝卸站由于貨物線長(zhǎng)度限制,每個(gè)裝卸站都有最大裝卸能力,網(wǎng)絡(luò)內(nèi)所有的裝卸站以及裝卸能力信息如表3所示。

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

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

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

根據(jù)以往參考文獻(xiàn)數(shù)據(jù),設(shè)定調(diào)機(jī)單位分鐘運(yùn)營(yíng)成本c1=16、貨車單位分鐘運(yùn)營(yíng)成本c2=1.2、貨車單位分鐘待取待送成本c3=8、調(diào)機(jī)最大牽引定數(shù)hcl=40、調(diào)機(jī)最大行駛時(shí)間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ù),分別測(cè)試每組參數(shù)對(duì)運(yùn)營(yíng)成本及CPU 運(yùn)行時(shí)間的影響,每組參數(shù)測(cè)試十次并將結(jié)果取平均值,不同參數(shù)組合下求得運(yùn)營(yíng)成本和CPU 運(yùn)行時(shí)間如表5 所示。

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

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

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

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

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

3.4 過(guò)程驗(yàn)證

按照3.2 節(jié)得到的最優(yōu)參數(shù)組合對(duì)IA-TS 算法進(jìn)行配置:固定頻率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。算法運(yùn)行結(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)機(jī)走行時(shí)長(zhǎng)和表2 的取送車組作業(yè)信息表可以得到作業(yè)所屬批次、批次的發(fā)車時(shí)刻和各個(gè)批次取送作業(yè)的總時(shí)長(zhǎng),以批次的發(fā)車時(shí)刻和完成時(shí)刻設(shè)置時(shí)間窗,并基于批次時(shí)間窗和調(diào)機(jī)走行時(shí)長(zhǎng)進(jìn)行調(diào)機(jī)的自適應(yīng)分配,得到調(diào)機(jī)的分配方案。

對(duì)表6 的實(shí)驗(yàn)仿真對(duì)比結(jié)果進(jìn)行分析,分析結(jié)果如下:

表6 IA-TS、GA-EAAP 和BA-EAAP 的運(yùn)行計(jì)算結(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)機(jī)走行時(shí)間為 1314 min,總營(yíng)運(yùn)成本為50091.2 元,調(diào)機(jī)分配方案[{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)機(jī)走行時(shí)間為1477 min,總營(yíng)運(yùn)成本為61496 元,調(diào)機(jī)分配方案[{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)機(jī)走行時(shí)間為1442 min,總營(yíng)運(yùn)成本為91182.4 元,調(diào)機(jī)分配方案[{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)運(yùn)成本隨迭代次數(shù)的收斂曲線對(duì)比如圖7所示。從圖中也可以明顯的看出:IA-TS 算法比GA-EAAP 和BA-EAAP 算法得到的解的質(zhì)量更好,運(yùn)營(yíng)成本比較結(jié)果為IA-TS＜GA-EAAP＜BA-EAAP。

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

3.5 實(shí)驗(yàn)測(cè)試對(duì)比與性能評(píng)估

為了對(duì)IA-TS 算法進(jìn)行性能測(cè)試和評(píng)估,本文利用圖6 的樹(shù)枝形專用線網(wǎng)絡(luò)和表2 的車流信息表數(shù)據(jù),分別設(shè)計(jì)12項(xiàng)取送作業(yè)、32 項(xiàng)取送作業(yè)和64 項(xiàng)取送作業(yè)等三組不同取送作業(yè)數(shù)量的實(shí)驗(yàn),測(cè)試IA-TS、GA-EAAP 和BA-EAAP 算法的性能。三種被測(cè)算法的參數(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 算法測(cè)試的停止條件。對(duì)每組參數(shù){π,hcl}測(cè)試10 次,取平均目標(biāo)函數(shù)值Fava、平均計(jì)算機(jī)運(yùn)行時(shí)間和算法改進(jìn)率RAC 作為比對(duì)參考指標(biāo)。RAC 為比對(duì)算法的平均Fava之差與IA-TS 算法平均Fava的比值。RAC1為IA-TS 相對(duì)于GA-EAAP 的改進(jìn)率,RAC2為IA-TS 相對(duì)于BA-EAAP 的改進(jìn)率,即

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

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

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

表8 三種算法在10 項(xiàng)取送作業(yè)問(wèn)題中的性能測(cè)試比對(duì)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 項(xiàng)取送作業(yè)問(wèn)題中的性能測(cè)試比對(duì)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 項(xiàng)取送作業(yè)問(wèn)題中的性能測(cè)試比對(duì)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)對(duì)于不同規(guī)模問(wèn)題,三種算法在解的表現(xiàn)上有所差異,其中BA-EAAP 算法CPU 運(yùn)行時(shí)間較短,求解質(zhì)量較差;IA-TS 算法的CPU 運(yùn)行時(shí)間較長(zhǎng),但求解質(zhì)量最好。

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

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

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

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

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

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

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

4 結(jié)論

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

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