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

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

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

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

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

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

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

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

1 問題分析與描述

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

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

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

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

1.2 問題描述及研究條件

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

LFTTS-BSS問題研究中考慮如下研究條件:

(1)鐵路專用線的拓撲結(jié)構(gòu)已知。

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

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

(4)非直達貨物列車到達編組站的時刻已知。

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

(6)特定作業(yè)時間窗要求,即特定作業(yè)有固定時間窗限制,調(diào)機在規(guī)定時間外未將特定作業(yè)送達裝卸站,會因為特定作業(yè)未能及時交貨而產(chǎn)生額外成本。

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

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

(9)調(diào)機在編組站和裝卸站進行人員整備、貨車甩掛時間不計。

2 模型構(gòu)建

2.1 符號約定

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

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

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

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

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

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

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

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

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

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

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

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

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

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

cl——調(diào)機單位分鐘運營成本

cw——貨車單位分鐘運營成本

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

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

狀態(tài)變量

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

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

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

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

決策變量

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

2.2 模型構(gòu)建

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

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

3 求解策略

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

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

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

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

具體步驟:

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

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

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

階段2小運轉(zhuǎn)列車開行批次構(gòu)造。

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

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

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

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

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

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

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

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

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

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

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

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

步驟5.2生成所有取送車批次。令k=k+1,重復階段3～5,生成所有取送車批次,即生成單個取送車徑路。

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

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

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

3.2 基于AIP的取送車集合更新過程

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

圖3 AIP算法流程

具體步驟:

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

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

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

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

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

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

圖4 伙伴取送車徑路的生成過程

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

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

步驟3.1基于伙伴取送車徑路的解更新過程。

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

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

步驟3.2基于中心取送車徑路的解更新過程。

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

圖5 中心取送車徑路的生成過程

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

步驟3.3基于變異取送車徑路的解更新過程。

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

(2)基于變異取送車徑路的解更新過程。計算當前取送車徑路h?目標函數(shù)值f(h?)和變異取送車徑路目標函數(shù)值,并對其進行比較:

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

圖6 變異取送車徑路的生成過程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1 實驗場景

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.3 過程驗證

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

根據(jù)循環(huán)體參數(shù)調(diào)試,在合理運行時間范圍內(nèi)為實現(xiàn)目標函數(shù)值最優(yōu)化,對H H-GAP&AIP算法參數(shù)設(shè)置如下:擁擠度負荷λ=0.8,取送車徑路視野V=4,最大嘗試次數(shù)Rmax=10,HH-GAP&AIP算法初始取送車徑路集合數(shù)w=30,迭代次數(shù)Q=100代。在解決優(yōu)化排序問題上,遺傳算法和模擬退火算法能夠很好地解決此類問題,參考文獻[21,24],引入?yún)?shù)自適應(yīng)遺傳算法(IGA)和模擬退火算法(SA)作為對比,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,初始馬爾科夫鏈長度為500。為公平比較算法,設(shè)置IGA 和SA 算法的停止時間與H HGAP&AIP求解算法迭代到100 代的運行時間相同,算法運行結(jié)果如表4所示。

由上述算例仿真對比結(jié)果可以看出,H HGAP&AIP求解算法調(diào)機被劃分為8個批次,最優(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)機總花費時間為988 min(包含調(diào)機早到等待時間),總調(diào)運成本為19 249.6元;用IGA 求解算法調(diào)機被劃分為9個批次,最優(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)機總花費時間為1 132 min(包含調(diào)機早到等待時間),總調(diào)運成本為24 469.2元;用SA 求解算法調(diào)機被劃分為9個批次,最優(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)機總花費時間為1 241 min(包含調(diào)機早到等待時間),總調(diào)運成本為24 719.6 元?？梢钥闯?HHGAP&AIP求解算法比IGA、SA 求解算法得到更好質(zhì)量的解。

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

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

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

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

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

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

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

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

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

5 結(jié)語

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