丁 一，王聰

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

0 引言

在全球經(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

1 相關(guān)工作

目前大部分的配載優(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)行分析研究。

2 問題描述

從自動(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è)量均衡的研究很有必要。

3 模型建立

3.1 參數(shù)

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ù)。

3.2 決策變量

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可表示為：

3.3 假設(shè)條件

假設(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)箱信息。

3.4 目標(biāo)函數(shù)及約束

以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）表示決策變量類型。

4 基于固定集搜索算法的模型求解方法

集裝箱船舶配載問題本身是一個(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）算法的模型求解方法。

4.1 基本原理

固定集搜索算法是在貪婪隨機(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 算法設(shè)計(jì)

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 基本步驟

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。

5 算例分析

本文根據(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。

5.1 數(shù)據(jù)說明

本文將上海洋山港某碼頭提供的配載數(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。

5.2 實(shí)例結(jié)果分析

在參數(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%。

5.3 不同算法對(duì)比

鑒于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

5.4 虛擬案例分析

鑒于實(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。

6 結(jié)語

傳統(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)化研究提供參考。