丁 一,王聰
(上海海事大學(xué)物流研究中心,上海 201306)
在全球經(jīng)濟(jì)一體化的大趨勢(shì)下,各國(guó)集裝箱貨物的海運(yùn)量呈爆發(fā)式增長(zhǎng),世界集裝箱船隊(duì)的數(shù)量也在不斷增加,船舶也逐漸向大型化、專業(yè)化和標(biāo)準(zhǔn)化發(fā)展,一方面提高了船公司的規(guī)模效益,另一方面給碼頭帶來了更大的挑戰(zhàn),傳統(tǒng)集裝箱碼頭也正逐步向半自動(dòng)化和全自動(dòng)化過渡。
自動(dòng)化碼頭在傳統(tǒng)碼頭的基礎(chǔ)上,優(yōu)化了工藝布局。如圖1 所示,自動(dòng)化碼頭將傳統(tǒng)碼頭平行于海岸線的堆場(chǎng)箱區(qū)布局改進(jìn)成垂直于海岸線的堆場(chǎng)箱區(qū)布局,同時(shí)在每個(gè)箱區(qū)增設(shè)了固定的發(fā)箱點(diǎn),解決了傳統(tǒng)碼頭發(fā)箱區(qū)域規(guī)劃紊亂、發(fā)箱效率低下的問題。在堆場(chǎng)設(shè)備上,自動(dòng)化碼頭采用了軌道吊(Rail-Mounted Gantry crane,RMG),替代了傳統(tǒng)碼頭的輪胎吊(Rubber-Tyred Gantry crane,RTG),RTG 可以跨箱區(qū)作業(yè),但在多個(gè)RTG 作業(yè)時(shí),容易在公共作業(yè)區(qū)域發(fā)生沖突,而RMG則是各箱區(qū)專用,發(fā)生的沖突較少。
圖1 傳統(tǒng)碼頭與自動(dòng)化碼頭箱區(qū)布局Fig.1 Block layouts of traditional terminal and automated terminal
在當(dāng)今碼頭集裝箱貨物運(yùn)輸?shù)母鱾€(gè)流程中,配載作為其中的核心環(huán)節(jié)之一,對(duì)自動(dòng)化碼頭的作業(yè)效率和安全、船舶在港時(shí)間以及貨方收益等方面都有著直接影響。配載作業(yè)流程如圖2 所示,一般分為兩個(gè)階段:第一階段是船舶公司制定的預(yù)配載計(jì)劃(分類/詳細(xì)的預(yù)配載箱位圖);第二階段是將預(yù)配載計(jì)劃作為輸入數(shù)據(jù),由碼頭運(yùn)營(yíng)商制定的碼頭配載計(jì)劃。
圖2 配載作業(yè)流程Fig.2 Flow chart of stowage operation
目前大部分的配載優(yōu)化研究主要是從船公司和碼頭這兩個(gè)方面考慮的。
船公司方面注重如何減少多港口運(yùn)輸裝卸所導(dǎo)致的翻箱問題以及船舶航行中的安全問題,如計(jì)明軍等[1]圍繞配載方式進(jìn)行分析,總結(jié)四種配載方式在船舶穩(wěn)性、強(qiáng)度和吃水差等方面的優(yōu)缺點(diǎn),以此來分析減少翻箱率的方法;而樂美龍等[2]考慮翻箱和橋吊的作業(yè)時(shí)間,并以此建立整數(shù)規(guī)劃模型,使得翻箱次數(shù)最少和橋吊工作時(shí)間跨度最小。
在考慮船舶靠泊時(shí)間成本因素后,Serban 等[3]在待卸集裝箱數(shù)量和箱區(qū)的初始狀態(tài)已知的情況下,以最小化場(chǎng)橋的搬運(yùn)時(shí)間總和為目標(biāo),利用遺傳算法確定集裝箱配載計(jì)劃;而田維等[4]研究船舶裝箱排序問題,將最小化裝船時(shí)間以及翻倒箱時(shí)間成本作為目標(biāo),對(duì)不同規(guī)模案例進(jìn)行求解,獲得問題的精確解;Roberti等[5]則在滿足許多操作限制的同時(shí),盡量減少在港口裝卸集裝箱的時(shí)間,使得集裝箱最大限度地減少不必要的配載作業(yè)。
為了提高集裝箱航線動(dòng)態(tài)裝載自動(dòng)調(diào)度的能力,Wang[6]提出了一種基于關(guān)聯(lián)規(guī)則信息的集裝箱航線動(dòng)態(tài)裝載自動(dòng)調(diào)度方法;鄭斐峰等[7]針對(duì)翻箱費(fèi)用和堆棧使用費(fèi)用,以船舶裝載穩(wěn)定性作為約束條件,求得最小化費(fèi)用的精確解;黃森佳等[8]綜合考慮集裝箱船舶縱向強(qiáng)度、岸橋作業(yè)安全距離和集裝箱倒箱量對(duì)裝船作業(yè)時(shí)間的影響,構(gòu)建了以裝船作業(yè)時(shí)間最短為目標(biāo)的配載優(yōu)化模型,引入岸橋作業(yè)均衡參數(shù),并使用遺傳算法對(duì)模型進(jìn)行求解;孫俊清等[9]以最小化集裝箱班輪在所有??扛劭诘目偟瓜淞繛槟繕?biāo),將船舶穩(wěn)性作為約束條件,使用改進(jìn)的遺傳算法進(jìn)行求解,并通過仿真實(shí)驗(yàn)比較了兩種配載方案。
碼頭方面考慮裝船作業(yè)時(shí)間的縮短以及配載結(jié)果保證船舶航行安全,如:黎明等[10]結(jié)合集裝箱的裝載位置,以集裝箱堆場(chǎng)的翻箱率、船舶卸載時(shí)的翻箱率以及裝船后的穩(wěn)性為目標(biāo),建立了裝船順序的多目標(biāo)規(guī)劃模型;張兆民[11]通過“關(guān)鍵相鄰柜口”的配載計(jì)劃優(yōu)化、作業(yè)拖車數(shù)量的增加和分級(jí)堆場(chǎng)堆存等操作策略的執(zhí)行,可有效控制“關(guān)鍵相鄰柜口”的作業(yè)時(shí)間,縮短船舶在港作業(yè)時(shí)間;祝慧靈等[12]以翻箱問題為切入點(diǎn),致力于保證配載計(jì)劃完成的前提下,建立三種提箱順序優(yōu)化策略來達(dá)到翻箱量最小的目標(biāo);Zhao 等[13]考慮堆場(chǎng)周轉(zhuǎn)、輪胎吊跨箱區(qū)作業(yè)和輪胎吊移動(dòng),基于配載原理和約束,建立多目標(biāo)優(yōu)化模型,建立蒙特卡洛樹搜索(Monte Carlo Tree Search,MCTS)方法,根據(jù)搜索樹設(shè)計(jì)可拓、可選等5 個(gè)步驟及相應(yīng)策略;李隋凱等[14]針對(duì)帶中轉(zhuǎn)排的自動(dòng)化碼頭出口箱進(jìn)箱選位問題,提出了一種兩倍狀態(tài)多階段動(dòng)態(tài)規(guī)劃算法;周宇濤等[15]通過運(yùn)用邏輯算法,設(shè)置配載策略和參數(shù),快速進(jìn)行深度運(yùn)算提高配載精度,更好地滿足船公司差異化配載要求。
兩個(gè)角度研究的考慮因素、模型和方法如表1所示。
表1 不同角度船舶配載考慮因素、模型和方法對(duì)比Tab.1 Comparison of ship stowage considerations,models and methods from different perspectives
通過上述的文獻(xiàn)分析可知,目前大多數(shù)的研究集中于從船公司的角度出發(fā),考慮常規(guī)約束(吃水差、穩(wěn)性和船體強(qiáng)度約束等)、翻箱問題和裝船時(shí)間等,從碼頭角度出發(fā)的研究較少,考慮的也多是翻箱問題、堆場(chǎng)堆存問題和配載裝船時(shí)間等;但由于自動(dòng)化碼頭箱區(qū)的發(fā)箱點(diǎn)固定,需要保證各設(shè)備的合理高效使用,避免出現(xiàn)設(shè)備等待擁擠的情況,只考慮這些問題無法保證集裝箱的高效裝卸,也無法最大化利用自動(dòng)化碼頭的設(shè)備資源。因此,本文在考慮常規(guī)約束的基礎(chǔ)下,引入箱區(qū)作業(yè)均衡性這一因素,從碼頭的角度出發(fā),對(duì)自動(dòng)化碼頭的裝船配載作業(yè)來進(jìn)行分析研究。
從自動(dòng)化碼頭的角度來說,配載問題一般可以分成三個(gè)子問題。結(jié)合右側(cè)圖3 自動(dòng)化碼頭配載作業(yè)圖來看,第一個(gè)是集裝箱由外集卡裝載通過閘門,進(jìn)入堆場(chǎng)箱區(qū),在哪個(gè)箱區(qū)箱位落位的箱位問題;第二個(gè)是堆場(chǎng)待裝集裝箱裝船的先后順序問題,即將集裝箱從堆場(chǎng)運(yùn)至岸側(cè)橋吊工作區(qū)的先后順序問題;最后一個(gè)是集裝箱分配的船箱位問題,即集裝箱在船上放置的位置問題。從位置①-②-③-④-⑤-⑥,即算完成配載計(jì)劃中一個(gè)待裝集裝箱的裝船作業(yè)任務(wù)。
圖3 配載作業(yè)圖Fig.3 Stowage operation diagram
首先,對(duì)于集裝箱的箱區(qū)箱位問題來說,無非就是如何極大化地方便裝船作業(yè),并且充分利用到堆場(chǎng)的自動(dòng)化設(shè)備資源,確保在裝船作業(yè)過程中設(shè)備閑置率較低,提升堆場(chǎng)集裝箱作業(yè)效率。
其次,是裝船先后順序問題,顧名思義就是決定堆場(chǎng)箱區(qū)待裝集裝箱裝載到運(yùn)輸船舶的排序問題。在裝船作業(yè)順序問題上,不得不提到翻箱問題,裝船過程中某些集裝箱存放在箱區(qū)的其他集裝箱下方,由于待裝船舶的到來,如果下方集裝箱需要優(yōu)先提箱,則會(huì)先移動(dòng)該集裝箱的上方集裝箱,再提取下方的集裝箱。具體的翻箱過程可結(jié)合圖4,描述如下:堆場(chǎng)箱區(qū)集裝箱i位于同貝同列不同層的集裝箱j的上方,任務(wù)1 是將箱區(qū)集裝箱i由A 點(diǎn)運(yùn)輸至船舶B 點(diǎn)上,任務(wù)2 是將箱區(qū)集裝箱j由C 點(diǎn)運(yùn)輸至船舶D 點(diǎn)上,由于配載船圖上顯示集裝箱i在船舶的箱位仍位于集裝箱j的上方,所以要先執(zhí)行任務(wù)2,而且需要先將集裝箱i移動(dòng)到箱區(qū)其他位置,這就形成了一次翻箱。
圖4 翻箱示意圖Fig.4 Schematic diagram of rehandle
而對(duì)于集裝箱分配的船箱位問題,就是解決集裝箱離場(chǎng)后的去處,即安排在哪一船舶箱位的問題,以便于在下一個(gè)卸貨港減少翻箱量,快速完成卸貨任務(wù)。
從圖5可以得知,配載問題作業(yè)時(shí)間是由翻箱時(shí)間、RMG提箱時(shí)間、自動(dòng)牽引車(Automated Guided Vehicle,AGV)運(yùn)輸時(shí)間和橋吊(Quay Crane,QC)作業(yè)時(shí)間組成的。配載問題的目標(biāo)在于減少?gòu)南鋮^(qū)箱位到船舶箱位的作業(yè)時(shí)間,從而減少船舶在港的停留時(shí)間,節(jié)約成本。
圖5 配載流程Fig.5 Flow chart of stowage
另外,在自動(dòng)化碼頭堆場(chǎng)中,如果同一時(shí)間段內(nèi)箱區(qū)的裝卸作業(yè)量相差過大時(shí),就會(huì)導(dǎo)致箱區(qū)作業(yè)不均衡問題:一方面,對(duì)于裝卸量偏大的箱區(qū),這些箱區(qū)的軌道吊連續(xù)工作時(shí)間過長(zhǎng),軌道吊的故障率上升,而且由于箱區(qū)的軌道吊作業(yè)能力有限,一旦提存箱的指令過于集中,可能會(huì)導(dǎo)致軌道吊作業(yè)沖突;另一方面,對(duì)于裝卸量偏小的箱區(qū),閑置的軌道吊沒有得到充分利用,單位成本上升。因此,對(duì)于箱區(qū)作業(yè)量均衡的研究很有必要。
i,j為待裝集裝箱號(hào),i=1,2,…,I,j=1,2,…J;k為貝位號(hào),k=1,2,…,K;c為列號(hào),c=1,2,…,C;r為層號(hào),r=1,2,…,R;b1為箱區(qū)編號(hào),b1=1,2,…,B1;b2為箱區(qū)區(qū)塊編號(hào),b2=1,2,…,B2;b3為小箱區(qū)編號(hào),b3=1,2,…,B3;b為箱區(qū)具體編號(hào),b=(b1,b2,b3);p為待裝集裝箱的船箱位,p=1,2,…,P;εp為箱位p的開始裝箱時(shí)間;U(p)為位于船舶箱位p(k,c,r)同貝同列上一層p(k,c,r+1)的箱位;t為表示t-1到t的時(shí)間間隔,t=1,2,…,T,?t∈T;wi為集裝箱i的重量;nbt為t時(shí)間段內(nèi)箱區(qū)b已完成場(chǎng)到船任務(wù)的集裝箱數(shù)量;Δi為與集裝箱i同一堆棧的上層集裝箱集合;α為箱區(qū)一個(gè)待裝集裝箱不考慮翻箱的場(chǎng)橋平均作業(yè)時(shí)間(場(chǎng)橋就位和取箱平均時(shí)間);βbt為t時(shí)間段內(nèi)箱區(qū)b作業(yè)量與各箱區(qū)平均作業(yè)量的差值比例值,其計(jì)算式為βbt=為t時(shí)間段內(nèi)所有箱區(qū)集裝箱作業(yè)量的平均值;ρ(ρ>0)為箱區(qū)作業(yè)不均衡判定比例值;σ1為堆場(chǎng)箱區(qū)一次翻箱時(shí)間;σ2為不均衡箱區(qū)的集裝箱單位等待懲罰時(shí)間;W為船舶貝位中單列允許的集裝箱最大載重量;τip為集裝箱i從場(chǎng)箱位到船舶箱位p(k,c,r)的水平運(yùn)輸時(shí)間;BLTip為安排到船箱位p的在場(chǎng)箱i在箱區(qū)的離開時(shí)間,BLTip=εp-τip,其中?i∈N,p∈P;φbt為箱區(qū)b在時(shí)間段t的箱區(qū)作業(yè)量閾值;γip為二維0-1 變量,按待裝船集裝箱i是否符合預(yù)配圖要求從而配載到船舶所對(duì)應(yīng)的船舶箱位p(k,c,r),滿足為1,否則為0;θip為二維0-1 變量,若待裝船集裝箱i位于箱區(qū)b,則對(duì)應(yīng)的元素為1,否則為0;M為一個(gè)極大的正數(shù)。
xip為0-1 變量,集裝箱i從箱區(qū)離場(chǎng),且被安排在船舶箱位p(k,c,r)則取1,否則為0;zij為0-1變量,當(dāng)集裝箱i先于j離場(chǎng)時(shí)取1,否則為0,其中?i∈N,j∈Δi;δbt為0-1 變量,箱區(qū)b在t時(shí)間段的作業(yè)不均衡判定變量。δbt可表示為:
假設(shè)條件如下:
1)目前船舶在碼頭的配載作業(yè)有單船配載作業(yè)和多船配載作業(yè)兩種,本文研究的是單船配載作業(yè),且為了避免裝卸同時(shí)進(jìn)行時(shí)設(shè)備沖突的增加以及翻箱數(shù)的上升,不考慮邊裝邊卸。
2)考慮到船公司一般會(huì)為特種箱安排特定的船箱位,配載會(huì)嚴(yán)格遵循,即使船公司沒有嚴(yán)格說明,也應(yīng)遵循特種箱的一般裝載要求,因此本文僅考慮普通箱的配載。
3)本文的視角是從自動(dòng)化碼頭出發(fā)的,預(yù)配載計(jì)劃由船方制定,卸船較為方便,且有臨時(shí)存放點(diǎn)可以加快卸船速度,因此本文研究的是碼頭方裝船配載方案的優(yōu)化。
4)配載是船方與碼頭方的協(xié)同工作,預(yù)配船圖需由船方提前給予碼頭方,了解集裝箱的各種信息,如尺寸大小等,且本文主要集中于堆場(chǎng)部分的研究,因此假設(shè)已知船舶預(yù)配總圖、橋吊作業(yè)計(jì)劃和待裝船的在場(chǎng)箱信息。
以f為目標(biāo)函數(shù),建立以集裝箱船舶裝船作業(yè)時(shí)間最小為目標(biāo)的優(yōu)化模型,即:
其中:目標(biāo)函數(shù)式(3)表示待裝集裝箱的離場(chǎng)數(shù);式(4)表示翻箱次數(shù);式(5)表示箱區(qū)作業(yè)不均衡判定次數(shù)。
另外,約束條件為:
其中:約束(6)~(7)為箱位限制約束,即一個(gè)集裝箱只能被安排到一個(gè)有且只有一個(gè)船舶箱位中;約束(8)表示待裝集裝箱離開箱區(qū)必須符合橋吊作業(yè)的時(shí)間安排;約束(9)表示位于同一堆棧不同層數(shù)的待裝集裝箱離開箱區(qū)的先后順序和翻箱的關(guān)系;約束(10)表示待裝集裝箱在船舶箱位緊挨著的下方有集裝箱即不能懸空;約束(11)表示待裝集裝箱與船舶貝位的匹配滿足預(yù)配要求;約束(12)表示船舶同貝同列集裝箱的裝載重量不能超過單列額定重量;約束(13)表示箱區(qū)集裝箱輕不壓重的堆垛要求;約束(14)表示確保離場(chǎng)集裝箱數(shù)量與待裝集裝箱數(shù)量相同;約束(15)表示箱區(qū)作業(yè)量限制,防止作業(yè)量過大;約束(16)表示決策變量類型。
集裝箱船舶配載問題本身是一個(gè)NP-hard 問題,同時(shí)通過上述模型部分描述可知該問題也是一個(gè)多目標(biāo)、多約束的組合優(yōu)化問題。當(dāng)船舶配載的集裝箱裝卸數(shù)量較少時(shí),可以通過Cplex 計(jì)算出較優(yōu)解,但隨著船舶大型化的發(fā)展、自動(dòng)化碼頭的不斷擴(kuò)容以及自動(dòng)化設(shè)備的更新迭代,集裝箱裝卸的數(shù)量一般是較大的,在這種情況下,運(yùn)用Cplex 求解計(jì)算時(shí)間會(huì)較長(zhǎng)或直接無法得出較優(yōu)解。因此,本文根據(jù)實(shí)際情況設(shè)計(jì)了基于固定集搜索(Fixed Set Search,F(xiàn)SS)算法的模型求解方法。
固定集搜索算法是在貪婪隨機(jī)自適應(yīng)搜索過程(Greedy Randomized Adaptive Search Procedure,GRASP)[16]中加入學(xué)習(xí)機(jī)制的一種算法,其重點(diǎn)在于避免專注于特定的較優(yōu)解,而是專注于這些解中的部分元素,通過固定多次出現(xiàn)在較優(yōu)解中的部分元素,致力于尋找固定部分元素組后的最優(yōu)解。
4.1.1 前提條件
使用固定集搜索算法需要滿足兩個(gè)前提條件:
前提一 通過固定所得解集中的部分解,可以降低正在搜索的解集空間大小,縮短目標(biāo)函數(shù)完成時(shí)間;
前提二 有一部分高質(zhì)量的解集中的固定解容易識(shí)別,不需要通過過多的比對(duì)。
4.1.2 貪婪隨機(jī)自適應(yīng)搜索
隨機(jī)組合箱區(qū)箱位和船舶箱位一一對(duì)應(yīng)來形成解集,在匹配組合過程中,將已經(jīng)確定的組合放入一個(gè)集合中,直至該集合包含所有的待裝集裝箱的安排組合,檢查是否符合約束條件,符合再計(jì)算目標(biāo)函數(shù)的結(jié)果,記錄目標(biāo)解與解集,如此反復(fù),每次排列完需要對(duì)解集進(jìn)行檢索,是否為已有解集,是否是新的最優(yōu)解。
4.1.3 固定集
通過固定出現(xiàn)在大量較優(yōu)解集中相同的部分組合,形成固定的部分解的集合,以此來縮小搜索空間,當(dāng)然固定集的形成需要滿足三個(gè)條件:
條件一 生成的固定集需要包含高質(zhì)量的解集的部分解;
條件二 一個(gè)生成的固定集至少能夠用來生成一個(gè)可行解;
條件三 固定集的規(guī)模是可以控制和變化的。
固定集具體的表現(xiàn)形式如圖6所示。
圖6 固定集表現(xiàn)形式Fig.6 Expression form of fixed set
圖6中,數(shù)字1~10代表箱區(qū)的待裝集裝箱,帶有相同特殊標(biāo)記的區(qū)域代表堆場(chǎng)與船舶位置的固定,未帶標(biāo)記的需要進(jìn)行繼續(xù)組合搜索,船舶貝位中打“×”的代表位置已有其他集裝箱存放。從圖6得知,箱區(qū)1號(hào)集裝箱已固定存放至右側(cè)船舶貝位06 列14 層中,5 號(hào)集裝箱固定至該貝位04 列18 層中,6 號(hào)集裝箱固定至該貝位03 列20 層,9 號(hào)集裝箱固定至該貝位05列12層,10號(hào)集裝箱固定至該貝位07列20層。
4.1.4 算法終止準(zhǔn)則
算法的終止判定條件如下:
1)首先,判斷最優(yōu)解搜索是否已經(jīng)停滯,如果是,將固定集規(guī)模大小設(shè)置為下一個(gè)值,需要注意的是如果當(dāng)前固定集規(guī)模大小已經(jīng)是最大值,則返回最小值。
2)接著,更新固定集規(guī)模大小前,檢驗(yàn)在尋找高質(zhì)量解時(shí)是否出現(xiàn)了停滯,如果停滯,即使用固定集所得解不是更優(yōu)解,再檢驗(yàn)所得解是不是已知最優(yōu)解集合中的一個(gè)解,如果不是,且這個(gè)固定集規(guī)模大小還是最小值,則將當(dāng)前固定集規(guī)模大小從固定集規(guī)模大小的集合中移除。
3)最后,當(dāng)固定集規(guī)模大小的集合為空集時(shí),則增加迭代次數(shù),達(dá)到最大迭代次數(shù)時(shí),終止算法。
4.2.1 參數(shù)設(shè)置
船舶配載的相關(guān)數(shù)據(jù)包括:具體的箱區(qū)在場(chǎng)箱數(shù)量與可用船箱位數(shù)量,箱區(qū)在場(chǎng)箱的箱位位置與船舶箱位位置,集裝箱各自對(duì)應(yīng)的卸貨港、貨物的尺寸以及船箱位的橋吊開始作業(yè)時(shí)間等,這些數(shù)據(jù)都是自動(dòng)化碼頭和船方分別提供匹配出來的結(jié)果。因此解的表達(dá)式需要包含兩者的信息,采用第一行“i”行的碼頭箱區(qū)集裝箱信息與第二行“p”行的船舶箱位信息一一對(duì)應(yīng)的方式來表示,解的具體表達(dá)形式如下:
碼頭與船方箱位信息的對(duì)應(yīng)關(guān)系如圖7所示。
圖7 碼頭與船方箱位信息對(duì)應(yīng)解的形式Fig.7 Corresponding solution form of terminal and ship’s slot information
4.2.2 搜索改進(jìn)
由于貪婪隨機(jī)搜索的隨機(jī)性過強(qiáng),計(jì)算時(shí)間可能較長(zhǎng),需對(duì)搜索方法進(jìn)行改進(jìn)。在搜索初始可行解時(shí),使用隨機(jī)的集裝箱與船舶箱位匹配,擴(kuò)大可行解的搜索范圍,對(duì)不滿足約束的解進(jìn)行二次匹配,改為鄰域交換和平滑匹配(首尾依次匹配)。
根據(jù)實(shí)際情況,其實(shí)待裝集裝箱是有許多不同屬性的,如尺寸不同、卸貨港不同等,一般相近屬性的集裝箱是存放在較近的位置的,為了避免跨度較大,對(duì)所有的同貝同層不同列的待裝集裝箱進(jìn)行劃分處理,將前一半歸為I 類,后一半歸為II類,基于預(yù)配載為初始參考解,如圖8 所示,將I類和II類分別進(jìn)行鄰域交換和平滑匹配,對(duì)同類同貝同層不同列的集裝箱進(jìn)行位置的交換,交換后的解仍然滿足預(yù)配和輕壓重約束,以此來尋找與預(yù)配結(jié)果持平或比預(yù)配更好的解。
圖8 箱位匹配Fig.8 Slot matching
4.3.1 參數(shù)定義
算法參數(shù)的具體定義如下:
P表示所有生成解(總體)的集合;Pn定義為n個(gè)最優(yōu)解的集合,Pn=Selectn(P);D為最大迭代次數(shù);Skn定義為從Pn隨機(jī)選取k個(gè)解的集合,Skn=Selectk(Pn),Skn={S1,S2,…,Sk} ;B為從m個(gè)最優(yōu)生成解的集合Pm中任意選取一個(gè)隨機(jī)解B,其中,B=Select(Pm),B={e1,e2,…}且B∈Pm,e1代表一個(gè)箱位安排;V代表待裝集裝箱總數(shù);C(ex,S)為0-1 變量,如果ex屬于S為1,否則為0;O(ex,Skn)表 示ex在Skn中出現(xiàn)的次數(shù),Sizes為固定集規(guī)模大小集合,Sizes[i]=|V|-,其中i為大于0 的整數(shù),用來根據(jù)當(dāng)前所得解對(duì)Sizes大小進(jìn)行更改;F為能夠在搜索中使用固定集,具體的表達(dá)式為F=Fix(B,Skn,Sizes),表示大小為Sizes、初始解B中在Skn中出現(xiàn)最多次的箱位安排;S表示使用固定集F而得到的解,S=RGF(F);T表示生成解的目標(biāo)函數(shù)值集合。
4.3.2 具體步驟
在對(duì)固定集搜索算法中的一些參數(shù)進(jìn)行定義并得到基本解之后,就可以利用算法對(duì)基本解進(jìn)行迭代優(yōu)化,首先獲得初始基本解,通過迭代得到初始可行解,最后通過迭代獲得能夠接受的最優(yōu)解。具體的迭代步驟如下:
步驟1 設(shè)置模型與算法參數(shù),將箱位可安排集合設(shè)為Candidates,待裝集裝箱總數(shù)為V,確定最大迭代次數(shù)D,且初始迭代次數(shù)d=0,固定集集合為F,固定集大小集合為Sizes,固定集大小為Size,固定集大小影響參數(shù)為i,集合為I,且初始參數(shù)i=1,最大值為Imax,GRASP中的箱位交換初始次數(shù)為f=0,最大交換次數(shù)為fmax,解的集合為P。
步驟2 輸入初始基本解x0(船方提供的預(yù)配數(shù)據(jù)),當(dāng)前解xf=x0。
步驟3 判斷當(dāng)前解xf是否滿足堆場(chǎng)箱區(qū)作業(yè)量閾值和船舶單列最大重量約束,即判斷是否為可行解,是則進(jìn)入步驟5,否則進(jìn)入步驟4(GRASP)。
步驟4 進(jìn)入步驟4.1;
步驟4.1 將同卸貨港同尺寸大小的集裝箱(箱位)作為同一類別集裝箱(箱位)進(jìn)行處理,提取當(dāng)前輸入數(shù)據(jù)的集裝箱的所有類別CC,在每一個(gè)類別中,提取該類別中的所有貝位CB和層數(shù)CT,進(jìn)入步驟4.2;
步驟4.2 記錄層號(hào)CT中存在兩個(gè)及兩個(gè)以上集裝箱的層號(hào)為Tier,進(jìn)入步驟4.3;
步驟4.3 隨機(jī)交換Tier中兩個(gè)集裝箱的位置,記錄f=f+1,得到新的箱位排列,生成當(dāng)前解xf,返回步驟3。
步驟5 計(jì)算當(dāng)前解xf的目標(biāo)函數(shù)值Vf,其中Vf=Value(xf),將各個(gè)目標(biāo)函數(shù)值放入集合T,將當(dāng)前解xf放入解的集合P,判斷是否f大于等于fmax,是則進(jìn)入步驟6,否則返回步驟4。
步驟6 記錄迭代次數(shù)d=d+1,判斷當(dāng)前迭代次數(shù)d是否大于等于最大迭代次數(shù)D:若是,則算法結(jié)束,比較各個(gè)最優(yōu)解BSd和最優(yōu)函數(shù)值BSVd,輸出在迭代D次之后的最終最優(yōu)解UBSd和最優(yōu)函數(shù)值UBSVd;否則進(jìn)入步驟7。
步驟7 從n個(gè)最優(yōu)生成解的集合Pn中隨機(jī)選取k個(gè)解得到Skn,從m個(gè)最優(yōu)生成解的集合Pm中任意選取一個(gè)隨機(jī)解B,固定集大小為Sizes[i],進(jìn)入步驟8。
步驟8 利用F=Fix(B,Skn,Sizes),確定固定集F,剔除Candidates中固定集F的箱位安排,即排除掉已經(jīng)確定位置的箱區(qū)箱位位置和船舶箱位位置,根據(jù)同卸貨港和箱位尺寸進(jìn)行箱位安排生成解S,S=RGF(F),進(jìn)入步驟9。
步驟9 判斷當(dāng)前解S是否滿足約束,即判斷是否為可行解:若是,進(jìn)入步驟11;否則進(jìn)入步驟10。
步驟10 進(jìn)入步驟10.1;
步驟10.1 更新輸入數(shù)據(jù)的集裝箱的所有類別NCC,同一類別中提取更新后的所有貝位NCB和層數(shù)NCT,進(jìn)入步驟10.2;
步驟10.2 記錄層號(hào)NCT中存在兩個(gè)及兩個(gè)以上集裝箱的層號(hào)為NewTier,進(jìn)入步驟10.3;
步驟10.3 在NewTier中任選一個(gè)層號(hào),計(jì)算該層待裝集裝箱數(shù)量num,選定劃分位置mod(num,2),前一半鄰域交換,后一半平滑匹配,進(jìn)行箱位交換,得到新的箱位排列,生成當(dāng)前解S,返回步驟9。
步驟11 計(jì)算解S的目標(biāo)函數(shù)值VS=Value(S),將解S加入到生成解集合P,將VS與集合T中最小值Tmin比較:若VS更小,則i=i+1,且記錄當(dāng)前最優(yōu)解BSd=S,最優(yōu)函數(shù)值為BSVd=VS,將VS加入T,進(jìn)入步驟15;否則進(jìn)入步驟12。
步驟12 判斷S是否為Pn或Pm中的一個(gè)解:若是,則i=i+1,進(jìn)入步驟15;否則進(jìn)入步驟13。
步驟13 判斷i是否為當(dāng)前影響參數(shù)集合的最小值Tmin:若是,則從I中刪除當(dāng)前i,進(jìn)入步驟14;否則i=i+1,進(jìn)入步驟15。
步驟14 判斷I是否為空集:若是,則f=0,返回步驟2;否則i=i+1,進(jìn)入步驟15。
步驟15 判斷當(dāng)前i是否大于Imax:若是,則i=Imin;否則i不變,返回步驟7。
本文根據(jù)上海某集裝箱碼頭的實(shí)際配載數(shù)據(jù)進(jìn)行分析,通過FSS與Cplex 的算例計(jì)算結(jié)果對(duì)比以及固定集搜索算法、粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法、遺傳算法(Genetic Algorithm,GA)和蟻群優(yōu)化(Ant Colony Optimization,ACO)算法之間的算例計(jì)算結(jié)果分析,驗(yàn)證本文所提模型與FSS 的有效性。實(shí)驗(yàn)所使用的電腦配置為Windows 1064 位操作系統(tǒng),8 GB 運(yùn)行內(nèi)存,處理器為Inter Core i5-8265U,CPU 頻率為1.6 GHz,使用軟件為IBMI LOG Cplex Optimization Studio 12.2和Matlab 2018a。
本文將上海洋山港某碼頭提供的配載數(shù)據(jù)作為實(shí)例研究,整理出6組規(guī)模不等的實(shí)例,詳細(xì)的數(shù)據(jù)說明如表2所示。其中,箱量是數(shù)據(jù)梳理后的待裝集裝箱數(shù)量,箱區(qū)數(shù)表示這些待裝集裝箱所屬的不同箱區(qū)數(shù),LD 表示該組實(shí)例的待裝集裝箱在堆場(chǎng)箱區(qū)中最左下角的位置,RU表示該組實(shí)例的待裝集裝箱在堆場(chǎng)箱區(qū)中最右上角的位置,2D 表示同一實(shí)例中只有2 個(gè)集裝箱的堆棧數(shù)比例,3D 表示同一實(shí)例中只有3 個(gè)集裝箱的堆棧數(shù)比例。
表2 實(shí)例數(shù)據(jù)說明Tab.2 Data description of real instances
首先為了方便統(tǒng)計(jì)數(shù)據(jù)將時(shí)間段t設(shè)置為1 h,作為單位時(shí)間段,參考上海洋山深水港四期自動(dòng)化碼頭的實(shí)際配載數(shù)據(jù)來確定模型的部分相關(guān)參數(shù),設(shè)定箱區(qū)單位時(shí)間內(nèi)的最大作業(yè)箱量為20 箱,箱區(qū)一個(gè)待裝集裝箱不考慮翻箱的場(chǎng)橋平均作業(yè)時(shí)間即平均場(chǎng)橋就位和取箱時(shí)間為2 min,箱區(qū)的一個(gè)待裝集裝箱從堆場(chǎng)到橋吊工作區(qū)的水平運(yùn)輸時(shí)間為3 min,箱區(qū)內(nèi)一次翻箱時(shí)間為3 min,箱區(qū)不平衡可能導(dǎo)致的集裝箱單位懲罰時(shí)間定為2 min。模型參數(shù)確定后,運(yùn)用Cplex 對(duì)模型進(jìn)行求解。鑒于問題復(fù)雜性較大,可能導(dǎo)致Cplex 無法求解,因此設(shè)定Cplex 的最大運(yùn)行時(shí)間為1 h,同時(shí)設(shè)定算法的相關(guān)參數(shù)如下:最大迭代次數(shù)D=50,固定集大小的影響參數(shù)最大值Imax=10,GRASP中的箱位最大交換次數(shù)fmax=200。
在參數(shù)ρ=0.5的情況下,F(xiàn)SS 與Cplex 的實(shí)例求解的最終解結(jié)果如表3所示。
表3 不同算法實(shí)例計(jì)算結(jié)果的對(duì)比Tab.3 Computational result comparison of different algorithms on real instances
表3 的實(shí)例計(jì)算結(jié)果包括翻箱量、不均衡程度、目標(biāo)函數(shù)值和求解時(shí)間,在計(jì)算中,由于Cplex 求解模型的限制,將Cplex 的求解時(shí)間設(shè)定為1 h,求解結(jié)束后返回目標(biāo)值,若超過1 h,則無最優(yōu)結(jié)果。首先,對(duì)Cplex 與所提算法兩者的求解時(shí)間作了對(duì)比,從表3 可以看出,箱量從100~600 箱的6 個(gè)實(shí)例中,所提算法的計(jì)算時(shí)間在18.7 s~161.6 s,而Cplex最短計(jì)算時(shí)間為178.1 s,仍超過了算法的最大計(jì)算時(shí)間,尤其箱量為600 時(shí)Cplex 計(jì)算時(shí)間超過了1 h,顯示無結(jié)果,相比之下FSS卻有著很好的求解結(jié)果和求解效率。相較于Cplex,F(xiàn)SS 求解的翻箱數(shù)和不均衡箱數(shù)都較小,實(shí)例A5 減少了最多的7 次翻箱,且實(shí)例A5 減少了最多的13 個(gè)不均衡箱數(shù);FSS 的目標(biāo)函數(shù)值一直是較小,最大差距74 min,只有規(guī)模較小的實(shí)例A1兩者計(jì)算的差距不大,最小差距42 min。綜上,不同規(guī)模的實(shí)例下,F(xiàn)SS 算法相較于Cplex,翻箱量和不均衡箱數(shù)分別平均減少了22.3%和11.7%,目標(biāo)函數(shù)值平均優(yōu)化了6.5%。
鑒于Cplex求解的時(shí)間較長(zhǎng)且存在無法求解的情況,增加粒子群優(yōu)化(PSO)算法、遺傳算法(GA)和蟻群優(yōu)化(ACO)算法對(duì)案例的計(jì)算分析,與本文所提的固定集搜索算法進(jìn)行比較,參數(shù)ρ取0.5,粒子群算法PSO 的種群規(guī)模取200,最大迭代次數(shù)為50,慣性權(quán)重為0.7189,加速常數(shù)為1.1503;遺傳算法的種群規(guī)模取200,最大迭代次數(shù)為50,以目標(biāo)函數(shù)的倒數(shù)作為適應(yīng)度值,交叉概率為0.9,變異概率為0.3;蟻群算法的種群規(guī)模取200,最大迭代次數(shù)為50,信息因子為1,期望因子為5,信息揮發(fā)因子為0.1。詳細(xì)的數(shù)據(jù)對(duì)比見表4。
從表4 可以看出,在箱量較小的案例中,各算法的四個(gè)指標(biāo)差距不大,且在案例A1 中,遺傳算法的目標(biāo)函數(shù)值最小為348 min,不均衡箱數(shù)和求解時(shí)間也是最低的,分別為16 箱和17.9 s;但隨著箱量的增加,翻箱次數(shù)和不均衡箱數(shù)的差距不斷拉大,固定集搜索算法的優(yōu)勢(shì)逐漸顯示出來,四個(gè)指標(biāo)的值一直是最小值??偟膩碚f,相較于其他三種算法,固定集搜索算法的穩(wěn)定性更好,在翻箱數(shù)和不均衡箱數(shù)的優(yōu)化上更優(yōu),求解的質(zhì)量更高,目標(biāo)函數(shù)值平均優(yōu)化了2.1%。
表4 不同算法的優(yōu)化結(jié)果對(duì)比Tab.4 Optimization result comparison of different algorithms
鑒于實(shí)例數(shù)據(jù)缺少變化性,需要對(duì)實(shí)例的數(shù)據(jù)進(jìn)行處理分組,增加一些不同情況下的虛擬案例進(jìn)行分析研究。與此同時(shí),為了更加方便直觀地了解港口的運(yùn)作情況,根據(jù)洋山港四期提供的數(shù)據(jù)對(duì)自動(dòng)化碼頭進(jìn)行模擬布局,具體布局如圖9所示。
圖9 算例配載箱區(qū)圖Fig.9 Instance stowage block diagram
由圖9 可知,箱區(qū)的區(qū)域范圍是很大的,箱區(qū)從1 到B 有11個(gè)箱區(qū),這11個(gè)箱區(qū)可以分成122個(gè)小箱區(qū),如101就是箱區(qū)10 的第一個(gè)小箱區(qū),根據(jù)距離待裝船舶的遠(yuǎn)近對(duì)箱區(qū)進(jìn)行分類編號(hào),如表5所示。
表5 箱區(qū)距離編號(hào)Tab.5 Number of block distance
接下來,對(duì)實(shí)例進(jìn)行如下處理,構(gòu)成虛擬案例,進(jìn)行多樣性分析:
1)重新安排同一實(shí)例中具有2 個(gè)和3 個(gè)待裝集裝箱的堆棧分布;
2)將實(shí)例中有2個(gè)和3個(gè)的集裝箱堆棧比例進(jìn)行調(diào)整。
第一步,堆棧分布按照箱區(qū)距離待裝船舶的距離遠(yuǎn)近進(jìn)行正態(tài)分布處理,如圖10所示,橫坐標(biāo)d表示箱區(qū)與待配載船只的距離,縱坐標(biāo)代表那些待裝集裝箱的分布概率n,越靠近作業(yè)船舶的待裝集裝箱概率就越大,但n值也有最大值為M,用來避免集裝箱數(shù)量過多,碼頭負(fù)荷運(yùn)作。隨著距離d變化的集裝箱分布概率n的正態(tài)分布函數(shù)表示為:
圖10 箱區(qū)待裝集裝箱正態(tài)分布Fig.10 Normal distribution of containers to be loaded in block
根據(jù)碼頭箱區(qū)集裝箱分布的實(shí)際情況,取μ為0、σ為,則M為1,將分布概率控制在區(qū)間[0,1]。
第二步,調(diào)節(jié)堆棧比例,堆棧配置所示如表6所示。
表6 堆棧配置Tab.6 Configuration of stacks
每組堆棧配置下進(jìn)行兩次正態(tài)分布的待裝集裝箱安排,則每組實(shí)例如箱量為100 的A1 就有a1、a2、b1、b2、c1、c2 這6個(gè)虛擬案例分析,由于數(shù)組過多,取6 個(gè)虛擬案例的平均值作為每一組的比較數(shù)據(jù),具體的計(jì)算結(jié)果如表7所示。
表7 虛擬案例計(jì)算結(jié)果Tab.7 Computational results of virtual instances
由表7 可知,虛擬案例將待裝集裝箱的堆場(chǎng)箱位集中在距離待裝船舶較近的箱區(qū),四個(gè)指標(biāo)數(shù)據(jù)都高于原本的實(shí)例數(shù)據(jù),但差距不是很大。固定集搜索算法依舊優(yōu)于其他三種算法的計(jì)算,目標(biāo)函數(shù)值平均減少了22 min,翻箱次數(shù)平均減少了16.1%,不均衡箱數(shù)最多減少了16 箱,求解時(shí)間平均減少了14.7 s。
傳統(tǒng)碼頭與自動(dòng)化碼頭在布局、設(shè)備與作業(yè)工藝等方面的不同,導(dǎo)致自動(dòng)化碼頭在配載問題上需要更多考慮設(shè)備與場(chǎng)地的充分利用。為了減少碼頭的運(yùn)營(yíng)成本,快速完成配載工作,因此以最小化翻箱次數(shù)、箱區(qū)集裝箱作業(yè)量的不均衡程度和總裝船時(shí)間為目標(biāo),建立相應(yīng)的配載優(yōu)化模型,設(shè)計(jì)固定集搜索算法進(jìn)行求解,且分別通過與Cplex、粒子群算法、遺傳算法和蟻群算法的對(duì)比,驗(yàn)證了本文所提固定集算法的高效性。與此同時(shí),為了增加算例的多樣性,設(shè)置了虛擬案例,與另外三種算法相比,固定集搜索算法的不均衡箱數(shù)平均減少了19.3%,目標(biāo)函數(shù)值即總裝船時(shí)間平均減少了22 min,求解時(shí)間平均減少了14.7 s。
綜上,無論是在求解效率還是在求解效果方面,本文所構(gòu)建的自動(dòng)化碼頭船舶配載混合整數(shù)規(guī)劃模型與固定集搜索算法都有較優(yōu)的配載結(jié)果,縮短了碼頭裝船時(shí)間與船舶靠泊時(shí)間,為后續(xù)不確定情況下的船舶配載優(yōu)化研究提供參考。