考慮集卡到港時間延遲的堆場起重機動態(tài)調(diào)度研究

王 耀 宗, 胡 志 華, 田 曦 丹, 陳 婉 婷

(上海海事大學(xué) 物流研究中心, 上海 201306)

0 引 言

在自動化集裝箱碼頭中,堆場面積占碼頭總面積的40%至60%,是碼頭重要的作業(yè)區(qū)域[1].自動化堆場連接岸邊船舶的裝卸與外集卡的運輸,用于集裝箱的堆存和中轉(zhuǎn),其作業(yè)效率制約碼頭的整體性能.為提升堆場的作業(yè)能力,碼頭采用穿越式雙起重機的作業(yè)工藝,協(xié)同作業(yè)箱區(qū)內(nèi)任意位置的裝卸和堆垛任務(wù)[1].然而,在同一箱區(qū)作業(yè)的兩臺起重機可能發(fā)生干涉[2],即如果小起重機穿越正在某一貝位作業(yè)的大起重機或者兩臺起重機同時在同一貝位作業(yè),將發(fā)生干涉.因此,起重機的調(diào)度計劃應(yīng)為一個無干涉的作業(yè)序列.

在集港作業(yè)中,集卡可能受交通擁堵等不確定因素的影響而延遲到港.通常,在集裝箱船靠泊前的1～3 d,碼頭為準(zhǔn)備裝船的集裝箱制訂集港計劃,集卡按照預(yù)約的時段依次到達(dá)堆場.然而,不確定因素可能導(dǎo)致集卡未能按照預(yù)約的時段到達(dá)堆場,實際交箱時間滯后于計劃的交箱時間,對原有作業(yè)計劃產(chǎn)生擾動.因此,碼頭需要及時調(diào)整作業(yè)計劃以降低擾動前后規(guī)劃結(jié)果的偏差.集卡延遲到港使得碼頭的調(diào)度作業(yè)具有動態(tài)性特征.碼頭通常以靜態(tài)方式制訂作業(yè)計劃[3],即調(diào)度期初做好所有任務(wù)的起重機作業(yè)計劃,但該作業(yè)模式的時效性較差,如果出現(xiàn)集卡到港時間延遲而產(chǎn)生即時請求,原有作業(yè)序列將不再滿足最優(yōu)性甚至不可行,影響堆場的作業(yè)效率.

在碼頭多級作業(yè)場景下,作業(yè)工序相互耦合與裝卸決策相互依賴是設(shè)備調(diào)度的復(fù)雜性所在,而雙起重機非交叉約束進一步增加了建模的難度[4].Vis等[5]把雙起重機問題轉(zhuǎn)化為單起重機問題進行求解;Gharehgozli等[6]把起重機的調(diào)度問題抽象為具有優(yōu)先約束的多重旅行商問題;鄭紅星等[7]研究考慮倒箱的混堆裝船箱區(qū)內(nèi)起重機調(diào)度優(yōu)化問題,提出了帶滾動時域的啟發(fā)式算法求解多起重機作業(yè)序列,并設(shè)計了帶有解空間切割的遺傳算法求解單個時域?qū)?yīng)的子調(diào)度問題;Hu等[8]把起重機之間的安全距離轉(zhuǎn)化為時間間隔以處理干涉,提出了混合整數(shù)規(guī)劃模型和非線性模型刻畫批次任務(wù)之間的順序約束,并設(shè)計了精確算法和遺傳算法求解起重機的作業(yè)計劃;Han等[9]以提箱完成時間最短為目標(biāo)建立起重機調(diào)度模型,優(yōu)化裝船過程中起重機的行駛路徑;秦磊磊等[10]以最小化任務(wù)完成時間為目標(biāo)建立考慮交接區(qū)緩沖貝位決策的雙起重機調(diào)度混合整數(shù)規(guī)劃模型,求解最優(yōu)緩沖貝位的位置與起重機作業(yè)序列.以上研究為堆場起重機的調(diào)度優(yōu)化提供了理論及方法上的參考.

一些研究考慮了不確定因素的碼頭作業(yè)場景.為降低集卡到港時間不確定對出口箱堆存和裝船效率的影響,范厚明等[11]構(gòu)建了雙層混合整數(shù)規(guī)劃模型優(yōu)化出口箱位分配與起重機作業(yè)序列,通過不斷平衡層與層之間的最優(yōu)解優(yōu)化堆場堆存和裝船作業(yè)效率;針對碼頭裝卸作業(yè)時間不確定性,孫玉姣等[12]以最小化作業(yè)完成時間、岸邊無集卡與堆場無集卡的時間和為目標(biāo),建立了混合整數(shù)規(guī)劃模型,研究了考慮裝卸時間受作業(yè)順序與位置等影響下碼頭生產(chǎn)調(diào)度問題,為碼頭提供動態(tài)場景下優(yōu)化裝卸作業(yè)的參考;范厚明等[13]關(guān)注交箱序列不確定的起重機調(diào)度問題,根據(jù)出口箱預(yù)約信息提出了新的堆存策略,建立了堆場箱位分配及多起重機調(diào)度集成優(yōu)化模型,同時對于預(yù)約時段的長度及準(zhǔn)確性對調(diào)度結(jié)果的影響做了魯棒性分析,補充了不確定情景下碼頭的運作優(yōu)化研究.此外,Dorndorf等[14]關(guān)注穿越式Triple-ASC調(diào)度,當(dāng)一個任務(wù)完成或一個新任務(wù)到達(dá)時,動態(tài)調(diào)整調(diào)度計劃以優(yōu)化任務(wù)的分配和起重機的作業(yè)序列.

在動態(tài)調(diào)度問題的研究中,Pillac等[15]綜述了動態(tài)車輛路徑優(yōu)化問題,著重研究了確定性、隨機性兩個特征組合下的車輛調(diào)度問題.針對客戶路線變更的路徑優(yōu)化問題,Ozbaygin等[16]建立了混合整數(shù)規(guī)劃模型,在迭代重優(yōu)化框架內(nèi),基于初始計劃動態(tài)調(diào)整路線變更后的計劃;為了減小重調(diào)度對系統(tǒng)的擾動,寧濤等[17]從干擾管理角度研究了車輛行駛時間延遲問題,以最小化用戶時間窗偏離度和最小化配送成本為目標(biāo)建立了數(shù)學(xué)規(guī)劃模型;針對自動導(dǎo)引車(AGV)動態(tài)調(diào)度問題,丁一等[18]采用周期和事件混合驅(qū)動的方式——根據(jù)AGV的狀態(tài)定義若干觸發(fā)規(guī)則響應(yīng)突發(fā)事件,并結(jié)合周期型調(diào)度策略生成調(diào)度計劃;楊珍花等[19]研究了甩掛車輛的動態(tài)調(diào)度問題,建立了掛車裝卸時間不確定混合整數(shù)規(guī)劃模型,并提出了多階段動態(tài)優(yōu)化算法生成牽引車的調(diào)度方案.

綜上所述,關(guān)于動態(tài)車輛路徑優(yōu)化和柔性車間動態(tài)調(diào)度問題的研究已取得豐碩的成果.多數(shù)文獻(xiàn)采用周期驅(qū)動或事件驅(qū)動的重調(diào)度方式處理延遲或緊急任務(wù),即在特定時刻或狀態(tài)下調(diào)整原有計劃.然而,該重調(diào)度方式下,如何在復(fù)雜場景下界定事件的存在形式與如何選擇調(diào)度時段長度是研究的難點,尤其在集裝箱碼頭這一多級物流系統(tǒng)中,難以窮盡作業(yè)場景下所有狀態(tài)及其對應(yīng)事件.為此,本文在原有研究基礎(chǔ)上,考慮在集卡到港時間延遲情形下的出口箱作業(yè),以作業(yè)完成時間最短為目標(biāo),建立雙起重機動態(tài)調(diào)度混合整數(shù)規(guī)劃模型,提出一種迭代重優(yōu)化框架處理延遲到港任務(wù).由于存在非交叉約束,堆場起重機調(diào)度的難度顯著增加,原有研究中,Ng[20]證明了其為NP-Hard問題.為了求解大規(guī)模作業(yè)計劃,把遺傳算法和貪婪插入算法納入迭代重優(yōu)化框架內(nèi),用遺傳算法求解初始作業(yè)計劃,用貪婪插入算法重優(yōu)化延遲到港任務(wù).貪婪插入算法的局部搜索技術(shù)具有快速生成最優(yōu)解的優(yōu)勢,能夠及時更新作業(yè)計劃,響應(yīng)動態(tài)性的要求.

1 動態(tài)調(diào)度問題描述

為了快速響應(yīng)延遲到港任務(wù)需求,以降低對起重機調(diào)度結(jié)果的影響,把集港作業(yè)的調(diào)度期T劃分為m個時段Ti,i∈{1,2,…,m},按照調(diào)度時段Ti的長度,把任務(wù)劃分為多個批次的子任務(wù)φi,在調(diào)度期內(nèi)分批次生成作業(yè)計劃.一旦出現(xiàn)延遲到港任務(wù)的即時請求,根據(jù)其延遲到港時間,把該任務(wù)臨機分配到相應(yīng)的調(diào)度時段內(nèi),與該調(diào)度時段的原有計劃一起執(zhí)行重調(diào)度作業(yè).基于此,提出迭代重優(yōu)化框架,動態(tài)優(yōu)化計劃期內(nèi)的任務(wù),其關(guān)鍵是把延遲到港任務(wù)分配到某一調(diào)度時段內(nèi)執(zhí)行重調(diào)度,同時刷新該調(diào)度時段之后的若干批次作業(yè)計劃.值得注意的是,把調(diào)度時段的劃分和存在延遲任務(wù)的重調(diào)度納入該框架內(nèi),降低了作業(yè)計劃調(diào)整的難度與成本.基于迭代重優(yōu)化框架的動態(tài)優(yōu)化流程如下:

步驟2在零時刻下,向后生成3批作業(yè)計劃Pi,即生成包括調(diào)度時段T1、T2、T3在內(nèi)的3批作業(yè)計劃P1、P2、P3.置i=1.

步驟5生成起重機作業(yè)計劃Pi,記錄完成集合Pi中所有任務(wù)的時刻t*.

動態(tài)優(yōu)化流程的核心是邊作業(yè)邊分配.即同一時刻起重機執(zhí)行已分配的作業(yè)計劃,同時碼頭為剩余的集港作業(yè)分配作業(yè)計劃;此外,不斷檢測是否存在延遲任務(wù),為延遲到港的集裝箱臨機分配作業(yè)計劃,并重優(yōu)化該調(diào)度時段內(nèi)的作業(yè)計劃.以上基于迭代更新的動態(tài)優(yōu)化框架是調(diào)度優(yōu)化模型及其優(yōu)化算法設(shè)計的前提.在該動態(tài)優(yōu)化框架下,每一時刻作業(yè)系統(tǒng)內(nèi)僅存在少量的作業(yè)計劃,不僅降低了計算成本,也保證了在小范圍內(nèi)為延遲到港集裝箱任務(wù)分配作業(yè)計劃的便利性,避免延遲到港的不確定性給系統(tǒng)帶來較大的擾動.

2 調(diào)度優(yōu)化模型

2.1 問題特征分析

本文研究的目標(biāo)是優(yōu)化集港作業(yè)內(nèi)任務(wù)的分配與起重機的作業(yè)序列,最小化任務(wù)完成時間;如果存在延遲到港任務(wù),則對原調(diào)度計劃進行重優(yōu)化,以保證調(diào)度計劃的最優(yōu)性,同時減少作業(yè)計劃調(diào)整所產(chǎn)生的延誤時間.因此,關(guān)鍵優(yōu)化問題:(1)決策每個任務(wù)的執(zhí)行者(起重機);(2)決策每臺起重機執(zhí)行任務(wù)的順序;(3)如果調(diào)度計劃存在干涉,執(zhí)行規(guī)避干涉;(4)如果存在延遲到港任務(wù),執(zhí)行重優(yōu)化.

2.2 變量定義

模型的基本符號及其變量定義如下:

Jd:延遲到港的任務(wù)集合,i,j∈Jd.

K:起重機k集合,k∈K,K={1,2}.

B:貝位b集合,b∈B,B={0,1,…,41}.

Oi,Di:任務(wù)i的起始貝位和目標(biāo)貝位,Oi=0,Di∈B{0,41}.

Tij:起重機作業(yè)任意兩個任務(wù)i、j之間的空載時間,i,j∈J.

Tv:起重機移動一個貝位的時間,Tv=u.

Tii:起重機作業(yè)任務(wù)i,從起始貝位Oi到目標(biāo)貝位Di的移動時間,?i∈J.

Ts:起重機提升或釋放一個集裝箱的服務(wù)時間,Ts=7.5u.

xkij:0-1變量.若起重機k依次作業(yè)任務(wù)i、j取1;否則取0.

yki:0-1變量.若任務(wù)i由起重機k作業(yè)取1;否則取0.

ski,eki:任務(wù)i由起重機k作業(yè)的開始、完成時間.

si,ei:任務(wù)i由起重機作業(yè)的開始、完成時間.

aij:0-1變量.若任務(wù)i的作業(yè)開始時間在任務(wù)j之前取1;否則取0.其中Oi=Oj,?i,j∈J.

bij:0-1變量.若任務(wù)i的作業(yè)完成時間在任務(wù)j之前取1;否則取0.其中Di=Dj,?i,j∈J.

2.3 模型建立

雙起重機調(diào)度問題與車輛路徑優(yōu)化問題的建模機理一致,均有分配約束和序約束,即雙起重機調(diào)度問題的分配約束確定起重機作業(yè)任務(wù)的集合,序約束確定每臺起重機作業(yè)任務(wù)的順序.不同的是,在堆場起重機調(diào)度問題上,需求是同質(zhì)的,起重機也無容量約束.因此,將起重機作業(yè)任務(wù)的開始和完成時間作為求解該問題的主要決策,而該決策過程也是序約束的實現(xiàn)方式;另外,要求每個任務(wù)都被某一起重機作業(yè),即對每一個任務(wù)而言,出度和入度相等且均為1.在不考慮起重機干涉的情況下,雙起重機調(diào)度問題約束為

(1)

(2)

(3)

?k∈K,?j∈J∪Jd

(4)

eki≥ski+Tii+2Ts+(yki-1)M1;

?i∈J∪Jd,?k∈K

(5)

skj≥eki+Tij+(xkij-1)M1;

?i∈J-∪Jd,j∈J+∪Jd,?k∈K

(6)

ski≤ykiM1; ?i∈J-∪Jd,?k∈K

(7)

eki≤ykiM1; ?i∈J-∪Jd,?k∈K

(8)

(9)

式(1)確保有且僅有一個任務(wù)從虛擬起始任務(wù)處之后允許起重機作業(yè),有且僅有一個任務(wù)在虛擬終止任務(wù)處結(jié)束作業(yè);式(2)保證每一個任務(wù)只能由同一臺起重機作業(yè);式(3)確保起重機k作業(yè)任務(wù)i之后,緊接著作業(yè)任務(wù)j;式(4)保證每一個任務(wù)的出度和入度相等,即每一個任務(wù)被起重機作業(yè);式(5)為任務(wù)作業(yè)的開始和完成時間的關(guān)系;式(6)約束起重機作業(yè)任務(wù)的先后關(guān)系;式(7)、(8)為作業(yè)時間上限約束;式(9)為M1的最小值.然而,由于干涉的存在,兩臺起重機的裝卸決策相互依賴,約束(1)～(9)的優(yōu)化結(jié)果可能出現(xiàn)無效解,即所得解包含干涉存在的形式.因此,為了生成無干涉的調(diào)度計劃,基于以上所界定的干涉形式及其規(guī)避規(guī)則,約束兩臺起重機在同一貝位作業(yè)時的依賴關(guān)系,即:

(10)

(11)

aij+aji=1; ?i,j∈J∪Jd,Oi=Oj,i≠j

(12)

bij+bji=1; ?i,j∈J∪Jd,Di=Dj,i≠j

(13)

sj≥si+Ts+(aij-1)M1;

?i,j∈J∪Jd,Oi=Oj,i≠j

(14)

ej≥ei+Ts+(bij-1)M1;

?i,j∈J∪Jd,Di=Dj,i≠j

(15)

決策變量的取值如下:

ski,eki,si,ei≥0; ?i∈J∪Jd,?k∈K

xkij,yki,aij,bij∈{0,1}; ?i,j∈J∪Jd

式(10)、(11)為任務(wù)作業(yè)的開始和完成時間;式(12)、(13)界定出現(xiàn)干涉情況,限定任務(wù)i或任務(wù)j其中一個完成時間較晚;干涉規(guī)避的同步約束如式(14)、(15)所示,限定位于同一貝位的兩個任務(wù)作業(yè)開始和完成時間之間的依賴關(guān)系.

2.4 下界推導(dǎo)

雙起重機調(diào)度問題求解的關(guān)鍵是計算單臺起重機的作業(yè)序列,Vis等[21]提出了一種基于動態(tài)規(guī)劃的最優(yōu)下界推導(dǎo)方法,其目標(biāo)是找到一條包含所有任務(wù)的起重機運行最短路徑.基于Vis等[21]的下界推導(dǎo)方法,文獻(xiàn)[5]證明了雙起重機作業(yè)完成時間近似等于單臺起重機作業(yè)所有任務(wù)時間(travel time)的一半.本文提出一種考慮兩臺起重機作業(yè)負(fù)載均衡的下界推導(dǎo)方法,使得所求的任務(wù)完成時間更接近所有任務(wù)作業(yè)時間的一半,縮小下界值與最優(yōu)值之間的差距.增加整數(shù)決策變量pki,表示起重機k作業(yè)任務(wù)i的次序,即為序約束的關(guān)鍵決策,建立松弛模型計算下界flb.目標(biāo)函數(shù)(16)是最小化兩臺起重機作業(yè)均衡條件下的完成時間,即下界flb.

(16)

(17)

(18)

pki-pkj+M2xkij≤M2-1;

?i∈J-,?j∈J,?k∈K

(19)

1≤pki≤M2; ?i∈J-,?k∈K

(20)

M2=N

(21)

式(17)表示起重機在虛擬開始任務(wù)處作業(yè),且任務(wù)必須分配給兩臺起重機;式(18)表示起重機作業(yè)任務(wù)量約束,為了均衡每臺起重機的作業(yè)負(fù)載;式(19)、(20)表示每臺起重機作業(yè)任務(wù)的序約束,用于消除子回路;式(21)表示M2的一個取值.

3 迭代重優(yōu)化框架及其算法

3.1 迭代重優(yōu)化框架

為了求解考慮集卡延遲到港的堆場起重機動態(tài)調(diào)度問題,在迭代更新的動態(tài)優(yōu)化流程基礎(chǔ)上,提出一種動態(tài)處理延遲到港任務(wù)的方法——迭代重優(yōu)化框架及其算法.首先,在所劃分的時段Ti內(nèi),依次生成對應(yīng)批次任務(wù)的起重機作業(yè)計劃;如果起重機在作業(yè)之前無延遲到港任務(wù),則執(zhí)行原有作業(yè)計劃.一旦存在延遲到港任務(wù),原有作業(yè)計劃變得次優(yōu)甚至不可行.因此,根據(jù)起重機作業(yè)進度和任務(wù)延遲到港時間,對特定批次任務(wù)進行重優(yōu)化.重優(yōu)化的前提是,定位延遲到港任務(wù)的到港時間落在哪個調(diào)度時段內(nèi),即延遲任務(wù)屬于哪一批次的作業(yè)計劃.然后,把延遲到港任務(wù)和該批次原有任務(wù)一起執(zhí)行重優(yōu)化生成更新的作業(yè)計劃.簡而言之,只要存在延遲到港任務(wù),就會生成一批更新的作業(yè)計劃.

基于此,設(shè)計兩個優(yōu)化算法支撐迭代重優(yōu)化框架:遺傳算法用于生成各時段所對應(yīng)批次任務(wù)的作業(yè)計劃;貪婪插入算法用于重優(yōu)化帶延遲到港批次任務(wù)的作業(yè)計劃,生成更新的作業(yè)計劃,應(yīng)對動態(tài)性.貪婪插入算法具有快速搜索的特征,能夠在遺傳算法求解結(jié)果的基礎(chǔ)上,把延遲到港任務(wù)插入原有作業(yè)計劃序列中最合適的位置.迭代重優(yōu)化框架及其算法構(gòu)成如圖1所示.以上算法的構(gòu)成邏輯及其形成的閉環(huán)優(yōu)化策略,其益處體現(xiàn)在3個方面:首先,遺傳算法僅僅作用于特定批次的任務(wù)集合而不是全部任務(wù)集合,因此,搜索空間限定在較小的范圍內(nèi),增加了搜索到全局最優(yōu)解的可能性[22];其次,由于原有作業(yè)計劃僅限定在某一批次任務(wù),針對延遲到港任務(wù),貪婪插入算法能夠在其有限鄰域內(nèi)快速生成最優(yōu)解,完成對應(yīng)批次任務(wù)的重優(yōu)化;最后,考慮延遲到港任務(wù)的重優(yōu)化是基于某個批次的作業(yè)計劃,重優(yōu)化后生成的作業(yè)計劃與原有作業(yè)計劃形成較為平穩(wěn)的過渡,避免由于作業(yè)計劃大范圍調(diào)整對起重機作業(yè)產(chǎn)生較大的擾動.

圖1 迭代重優(yōu)化框架及其算法

3.2 算法設(shè)計

(1)編碼方式和解碼策略

采用隨機排列編碼向量表示雙起重機作業(yè)序列中的任務(wù),即染色體上每一位元素(等位基因)都是互異的,代表一個作業(yè)任務(wù),如圖2所示.在解碼過程中,根據(jù)染色體上等位基因的排列順序依次確定起重機的作業(yè)序列.

圖2 雙起重機作業(yè)序列的染色體編碼結(jié)構(gòu)

遺傳算法的解碼策略是將編碼向量轉(zhuǎn)化為兩臺起重機的作業(yè)序列,以便利用適應(yīng)度函數(shù)計算編碼向量對應(yīng)的評價值.根據(jù)雙起重機作業(yè)的順序約束和干涉規(guī)避約束,將編碼向量轉(zhuǎn)換為可行的雙起重機作業(yè)序列,并使遺傳算法的交叉算子和變異算子在全局范圍內(nèi)尋優(yōu),最終確定最優(yōu)解.以某一批次的作業(yè)任務(wù)為例,說明解碼策略及其對應(yīng)的算法,如算法1所示.

算法1基于隨機排列編碼的解碼策略

輸入：(1)參數(shù):[J,K,Oi,Di];

(2)隨機排列序列:S0.

輸出：(1)Sk:最優(yōu)雙起重機作業(yè)計劃,?k∈K;

(2)[ski,eki]:作業(yè)計劃中,任務(wù)作業(yè)開始、完成時間,?i∈J,?k∈K;

(3)f:完成時間(makespan).

步驟1初始化:令f為足夠大的實數(shù);ski、eki置零.

步驟2forxinX.其中,X=|S0|.

步驟2.3檢測干涉的存在與執(zhí)行規(guī)避.

步驟2.4分別計算兩臺起重機作業(yè)序列對應(yīng)的完成時間f1*、f2*.

步驟2.5令f*=max(f1*,f2*).

步驟3輸出f、Sk、ski、eki,i∈J,k∈K.

(2)貪婪插入算法

一旦存在延遲到港任務(wù)(即時請求),臨機分配該任務(wù)到相近的調(diào)度時段內(nèi),用貪婪插入算法重優(yōu)化該時段內(nèi)原有作業(yè)計劃.貪婪插入示意如圖3所示,把新增任務(wù)依據(jù)完成時間增量最小的原則插入原有序列的相應(yīng)位置.若存在多個新任務(wù),則按照移動時間Tii從小到大進行遞增排序,依次執(zhí)行貪婪插入操作,如算法2所示.

圖3 延遲到港任務(wù)重優(yōu)化示意圖

算法2迭代重優(yōu)化框架下貪婪插入算法

輸入：(1)參數(shù):[J,K,Oi,Di];

(2)原有作業(yè)序列:Skp,?k∈K,p∈Pi={pi,pi+1,pi+2};

(3)當(dāng)前時刻:τ.

輸出：(1)Pp:更新后的第p批次作業(yè)計劃,?p∈Pi;

(2)[ski,eki]:作業(yè)計劃中,批次p作業(yè)的開始和完成時間,?i∈J,?k∈K.

變量：Bp,Ep:批次p作業(yè)計劃的開始、完成時間;

δ:任務(wù)開始執(zhí)行前,允許變更計劃的最大持續(xù)時間.

步驟1零時刻下,產(chǎn)生3批作業(yè)序列,即初始作業(yè)計劃Pp,完成時間為Ep,p∈{1,2,3}.令m=1.

步驟2起重機執(zhí)行作業(yè)計劃Pm.

步驟3在τ∈(Bm,Em)下,向后生成1批作業(yè)計劃Pm+3.

步驟4若延遲到港集裝箱的到港時間落在第p批次作業(yè)計劃中,即τ

步驟4.1把延遲到港任務(wù)集合N(j∈N)按照移動時間Tjj遞增排序,依次執(zhí)行插入操作.取l=arg mineki,把任務(wù)l插入序列Skp中,使完成時間的增量最小.

步驟4.2更新任務(wù)序列,Skp←Skp∪{l}.

步驟6生成重優(yōu)化后的作業(yè)計劃Pp,p={m+1,m+2}.

步驟7當(dāng)τ≥Bm+1時,起重機執(zhí)行作業(yè)計劃Pm+1;令m←m+1,若m≤3,返回步驟3;否則,結(jié)束重優(yōu)化.

4 數(shù)值實驗

設(shè)計多組算例驗證堆場起重機調(diào)度模型和松弛模型的有效性、算法1的計算性能以及算法2的重優(yōu)化性能.計算在Windows 10操作系統(tǒng)上用Python語言編程實現(xiàn),計算機配置:Intel(R)Core(TM)i7-10510 CPU @1.8 GHz,16 GB RAM.用CPLEX作為模型求解的分支切割(branch-and-cut)求解器.

數(shù)據(jù)來源于自動化碼頭作業(yè)數(shù)據(jù)生成平臺(https://www.instances.de/dfg/),分別生成多組小規(guī)模算例(N≤12)和大規(guī)模算例(N≤50).箱區(qū)規(guī)模為40貝位×6棧×5層.堆場起重機移動速度為3 m/s,即起重機在4 s(u)內(nèi)通過一個貝位.另外,設(shè)起重機抓取或釋放一個集裝箱需要30 s(7.5u).對于起重機而言,其調(diào)度主要關(guān)注進口箱任務(wù)的起始貝位(Oi)和目標(biāo)貝位(Di).由實例生成器導(dǎo)出的小規(guī)模算例(N=5)見表1.

表1 算例示例(N=5)

4.1 實驗設(shè)計

實驗設(shè)計的目的及其相應(yīng)設(shè)置見表2.

表2 實驗設(shè)置

4.2 實驗結(jié)果與分析

4.2.1 模型與算法有效性驗證 模型和算法1的規(guī)劃結(jié)果見表3.其中,flb表示松弛模型所計算的松弛解.結(jié)果顯示,松弛解flb與最優(yōu)解f1的最大誤差為3.91%,說明松弛模型為該數(shù)學(xué)規(guī)劃問題提供了一個良好下界,可作為模型和算法優(yōu)化性能的評判基準(zhǔn).算法1與CPLEX所求得最優(yōu)解之間的平均誤差僅為0.49%;當(dāng)任務(wù)規(guī)模增加到12時,CPLEX無法在可接受的時間內(nèi)求得最優(yōu)解,但算法1能夠在較短時間內(nèi)求得近似最優(yōu)解.由此可見,算法1在求解雙起重機調(diào)度問題上具備良好性能.此外,雙起重機作業(yè)路徑如圖4所示,兩臺起重機在同一時間f同一貝位b下的(重載)路徑無交點,表明模型的干涉規(guī)避約束有效.

4.2.2 算法參數(shù)調(diào)節(jié)與性能驗證 為研究算法的參數(shù)取值對優(yōu)化結(jié)果的影響,在[0,1]以步長0.1分別取交叉概率Pc和變異概率Pm,組合后獲得非連續(xù)分布解的變化規(guī)律,如圖5的等值線所示.由于算例結(jié)構(gòu)的一致性,通過分析算法1在Pc和Pm組合下解的演變規(guī)律,限定參數(shù)的取值范圍,以此作為其他實驗中參數(shù)選擇的依據(jù),避免大范圍參數(shù)調(diào)節(jié)造成的冗余計算影響求解效率.

(a)最小值

為進一步驗證算法1的計算性能,分別選取任務(wù)規(guī)模為30和50進行測試.不失一般性地,取不同的交叉和變異概率組合,減小固定交叉和變異概率對求解結(jié)果的局限性,計算結(jié)果見表4、5.計算結(jié)果表明,算法求解結(jié)果與松弛模型下界之間的平均誤差均不超過2%;另外,圖6為算法求解任務(wù)規(guī)模為50的收斂曲線,在150代內(nèi)收斂到最優(yōu)目標(biāo)值.因此,在優(yōu)化結(jié)果和計算時間兩方面驗證了算法具備的良好優(yōu)化性能.

表4 大規(guī)模算例下算法1的規(guī)劃結(jié)果(N=30)

表5 大規(guī)模算例下算法1的規(guī)劃結(jié)果(N=50)

圖6 算法1的收斂圖

4.2.3 迭代重優(yōu)化框架有效性驗證與分析 在迭代重優(yōu)化框架下,把某一時間段內(nèi)的集港作業(yè)劃分為若干調(diào)度時段,使出口箱任務(wù)分別在相應(yīng)的調(diào)度時段內(nèi)生成作業(yè)計劃,一旦出現(xiàn)延遲到港集裝箱的即時請求,可臨機分配至與到港時間最近的調(diào)度時段內(nèi).為驗證該框架的有效性,依次取不同長度的調(diào)度時段和不同延遲到港的箱量,求解相應(yīng)的規(guī)劃結(jié)果.

(1)調(diào)度時段長度對規(guī)劃結(jié)果的影響

調(diào)度時段長度T分別取M、900u、600u和300u,其中M表示不對集港作業(yè)進行拆分.規(guī)劃結(jié)果如表6、圖7所示,可見:調(diào)度時段長度越小,作業(yè)完成時間越長,但計算時間明顯縮短.因此,均衡解的質(zhì)量與計算時間,選取合適的調(diào)度時段長度有利于提高碼頭制訂作業(yè)計劃的效率.

表6 調(diào)度時段長度對規(guī)劃結(jié)果的影響

(a)作業(yè)完成時間

(2)延遲到港的箱量分析

定義延遲程度β表示某一交箱時段內(nèi)延遲到港箱量Nd與原始箱量No的比值,即β=Nd/No.以調(diào)度時段T為基準(zhǔn),用算法1生成基礎(chǔ)作業(yè)計劃,調(diào)用算法2對延遲到港任務(wù)執(zhí)行重調(diào)度,計算結(jié)果如圖8所示.

圖8 延遲到港箱量對規(guī)劃結(jié)果的影響

結(jié)果顯示,延遲到港箱量占比β越大,作業(yè)時間的增量Δ越大;而隨著調(diào)度時段T的減小,這一影響逐漸弱化.其原因在于,隨著延遲任務(wù)的數(shù)量增加,重調(diào)度對原作業(yè)計劃的擾動增大,可行解數(shù)量減少(或增加)的變化幅度增大;而縮短調(diào)度時段,有利于為延遲到港任務(wù)分配更適合的調(diào)度時段,從而增加重調(diào)度結(jié)果需求到最優(yōu)解的可能性.

5 結(jié) 語

自動化集裝箱碼頭的堆場作業(yè)受諸多外部不確定因素的干擾,制約作業(yè)效率的提升,如交通擁堵、雨雪天氣影響集卡的到達(dá)時間,對原有作業(yè)計劃產(chǎn)生擾動.針對集卡到港時間延遲的堆場起重機動態(tài)調(diào)度問題,本文提出了迭代重優(yōu)化框架,把集港作業(yè)的調(diào)度期劃分為多個時段,出口箱任務(wù)分別在相應(yīng)的時段內(nèi)被安排作業(yè),一旦出現(xiàn)延遲到港集裝箱的即時請求,可臨機分配至與到港時間鄰近的時段內(nèi)執(zhí)行重調(diào)度.借助自動化碼頭作業(yè)數(shù)據(jù)生成平臺,構(gòu)造小規(guī)模和大規(guī)模算例,驗證本文提出的模型和算法的有效性.通過結(jié)果分析驗證了模型和算法的有效性,并提出兩方面有益于碼頭運作優(yōu)化的管理啟示.

一方面,在計劃制訂之前,若待作業(yè)的任務(wù)量較少,調(diào)度人員可增大調(diào)度時段長度,以保證解的質(zhì)量,縮短作業(yè)的持續(xù)時長;若任務(wù)量較多,可適當(dāng)減小調(diào)度時段長度,從而縮短計算時間以提高計算效率.另一方面,碼頭運營者需及時與客戶溝通,獲取集卡的行駛狀況、預(yù)計到達(dá)堆場的時間等信息,為可能延遲到港的集卡提前部署應(yīng)對策略:當(dāng)延遲到港箱量占比較小時,可適當(dāng)增大調(diào)度時段長度,保證整體作業(yè)水平;當(dāng)延遲到港箱量占比較大時,可減小調(diào)度時段長度從而降低重調(diào)度對作業(yè)系統(tǒng)的擾動.

本文研究還存在一些不足,即便是分段調(diào)度提供了應(yīng)對集卡作業(yè)不確定性的方式,但難以快速消除集卡到港動態(tài)性對系統(tǒng)的擾動.未來的研究可結(jié)合強化學(xué)習(xí)方法,在歷史作業(yè)數(shù)據(jù)中學(xué)習(xí)相關(guān)場景下的調(diào)度經(jīng)驗,從而及時、準(zhǔn)確地調(diào)用相應(yīng)策略生成或調(diào)整作業(yè)計劃.