基于樹(shù)枝形鐵路專用線網(wǎng)絡(luò)的小運(yùn)轉(zhuǎn)貨物作業(yè)系統(tǒng)優(yōu)化

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

鐵路樞紐是龐大而復(fù)雜的系統(tǒng),是國(guó)家交通運(yùn)輸網(wǎng)的重要組成部分。在具有大量客貨流發(fā)生、消失和中轉(zhuǎn)作業(yè)的大城市、大工業(yè)區(qū)等都可能形成鐵路樞紐。鐵路樞紐是由若干專用車(chē)站和連接這些車(chē)站的聯(lián)絡(luò)線、迂回線等技術(shù)設(shè)備所構(gòu)成的綜合體。鐵路樞紐的中心任務(wù)是合理使用各種技術(shù)設(shè)備,順利完成車(chē)流交換和客貨運(yùn)輸工作。因此,正確組織鐵路樞紐工作對(duì)保證整個(gè)運(yùn)輸工作的均衡性、節(jié)奏性,以及加速貨車(chē)周轉(zhuǎn)、降低運(yùn)輸成本都具有重要的作用。

據(jù)我國(guó)幾大樞紐統(tǒng)計(jì),地方流的發(fā)送作業(yè)量均占該樞紐所在分局總發(fā)送作業(yè)量的50%左右,有的甚至更多。小運(yùn)轉(zhuǎn)貨物作業(yè)系統(tǒng)擔(dān)當(dāng)了地方流的輸送任務(wù),同時(shí)還在樞紐內(nèi)各專業(yè)車(chē)站間起著紐帶作用,可以說(shuō)小運(yùn)轉(zhuǎn)列車(chē)組織的好壞將直接影響到樞紐的暢通無(wú)阻。

關(guān)于貨物運(yùn)輸組織優(yōu)化調(diào)度是一項(xiàng)融合技術(shù)與管理的復(fù)雜系統(tǒng)工程,相關(guān)研究多集中在鐵路調(diào)車(chē)作業(yè)優(yōu)化、貨車(chē)取送作業(yè)優(yōu)化以及車(chē)隊(duì)綜合協(xié)調(diào)調(diào)度等方面。

(1)在鐵路調(diào)車(chē)作業(yè)優(yōu)化研究方面:郭瑞等[1]以所有車(chē)輛在站停留時(shí)間最短為目標(biāo),對(duì)單向單推單溜配流模型進(jìn)行理論分析,構(gòu)建以每列出發(fā)列車(chē)獲得最大車(chē)流數(shù)最多為子目標(biāo)的多階段配流問(wèn)題推理算法;王典等[2]考慮到達(dá)列車(chē)殘存、出發(fā)列車(chē)停運(yùn)和出發(fā)時(shí)刻調(diào)整等實(shí)際情況,以車(chē)輛在編組站總停留時(shí)間和車(chē)輛在前方站總額外中轉(zhuǎn)時(shí)間最小為目標(biāo),為重載列車(chē)組合問(wèn)題構(gòu)建改進(jìn)多目標(biāo)混合整數(shù)線性規(guī)劃模型;Li等[3]研究了鐵路編組站的貨物列車(chē)列檢、解體和集結(jié)作業(yè)優(yōu)化,構(gòu)建基于多調(diào)機(jī)和列檢組的一種排序模型,并利用商業(yè)軟件對(duì)模型進(jìn)行求解;Shi等[4]構(gòu)建了一個(gè)多層網(wǎng)絡(luò)流模型來(lái)描述鐵路編組站的列車(chē)到達(dá)、解體、集結(jié)、編組和出發(fā)作業(yè)過(guò)程,進(jìn)而構(gòu)建多級(jí)作業(yè)過(guò)程的混合整數(shù)規(guī)劃模型并給出啟發(fā)式求解方法;Haahr等[5]研究了調(diào)車(chē)場(chǎng)調(diào)車(chē)線分配問(wèn)題,并給出一個(gè)啟發(fā)式方法解決解體調(diào)車(chē)和編組調(diào)車(chē)問(wèn)題;Stephan等[6]研究了鐵路集裝箱堆場(chǎng)起重設(shè)備調(diào)度問(wèn)題。

(2)在貨車(chē)取送作業(yè)優(yōu)化研究方面:Jaehn等[7]研究了鐵路專用線取送調(diào)車(chē)優(yōu)化問(wèn)題,構(gòu)建取送調(diào)車(chē)混合整數(shù)規(guī)劃模型,并設(shè)計(jì)了具有一個(gè)多項(xiàng)式時(shí)間求解算法;張文晰等[8]針對(duì)路企直通列車(chē)組織過(guò)程中車(chē)流整列到發(fā)的取送問(wèn)題,研究了裝卸區(qū)呈樹(shù)枝形布置成組裝卸情形的取送方案;郭垂江[9]以鐵路車(chē)站取送車(chē)作業(yè)為研究對(duì)象,建立樹(shù)枝形貨物作業(yè)點(diǎn)取送車(chē)作業(yè)方案的多目標(biāo)優(yōu)化模型,并設(shè)計(jì)了模擬退火算法對(duì)模型進(jìn)行求解;牟峰等[10]以“先順序、后批次”為構(gòu)造取送車(chē)作業(yè)方案的總體思路,根據(jù)取送車(chē)作業(yè)問(wèn)題的客觀約束條件和實(shí)際生產(chǎn)經(jīng)驗(yàn),設(shè)計(jì)了取送車(chē)作業(yè)問(wèn)題一般模型解的模塊化構(gòu)造方法;趙娟[11]針對(duì)裝車(chē)地始發(fā)直達(dá)車(chē)流、時(shí)效要求較低的零散車(chē)流,以車(chē)流總的走行車(chē)公里最小為目標(biāo),以徑路唯一性、樹(shù)形徑路及線路能力為約束,建立線性0～1規(guī)劃模型;Wang等[12]研究了以碳排量最小化為目標(biāo)的合作綠色取送問(wèn)題,提出基于合作博弈理論的精確求解策略,完成合作方的薪酬和利潤(rùn)分配方案;Ghilas等[13]提出一種分支定界算法用來(lái)求解帶時(shí)間窗貨物取送問(wèn)題;Haddad等[14]研究了貨物分批取送問(wèn)題,并設(shè)計(jì)了一個(gè)局部搜索啟發(fā)式算法;Danloup等[15]研究了帶轉(zhuǎn)運(yùn)的貨物取送問(wèn)題,設(shè)計(jì)了大規(guī)模鄰域搜索算法和遺傳算法對(duì)問(wèn)題進(jìn)行求解,并對(duì)兩個(gè)求解算法進(jìn)行比對(duì)分析;Wang等[16]研究了基于合作聯(lián)盟企業(yè)共享車(chē)隊(duì)的取送車(chē)優(yōu)化問(wèn)題,并提出了一種集成改進(jìn)粒子群優(yōu)化算法和蟻群優(yōu)化算法的混合求解算法;Capelle等[17]研究了考慮貨物取送作業(yè)的選址-路徑問(wèn)題,構(gòu)建了問(wèn)題的整數(shù)規(guī)劃模型,提出了一種列生成求解算法;Zhu等[18]研究了帶隨機(jī)需求的貨物同步取送問(wèn)題,提出了新型貨物取送策略,該策略允許車(chē)輛合作完成貨物取送作業(yè),但如果合作失敗需要給予懲罰,并與不允許車(chē)輛合作取送策略進(jìn)行了比較,驗(yàn)證了所提出的貨物取送策略的優(yōu)越性。

(3)在車(chē)隊(duì)綜合協(xié)調(diào)調(diào)度研究方面:王保華等[19]研究考慮車(chē)輛周轉(zhuǎn)的鐵路動(dòng)態(tài)貨運(yùn)服務(wù)網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題,構(gòu)建了混合整數(shù)規(guī)劃模型,并給出一種“分支-定價(jià)-切割”算法;李冰等[20-22]集中不同類型的隨機(jī)動(dòng)態(tài)車(chē)隊(duì)調(diào)度問(wèn)題,設(shè)計(jì)了基于參數(shù)誘導(dǎo)的逐段分解求解算法;柳毅等[23]研究了一類帶時(shí)間窗可回程取貨的車(chē)輛路徑問(wèn)題,通過(guò)將人工魚(yú)群算法的仿生學(xué)原理與元胞自動(dòng)機(jī)的鄰域模型和狀態(tài)遷移規(guī)則相結(jié)合,設(shè)計(jì)了元胞魚(yú)群算法進(jìn)行求解。

本文圍繞服務(wù)鐵路樞紐地方貨物流,研究一類基于樹(shù)枝形鐵路專用線的小運(yùn)轉(zhuǎn)貨物作業(yè)系統(tǒng)協(xié)調(diào)優(yōu)化問(wèn)題(Local Freight Trains Transship System on Branch-Shaped Sidings,LFTTS-BSS)。從小運(yùn)轉(zhuǎn)列車(chē)調(diào)配與作業(yè)車(chē)取送協(xié)同優(yōu)化調(diào)度角度,以調(diào)機(jī)早到等待成本、調(diào)機(jī)晚到懲罰成本、鐵路樞紐專用線調(diào)機(jī)和貨車(chē)運(yùn)營(yíng)成本最小化為目標(biāo),構(gòu)建問(wèn)題模型。利用作業(yè)緊急度-編組定額-集結(jié)時(shí)間的送車(chē)-取車(chē)分步進(jìn)行策略對(duì)小運(yùn)轉(zhuǎn)列車(chē)初始方案進(jìn)行構(gòu)造,進(jìn)而設(shè)計(jì)伙伴-中心-變異取送車(chē)徑路更新的異步循環(huán)求解策略,最后進(jìn)行實(shí)驗(yàn)驗(yàn)證與數(shù)值分析。

1 問(wèn)題分析與描述

1.1 小運(yùn)轉(zhuǎn)作業(yè)系統(tǒng)分析

樹(shù)枝形專用線是鐵路樞紐內(nèi)常見(jiàn)的一種鐵路聯(lián)絡(luò)線布置形式,其特點(diǎn)是小運(yùn)轉(zhuǎn)列車(chē)連掛本地車(chē)組到達(dá)裝卸站并完成取送作業(yè)后可直接前往下一裝卸站而不必返回編組站。樹(shù)枝形專用線取送車(chē)作業(yè)中,各裝卸站貨車(chē)入線時(shí)刻不同,但取回編組站內(nèi)時(shí)刻相同。

樞紐內(nèi)編組站對(duì)到達(dá)列車(chē)解體和出發(fā)列車(chē)編組,完成“列流轉(zhuǎn)變?yōu)檐?chē)流”和“車(chē)流轉(zhuǎn)變?yōu)榱辛鳌?裝卸站對(duì)貨物進(jìn)行裝車(chē)和卸車(chē)工作,完成“貨流轉(zhuǎn)變?yōu)檐?chē)流”和“車(chē)流轉(zhuǎn)變?yōu)樨浟鳌薄８鶕?jù)裝卸站取出車(chē)流的出發(fā)形式,主要分為可隨就近列車(chē)掛走的車(chē)流和明確指定掛運(yùn)車(chē)次的車(chē)流兩種方式。在編組站,合理安排面向裝卸站開(kāi)行的小運(yùn)轉(zhuǎn)列車(chē)編組輛數(shù)和開(kāi)行批次,從而完成小運(yùn)轉(zhuǎn)列車(chē)調(diào)配,實(shí)現(xiàn)列流向車(chē)流的轉(zhuǎn)變;進(jìn)而依據(jù)編組站小運(yùn)轉(zhuǎn)列車(chē)編排方案,給出合理取送車(chē)策略,完成裝卸站間貨車(chē)取送徑路安排,實(shí)現(xiàn)車(chē)流向貨流的轉(zhuǎn)變。由此可見(jiàn),這兩個(gè)環(huán)節(jié)為一個(gè)整體,實(shí)現(xiàn)小運(yùn)轉(zhuǎn)列車(chē)調(diào)配-作業(yè)車(chē)取送一體化調(diào)度,就要做到前后作業(yè)計(jì)劃同步化。基于編組站-裝卸站的小運(yùn)轉(zhuǎn)列車(chē)調(diào)配-作業(yè)車(chē)取送一體化調(diào)度如圖1所示。

圖1 樞紐內(nèi)小運(yùn)轉(zhuǎn)列車(chē)調(diào)配-作業(yè)車(chē)取送一體化綜合協(xié)調(diào)

1.2 問(wèn)題描述及研究條件

本文圍繞服務(wù)鐵路樞紐地方貨物流,研究基于樹(shù)枝形鐵路專用線的小運(yùn)轉(zhuǎn)貨物作業(yè)系統(tǒng)協(xié)調(diào)優(yōu)化問(wèn)題。該問(wèn)題中,非直達(dá)列車(chē)陸續(xù)到達(dá)編組站,根據(jù)各車(chē)組到達(dá)編組站時(shí)分、車(chē)組目的裝卸站位置、車(chē)組作業(yè)時(shí)間要求以及調(diào)機(jī)牽引定數(shù)等限制,以調(diào)機(jī)早到等待成本、調(diào)機(jī)晚到懲罰成本、鐵路樞紐專用線調(diào)機(jī)和貨車(chē)運(yùn)營(yíng)成本最小化為目標(biāo),構(gòu)建問(wèn)題模型。利用作業(yè)編號(hào)構(gòu)造問(wèn)題的解,將階段時(shí)間段內(nèi)的全部取送作業(yè)視為整體考慮,從而實(shí)現(xiàn)小運(yùn)轉(zhuǎn)列車(chē)調(diào)配-作業(yè)車(chē)取送一體化綜合協(xié)調(diào)的目標(biāo)。

LFTTS-BSS問(wèn)題研究中考慮如下研究條件:

(1)鐵路專用線的拓?fù)浣Y(jié)構(gòu)已知。

(2)單調(diào)機(jī)作業(yè),調(diào)機(jī)最大牽引定數(shù)和最大走行時(shí)間已知。

(3)樹(shù)枝形專用線網(wǎng)絡(luò)中編組站、裝卸站間的機(jī)車(chē)走行時(shí)間已知。

(4)非直達(dá)貨物列車(chē)到達(dá)編組站的時(shí)刻已知。

(5)裝卸站待送貨車(chē)、待取貨車(chē)已知。

(6)特定作業(yè)時(shí)間窗要求,即特定作業(yè)有固定時(shí)間窗限制,調(diào)機(jī)在規(guī)定時(shí)間外未將特定作業(yè)送達(dá)裝卸站,會(huì)因?yàn)樘囟ㄗ鳂I(yè)未能及時(shí)交貨而產(chǎn)生額外成本。

(7)裝卸站同步即時(shí)取送,即調(diào)機(jī)將貨車(chē)送達(dá)目的裝卸站后,若有裝卸完畢的待取貨車(chē),則立即取回;若無(wú)裝卸完畢的待取貨車(chē),則直接前往下一目的裝卸站。

(8)隨同一列車(chē)到達(dá)編組站,且目的裝卸站一致的貨車(chē)編為同一車(chē)組。車(chē)組取、送兩種作業(yè)獨(dú)立核算。

(9)調(diào)機(jī)在編組站和裝卸站進(jìn)行人員整備、貨車(chē)甩掛時(shí)間不計(jì)。

2 模型構(gòu)建

2.1 符號(hào)約定

為構(gòu)建模型,引入如下參數(shù)與變量:

輸入?yún)⒘?/p>

N——鐵路樞紐內(nèi)專用車(chē)站集合,記為N={i|i=0,1,…,n},其中:i=0 表示編組站,i≠0表示裝卸站;n為鐵路樞紐內(nèi)的裝卸站總數(shù)

L——陸續(xù)到達(dá)鐵路樞紐的貨物列車(chē)序號(hào)集合,記為L(zhǎng)={l|l=1,2,…,A},其中,A為到達(dá)的貨物列車(chē)總數(shù)

R——從裝卸站取回車(chē)組可掛運(yùn)列車(chē)序號(hào)集合,即為R={r|r=1,2,…,},其中,為可掛運(yùn)列車(chē)總數(shù)

l(i)——隨貨物列車(chē)L到達(dá)鐵路樞紐且目的裝卸站為i的本地作業(yè)車(chē)組,l∈L,i∈N

Ml(i)——車(chē)組l(i)的貨車(chē)編組數(shù),l∈L,i∈N

Ol(i)——本地作業(yè)車(chē)組l(i)在目的裝卸站i處完成裝卸作業(yè)所需時(shí)間,l∈L,i∈N

Z——作業(yè)性質(zhì)集合,記為Z={z|z=1,2},其中:z=1表示送車(chē)作業(yè);z=2表示取車(chē)作業(yè)

U——取送作業(yè)編號(hào)集合,記為U={u=l(i)z|i∈N,l∈L,z∈Z},其中:l(i)1表示將車(chē)組l(i)送往裝卸站i的送車(chē)作業(yè);l(i)2表示將車(chē)組l(i)由裝卸站i取回編組站的取車(chē)作業(yè)

[ETu,LTu]——作業(yè)編號(hào)u允許的作業(yè)時(shí)間窗。ETu和LTu分別為作業(yè)編號(hào)u到達(dá)裝卸站的最早作業(yè)時(shí)刻和最晚作業(yè)時(shí)刻,u∈U

T(r)——第r車(chē)次列車(chē)出發(fā)編組最晚時(shí)刻,r∈R

tij——從裝卸站i到裝卸站j的走行時(shí)間,其中i或j=0表示編組站到裝卸站的走行時(shí)間,i,j∈N

e1——時(shí)間窗外單位分鐘調(diào)機(jī)早到等待成本e2——時(shí)間窗外單位分鐘調(diào)機(jī)晚到懲罰成本

cl——調(diào)機(jī)單位分鐘運(yùn)營(yíng)成本

cw——貨車(chē)單位分鐘運(yùn)營(yíng)成本

D——調(diào)機(jī)最大牽引定數(shù)

P——調(diào)機(jī)的最大行駛時(shí)間

狀態(tài)變量

K——調(diào)機(jī)取送批次集合,記為K={k|k=1,2,…,},其中,為小運(yùn)轉(zhuǎn)列車(chē)取送批次總數(shù)

Tu——作業(yè)編號(hào)u在目的裝卸站的取送時(shí)刻,u∈U

sik——第k批次作業(yè)中,調(diào)機(jī)訪問(wèn)裝卸站i時(shí)的累計(jì)行駛時(shí)間,k∈K,i∈N

yijk——第k批次作業(yè)中,調(diào)機(jī)途徑裝卸站(i,j)時(shí)所牽引的貨車(chē)總編組數(shù),k∈K,i,j∈N

決策變量

xijk——第k批次作業(yè)中,調(diào)機(jī)是否由裝卸站i駛向裝卸站j,如果調(diào)機(jī)途徑裝卸站(i,j),則xijk=1;否則,xijk=0,k∈K,i,j∈N

2.2 模型構(gòu)建

考慮各車(chē)組到達(dá)編組站時(shí)分、車(chē)組目的裝卸站位置、車(chē)組作業(yè)時(shí)間要求以及調(diào)機(jī)牽引定數(shù)等限制,以調(diào)機(jī)早到等待成本、調(diào)機(jī)晚到懲罰成本、鐵路樞紐專用線調(diào)機(jī)和貨車(chē)運(yùn)營(yíng)成本最小化為目標(biāo),構(gòu)建如下問(wèn)題模型:

式(2)～(11)為約束條件。其中:式(2)、(3)表示同一批次取送車(chē)作業(yè)中每個(gè)裝卸站最多被訪問(wèn)1次,從而減少調(diào)機(jī)不必要走行時(shí)間;式(4)～(7)保證了調(diào)機(jī)在每個(gè)取送批次中的行駛時(shí)間不超過(guò)調(diào)機(jī)最大走行時(shí)間,即單批次取送過(guò)程中調(diào)機(jī)從編組站出發(fā)至回到編組站的總時(shí)間不大于調(diào)機(jī)最大走行時(shí)間;式(8)明確指定掛運(yùn)r車(chē)次列車(chē)的車(chē)組l(i)取回編組站時(shí)刻小于第r車(chē)次出發(fā)列車(chē)編組最晚時(shí)刻;式(9)表示調(diào)機(jī)最大牽引定數(shù)限制,即調(diào)機(jī)每次牽引的最大貨車(chē)數(shù)要小于調(diào)機(jī)最大牽引定數(shù);式(10)、(11)表示各變量的取值約束。

3 求解策略

該模型為混合整數(shù)規(guī)劃模型(Mixed Integer Programming Model,MIP),直接求解較為困難,故設(shè)計(jì)H H-GAP&AIP(Hybrid Heuristic Combining Greedy Assignment Procedure and Asynchronous Iteration Procedure)求解策略。該策略首先給出基于作業(yè)緊急度-編組定額-集結(jié)時(shí)間的小運(yùn)轉(zhuǎn)列車(chē)初始取送方案貪婪生成過(guò)程,進(jìn)而提出三階段異步循環(huán)啟發(fā)式,利用伙伴-中心-變異取送車(chē)徑路三階段更新過(guò)程,完成裝卸站間貨物作業(yè)車(chē)取送徑路方案優(yōu)化。最后,利用所設(shè)計(jì)的終止規(guī)則完成循環(huán)迭代,得到作業(yè)車(chē)取送徑路方案。

3.1 基于GAP的小運(yùn)轉(zhuǎn)列車(chē)初始方案生成

首先提出優(yōu)先安排緊急和特殊車(chē)組,進(jìn)而利用大車(chē)組優(yōu)先原則安排一般車(chē)組,再基于編組定額與集結(jié)時(shí)間判別參數(shù)進(jìn)行小運(yùn)轉(zhuǎn)列車(chē)批次調(diào)整,按照送車(chē)-取車(chē)分步進(jìn)行,形成基于作業(yè)緊急度-編組定額-集結(jié)時(shí)間的小運(yùn)轉(zhuǎn)列車(chē)初始取送策略。基于貪婪指派的小運(yùn)轉(zhuǎn)列車(chē)初始取送方案生成過(guò)程(Greedy Assignment Procedure,GAP)如圖2所示。

圖2 基于GAP的小運(yùn)轉(zhuǎn)列車(chē)初始方案生成流程圖

具體步驟:

階段1初始本地車(chē)組作業(yè)編號(hào)的構(gòu)造。

步驟1.1生成初始本地車(chē)組序列。統(tǒng)計(jì)到達(dá)編組站的列車(chē)數(shù),根據(jù)列車(chē)到解時(shí)間先后順序,將各列車(chē)中的本地車(chē)組編號(hào),生成初始本地車(chē)組序列,記為={1(i1),…,A(im)},其中,m為本地車(chē)組數(shù),im∈N。

步驟1.2生成初始本地車(chē)組作業(yè)編號(hào)。根據(jù)各本地車(chē)組在裝卸站完成的作業(yè)類型,得到本地車(chē)組作業(yè)編號(hào),記為={1(i1)1,1(i1)2,…,A(im)1,A(im)2},其中:A(im)1為本地車(chē)組A(im)的送車(chē)作業(yè)編號(hào);A(im)2為本地車(chē)組A(im)的取車(chē)作業(yè)編號(hào)。

階段2小運(yùn)轉(zhuǎn)列車(chē)開(kāi)行批次構(gòu)造。

步驟2.1設(shè)置小運(yùn)轉(zhuǎn)列車(chē)開(kāi)行批次。設(shè)O為已編入特定批次小運(yùn)轉(zhuǎn)列車(chē)的作業(yè)編號(hào),Ok為已編入第k批次小運(yùn)轉(zhuǎn)列車(chē)的作業(yè)編號(hào)。

步驟2.2參數(shù)初始化設(shè)置。初始已編入小運(yùn)轉(zhuǎn)列車(chē)的作業(yè)編號(hào)O為空集,初始小運(yùn)轉(zhuǎn)列車(chē)的批次編號(hào)k=1。

階段3送車(chē)作業(yè)編號(hào)的小運(yùn)轉(zhuǎn)列車(chē)批次選取。

步驟3.1緊急和特殊送車(chē)作業(yè)安排。將緊急和特殊送車(chē)要求作業(yè)編號(hào)編入當(dāng)前批次小運(yùn)轉(zhuǎn)列車(chē)Ok。

步驟3.2一般送車(chē)作業(yè)安排。對(duì)于沒(méi)有緊急和特殊要求的作業(yè),按大車(chē)組優(yōu)先原則,依次編入小運(yùn)轉(zhuǎn)列車(chē)Ok,直至滿足調(diào)機(jī)約束限制。

步驟3.3小運(yùn)轉(zhuǎn)列車(chē)是否繼續(xù)集結(jié)的編組數(shù)判別參數(shù)Φ。將未編入任何批次小運(yùn)轉(zhuǎn)列車(chē)的送車(chē)作業(yè)編號(hào)依次編入集合Ok,若未滿足調(diào)機(jī)約束限制,引入編組數(shù)判別參數(shù)Φ,若D-Ok＜Φ,則生成第k批次小運(yùn)轉(zhuǎn)列車(chē)送車(chē)作業(yè);否則,轉(zhuǎn)步驟3.4。

步驟3.4小運(yùn)轉(zhuǎn)列車(chē)是否繼續(xù)集結(jié)的時(shí)間判別參數(shù)I。若距下次列車(chē)到解時(shí)間大于時(shí)間判別參數(shù)I,則生成第k批次小運(yùn)轉(zhuǎn)列車(chē)送車(chē)作業(yè);否則,等待下次列車(chē),重復(fù)步驟3.1～3.4至生成第k批次小運(yùn)轉(zhuǎn)列車(chē)送車(chē)作業(yè)。

階段4取車(chē)作業(yè)編號(hào)的小運(yùn)轉(zhuǎn)列車(chē)批次選取。

步驟4.1緊急和特殊取車(chē)作業(yè)安排。將緊急和特殊取車(chē)要求作業(yè)編號(hào)編入當(dāng)前批次小運(yùn)轉(zhuǎn)列車(chē)Ok。

步驟4.2一般取車(chē)作業(yè)安排。對(duì)于沒(méi)有緊急和特殊要求的作業(yè),按大車(chē)組優(yōu)先原則,依次編入小運(yùn)轉(zhuǎn)列車(chē)Ok,直至滿足調(diào)機(jī)約束限制。

階段5小運(yùn)轉(zhuǎn)列車(chē)批次生成。

步驟5.1小運(yùn)轉(zhuǎn)列車(chē)單批次生成。第k批次送車(chē)作業(yè)、第k批次取車(chē)作業(yè)即為第k批次取送車(chē)作業(yè)。

步驟5.2生成所有取送車(chē)批次。令k=k+1,重復(fù)階段3～5,生成所有取送車(chē)批次,即生成單個(gè)取送車(chē)徑路。

階段6初始取送車(chē)徑路集合H生成。

步驟6.1重復(fù)上述步驟,產(chǎn)生w個(gè)初始取送車(chē)徑路。

步驟6.2對(duì)重復(fù)取送車(chē)徑路進(jìn)行基于作業(yè)編號(hào)的調(diào)整,從而生成初始取送車(chē)徑路集合H。令H=[h1,h2,…,hw]T,其中:hw為一個(gè)取送車(chē)徑路的解;w為取送車(chē)徑路集合H中所涵蓋的初始取送車(chē)徑路集合數(shù)量。

3.2 基于AIP的取送車(chē)集合更新過(guò)程

基于迭代尋優(yōu)思路,設(shè)計(jì)異步循環(huán)迭代過(guò)程(Asynchronous Iteration Procedure,AIP)。該方法首先利用GAP策略生成的初始取送車(chē)方案進(jìn)入循環(huán)迭代過(guò)程。在每次迭代中,執(zhí)行基于伙伴取送車(chē)徑路的解更新、基于中心取送車(chē)徑路的解更新和基于變異取送車(chē)徑路的解更新,為避免算法陷入局部最優(yōu)及擴(kuò)大解的搜索空間,給出基于檢測(cè)-剔除-變換的取送車(chē)徑路調(diào)整策略,從而完成迭代尋優(yōu)。最后,利用所設(shè)計(jì)的終止規(guī)則完成循環(huán)迭代,得到作業(yè)車(chē)取送徑路方案。AIP過(guò)程如圖3所示。

圖3 AIP算法流程

具體步驟:

階段1基于作業(yè)編號(hào)的取送車(chē)方案表述。

對(duì)于GAP 策略生成的初始取送車(chē)徑路集合H=[h1,h2,…,hw]T,為便于迭代更新,利用取送車(chē)作業(yè)編號(hào)構(gòu)造問(wèn)題的解,令每一個(gè)取送車(chē)徑路為hw,則

其中:ψ(h(x))為所有取送車(chē)作業(yè)集合的排列組合,即為一個(gè)取送車(chē)徑路的解;S為取送作業(yè)編號(hào)集合數(shù)。每個(gè)取送車(chē)徑路hw在尋優(yōu)過(guò)程中生成的取送車(chē)徑路需要進(jìn)行批次劃分,從而計(jì)算目標(biāo)函數(shù)值。當(dāng)調(diào)機(jī)服務(wù)下一個(gè)作業(yè)編號(hào)h(x)時(shí),根據(jù)調(diào)機(jī)最大牽引定數(shù)及最大走行時(shí)間等約束限制,從而完成批次劃分。

該表述方式將一個(gè)時(shí)段內(nèi)的全部取送作業(yè)視為整體考慮,進(jìn)而根據(jù)調(diào)機(jī)牽引定數(shù)和最大行駛時(shí)間等合理安排面向裝卸站的小運(yùn)轉(zhuǎn)列車(chē)開(kāi)行批次和裝卸站間貨車(chē)取送徑路順序,從而實(shí)現(xiàn)小運(yùn)轉(zhuǎn)列車(chē)調(diào)配-作業(yè)車(chē)取送一體化綜合協(xié)調(diào)的目標(biāo)。

階段2基于伙伴取送車(chē)徑路集合的表述。

對(duì)于取送車(chē)徑路集合H中取送車(chē)徑路hi和hj,統(tǒng)計(jì)hi和hj之間對(duì)應(yīng)位置相同作業(yè)編號(hào)的數(shù)量v(hi,hj),設(shè)定視野值V,對(duì)于取送車(chē)徑路hi,若v(hi,hj)＜V,則稱取送車(chē)徑路hj為取送車(chē)徑路hi的伙伴取送車(chē)徑路,記做,如圖4所示。

圖4 伙伴取送車(chē)徑路的生成過(guò)程

從取送車(chē)徑路集合H中尋找取送車(chē)徑路hi的所有伙伴取送車(chē)徑路,從而形成伙伴取送車(chē)徑路集合Hi,集合H中的取送車(chē)徑路數(shù)為n(H),集合Hi中的伙伴取送車(chē)徑路數(shù)為n(Hi)。

階段3基于單次循環(huán)的三階段異步更新過(guò)程。

步驟3.1基于伙伴取送車(chē)徑路的解更新過(guò)程。

(1)最小伙伴取送車(chē)徑路確定。從取送車(chē)徑路集合H中選擇一個(gè)取送車(chē)徑路h?,生成伙伴取送車(chē)徑路集合H?,計(jì)算集合H?中所有伙伴取送車(chē)徑路的目標(biāo)函數(shù)值,并尋找目標(biāo)函數(shù)值最小的伙伴取送車(chē)徑路,即。

(2)基于最小伙伴取送車(chē)徑路的解更新過(guò)程。給出最大擁擠度負(fù)荷λ,利用取送車(chē)徑路的伙伴取送車(chē)徑路集合數(shù)除以取送車(chē)徑路集合數(shù)n(H),計(jì)算最小伙伴取送車(chē)徑路的擁擠度因子,記為。如果＜λ,且＜f(h?),則令替換h?,即;否則,保持當(dāng)前取送車(chē)徑路不變。

步驟3.2基于中心取送車(chē)徑路的解更新過(guò)程。

(1)中心取送車(chē)徑路確定。從取送車(chē)徑路集合H中選擇一個(gè)取送車(chē)徑路h?,生成伙伴取送車(chē)徑路集合H?,對(duì)H?中的每個(gè)伙伴取送車(chē)徑路進(jìn)行比較。將H?中對(duì)應(yīng)位置的作業(yè)編號(hào)出現(xiàn)次數(shù)最多的值作為中心取送車(chē)徑路該位置的值,如果該位置的值在同一批次內(nèi)已經(jīng)出現(xiàn)過(guò),則取對(duì)應(yīng)作業(yè)編號(hào)出現(xiàn)次多的值作為該位置的值,如圖5所示。

圖5 中心取送車(chē)徑路的生成過(guò)程

(2)基于中心取送車(chē)徑路的解更新過(guò)程。給出最大擁擠度負(fù)荷λ,計(jì)算當(dāng)前取送車(chē)徑路h?目標(biāo)函數(shù)值f(h?)和中心取送車(chē)徑路目標(biāo)函數(shù)值。利用中心取送車(chē)徑路的伙伴取送車(chē)徑路集合數(shù)除以取送車(chē)徑路集合數(shù)n(H),計(jì)算的擁擠度因子,記為。如果＜λ,且,則令替換h?,即;否則,保持當(dāng)前取送車(chē)徑路不變。

步驟3.3基于變異取送車(chē)徑路的解更新過(guò)程。

(1)變異取送車(chē)徑路的確定。從取送車(chē)徑路集合H中選擇一個(gè)取送車(chē)徑路h?,生成隨機(jī)數(shù)rand,其中1＜rand≤V,隨機(jī)選擇rand個(gè)作業(yè)編號(hào),將rand個(gè)作業(yè)編號(hào)進(jìn)行基于次序的替換,從而生成一個(gè)新的變異取送車(chē)徑路,如圖6所示。

(2)基于變異取送車(chē)徑路的解更新過(guò)程。計(jì)算當(dāng)前取送車(chē)徑路h?目標(biāo)函數(shù)值f(h?)和變異取送車(chē)徑路目標(biāo)函數(shù)值,并對(duì)其進(jìn)行比較:

情況1若變異取送車(chē)徑路目標(biāo)函數(shù)值小于當(dāng)前取送車(chē)徑路目標(biāo)函數(shù)值f(h?),即＜f(h?),則令替換,即;否則,轉(zhuǎn)下步。

圖6 變異取送車(chē)徑路的生成過(guò)程

情況2若變異取送車(chē)徑路目標(biāo)函數(shù)值大于當(dāng)前取送車(chē)徑路h?目標(biāo)函數(shù)值f(h?),則重新生成變異取送車(chē)徑路,并比較其目標(biāo)函數(shù)值。若嘗試次數(shù)超過(guò)最大嘗試次數(shù)Rmax仍未找到滿足要求的變異取送車(chē)徑路,則保持當(dāng)前取送車(chē)徑路不變。

階段4基于三階段異步更新的取送車(chē)徑路選取。

計(jì)算第q次迭代得到的取送車(chē)徑路集合Hq=中各條取送車(chē)徑路的目標(biāo)函數(shù)值,并記錄q次迭代最優(yōu)取送車(chē)徑路,即

從而得到q+1次迭代取送車(chē)徑路可行集合Hq+1=,同時(shí)記錄q+1次更新后的最優(yōu)取送車(chē)徑路,即

依次執(zhí)行上述過(guò)程,直至迭代次數(shù)達(dá)到Q為止。從最優(yōu)取送車(chē)徑路序列中選取目標(biāo)函數(shù)值最小的取送車(chē)徑路,即為取送車(chē)作業(yè)的最優(yōu)取送車(chē)徑路。

階段5基于檢測(cè)-剔除-變換的取送車(chē)徑路調(diào)整。

步驟5.1最優(yōu)取送車(chē)徑路檢測(cè)調(diào)整。

為防止陷入局部最優(yōu),設(shè)置檢測(cè)因子α,每進(jìn)行u次迭代檢測(cè)當(dāng)前最優(yōu)取送車(chē)徑路的目標(biāo)函數(shù)值與u代以前的最優(yōu)目標(biāo)函數(shù)值,并比較大小,若,表明算法陷入局部最優(yōu)。為跳出循環(huán),重新生成取送車(chē)徑路集合。若,則當(dāng)前取送車(chē)徑路集合保持不變。

步驟5.2較差取送車(chē)徑路的剔除調(diào)整。

為加快算法迭代收斂,設(shè)置加速次數(shù)m,對(duì)于每進(jìn)行Q/m次迭代的取送車(chē)徑路集合,給出剔除因子β,將wβ個(gè)目標(biāo)函數(shù)值較大的取送車(chē)徑路剔除,即剔除較差的取送車(chē)徑路,從而減少取送車(chē)徑路集合數(shù),以提高算法運(yùn)行能力。

步驟5.3重復(fù)取送車(chē)徑路變換調(diào)整。

為擴(kuò)大解的搜索空間,對(duì)于每次迭代的取送車(chē)徑路集合,篩選找出相同的取送車(chē)徑路,設(shè)計(jì)3點(diǎn)換位原則,將重復(fù)取送車(chē)徑路更新為相似取送車(chē)徑路,具體過(guò)程如圖7所示。

圖7 重復(fù)取送車(chē)徑路變換調(diào)整

3.3 基于HH-GAP&AIP求解策略的復(fù)雜性分析

由上述算法描述可以看出,HH-GAP&AIP求解策略本質(zhì)上是利用最小伙伴取送車(chē)徑路、中心取送車(chē)徑路以及變異取送車(chē)徑路進(jìn)行迭代更新,探索當(dāng)前階段的最優(yōu)解,從而利用局部最優(yōu)解找到全局最優(yōu)解,H H-GAP&AIP在解的編碼上有了一定改進(jìn),將階段時(shí)間內(nèi)取送車(chē)作業(yè)編號(hào)視為一個(gè)整體,增加了解的全局信息,從而保證了解更新的多樣性。同時(shí),還可以看出,參數(shù)視野值V、擁擠度負(fù)荷λ以及嘗試次數(shù)Rmax作為主要循環(huán)體參數(shù),對(duì)算法收斂速度和精度有著重要影響,特別是參數(shù)視野值V的設(shè)置,決定了伙伴取送車(chē)徑路集合的數(shù)量,從而在很大程度上決定了算法的復(fù)雜性。HH-GAP&AIP求解策略的計(jì)算復(fù)雜性除了受主循環(huán)體參數(shù)的影響之外,取送車(chē)徑路集合的數(shù)量也決定了算法的復(fù)雜性和收斂速度,取送車(chē)徑路集合數(shù)較多,在一定程度上增加了算法的計(jì)算時(shí)間,同時(shí)也增加了伙伴取送車(chē)集合的儲(chǔ)存空間,剔除較差取送車(chē)徑路能夠降低算法復(fù)雜性,提高算法運(yùn)行速度。檢測(cè)和變換策略在一定程度上增加了解變換的多樣性,從而能夠更好地找到全局最優(yōu)解。

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

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

設(shè)計(jì)由12個(gè)裝卸站組成的樹(shù)枝形小運(yùn)轉(zhuǎn)作業(yè)網(wǎng)絡(luò)(見(jiàn)圖8)。樹(shù)枝形專用線網(wǎng)絡(luò)中各裝卸站及編組站間的調(diào)機(jī)走行時(shí)間數(shù)據(jù)如表1 所示,其中0表示編組站。本地作業(yè)車(chē)取送信息數(shù)據(jù)如表2所示,出發(fā)列車(chē)最晚編組時(shí)分如表3所示。

圖8 樞紐地方貨物流小運(yùn)轉(zhuǎn)作業(yè)網(wǎng)絡(luò)示意圖

表1 裝卸站間調(diào)機(jī)走行時(shí)間表 min

4.2 HH-GAP&AIP主要循環(huán)體參數(shù)調(diào)試

算法利用Matlab R2014a 對(duì)H H-GAP&AIP求解策略進(jìn)行編程,在Intel(R)Core(TM)i5-3337U CPU(1.80 GHz)微機(jī)上運(yùn)行。鑒于鐵路實(shí)際作業(yè)環(huán)境和以往參考文獻(xiàn),將已知參數(shù)進(jìn)行如下設(shè)置:調(diào)機(jī)單位分鐘運(yùn)營(yíng)成本cl=16,貨車(chē)單位分鐘運(yùn)營(yíng)成本cw=16,單位分鐘等待成本e1=2,單位分鐘懲罰成本e2=2。調(diào)機(jī)最大行駛時(shí)間為300 min,調(diào)機(jī)牽引定數(shù)D=40,編組數(shù)判別參數(shù)Φ=8輛,時(shí)間判別參數(shù)I=30 min,最大迭代次數(shù)Q=100。

對(duì)于取送車(chē)徑路集合的取送車(chē)徑路調(diào)整階段所涉及的參數(shù),做出如下處理:取u=Q/10,檢測(cè)因子α=10,表明目標(biāo)函數(shù)在更新,算法就繼續(xù)迭代尋優(yōu);加速次數(shù)m=5,剔除因子β=0.2,從而降低算法計(jì)算復(fù)雜度,提高算法運(yùn)行速度。

考慮到參數(shù)視野值V、擁擠度負(fù)荷λ以及嘗試次數(shù)Rmax作為HH-GAP&AIP 求解策略的主要循環(huán)體參數(shù),故對(duì)參數(shù)不同取值進(jìn)行多次實(shí)驗(yàn),分析參數(shù)對(duì)解質(zhì)量的影響。采用固定其他參數(shù),觀察某一參數(shù)對(duì)解分布情況的影響。設(shè)置3組實(shí)驗(yàn),即視野值參數(shù)測(cè)試實(shí)驗(yàn)、最大嘗試次數(shù)參數(shù)測(cè)試實(shí)驗(yàn)和擁擠度負(fù)荷參數(shù)測(cè)試實(shí)驗(yàn),對(duì)于3組實(shí)驗(yàn)各測(cè)試參數(shù)取值均運(yùn)行10次取其平均值,從而更準(zhǔn)確地進(jìn)行測(cè)試對(duì)比。

表2 樞紐內(nèi)本地作業(yè)車(chē)取送信息表

表3 出發(fā)列車(chē)最晚編組時(shí)分

(1)視野值參數(shù)測(cè)試實(shí)驗(yàn)。在初始取送車(chē)徑路集合數(shù)w=30,w=10下,固定擁擠度負(fù)荷λ=0.6,最大嘗試次數(shù)Rmax=3,觀察視野值V對(duì)調(diào)運(yùn)成本和計(jì)算機(jī)運(yùn)行時(shí)間的變化關(guān)系,具體結(jié)果如圖9所示。

圖9 視野值參數(shù)調(diào)試

由圖9可見(jiàn),當(dāng)初始取送車(chē)徑路集合數(shù)分別為w=30和w=10時(shí),視野值V對(duì)于調(diào)運(yùn)成本的影響規(guī)律都不明顯,但總體而言,兩者在較小視野值求得的解優(yōu)于較大視野值求得的解;隨著視野值V不斷增加,CPU 運(yùn)行時(shí)間也越來(lái)越長(zhǎng)。當(dāng)初始取送車(chē)徑路集合數(shù)為30時(shí),求得解的質(zhì)量較好;當(dāng)初始取送車(chē)徑路集合數(shù)為10時(shí),求得解的質(zhì)量較差。當(dāng)初始取送車(chē)徑路集合數(shù)增加為30時(shí),CPU 運(yùn)行時(shí)間明顯提高,說(shuō)明提高初始取送車(chē)徑路集合數(shù)雖提高了解的質(zhì)量,但也消耗了一定的CPU 運(yùn)行時(shí)間。

(2)最大嘗試次數(shù)參數(shù)測(cè)試實(shí)驗(yàn)。在初始取送車(chē)徑路集合數(shù)w=30,w=10下,固定視野值V=5,擁擠度負(fù)荷λ=0.6,觀察最大嘗試次數(shù)Rmax對(duì)調(diào)運(yùn)成本和計(jì)算機(jī)運(yùn)行時(shí)間的變化關(guān)系,具體結(jié)果如圖10所示。

圖10 最大嘗試次數(shù)參數(shù)調(diào)試

由圖10可見(jiàn),當(dāng)初始取送車(chē)徑路集合數(shù)分別為w=30和w=10時(shí),最大嘗試次數(shù)Rmax對(duì)于調(diào)運(yùn)成本和CPU 運(yùn)行時(shí)間的影響呈現(xiàn)出一定的規(guī)律性,即隨著Rmax的不斷增加,求得解的質(zhì)量越來(lái)越好,但CPU 運(yùn)行時(shí)間也隨之增加,說(shuō)明增加最大嘗試次數(shù)Rmax雖能提高解的質(zhì)量,但也消耗了一定的CPU 運(yùn)行時(shí)間。同樣,當(dāng)初始取送車(chē)徑路集合數(shù)為30時(shí),求得解的質(zhì)量較好;當(dāng)初始取送車(chē)徑路集合數(shù)為10時(shí),求得解的質(zhì)量較差。當(dāng)初始取送車(chē)徑路集合數(shù)增加為30時(shí),CPU 運(yùn)行時(shí)間明顯提高。

(3)擁擠度負(fù)荷參數(shù)測(cè)試實(shí)驗(yàn)。在初始取送車(chē)徑路集合數(shù)w=30,w=10下,固定視野值V=5,最大嘗試次數(shù)Rmax=3,觀察擁擠度負(fù)荷λ對(duì)調(diào)運(yùn)成本和計(jì)算機(jī)運(yùn)行時(shí)間的變化關(guān)系,具體結(jié)果如圖11所示。

由圖11可見(jiàn),當(dāng)初始取送車(chē)徑路集合數(shù)分別為w=30和w=10時(shí),擁擠度負(fù)荷λ對(duì)于調(diào)運(yùn)成本和CPU 運(yùn)行時(shí)間的影響沒(méi)有呈現(xiàn)出一定的規(guī)律性,說(shuō)明在此實(shí)驗(yàn)條件下,擁擠度負(fù)荷λ對(duì)解的影響具有隨機(jī)性。當(dāng)初始取送車(chē)徑路集合數(shù)為30時(shí),求得解的質(zhì)量較好;當(dāng)初始取送車(chē)徑路集合數(shù)為10時(shí),求得解的質(zhì)量較差。當(dāng)初始取送車(chē)徑路集合數(shù)增加為30時(shí),CPU 運(yùn)行時(shí)間明顯提高。

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

圖11 擁擠度負(fù)荷參數(shù)調(diào)試

根據(jù)循環(huán)體參數(shù)調(diào)試,在合理運(yùn)行時(shí)間范圍內(nèi)為實(shí)現(xiàn)目標(biāo)函數(shù)值最優(yōu)化,對(duì)H H-GAP&AIP算法參數(shù)設(shè)置如下:擁擠度負(fù)荷λ=0.8,取送車(chē)徑路視野V=4,最大嘗試次數(shù)Rmax=10,HH-GAP&AIP算法初始取送車(chē)徑路集合數(shù)w=30,迭代次數(shù)Q=100代。在解決優(yōu)化排序問(wèn)題上,遺傳算法和模擬退火算法能夠很好地解決此類問(wèn)題,參考文獻(xiàn)[21,24],引入?yún)?shù)自適應(yīng)遺傳算法(IGA)和模擬退火算法(SA)作為對(duì)比,IGA 算法初始種群規(guī)模與H HGAP&AIP求解算法保持一致,交叉概率為[0.5,0.99],變異概率為[0.1,0.5]。SA 算法所涉及的參數(shù)多次嘗試取較優(yōu)結(jié)果設(shè)置如下:初始溫度控制參數(shù)為1 000,溫度停止控制參數(shù)為0.01,溫度衰減因子為0.99,初始馬爾科夫鏈長(zhǎng)度為500。為公平比較算法,設(shè)置IGA 和SA 算法的停止時(shí)間與H HGAP&AIP求解算法迭代到100 代的運(yùn)行時(shí)間相同,算法運(yùn)行結(jié)果如表4所示。

由上述算例仿真對(duì)比結(jié)果可以看出,H HGAP&AIP求解算法調(diào)機(jī)被劃分為8個(gè)批次,最優(yōu)路徑為0-4-6-5-0-12-8-7-0-10-1-0-3-9-1-0-2-11-10-0-12-8-5-4-0-3-2-11-0-9-6-7-0,調(diào)機(jī)總花費(fèi)時(shí)間為988 min(包含調(diào)機(jī)早到等待時(shí)間),總調(diào)運(yùn)成本為19 249.6元;用IGA 求解算法調(diào)機(jī)被劃分為9個(gè)批次,最優(yōu)路徑為0-5-4-11-12-0-6-5-8-0-9-0-1-10-0-3-2-1-0-7-8-4-0-2-6-7-0-10-9-0-3-12-11-0,調(diào)機(jī)總花費(fèi)時(shí)間為1 132 min(包含調(diào)機(jī)早到等待時(shí)間),總調(diào)運(yùn)成本為24 469.2元;用SA 求解算法調(diào)機(jī)被劃分為9個(gè)批次,最優(yōu)路徑為0-11-5-12-4-0-6-7-0-10-9-2-0-8-1-3-0-6-7-5-0-1-12-9-0-4-2-11-0-3-10-0-8-0,調(diào)機(jī)總花費(fèi)時(shí)間為1 241 min(包含調(diào)機(jī)早到等待時(shí)間),總調(diào)運(yùn)成本為24 719.6 元。可以看出,HHGAP&AIP求解算法比IGA、SA 求解算法得到更好質(zhì)量的解。

圖12給出了H H-GAP&AIP、IGA 和SA 算法的迭代次數(shù)與目標(biāo)函數(shù)值的演進(jìn)關(guān)系,限定3種算法迭代次數(shù)為100代。由圖12可見(jiàn),IGA 和SA 求解算法收斂較早,容易陷入局部最優(yōu),HHGAP&AIP求解算法收斂較晚,迭代后期能夠擴(kuò)大搜索范圍,得到更好質(zhì)量的解。

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

為對(duì)算法進(jìn)行性能測(cè)試與評(píng)估,將本地作業(yè)車(chē)取送信息根據(jù)經(jīng)驗(yàn)數(shù)據(jù)進(jìn)行適當(dāng)增減,設(shè)定不同規(guī)模作業(yè)數(shù)量,分別利用HH-GAP&AIP、IGA 和SA算法進(jìn)行求解,從而更全方位地進(jìn)行算法對(duì)比。引入調(diào)運(yùn)成本偏差比RAT(C1)和RAT(C2)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行比對(duì)分析,RAT(C1) 表示 H HGAP&AIP目標(biāo)函數(shù)值相對(duì)于IGA 算法的改進(jìn)率,RAT(C2)表示H H-GAP&AIP目標(biāo)函數(shù)值相對(duì)于SA 算法的改進(jìn)率,令HH-GAP&AIPC、IGAC和SAC分別表示HH-GAP&AIP、IGA 和SA 算法求得的模型目標(biāo)函數(shù)值,即調(diào)運(yùn)成本,則:

對(duì)于HH-GAP&AIP、IGA 和SA 算法所涉及的參數(shù)與上階段保持一致,H H-GAP&AIP算法迭代次數(shù)為100代,設(shè)置IGA 和SA 算法的停止時(shí)間與HH-GAP&AIP 求解算法迭代到100 代的運(yùn)行時(shí)間相同,具體求解信息如表5所示。

由表5可見(jiàn),對(duì)于不同作業(yè)數(shù)量規(guī)模問(wèn)題,3種算法都能在合理的時(shí)間內(nèi)得到較好的解,其中,H H-GAP&AIP求解結(jié)果較好,SA 算法求解較差。圖13給出了作業(yè)數(shù)量規(guī)模與調(diào)運(yùn)成本偏差比關(guān)系,由圖13 可見(jiàn),隨著作業(yè)數(shù)量規(guī)模的增加,RAT(C1)和RAT(C2)呈現(xiàn)逐漸擴(kuò)大趨勢(shì),說(shuō)明隨著作業(yè)數(shù)量規(guī)模的不斷增加,H H-GAP&AIP 算法相對(duì)于IGA 和SA 算法優(yōu)勢(shì)更加明顯。

表4 計(jì)算時(shí)間限定條件下HH-GAP&AIP、IGA和SA算法計(jì)算結(jié)果

圖12 HH-GAP&AIP、IGA 和SA 算法調(diào)運(yùn)成本隨迭代次數(shù)收斂曲線圖

表5 HH-GAP&AIP、IGA和SA算法不同作業(yè)規(guī)模下求解質(zhì)量對(duì)比

圖13 作業(yè)數(shù)量規(guī)模與調(diào)運(yùn)成本偏差比關(guān)系

5 結(jié)語(yǔ)

本文研究了一類基于樹(shù)枝形專用線網(wǎng)絡(luò)的小運(yùn)轉(zhuǎn)貨物作業(yè)系統(tǒng)優(yōu)化問(wèn)題。首先剖析了鐵路樞紐小運(yùn)轉(zhuǎn)貨物作業(yè)機(jī)理,進(jìn)而根據(jù)各車(chē)組到達(dá)編組站時(shí)分、車(chē)組目的裝卸站位置、車(chē)組取送作業(yè)時(shí)間要求以及調(diào)機(jī)牽引定數(shù)等限制,以調(diào)機(jī)早到等待成本、調(diào)機(jī)晚到懲罰成本、鐵路樞紐專用線調(diào)機(jī)和貨車(chē)運(yùn)營(yíng)成本最小化為目標(biāo),構(gòu)建問(wèn)題模型。鑒于模型復(fù)雜,直接求解較為困難,故設(shè)計(jì)HH-GAP&AIP 求解策略,該方法首先基于作業(yè)緊急度-編組定額-集結(jié)時(shí)間的送車(chē)-取車(chē)分步進(jìn)行策略對(duì)小運(yùn)轉(zhuǎn)列車(chē)初始取送方案進(jìn)行貪婪過(guò)程構(gòu)造,進(jìn)而設(shè)計(jì)異步循環(huán)啟發(fā)式完成解的迭代尋優(yōu),同時(shí),為避免算法陷入局部最優(yōu)及擴(kuò)大解的搜索空間,給出檢測(cè)-剔除-變換的取送車(chē)徑路調(diào)整策略。最后,設(shè)計(jì)實(shí)驗(yàn)場(chǎng)景,對(duì)本文所提出的方法進(jìn)行過(guò)程驗(yàn)證,并設(shè)計(jì)不同規(guī)模問(wèn)題,對(duì)算法進(jìn)行測(cè)試對(duì)比及性能評(píng)估。