基于樹枝形鐵路專用線網絡的小運轉貨物作業系統優化

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

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

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

關于貨物運輸組織優化調度是一項融合技術與管理的復雜系統工程,相關研究多集中在鐵路調車作業優化、貨車取送作業優化以及車隊綜合協調調度等方面。

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

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

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

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

1 問題分析與描述

1.1 小運轉作業系統分析

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

樞紐內編組站對到達列車解體和出發列車編組,完成“列流轉變為車流”和“車流轉變為列流”;裝卸站對貨物進行裝車和卸車工作,完成“貨流轉變為車流”和“車流轉變為貨流”。根據裝卸站取出車流的出發形式,主要分為可隨就近列車掛走的車流和明確指定掛運車次的車流兩種方式。在編組站,合理安排面向裝卸站開行的小運轉列車編組輛數和開行批次,從而完成小運轉列車調配,實現列流向車流的轉變;進而依據編組站小運轉列車編排方案,給出合理取送車策略,完成裝卸站間貨車取送徑路安排,實現車流向貨流的轉變。由此可見,這兩個環節為一個整體,實現小運轉列車調配-作業車取送一體化調度,就要做到前后作業計劃同步化。基于編組站-裝卸站的小運轉列車調配-作業車取送一體化調度如圖1所示。

圖1 樞紐內小運轉列車調配-作業車取送一體化綜合協調

1.2 問題描述及研究條件

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

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

(1)鐵路專用線的拓撲結構已知。

(2)單調機作業,調機最大牽引定數和最大走行時間已知。

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

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

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

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

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

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

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

2 模型構建

2.1 符號約定

為構建模型,引入如下參數與變量:

輸入參量

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

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

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

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

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

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

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

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

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

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

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

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

cl——調機單位分鐘運營成本

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

D——調機最大牽引定數

P——調機的最大行駛時間

狀態變量

K——調機取送批次集合,記為K={k|k=1,2,…,},其中,為小運轉列車取送批次總數

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

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

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

決策變量

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

2.2 模型構建

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

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

3 求解策略

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

3.1 基于GAP的小運轉列車初始方案生成

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

圖2 基于GAP的小運轉列車初始方案生成流程圖

具體步驟:

階段1初始本地車組作業編號的構造。

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

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

階段2小運轉列車開行批次構造。

步驟2.1設置小運轉列車開行批次。設O為已編入特定批次小運轉列車的作業編號,Ok為已編入第k批次小運轉列車的作業編號。

步驟2.2參數初始化設置。初始已編入小運轉列車的作業編號O為空集,初始小運轉列車的批次編號k=1。

階段3送車作業編號的小運轉列車批次選取。

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

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

步驟3.3小運轉列車是否繼續集結的編組數判別參數Φ。將未編入任何批次小運轉列車的送車作業編號依次編入集合Ok,若未滿足調機約束限制,引入編組數判別參數Φ,若D-Ok＜Φ,則生成第k批次小運轉列車送車作業;否則,轉步驟3.4。

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

階段4取車作業編號的小運轉列車批次選取。

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

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

階段5小運轉列車批次生成。

步驟5.1小運轉列車單批次生成。第k批次送車作業、第k批次取車作業即為第k批次取送車作業。

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

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

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

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

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

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

圖3 AIP算法流程

具體步驟:

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

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

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

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

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

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

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

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

階段3基于單次循環的三階段異步更新過程。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟5.1最優取送車徑路檢測調整。

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

步驟5.2較差取送車徑路的剔除調整。

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

步驟5.3重復取送車徑路變換調整。

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

圖7 重復取送車徑路變換調整

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

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

4 實驗驗證及結果分析

4.1 實驗場景

設計由12個裝卸站組成的樹枝形小運轉作業網絡(見圖8)。樹枝形專用線網絡中各裝卸站及編組站間的調機走行時間數據如表1 所示,其中0表示編組站。本地作業車取送信息數據如表2所示,出發列車最晚編組時分如表3所示。

圖8 樞紐地方貨物流小運轉作業網絡示意圖

表1 裝卸站間調機走行時間表 min

4.2 HH-GAP&AIP主要循環體參數調試

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

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

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

表2 樞紐內本地作業車取送信息表

表3 出發列車最晚編組時分

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

圖9 視野值參數調試

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

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

圖10 最大嘗試次數參數調試

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

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

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

4.3 過程驗證

圖11 擁擠度負荷參數調試

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

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

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

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

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

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

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

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

圖12 HH-GAP&AIP、IGA 和SA 算法調運成本隨迭代次數收斂曲線圖

表5 HH-GAP&AIP、IGA和SA算法不同作業規模下求解質量對比

圖13 作業數量規模與調運成本偏差比關系

5 結語

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