樹枝形專用線非直達車流取送的三階段綜合協調優化

李 冰 李明向 軒 華

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

0 引言

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

鐵路樞紐利用編組站解體到達列車、編組始發列車,實現“列流”向“車流”轉變。除此之外,樞紐內分布有大量為城市、居民和倉庫區服務的公共貨運站,為工礦企業或工礦區服務的工業站,主要承擔貨物裝卸功能,故稱為裝卸站。公共貨運站或工業站等裝卸站主要負責貨物的裝車和卸車工作,完成“車流”和“貨流”的轉換。

鐵路樞紐的貨流由通過流和本地流組成,其中通過流僅需辦理有調和無調中轉作業,而本地流則除此之外還要辦理面向裝卸站的作業車取送。據我國幾大樞紐所在鐵路局的貨流統計數據,本地流作業量占到貨流總量的比例均達到一半以上。

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

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

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

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

1 問題建模

1.1 問題描述

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

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

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

1.2 符號變量

為構建模型,研究引入以下參量與變量:

(1)集合

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

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

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

K:調機編號集合,記為K={k∣k=1,2,…,},為調機總數。

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

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

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

W:取送作業集合。用自然碼標記G中各車組的送車和取車作業,記為W={w∣w=1,2,…,},為取送作業總數。

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

(2)參數

hcl:調機牽引定數。

Tk:調機k的最長走行時間。

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

c1:單位時間調機使用成本。

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

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

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

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

(3)狀態變量

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

τu:第u批作業的取送總時間。

(4)決策變量

yuk:批次-調機匹配變量。yuk=1 表示第u批次由調機k服務,否則yuk=0。

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

(5)取送順序表述

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

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

1.3 模型構建

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

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

2 優化求解策略

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

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

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

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

Stage1初始取送作業順序構造

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

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

圖3 初始取送作業順序的構造Figure 3 Setting up initial placing-in and taking out wagons sequence

Stage2取送作業順序更新調整

對初始取送順序依據先送后取順序限制-裝卸能力限制再進行更新調整。

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

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

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

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

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

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

Stage3調機開行批次劃分

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

Step3.1基于調機牽引定數約束的批次劃分

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

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

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

Step3.3基于調機走行時長約束的批次更新

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

Stage4取送作業順序集合生成

Step4.1設定取送作業順序集合中的取送作業順序數為π。

Step4.2重復上述步驟,產生π個取送作業順序。

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

2.2 基于IBH-GA 的取送作業順序集合優化

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

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

Step1蝙蝠群初始參數設置

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

Step2最優蝙蝠個體搜索

根據適應度值函數計算出初始蝙蝠群中所有個體的適應度值,選擇最小的適應度值作為初始種群中最優蝙蝠個體記為x*,其適應度值為。

Step3蝙蝠群參數更新

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

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

Step4基于最優蝙蝠個體的局部搜索

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

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

Step5基于GA 的蝙蝠群再更新

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

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

計算新的蝙蝠群xbat1的適應度值,找出最優的解,記為xcross。

Step6輸出最佳蝙蝠個體

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

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

Step7迭代終止條件

返回Step3,重復迭代。若迭代次數達到nc_max,則停止迭代,輸出最優解及對應最佳取送作業順序,并記錄隨迭代次數的變化曲線。

2.3 基于批次時間窗-走行時長的調機自適應分配

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

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

Step1參數設定。

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

Step2取送批次時間窗計算

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

Step3基于批次時間窗的調機自適應分配

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

Step4基于走行時長的調機自適應分配更新

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

Step5輸出調機分配方案

依次完成所有批次的取送任務,得到調機分配方案,完成調機自適應分配。

3 實驗驗證及結果分析

3.1 實驗場景

(1)樹枝形鐵路專用線網絡

設計一個樹枝形鐵路專用線網絡,其中0 表示編組站,1～12 表示裝卸站,如圖6 所示。各裝卸站間的調機走行時間如表1 所示。

表1 各裝卸站之間的調機走行時間(單位:分鐘)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)樞紐內車流到達信息

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

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

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

12 個裝卸站由于貨物線長度限制,每個裝卸站都有最大裝卸能力,網絡內所有的裝卸站以及裝卸能力信息如表3所示。

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

3.2 IA-TS 主要參數的調試

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

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

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

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

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

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

3.3 算法比對方案設計

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

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

3.4 過程驗證

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

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

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

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

IA-TS 求解結果為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,調機走行時間為 1314 min,總營運成本為50091.2 元,調機分配方案[{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 求解結果為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,調機走行時間為1477 min,總營運成本為61496 元,調機分配方案[{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 求解結果為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,調機走行時間為1442 min,總營運成本為91182.4 元,調機分配方案[{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}]。

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

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

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

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

表7 三種算法的參數設置Table 7 Parameter setting for the three algorithms

本文設置迭代次數nc_max為300 次,將其作為IA-TS、GA-EAAP 和BA-EAAP 算法測試的停止條件。對每組參數{π,hcl}測試10 次,取平均目標函數值Fava、平均計算機運行時間和算法改進率RAC 作為比對參考指標。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%

測試結果如表8、表9 和表10 所示。

表8 三種算法在10 項取送作業問題中的性能測試比對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 項取送作業問題中的性能測試比對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 項取送作業問題中的性能測試比對Table 10 Performance for IA-TS、GA-EAAP and BA-EAAP applied to the problem with 64 placing-in and taking-out wagons

可得到如下結論:

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

在10 項取送作業問題中,IA-TS 算法的解的質量分別平均高于GA-EAAP 算法14%和BA-EAAP 算法19%;在32 項取送作業問題中,IA-TS 算法的解的質量分別平均高于GAEAAP 算法17%和BA-EAAP 算法51%;在64 項取送作業問題中,IA-TS 算法的解的質量分別平均高于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

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

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

3.6 求解質量與算法迭代次數的相關性

選用3.5 節的三組實驗,選取3.2 節中參數調試結果中的較優參數組合{V=0.95,r=0.3}。測試算法求解質量與迭代次數的相關性,如圖8 所示。由此可以看出,隨著迭代次數的增加,IA-TS 算法的優勢更為明顯。

圖8 求解質量與算法迭代次數的演進關系Figure 8 Comparison for solution quality with iteration number of algorithms under different size problems

4 結論

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

鐵路樞紐專用線網絡主要有放射形、樹枝形和混合形三種形式,本文研究了樹枝形鐵路專用線取送車優化問題,作業車均為單重作業車,沒有考慮作業車在樞紐內不同裝卸站間的調移問題。未來研究工作將聚焦更為復雜的混合形鐵路專用線取送車優化,并考慮帶調移的雙重作業車取送問題。