郭鵬，何迅，許素瑕

(西南交通大學(xué)機(jī)械工程學(xué)院，四川成都，610031)

隨著國家“一帶一路”倡議的全面展開，鐵路貨運(yùn)將面臨更為廣闊的市場挑戰(zhàn)，如何全面提高其市場競爭力已成為當(dāng)前的難題之一。集裝箱鐵路運(yùn)輸能夠有效縮減轉(zhuǎn)運(yùn)時(shí)間和成本，但我國鐵路集裝箱運(yùn)量僅占鐵路貨運(yùn)總量的2%～3%，遠(yuǎn)遠(yuǎn)低于發(fā)達(dá)國家(30%～40%)[1]。如此大的差距表明我國集裝箱鐵路運(yùn)輸存在巨大的潛力和發(fā)展空間。為了提高集裝箱鐵路運(yùn)輸能力，國家“十一五”規(guī)劃提出建設(shè)18個(gè)鐵路集裝箱中心站(以下簡稱中心站)，以實(shí)現(xiàn)區(qū)域集裝箱鐵路運(yùn)輸與其他運(yùn)輸方式的無縫銜接。不同集裝箱班列、集裝箱卡車和堆場之間的裝卸及轉(zhuǎn)運(yùn)作業(yè)均由軌道式集裝箱起重機(jī)完成，對其開展調(diào)度優(yōu)化是站場實(shí)現(xiàn)高效轉(zhuǎn)運(yùn)作業(yè)的有效途徑。起重機(jī)調(diào)度問題作為最為關(guān)鍵的站場決策問題之一，現(xiàn)已受到廣泛的關(guān)注[2]。為了確保同一軌道上各個(gè)起重機(jī)不可交叉且滿足安全距離約束，BOYSEN 等[3?4]提出利用動(dòng)態(tài)規(guī)劃劃分起重機(jī)的堆場作業(yè)區(qū)域。采用集裝箱整理系統(tǒng)能夠大幅度簡化鐵路堆場的轉(zhuǎn)運(yùn)作業(yè)，在此基礎(chǔ)上研究起重機(jī)與集裝箱轉(zhuǎn)運(yùn)卡車的集成調(diào)度更加符合實(shí)際[5]。GUO 等[6?7]在借鑒集裝箱碼頭岸橋調(diào)度問題干涉約束處理技巧的基礎(chǔ)上，采用人工蜂群算法對鐵路集裝箱起重機(jī)調(diào)度問題進(jìn)行求解，并從提升外部卡車服務(wù)水平的角度構(gòu)建了更全面的調(diào)度優(yōu)化模型。王力等[8?9]認(rèn)為集裝箱班列卸箱作業(yè)和裝箱作業(yè)過程相同，針對卸箱作業(yè)過程建立了中心站起重機(jī)調(diào)度優(yōu)化模型，設(shè)計(jì)了混合粒子群求解算法；針對堆場混堆優(yōu)化問題，以兩階段優(yōu)化模型來平衡堆場各箱區(qū)進(jìn)站箱和出站箱的數(shù)量并減少堆存所產(chǎn)生的壓箱數(shù)。上述國內(nèi)外研究主要側(cè)重于起重機(jī)調(diào)度優(yōu)化研究，沒有考慮翻箱活動(dòng)對其作業(yè)調(diào)度的影響。受堆場空間限制，集裝箱必須堆疊放置，使得裝卸過程中翻箱作業(yè)無法避免。集裝箱翻箱作業(yè)在碼頭已得到較為全面的研究[10]，模擬退火[11]、束搜索[12]等方法均已用于翻箱操作調(diào)度，但與起重機(jī)進(jìn)行集成調(diào)度的研究仍較少。目標(biāo)箱不及時(shí)搬運(yùn)會(huì)造成后期搬運(yùn)時(shí)裝卸時(shí)間的延長，此時(shí)1次或多次翻箱作業(yè)會(huì)被執(zhí)行，即集裝箱裝載所需處理時(shí)間取決于其開始時(shí)間。這一現(xiàn)象與工時(shí)階梯惡化現(xiàn)象相符，即任務(wù)開始前的任何延遲都可能導(dǎo)致實(shí)際處理時(shí)間增加。考慮工時(shí)階梯惡化的調(diào)度問題在單機(jī)和并行機(jī)調(diào)度中已有一定研究[13?15]，其在鋼鐵生產(chǎn)、設(shè)備維護(hù)及醫(yī)療救治等過程中具有應(yīng)用潛力。本文作者采用階梯惡化函數(shù)來描述考慮翻箱作業(yè)的集裝箱裝載作業(yè)過程，以此為基礎(chǔ)開展鐵路集裝箱起重機(jī)調(diào)度優(yōu)化研究，以期提升站場的轉(zhuǎn)運(yùn)作業(yè)效率。

1 問題描述與建模

1.1 問題描述

考慮翻箱作業(yè)的軌道式集裝箱起重機(jī)調(diào)度問題(gantry crane scheduling problem with rehandling operations，GCSPRO)，旨在以最短的時(shí)間處理在不同集裝箱班列、卡車和堆場之間的轉(zhuǎn)運(yùn)任務(wù)或從集裝箱班列和轉(zhuǎn)運(yùn)集卡上裝載/卸載任務(wù)，用集合Ω={1,…,n}表示。中心站堆場分割成l個(gè)操作位置，且從左向右按升序排列。對于任務(wù)i(i∈Ω)，給定操作位置li來定義起重機(jī)對其進(jìn)行處理的?？课恢茫蝗蝿?wù)i有對應(yīng)的基本裝卸作業(yè)時(shí)間ai和給定的惡化臨界閾值hi；任務(wù)i的實(shí)際作業(yè)時(shí)間pi受實(shí)際開始搬運(yùn)時(shí)刻si影響，如果si≤hi，那么實(shí)際作業(yè)時(shí)間pi=ai，否則受場地空間限制會(huì)有其他箱堆垛到該箱上面，發(fā)生1次或多次的翻箱作業(yè)(時(shí)間為bi)，從而實(shí)際作業(yè)時(shí)間pi=ai+bi，若不發(fā)生翻箱則其懲罰時(shí)間bi為0 s。

所有作業(yè)任務(wù)交由多臺(tái)同軌且處理速度相同的起重機(jī)進(jìn)行處理，用集合Q={1,2,…,m}表示。所有起重機(jī)沿堆場水平方向左右移動(dòng)，且操作位置自左向右按升序編號(hào)。由于共享走行軌道，起重機(jī)相互之間不可交叉。起重機(jī)k(k∈Q)最早可用時(shí)刻為，初始位置為，起重機(jī)單位走行時(shí)間為t0。起重機(jī)k從其初始位置移動(dòng)到任務(wù)j的位置lj所需走行時(shí)間。對于任務(wù)i和j，從操作位置li移動(dòng)到操作位置lj起重機(jī)所需的走行時(shí)間tij=。

在建模過程中應(yīng)考慮以下約束。

1)優(yōu)先關(guān)系。對于滿載的集裝箱班列，到達(dá)堆場后須將已有的集裝箱卸載，隨后才能在同一位置進(jìn)行裝載，即同一操作位置上的2個(gè)任務(wù)不能同時(shí)處理且存在優(yōu)先關(guān)系。為了保證此類優(yōu)先關(guān)系，對于位于同一位置的任務(wù)對(i,j)用集合Φ來表示即(i,j)∈Φ，且要求任務(wù)i須在任務(wù)j開工之前完成。一旦待裝卸的作業(yè)任務(wù)給定后，集合Φ可根據(jù)任務(wù)的屬性提前確定。

2)干涉約束。為保證整個(gè)作業(yè)過程的安全，相鄰起重機(jī)之間必須保證一定的安全距離，從而使得部分任務(wù)不能同時(shí)處理。在此用集合Ψ表示不能同時(shí)處理的任務(wù)對，即對于任務(wù)(i,j)∈Ψ，要么在任務(wù)j開工前任務(wù)i已完成，要么任務(wù)i只能開始于任務(wù)j完工之后。起重機(jī)因安裝在同一走行軌道上相互之間也不可交叉作業(yè)。以上不可交叉作業(yè)和安全距離約束統(tǒng)稱為干涉約束。為了避免發(fā)生干涉約束，當(dāng)任務(wù)i與j分別指派給編號(hào)為u和w的起重機(jī)(u,w∈Q)進(jìn)行處理時(shí)，引入最小起重機(jī)走行時(shí)間跨度來間隔起重機(jī)處理任務(wù)的完工與開工時(shí)刻[16]。若δ為相鄰起重機(jī)之間的最小安全距離，則起重機(jī)u和起重機(jī)w操作位置間的最小距離δuw=(δ+1)×|u-w|。由下式計(jì)算得出：

由式(1)可知：當(dāng)u>w時(shí)，若處理任務(wù)i的起重機(jī)u位于處理任務(wù)j的起重機(jī)w的安全距離內(nèi)，則任務(wù)i和j不能同時(shí)處理，為避免干涉須插入最小走行時(shí)間跨度(lj-li+δuw)×t0；相反，當(dāng)u

3)邊界限制。由于安全距離約束，起重機(jī)可能會(huì)被擠出軌道邊界。為確保邊界限制，需要指定部分操作位置交由某個(gè)特定起重機(jī)訪問[17?18]。假設(shè)最低操作位置為1，最高操作位置為l。若起重機(jī)k(k∈Q)處理任務(wù)j，為保證起重機(jī)安全距離，則有：

根據(jù)式(2)和式(3)，起重機(jī)k(k∈Q)能到達(dá)的最低和最高的位置分別被定義為。

1.2 數(shù)學(xué)模型

針對翻箱作業(yè)的鐵路集裝箱起重機(jī)調(diào)度優(yōu)化問題，以最小化最大完工時(shí)間Cmax為目標(biāo)，構(gòu)建混合整數(shù)規(guī)劃(MIP)模型，模型中各參數(shù)定義見表1。

目標(biāo)函數(shù)：

約束條件：

表1 MIP模型中的參數(shù)Table 1 Parameters for MIP model

模型中，目標(biāo)函數(shù)式(4)使最大完工時(shí)間最小化；式(5)定義了Cmax屬性為同軌道起重機(jī)處理各個(gè)集裝箱裝卸作業(yè)任務(wù)完工時(shí)間的最大值，各個(gè)任務(wù)的完工時(shí)間由決策變量xik，yij和zi決定，從而使得最大完工時(shí)間Cmax與問題決策變量構(gòu)建了聯(lián)系；式(6)計(jì)算了每個(gè)任務(wù)的完工時(shí)間；式(7)給出了實(shí)際作業(yè)時(shí)間pi的取值范圍；式(8)定義了決策變量zi作用下任務(wù)的處理時(shí)間；式(9)保證當(dāng)任務(wù)i的開工時(shí)刻不晚于任務(wù)i的惡化閾值hi時(shí)，變量zi=1；式(10)保證每個(gè)任務(wù)只能被1 臺(tái)起重機(jī)處理；式(11)給出起重機(jī)處理首個(gè)任務(wù)的最小完工時(shí)間；式(12)和式(13)確定每個(gè)任務(wù)關(guān)于變量yij的開工時(shí)刻；屬于集合Φ的任務(wù)間優(yōu)先關(guān)系通過式(14)限定；式(15)確保當(dāng)任務(wù)對(i,j)∈Ψ時(shí)，任務(wù)i和任務(wù)j不能同時(shí)處理；不等式(16)～(18)為起重機(jī)間的干涉約束，式(16)保證每1對來自集合Θ的任務(wù)i和任務(wù)j被分配給起重機(jī)u和w時(shí)不能同時(shí)被處理；xiu=1表示任務(wù)i∈Ω交由起重機(jī)u處理，而xjw=1表示任務(wù)j∈Ω交由起重機(jī)w處理，如果以上分配情況同時(shí)出現(xiàn)，則任務(wù)i和任務(wù)j不能被同時(shí)處理，也就意味著變量yij和yji不能同時(shí)等于1；式(17)中考慮當(dāng)yij=1的情況，而yji=1的情況則在式(18)中處理；式(19)和式(20)確保如果操作位置li不在起重機(jī)k的可操作范圍內(nèi)，則任務(wù)i不能交由該起重機(jī)進(jìn)行處理，即xik=0；最后，式(21)定義了決策變量。

2 求解方法

上述問題若不引入翻箱操作則與岸橋起重機(jī)調(diào)度問題[19]相似，因此，所提出的GCSPRO 是NP-hard的，依靠精確的算法難以在合適的計(jì)算時(shí)間內(nèi)獲得問題最優(yōu)解。本文提出將自適應(yīng)大規(guī)模鄰域搜索(adaptive large neighborhood search，ALNS)與數(shù)學(xué)模型相結(jié)合構(gòu)建啟發(fā)式求解策略。該算法框架與固定及再優(yōu)化(fix and optimize，F(xiàn)&O)算法[20]類似，在解決復(fù)雜組合問題上已得到成功應(yīng)用[7,21]。在此將該算法稱之為自適應(yīng)鄰域規(guī)劃搜索(adaptive neighborhood programming search，ANPS)算法，其搜索過程中基于鄰域操作的破壞算子保留部分變量的取值，基于規(guī)劃模型的修復(fù)算子則重新處理待優(yōu)化變量。該規(guī)劃模型的求解交由標(biāo)準(zhǔn)求解器Gurobi完成。

2.1 初始解生成

初始解的產(chǎn)生采用SAMMARRA等[22]提出的STASKS 與S-LOAD 規(guī)則，即將任務(wù)數(shù)或者任務(wù)負(fù)荷均分給所有起重機(jī)。結(jié)合本文所提出問題，在此S-LOAD考慮2種情況：1)只考慮基本裝卸作業(yè)時(shí)間；2)考慮基本裝卸作業(yè)時(shí)間和懲罰時(shí)間之和。一旦完成起重機(jī)任務(wù)分配即可確定決策變量xik，隨后采用起重機(jī)單向走行策略確定每臺(tái)起重機(jī)處理任務(wù)時(shí)的作業(yè)順序。假設(shè)起重機(jī)和任務(wù)均從左到右進(jìn)行索引且起重機(jī)從左向右移動(dòng)，須對所構(gòu)建的模型施加約束：

當(dāng)任務(wù)對(i,j)∈Φ，即任務(wù)i在任務(wù)j開工之前被處理，為了確保起重機(jī)的單向走行，須在模型中添加下列約束[23]：

一旦以上步驟完成，變量xik和變量yij的部分值即可給定，未給定值的變量yij即視為待優(yōu)化變量，由此形成子問題交由求解器Gurobi求解。

采用類似的步驟處理從右到左的走行順序，從而獲得另一個(gè)解。為了確保起重機(jī)單向走行，須在模型中添加以下2個(gè)約束：

基于S-TASKS和S-LOAD 與單向走行策略，產(chǎn)生4組不同解，從中選擇最優(yōu)組作為算法的初始解。上述基于數(shù)學(xué)規(guī)劃的單向走行策略將用于算法的解修復(fù)算子。

2.2 破壞算子

本文提出5種不同的解破壞移除算子，每個(gè)破壞算子都從原有起重機(jī)調(diào)度序列中刪除d個(gè)作業(yè)任務(wù)。所有的破壞算子均是基于當(dāng)前解進(jìn)行任務(wù)選取，可視為在已有解結(jié)構(gòu)上進(jìn)行鄰域操作。同時(shí)每次的任務(wù)選取規(guī)模較總?cè)蝿?wù)數(shù)n來說相對較小，從而保證了解修復(fù)算子能夠較快地確定待優(yōu)化變量。一旦任務(wù)子集被選定后，相應(yīng)的變量即視為待優(yōu)化的，而剩余變量的取值則與原有調(diào)度方案中的取值一致。由于起重機(jī)干涉約束影響，任務(wù)完工時(shí)間ci依賴于每臺(tái)起重機(jī)的作業(yè)順序，因此，變量yij，zi和ci(i∈Ω)在以下操作中均視為待優(yōu)化變量：

1)隨機(jī)起重機(jī)作業(yè)移除算子。該算子允許將所選任務(wù)重新分配給其他起重機(jī)。針對起重機(jī)k∈Q，用Ωk表示分配給起重機(jī)k的任務(wù)集合。該算子隨機(jī)選擇起重機(jī)k，從分配給起重機(jī)k的任務(wù)中選擇min{d,|Ωk|}個(gè)任務(wù)，其中以上選定的任務(wù)將會(huì)在所有起重機(jī)之間重新考慮分配，即與上述選定任務(wù)有關(guān)的變量xik均視為待優(yōu)化變量。

2)最大負(fù)載移除算子。在此僅考慮瓶頸起重機(jī)，分配給起重機(jī)k的任務(wù)集合Ωk中任務(wù)操作順序按照各任務(wù)對應(yīng)的操作位置進(jìn)行升序排列。選取前d/2和后d/2個(gè)任務(wù)，若|Ωk|

3)基于基本裝卸作業(yè)時(shí)間的Shaw 移除算子。參考文獻(xiàn)[24]，選擇相似的任務(wù)來產(chǎn)生更優(yōu)解。初始化選定任務(wù)集合D為空集，而后隨機(jī)從集合Ω中選擇1個(gè)任務(wù)j′。隨后計(jì)算任務(wù)j′和所有剩下的任務(wù)的相關(guān)性度量值R(j′,j)=|aj′?aj|，再基于參數(shù)ε隨機(jī)選擇新的任務(wù)j″插入集合D中?；诤唵斡?jì)算，在此將參數(shù)ε設(shè)定為3。重復(fù)上述選擇操作直到所選任務(wù)集合D的大小為d時(shí)停止，該算子流程如圖1所示，與選定任務(wù)相關(guān)的變量xik被視為待優(yōu)化變量。

4)基于基本裝卸作業(yè)時(shí)間和懲罰時(shí)間的Shaw移除算子。該算子與算子3)相似，僅僅相關(guān)性度量值R(j′,j)的計(jì)算方式不一樣。此算子中R(j′,j)的計(jì)算將考慮任務(wù)i的懲罰時(shí)間bi，即R(j′,j)=|aj′+bj′?(aj+bj)|。

5)作業(yè)隨機(jī)移除算子。該算子隨機(jī)選擇任務(wù)子集，并允許重新安排所有相關(guān)變量，即在所有任務(wù)中隨機(jī)選擇min{d,|Ω|}個(gè)任務(wù)，并且所有相關(guān)變量xik都作為待優(yōu)化變量。

2.3 修復(fù)算子

圖1 Shaw移除算子操作流程Fig.1 Flow chart of shaw removal

在修復(fù)算子方面，使用標(biāo)準(zhǔn)數(shù)學(xué)求解器來解決基于上述破壞算子和單向走行策略下的數(shù)學(xué)模型。該數(shù)學(xué)模型包含MIP和約束(22)～(23)(或者約束(24)～(25))。在該模型中，xik分為待優(yōu)化部分和已經(jīng)賦值部分。為了保證求解速度，在此設(shè)定該模型的求解時(shí)間為Tlocal。

2.4 破壞算子自適應(yīng)選擇策略

破壞算子的選擇基于其在之前迭代過程中的搜索性能，在此用O表示破壞算子集合。整個(gè)搜索過程被分成若干個(gè)片段，每一段包含κ次迭代，最后一段迭代可能會(huì)少于κ次?；谄茐乃阕拥臋?quán)重，采用標(biāo)準(zhǔn)輪盤賭選擇機(jī)制來選擇算子。

每次搜索開始時(shí)，將每個(gè)破壞算子的權(quán)重設(shè)置為0.5，以保證其選擇概率一致(wθ=0.5，θ∈O)。權(quán)重在此后的κ次迭代中保持不變，然后采用下式對其進(jìn)行更新：

式中：Sθ為破壞算子θ的累計(jì)得分；Smin和Smax分別為Sθ(θ∈O)的最小值和最大值；參數(shù)η∈[0,1]，可反映權(quán)重wθ(θ∈O)如何快速對搜索性能作出反應(yīng)。

為了衡量破壞算子θ(θ∈O)的性能，在每次迭代過程中均記錄Sθ。在每一段迭代初始，所有算子得分均重置為0。當(dāng)使用算子θ時(shí)，用τθ表示在某段迭代過程中目標(biāo)值的累積改進(jìn)，而?θ表示在該段迭代過程中累積的計(jì)算用時(shí)。在每段迭代過程開始時(shí)，?θ和τθ初始化為0，則Sθ可表示為

式中：Sθ考慮了在某一段迭代過程中使用算子θ對候選解的質(zhì)量改進(jìn)速度。

2.5 更新與停止準(zhǔn)則

修復(fù)算子存在時(shí)間限制，新解的質(zhì)量并不總是比現(xiàn)有解質(zhì)量更好。為了避免陷入局部最優(yōu)解，在此使用模擬退火來更新現(xiàn)有的解。該方法的初始溫度為T0，并在每次迭代中通過冷卻參數(shù)μ進(jìn)行更新。若新發(fā)現(xiàn)的解Unew優(yōu)于當(dāng)前解U，則當(dāng)前解被最新解代替。另外，每次迭代產(chǎn)生隨機(jī)數(shù)，如果該值小于e-(Znew-Z)/T(其中T為當(dāng)前溫度)，那么，當(dāng)前解被Unew取代更新。當(dāng)滿足下列任一終止條件則算法停止搜索：1)達(dá)到最大迭代次數(shù)Imax；2)連續(xù)Inip次迭代中最佳解并無改善。

2.6 算法框架

圖2 ANPS算法框架Fig.2 Flow chart of the proposed ANPS algorithm

ANPS 算法框架如圖2所示，從參數(shù)初始化開始，然后根據(jù)第2.1節(jié)中提到的啟發(fā)式策略生成初始解U，并計(jì)算其目標(biāo)值Z。算法的最優(yōu)解為其迭代過程中已發(fā)現(xiàn)的最佳計(jì)算結(jié)果。令最優(yōu)解Ubest=U及其目標(biāo)函數(shù)Zbest=Z。算法開始迭代直到滿足停止準(zhǔn)則為止。對于每次迭代，基于輪盤賭選擇機(jī)制選擇破壞算子θ，然后利用算子θ生成子問題。若產(chǎn)生的子問題可行，則通過標(biāo)準(zhǔn)求解器求解得到新的Unew和Znew，并觀察是否存在更新最優(yōu)解和替代當(dāng)前解的可能。若新解的目標(biāo)函數(shù)值優(yōu)于當(dāng)前解則將其更新為當(dāng)前解，否則，引入隨機(jī)數(shù)繼續(xù)判斷。若新解的目標(biāo)函數(shù)值優(yōu)于已發(fā)現(xiàn)的最優(yōu)解，則更新最優(yōu)解。同時(shí)，參數(shù)τθ和?θ通過τθ:=τθ+Z-Znew和?θ:=?θ+tθ更新，其中tθ表示在迭代過程中破壞算子θ的計(jì)算用時(shí)。一旦權(quán)重更新條件滿足，則更新權(quán)重wθ，并重置參數(shù)τθ和?θ。

3 算例分析

本文所提出的GCSPRO 問題與現(xiàn)有的起重機(jī)調(diào)度問題有所不同，因此須構(gòu)建算例進(jìn)行分析。在此將單向走行策略、MIP和初始解與所提出的ANPS 算法進(jìn)行比較。升序單向搜索由目標(biāo)函數(shù)(4)、約束(5)～(21)以及約束(22)～(23)進(jìn)行定義(稱為UDS_A)；降序單向搜索由目標(biāo)函數(shù)(4)、約束(5)～(21)及約束(24)～(25)定義(稱為UDS_D)。初始解為S-TASKS和S-LOAD 求得的最優(yōu)解。采用默認(rèn)設(shè)置下Gurobi7.5.1 來求解優(yōu)化模型，使用C#在Visual Studio 2017 環(huán)境中實(shí)現(xiàn)算法。運(yùn)算采用英特爾i7-7700 CPU(3.6 GHz)、12 GB RAM和安裝有Windows 10操作系統(tǒng)的臺(tái)式電腦。

3.1 算例生成

基于成都青白江鐵路集裝箱中心站實(shí)際運(yùn)營情況以及由KIM 等[25]提供的基準(zhǔn)數(shù)據(jù)生成方法來產(chǎn)生算例。實(shí)際裝卸作業(yè)時(shí)間為3～10 min，為此測試算例中任務(wù)j的基本處理時(shí)間aj在U(3,10)均勻分布中產(chǎn)生。集裝箱任務(wù)的作業(yè)位置沿班列分布，每個(gè)位置都有1個(gè)卸載或裝載任務(wù)，同一位置的班列或卡車關(guān)聯(lián)任務(wù)數(shù)不超過2個(gè)。任務(wù)j∈Ω的操作位置lj通過均勻分布從集合{1,2,…,n}中獲得，其處理優(yōu)先順序如下：卡車卸載任務(wù)、卡車裝載任務(wù)、班列卸載任務(wù)、班列裝載任務(wù)。集裝箱翻箱作業(yè)只發(fā)生在裝載過程中，現(xiàn)有堆場設(shè)置下集裝箱可堆疊3層，第4層為起重機(jī)吊具移動(dòng)預(yù)留空間。如果只有1個(gè)集裝箱位于目標(biāo)集裝箱頂部，集裝箱的翻箱處理時(shí)間是2個(gè)時(shí)間單位，那么，因翻箱作業(yè)導(dǎo)致的懲罰時(shí)間bj可通過均勻分布從{2,4,6}中取得；參考文獻(xiàn)[13]中的方法，惡化閾值hj從3個(gè)均勻分布的取值區(qū)間中獲取，即H1:=[1,A/2)，H2:=[A/2,A]和H3:=[1,A]，其中。對于軌道式集裝箱起重機(jī)，假設(shè)其初始位置沿班列等距分布，最早到位時(shí)刻設(shè)置為0；在相鄰操作位置之間，起重機(jī)走行時(shí)間為t0個(gè)時(shí)間單位，安全距離設(shè)置為1個(gè)作業(yè)位置。

算例包含小規(guī)模和大規(guī)模算例集。對于小規(guī)模算例，任務(wù)數(shù)量n在集合{10,15,20,25}中選取，起重機(jī)數(shù)量m在{2,3}中選擇；對于大規(guī)模算例，任務(wù)數(shù)量n從{40,60,80,100}中選擇，起重機(jī)數(shù)m從{3,4}中選擇；每個(gè)參數(shù)n和m組合生成5個(gè)算例，共計(jì)240個(gè)算例。

3.2 算法參數(shù)選取

參數(shù)設(shè)置是通過解的質(zhì)量和計(jì)算時(shí)間之間的權(quán)衡來實(shí)現(xiàn)的，利用小規(guī)模算例進(jìn)行測算確定參數(shù)取值。在此考慮不同參數(shù)值對解的質(zhì)量和計(jì)算耗時(shí)的影響，以平均偏差和平均運(yùn)行時(shí)間為基準(zhǔn)。本文所提出的ANPS 算法主要包括d，κ，η，T0，μ，Inip，Imax和Tlocal這8個(gè)基本參數(shù)?；跍y算結(jié)果，Inip和Imax分別被設(shè)置為20和200；初始溫度T0和冷卻參數(shù)μ分別設(shè)置為100和0.95；由Gurobi求解子問題的時(shí)間限制Tlocal=50 s，而參數(shù)d則為滿足10≤d≤min(20,0.4n)的隨機(jī)數(shù)，d最小值為10；經(jīng)過正交試驗(yàn)后確定κ=8，η=0.7 為最佳組合。

3.3 結(jié)果分析

對于每個(gè)算例，用RPD=100%×(Z-Zbest)/Zbest表示所得目標(biāo)函數(shù)值與不同方法求得的最優(yōu)解之間的相對偏差(%)，同時(shí)算法所得最優(yōu)解個(gè)數(shù)與平均計(jì)算用時(shí)也列入結(jié)果中，在此最優(yōu)解指的是所有方法給出的最佳結(jié)果。Gurobi求解MIP的計(jì)算時(shí)間限定為1 800 s，若實(shí)際計(jì)算時(shí)間未超過設(shè)定的1 800 s，則給出的解為問題的最優(yōu)解。UDS_A和UDS_D 中較優(yōu)解列于UDS 欄中。值得注意的是，“UDS”中列出的運(yùn)行時(shí)間是UDS_A和UDS_D 之和。表2所示為小規(guī)模算例的計(jì)算結(jié)果。由表2可知：Gurobi求解MIP可得到作業(yè)任務(wù)數(shù)為10和15的算例最優(yōu)解，所有算例與最優(yōu)解的平均相對偏差為2.01%左右，平均計(jì)算用時(shí)為773.09 s。在120個(gè)算例中，有88個(gè)算例在使用MIP 求解時(shí)因1 800 s 時(shí)間限制而停止。采用單向走行時(shí)，UDS_D的性能略微優(yōu)于UDS_A的性能，UDS 結(jié)果堪比MIP的結(jié)果，但并不總能產(chǎn)生最優(yōu)解，UDS 中解的平均相對偏差為1.13%，而UDS的平均計(jì)算用時(shí)還不到MIP的平均計(jì)算用時(shí)的2%。因此，在解決起重機(jī)調(diào)度問題上UDS具有較強(qiáng)的優(yōu)勢。本文提出的ANPS算法除了在120個(gè)算例中有2個(gè)無法找到比UDS 更好的解以外，其他結(jié)果與UDS的求解質(zhì)量一樣好。此外，初始解與最優(yōu)解的平均相對偏差為6.25%，而ANPS 解與最優(yōu)解的平均相對偏差僅僅為1.16%。這意味著通過ANPS算法，解的平均相對偏差了5.09%。

表2 小規(guī)模算例的計(jì)算結(jié)果Table 2 Computational results for small scale example

表3所示為大規(guī)模算例計(jì)算結(jié)果。當(dāng)任務(wù)數(shù)n≥20 時(shí)MIP的求解時(shí)間明顯變長，耗盡時(shí)間限定的1 800 s。隨著算例的增加，使用Gurobi 求解的UDS 平均運(yùn)行時(shí)間顯著增加。UDS_A和UDS_D都耗盡了給定的限制時(shí)間，并且僅僅6個(gè)算例找到了最優(yōu)解。UDS 求解大規(guī)模算例平均相對偏差為19.56%，由此表明算例規(guī)模增加，問題的復(fù)雜程度也急劇增加。初始解的平均相對偏差為3.83%，這比UDS 策略解的質(zhì)量要高得多。此外，初始解的平均計(jì)算用時(shí)僅為8.09 s；對于ANPS 算法，相對偏差從0%到0.71%不等，120個(gè)算例的平均相對偏差僅為0.08%。從表3 可以發(fā)現(xiàn)ANPS 算法為120個(gè)算例中的115個(gè)提供了最優(yōu)解，平均運(yùn)行時(shí)間為275.15 s。值得注意的是，當(dāng)作業(yè)任務(wù)數(shù)n大于60個(gè)時(shí)，ANPS算法總能給出最優(yōu)解，由此證明ANPS算法在求解大規(guī)模算例時(shí)是有效的。初始解給出最優(yōu)解數(shù)量為24，這意味著91個(gè)算例的最優(yōu)解是由ANPS算法搜索得出的。

表3 大規(guī)模算例的計(jì)算結(jié)果Table 3 Computational results for large scale example

4 結(jié)論

1)采用階梯惡化函數(shù)對集裝箱裝卸轉(zhuǎn)運(yùn)作業(yè)時(shí)間進(jìn)行描述。在考慮作業(yè)優(yōu)先約束、軌道式集裝箱起重機(jī)干涉約束與邊界約束的基礎(chǔ)上，構(gòu)建了混合整數(shù)規(guī)劃模型。

2)將數(shù)學(xué)規(guī)劃與自適應(yīng)大規(guī)模鄰域搜索進(jìn)行集成，提出了自適應(yīng)鄰域規(guī)劃搜索求解算法。該算法采用5種破壞算子構(gòu)建子問題，并利用標(biāo)準(zhǔn)求解器Gurobi 實(shí)現(xiàn)求解?；阼F路集裝箱中心站實(shí)際運(yùn)行情況構(gòu)建的算例測試結(jié)果表明：所提出的ANPS 算法在大規(guī)模算例中取得了良好的計(jì)算效果，較之混合整數(shù)規(guī)劃與單向搜索策略均有明顯的優(yōu)勢，適用于求解此類問題，從而為大規(guī)模鐵路集裝箱轉(zhuǎn)運(yùn)過程中的資源調(diào)度問題提供決策支持。