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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

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

2.1 問題特征分析

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

2.2 變量定義

模型的基本符號(hào)及其變量定義如下:

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

K:起重機(jī)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:起重機(jī)作業(yè)任意兩個(gè)任務(wù)i、j之間的空載時(shí)間,i,j∈J.

Tv:起重機(jī)移動(dòng)一個(gè)貝位的時(shí)間,Tv=u.

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

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

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

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

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

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

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

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

2.3 模型建立

雙起重機(jī)調(diào)度問題與車輛路徑優(yōu)化問題的建模機(jī)理一致,均有分配約束和序約束,即雙起重機(jī)調(diào)度問題的分配約束確定起重機(jī)作業(yè)任務(wù)的集合,序約束確定每臺(tái)起重機(jī)作業(yè)任務(wù)的順序.不同的是,在堆場(chǎng)起重機(jī)調(diào)度問題上,需求是同質(zhì)的,起重機(jī)也無容量約束.因此,將起重機(jī)作業(yè)任務(wù)的開始和完成時(shí)間作為求解該問題的主要決策,而該決策過程也是序約束的實(shí)現(xiàn)方式;另外,要求每個(gè)任務(wù)都被某一起重機(jī)作業(yè),即對(duì)每一個(gè)任務(wù)而言,出度和入度相等且均為1.在不考慮起重機(jī)干涉的情況下,雙起重機(jī)調(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)確保有且僅有一個(gè)任務(wù)從虛擬起始任務(wù)處之后允許起重機(jī)作業(yè),有且僅有一個(gè)任務(wù)在虛擬終止任務(wù)處結(jié)束作業(yè);式(2)保證每一個(gè)任務(wù)只能由同一臺(tái)起重機(jī)作業(yè);式(3)確保起重機(jī)k作業(yè)任務(wù)i之后,緊接著作業(yè)任務(wù)j;式(4)保證每一個(gè)任務(wù)的出度和入度相等,即每一個(gè)任務(wù)被起重機(jī)作業(yè);式(5)為任務(wù)作業(yè)的開始和完成時(shí)間的關(guān)系;式(6)約束起重機(jī)作業(yè)任務(wù)的先后關(guān)系;式(7)、(8)為作業(yè)時(shí)間上限約束;式(9)為M1的最小值.然而,由于干涉的存在,兩臺(tái)起重機(jī)的裝卸決策相互依賴,約束(1)～(9)的優(yōu)化結(jié)果可能出現(xiàn)無效解,即所得解包含干涉存在的形式.因此,為了生成無干涉的調(diào)度計(jì)劃,基于以上所界定的干涉形式及其規(guī)避規(guī)則,約束兩臺(tái)起重機(jī)在同一貝位作業(yè)時(shí)的依賴關(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è)的開始和完成時(shí)間;式(12)、(13)界定出現(xiàn)干涉情況,限定任務(wù)i或任務(wù)j其中一個(gè)完成時(shí)間較晚;干涉規(guī)避的同步約束如式(14)、(15)所示,限定位于同一貝位的兩個(gè)任務(wù)作業(yè)開始和完成時(shí)間之間的依賴關(guān)系.

2.4 下界推導(dǎo)

雙起重機(jī)調(diào)度問題求解的關(guān)鍵是計(jì)算單臺(tái)起重機(jī)的作業(yè)序列,Vis等[21]提出了一種基于動(dòng)態(tài)規(guī)劃的最優(yōu)下界推導(dǎo)方法,其目標(biāo)是找到一條包含所有任務(wù)的起重機(jī)運(yùn)行最短路徑.基于Vis等[21]的下界推導(dǎo)方法,文獻(xiàn)[5]證明了雙起重機(jī)作業(yè)完成時(shí)間近似等于單臺(tái)起重機(jī)作業(yè)所有任務(wù)時(shí)間(travel time)的一半.本文提出一種考慮兩臺(tái)起重機(jī)作業(yè)負(fù)載均衡的下界推導(dǎo)方法,使得所求的任務(wù)完成時(shí)間更接近所有任務(wù)作業(yè)時(shí)間的一半,縮小下界值與最優(yōu)值之間的差距.增加整數(shù)決策變量pki,表示起重機(jī)k作業(yè)任務(wù)i的次序,即為序約束的關(guān)鍵決策,建立松弛模型計(jì)算下界flb.目標(biāo)函數(shù)(16)是最小化兩臺(tái)起重機(jī)作業(yè)均衡條件下的完成時(shí)間,即下界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)表示起重機(jī)在虛擬開始任務(wù)處作業(yè),且任務(wù)必須分配給兩臺(tái)起重機(jī);式(18)表示起重機(jī)作業(yè)任務(wù)量約束,為了均衡每臺(tái)起重機(jī)的作業(yè)負(fù)載;式(19)、(20)表示每臺(tái)起重機(jī)作業(yè)任務(wù)的序約束,用于消除子回路;式(21)表示M2的一個(gè)取值.

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

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

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

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

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

3.2 算法設(shè)計(jì)

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

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

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

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

算法1基于隨機(jī)排列編碼的解碼策略

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

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

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

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

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

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

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

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

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

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

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

(2)貪婪插入算法

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

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

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

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

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

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

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

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

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

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

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

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

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

4 數(shù)值實(shí)驗(yàn)

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

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

表1 算例示例(N=5)

4.1 實(shí)驗(yàn)設(shè)計(jì)

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

表2 實(shí)驗(yàn)設(shè)置

4.2 實(shí)驗(yàn)結(jié)果與分析

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

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

(a)最小值

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

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

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

圖6 算法1的收斂圖

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

(1)調(diào)度時(shí)段長(zhǎng)度對(duì)規(guī)劃結(jié)果的影響

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

表6 調(diào)度時(shí)段長(zhǎng)度對(duì)規(guī)劃結(jié)果的影響

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

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

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

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

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

5 結(jié) 語

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

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

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