丁 一，田 亮，龔 杰

上海海事大學 物流研究中心，上海 201306

1 引言

近年來，隨著經(jīng)濟的發(fā)展，科技的進步以及傳統(tǒng)集裝箱碼頭相較于自動化碼頭在人力成本、人員安全和作業(yè)效率等方面的劣勢，諸如上海洋山四期等自動化集裝箱碼頭相繼建成并投入運營。自動化集裝箱碼頭（Automatic Container Terminal，ACT）高效作業(yè)的重要原因在于持續(xù)的智能化無人作業(yè)以及多決策系統(tǒng)模塊的集成，配載就是集中系統(tǒng)中的一個關鍵環(huán)節(jié)。集裝箱碼頭的配載業(yè)務是按船舶的運輸要求和碼頭的作業(yè)要求，編制預定裝載于既定船舶箱位的裝載計劃[1]，配載質量的高低直接影響到船舶航行安全以及碼頭裝船作業(yè)效率與成本，因此碼頭必須在考慮船舶的航行安全與盈利的條件下，充分考慮在場箱堆存情況與作業(yè)工藝的情況，以確定最佳配載方案，提高裝船作業(yè)效率，減少裝卸作業(yè)成本。自動化碼頭堆場與傳統(tǒng)碼頭堆場的布局與機械配置如圖1所示，堆場布局與機械配載方面的差異導致作業(yè)工藝的不同，也直接影響著配載的考慮因素。

圖1 集裝箱碼頭堆場布局圖

在傳統(tǒng)集裝箱碼頭堆場中，堆場箱區(qū)平行于碼頭岸線布置，箱區(qū)龍門吊大多使用的是輪胎吊（Rubber-Tyred Gantry Crane，RTG），RTG 的運行軌跡平行于碼頭岸線，可以跨箱區(qū)作業(yè)，因此RTG與內外集卡的交互點不固定，而在ACT 堆場中，堆場箱區(qū)垂直于碼頭岸線，箱區(qū)龍門吊大多使用軌道吊（Rail-Mounted Gantry Crane，RMG），RMG 的運行軌跡也垂直于碼頭岸線，相鄰箱區(qū)之間沒有作業(yè)區(qū)域（設有懸臂吊的箱區(qū)除外），只設有海側和陸側交換區(qū)作為RMG與外集卡和自動導引車（Automated Guided Vehicle，AGV）的交互點，因此收發(fā)箱點固定，屬于單側作業(yè)模式，如果同一時間內部分ACT箱區(qū)裝卸量偏小，而部分ACT箱區(qū)裝卸量偏大，即作業(yè)不均衡，而單位時間內RMG的作業(yè)能力有限，一旦某個箱區(qū)的發(fā)箱指令過于集中，就會造成某一段時間內該箱區(qū)作業(yè)量過大，易產(chǎn)生RMG 作業(yè)沖突，會造成AGV 和岸橋（Quay Crane，QC）的等待時間增加，從而影響港口作業(yè)效率，延長總裝船時間，進而延誤船期，因此發(fā)箱時考慮箱區(qū)之間的作業(yè)均衡至關重要。

目前，學者們主要從兩個視角對船舶配載問題進行研究，一是從船公司的視角，另一種是從碼頭視角。從船公司的角度，主要解決的問題是如何減少裝卸箱時由于多裝貨港與多卸貨港貨物的存在導致的倒箱，其次是考慮船舶的航行安全，如Delgado等[2]考慮20′/40′箱的混裝、冷藏箱等特種箱的配載以及船舶積載強度等因素，以最小化倒箱為目標，建立解決集裝箱船舶配載中的倍位計劃（master planning）子問題的整數(shù)規(guī)劃模型與解決箱配（slot planning）子問題的約束規(guī)劃模型，并證明約束規(guī)劃在求解此類問題中的有效性；而Parre?o等[3]在Delgado等[2]的基礎上，以最小化漏配箱數(shù)、倒箱為目標，建立新的整數(shù)規(guī)劃模型，并設計GRASP方法，重點解決配載的箱位分配子問題。在追加考慮船舶穩(wěn)性的因素后，Ambrosino 等[4]將單卸貨港倍位計劃問題延伸到多卸貨港倍位計劃問題，以最小化靠泊時間為目標，設計求解問題的MIP 啟發(fā)式方法；而Pacino 等[5]則以同樣的目標，分別建立倍位計劃問題的整數(shù)規(guī)劃模型和單個集裝箱的箱位問題的約束規(guī)劃模型，Ding等[6]則將目標換成最小化倒箱；汪圓圓等[7]在保證倒箱量為零的策略下，以船舶中縱剖面彎矩值、重心橫向偏移、初穩(wěn)性高為目標，以船舶吃水差值為約束條件，優(yōu)化集裝箱配載；孫俊清等[8]將船舶穩(wěn)定性作為約束條件，以最小化集裝箱船舶在整個航線所有港口的倒箱量為目標，設計了求解問題的改進遺傳算法。

而從碼頭的角度，解決的問題主要是確保配載結果足以保證船舶航行安全，此外盡量縮短裝船作業(yè)時間，如Araújo等[9]將三維集裝箱船舶裝船計劃問題（3D-CLPP）的目標定為最小化船上的倒箱和最大化船舶的穩(wěn)定性；Monaco 等[10]在預配規(guī)則已定的條件下，建立配載問題0-1整數(shù)規(guī)劃模型以優(yōu)化碼頭的堆場翻箱時間與集裝箱水平運輸時間，但沒有考慮堆場作業(yè)不均衡造成的作業(yè)等待。在滿足船舶配載計劃的前提下，祝慧靈等[11]以堆場翻箱量最小為目標分別建立3 種翻箱策略下的提箱順序優(yōu)化模型；在增加最小化船舶貝內翻倒箱數(shù)量及橫傾力矩的目標后，李俊等[12]構建集裝箱船舶裝箱排序問題的數(shù)學模型并設計SWO-HES 兩階段算法對問題進行求解。

通過對文獻的系統(tǒng)梳理可以發(fā)現(xiàn)，目前學者們在研究集裝箱船舶配載問題時，大多從船公司角度出發(fā)，較少從碼頭角度出發(fā)，所考慮的因素主要有以下幾點：（1）“重不壓輕”、“遠不壓近”約束，即重箱在下，輕箱在上，遠卸貨港箱在下，近卸貨港箱在上；（2）偶數(shù)倍位集裝箱箱槽內20′與40′箱的混裝約束（甲板或艙內的同倍位同排位不同層位的所有箱位同屬一根箱槽）；（3）特種箱的配載約束；（4）吃水差、穩(wěn)性和船體強度約束等。鑒于ACT 箱區(qū)單側作業(yè)的特殊性以及對裝船效率的要求，僅考慮以上這些常規(guī)約束制定出的配載方案已滿足不了ACT 實際生產(chǎn)需要，引入ACT 箱區(qū)作業(yè)均衡性就顯得尤為重要。但目前以ACT 為背景的配載研究較少，缺乏ACT 箱區(qū)的作業(yè)均衡對配載裝船作業(yè)影響的研究。此外，在實際裝船過程中，存在眾多不確定因素，如QC作業(yè)時間、AGV水平運輸時間、RMG堆場作業(yè)時間、集裝箱未按規(guī)定時間順利進場等，這些不確定性直接影響著配載方案的可行性與滿意度。在目前的配載研究中，所有的參數(shù)都是確定的，缺乏不確定性對配載結果影響的研究。

2 問題描述

集裝箱船舶配載[13]是指：碼頭根據(jù)作業(yè)規(guī)定和船舶安全航運要求，制定出滿足船舶最基本穩(wěn)定性要求，盡可能減少翻箱次數(shù)，縮短裝船時間，降低營運成本的船舶裝載計劃。從根本上來說，船舶配載問題可以劃分為兩個子問題：（1）“When”問題，即在場箱何時離場，也即裝船作業(yè)順序（loading sequence）問題。船舶箱槽（船上同倍位同排位不同層位的船箱位所屬同一根槽）中一定是下層箱位先裝箱，如果將同一堆棧（同箱區(qū)同倍位同排位不同層位的集裝箱所屬同一堆棧）的下層箱子配于船舶同一根槽的上層箱位，則裝船時就需要將同一堆棧的上層箱子移走才能取出下層箱子裝船，堆場翻箱操作由此產(chǎn)生。做配載時，待裝船的在場箱的場箱位是已知的，是否翻箱或有多少翻箱完全取決于配載的結果，即配載船圖?！癢hen”問題的結果就是最優(yōu)的裝船作業(yè)順序。（2）“Where”問題，確定該箱離場后被安排在哪一船箱位，“Where”問題的結果就是配載的貝位船圖。

船舶配載的一個重要目標在于減少船舶在港裝卸時間，因此在給定船舶預配船圖、橋吊作業(yè)計劃（Crane Working Planning，CWP）和在場箱信息后，考慮常規(guī)配載約束和箱區(qū)單位時間作業(yè)量約束，以最小化總裝船時間和同時段內箱區(qū)最大與最小作業(yè)量的差額（即箱區(qū)作業(yè)均衡）為目標，建立混合整數(shù)規(guī)劃模型。在上述確定性優(yōu)化模型的基礎上，考慮到橋吊作業(yè)時間的不確定性對配載的影響最為直接，將橋吊作業(yè)時間改為不確定參數(shù)，建立考慮橋吊作業(yè)時間不確定性的ACT 船舶配載魯棒優(yōu)化模型，通過基于編號與排序的禁忌搜素算法得到最優(yōu)的配載方案，保證該配載方案能夠使得裝船作業(yè)過程中的箱區(qū)作業(yè)均衡，并且對橋吊作業(yè)時間的不確定具有較強的魯棒性。

3 確定性模型建立

3.1 參數(shù)

N：所有待裝船的在場集裝箱的集合，i=1,2,…,|N|，?i∈N；

B：所有待裝船的在場集裝箱所在堆場箱區(qū)（Block）的集合，b=1,2,…,|B|，?b∈B；

P：船上待裝集裝箱的箱位（Slot）集合，p=1,2,…,|P|，?p∈P；

T：作業(yè)總時間內分鐘段集合，t=1,2,…,|T|，?t∈T，如t=3 表示第3分鐘內；

H：作業(yè)總時間內小時段集合，h=1,2,…,|H|,|H|=ceil(|T|/60)，表示取大于等于|T|/60 的最小整數(shù)值，則t=[1+60(h-1)，60+60(h-1)]，?h∈H，如h=3 表示第3h內；

qb：每一小時段內箱區(qū)b的最大集裝箱作業(yè)量；

fb：箱區(qū)b內待裝船的集裝箱總數(shù)；

wi：集裝箱i的重量，其中 ?i∈N；

θp：箱位p的開始裝箱時間，其中?p∈P；

τip：集裝箱i從其所在的堆場箱區(qū)到最終的箱位p所對應的船舶倍位的水平運輸時間，其中?i∈N,p∈P；

L：表示船上根據(jù)預配載計劃所形成的集裝箱箱槽的集合，；

Ψl：屬于船上箱槽l中的箱位，?l∈L,Ψl∈P；

Wl：船上箱槽l所能容許的最大裝箱總重量，?l∈L；

Δi：表示與集裝箱i在同一箱區(qū)同一堆棧且位于i之上的集裝箱的集合，Δi?N,?i∈N；

πp：表示與船舶箱位p在同一根箱槽且位于p之上的箱位的集合，πp?P,?p∈P；

σ1：箱區(qū)內的一次翻箱時間；

σ2：對不均衡可能導致的等待的懲罰時間。

IFIP：是一個二維|N|*|P|的0-1 矩陣，表示 |N|個待裝船在場箱中的i是否符合預配總圖關于該箱位的類型、尺寸、卸貨港的要求從而裝到|P|個計劃船箱位中的p，如果可以，則矩陣對應元素IFIPip=1，否則為0。如果IFIPip=0，則說明按預配計劃，i不可以裝到p箱位，那么xipt=0，因此有關系式：xipt≤IFIPip；

IFIB：是一個二維|N|*|B|的0-1 矩陣，如果在場箱i位于箱區(qū)b，則矩陣對應元素IFIBib=1，否則為0。

TIP：是一個二維|N|*|P|的整數(shù)矩陣，表示如果在場箱i被安排到船箱位中的p，那么該集裝箱應該離場的時間TIPip=θp-τip；

λ1，λ2：權重系數(shù)；

M：一個極大正數(shù)。

3.2 決策變量

xipt：代表集裝箱i在t時間從箱區(qū)離場，并且被安排到船箱位p；

zij：0-1變量，當集裝箱i先于j離場時取1，否則為0，其中

Ωh：第h小時各箱區(qū)出箱量的最小值；

Rh：第h小時各箱區(qū)出箱量的最大值。

3.3 假設條件

（1）當前待配載船舶只有一條船，且不考慮邊裝邊卸。

（2）考慮到冷藏箱和危險品箱一般有配載員直接指定配載位置，本文僅考慮普通箱的配載。

（3）只考慮裝船情況，假設到港后進口箱均已卸載。

（4）碼頭一般根據(jù)進、出口箱和碼頭自身情況，配置一定數(shù)量的集裝箱岸橋，本文假設已事先獲得各港口可分配的岸橋類型和數(shù)量。

（5）在計算箱區(qū)翻箱量時，只考慮單條船舶裝船作業(yè)時堆場的翻箱，不考慮因多船舶同時裝船造成的翻箱。

（6）預配船圖一經(jīng)船方確定，不會發(fā)生變化。

3.4 完整模型

其中，目標函數(shù)：

（1）最小化總裝船時間：

（2）最小化各箱區(qū)作業(yè)量的不均衡程度：

為了便于計算，可將目標函數(shù)（2）線性化，定義：

由此，式（2）轉化為式（5）：

問題描述中，箱區(qū)作業(yè)量的不均衡程度較大時可能會造成裝船作業(yè)時的等待時間，因此為了減少等待的發(fā)生，給不均衡的箱量以一定的懲罰時間σ2，另外引入權重系數(shù)λ1、λ2，將多目標函數(shù)轉化為單目標函數(shù)：

可得完整的考慮箱區(qū)作業(yè)均衡的ACT船舶配載混合整數(shù)規(guī)劃模型如下：

s.t.

公式（7）表示目標函數(shù)，最小化實配過程的集裝箱裝船作業(yè)時間和最小化不同箱區(qū)作業(yè)量的不均衡程度。式（8）和（9）為匹配約束，即一個集裝箱只能被安排到一個船箱位中，而一個箱位也只能放一個集裝箱。式（10）表示集裝箱與船箱位的匹配需要滿足預配要求。式（11）表示在場箱離場須符合CWP作業(yè)時間安排。式（12）為輕壓重約束，即船上同一根箱槽的集裝箱，重箱一定位于輕箱的下層。式（13）為船舶單根箱槽的裝載重量約束，規(guī)定每一根箱槽堆碼的總重量不允許超過設定的最大值。式（14）和（15）為箱區(qū)作業(yè)約束，式（14）表示同一時間段內從該箱區(qū)離場的最大集裝箱數(shù)量。式（15）表示從堆場一箱區(qū)離場的集裝箱總數(shù)量。式（16）表示在場箱離場先后順序與翻箱的關系。式（17）和（18）用來求取每一時間段內各箱區(qū)作業(yè)量的最小值和最大值，同目標函數(shù)一起達成箱區(qū)作業(yè)均衡的目標。式（19）表示決策變量類型。

4 魯棒性優(yōu)化模型

4.1 魯棒優(yōu)化方法

根據(jù)不確定性變量建模方法的不同，不確定性優(yōu)化方法一般可分為三類：隨機規(guī)劃、模糊規(guī)劃及魯棒優(yōu)化[14]。魯棒優(yōu)化[15]是一種解決不確定性問題強有力的工具，其通過“集合”的形式描述變量的不確定性（而不是通過概率分布），使得約束條件在不確定變量取值于已知集合中所有可能值時都能夠滿足，并以此建立最極端情況下優(yōu)化目標函數(shù)的魯棒對等模型。該方法的優(yōu)點是：（1）決策者能夠調節(jié)解的魯棒水平；（2）魯棒模型可以轉化成線性規(guī)劃，易于求解；（3）能夠求出魯棒解滿足約束條件的概率下界。因此本文應用Bertsimas 和Sim[16]提出的魯棒方法，采用“盒子”作為不確定時間的集合，并引入保守性參數(shù)，提出橋吊作業(yè)時間不確定的考慮箱區(qū)作業(yè)均衡的ACT 船舶配載魯棒優(yōu)化模型，再應用強對偶定理，將非凸非線性的魯棒模型轉化為線性規(guī)劃。

4.2 魯棒優(yōu)化模型

確定性模型中，橋吊作業(yè)時間是確定的，這里將橋吊作業(yè)每關箱子的時間作為一個不確定參數(shù)處理，引入如下參數(shù)。

gp：箱位p的作業(yè)關號，?p∈P；

θp：箱位p的開始裝箱時間（CWP預計值，名義值）；

ξp：箱位p的開始裝箱時間，為一個不確定值，其中?p∈P，假設ξp取值于有界的對稱區(qū)間上，也稱為“盒式”集合，為最大時間偏差（定值），ρ為偏差系數(shù)，ρ∈[-1,1] 。

根據(jù)CWP，按計劃作業(yè)開始時間的先后（計劃關號）對箱位進行編號（遞增），考慮到橋吊作業(yè)時間的不確定性將直接影響后續(xù)箱位的開始裝船時間，因此為簡化相關關系，將橋吊作業(yè)的不確定性轉移到箱位的開始作業(yè)時間上去，有如下關系：fgp

本文應用Bertsimas和Sim[16]提出的魯棒方法，在約束（16）中，對 ?i∈N,j∈Δi，引入一個參數(shù)Γij，Γij不一定是整數(shù)，取值在區(qū)間[0,|P|]，參數(shù)Γij的作用是調節(jié)魯棒水平，控制解的保守性。直觀地講，不是所有的ξp都會變動，該魯棒方法的目標是當最多有個ξp在其區(qū)間內發(fā)生變化時魯棒解仍是可行解，不失一般性，Γij的取值越高，決策的風險性越低，但代價也越大。

由于約束（16）含有不確定參數(shù)ξp(ξp)，且決策變量xipt為0-1變量，可將約束（16）轉化為：

其中：

此時，當

時，必有zij=1。

如果：

時，只有當

時，才有zij=1。

當Γij的取值不是整數(shù)時，表示有個ξp在其區(qū)間內發(fā)生變化，一個ξp的取值擾動為當Γij的取值是整數(shù)時：

引入輔助變量zp,?p∈P，則函數(shù)g(x,Γij)可表示為：

式（23）是一個線性規(guī)劃問題，若給定x* ，可用Cplex求解器進行求解。當Γij=0時，此時最多有0個ξp同時偏離均值，即所有ξp都取均值，此時約束（20）與約束（16）相同，魯棒問題轉為確定問題，當=Γij=|P|時，此時最多有|P|個ξp同時偏離均值，也就是所有ξp都取最大值，此時約束（20）變?yōu)椋?/p>

即當Γij=|P|時，該魯棒方法轉化為Ben-Tal和El-Ghaoui[17]提出的魯棒方法，即考慮ξp都取最大值的情景，雖然該方法求得的解在ξp的任何變動下均為可行解，但是會對目標函數(shù)值造成較大的影響，顯然，此時得到的解過于保守。而應用Bertsimas和Sim[16]提出的魯棒方法，決策者可以通過控制Γij的值，調節(jié)解的魯棒性來避免對目標函數(shù)值造成較大的影響。通過引入輔助參數(shù)ωij和rp，由線性規(guī)劃的強對偶理論將約束（20）轉化為如下魯棒線性對應式：

此外，約束（11）中也含有唯一的不確定性因素ξp，考慮到在場箱離場時間與ξp的實際關系，這里根據(jù)Soyster[18]提出的方法將約束（11）轉化為：

由以上的轉換可得，自動化集裝箱碼頭船舶配載魯棒優(yōu)化模型為：

s.t.（8）～（10），（12）～（15），（17）～（19），（25）～（29）

5 基于改進的禁忌搜索算法

本文所研究的集裝箱船舶配載問題是一個多目標多約束的組合優(yōu)化問題，屬于NP-hard問題[19-20]，當問題的規(guī)模較小時，尚且可以使用Cplex求解器利用精確算法求得最優(yōu)解，但當問題的規(guī)模較大，且決策變量維度較多時，欲求準確的最優(yōu)解已基本不可能，并且船舶大型化使得配載問題更加復雜。因此從滿足實際應用的角度出發(fā)，本文基于配載問題自身的特點設計了基于編號與排序的禁忌搜索算法。

禁忌搜索算法（Tabu Search，TS）由美國科羅拉多大學系統(tǒng)科學家Glover[21]教授于1986 年首次提出，是一種擴展鄰域的啟發(fā)式搜索辦法，是對人工智能的一種模擬，用于求解大規(guī)模組合優(yōu)化問題的有效算法。該算法能以較大概率跳出局部最優(yōu)點，通過引入一個靈活的存儲結構和相應的禁忌準則來避免迂回搜索，并通過藐視準則來挽回一些被禁忌的優(yōu)良狀態(tài)，進而保證多樣化的有效搜索以最終實現(xiàn)全局優(yōu)化。禁忌搜索涉及到鄰域結構（neighborhood）、禁忌表（tabu list）、禁忌長度（tabu length）、候選解（candidate）、藐視準則（aspiration criterion）、禁忌對象和終止準則等環(huán)節(jié)。

5.1 參數(shù)設置與初始解

配載所需數(shù)據(jù)包括在場箱信息、預配船圖及CWP等，對配載所需數(shù)據(jù)進行詳細梳理，如圖2 所示，這樣，“i”行的集裝箱與“p”行的船箱位一一對應，就可以用來表示計劃配載的結果，因此解的形式如式（31）所示：

因為在場箱離場時間與橋吊開始作業(yè)時間直接相關，并且翻箱量與箱-位安排即配載直接相關，因此確定了這樣的x，也就確定了模型中的決策變量xipt與zij。

下面說明禁忌搜索的重要參數(shù)設計。

圖2 解的形式與數(shù)據(jù)結構示意

（1）初始解

TS對于初始解具有較強的依賴性，較好的初始解可使TS在解空間中搜索到更好的解，為了獲得一個較好初始解，如圖3所示，首先對預配計劃箱位根據(jù)預配規(guī)則進行編號和排序（按卸貨港、箱位尺寸進行升序排序，對于同一卸貨港和箱位尺寸的箱位再根據(jù)倍位、層位和排位進行升序排序）形成預配計劃箱位列表，再對在場箱進行編號和排序（先根據(jù)卸貨港、箱位尺寸進行升序排序，對于同一卸貨港和箱位尺寸的集裝箱再根據(jù)集裝箱重量進行降序排序）形成在場箱列表，若在場箱（20′與40′箱）多于預配計劃箱，以20′箱為例，將在場箱列表中的最后一個集裝箱與預配計劃箱位列表中的最后一個箱位對應，以此向前截取連續(xù)的在場箱列表，滿足與預配計劃箱位列表全部箱位一一對應，40′箱同樣操作，這樣所有船箱位都安排了在場箱，構成一個基本解xr。

圖3 初始解的獲得

在得到一個基本解xr（以及后續(xù)解的交換）后，需要驗證其可行性，考慮到所有約束以及不確定性參數(shù)對配載結果的影響，在此作如下定義：

以上參數(shù)代表分別代表對相應約束的違背程度，其中ν(αij(xr),βp(xr),γbh(xr))表示所有約束的總違背程度，如果ν(αij(xr),βp(xr),γbh(xr))=0，則可認為xr滿足所有約束，為一個初始可行解F。如果ν(αij(xr),βp(xr),γbh(xr))≠0，則將xr的評價函數(shù)eval(x)定義為如下：

其中，f(x)為實際目標函數(shù)值。若選擇合適的懲罰函數(shù)penalty(x)，則無論不可行解的實際目標函數(shù)值如何，都不會選為最優(yōu)解。

（2）鄰域結構

采用隨機混合鄰域結構。輪盤賭選擇一種鄰域交換方法，獲得新的解，在迭代過程中每次都隨機選用其中的一種。

①交換算子M1(xr,i,j)

在配載方案xr中，若任意的兩倍位Bayi與Bayj之間具有同類屬性的箱子，選擇Bayi與Bayj中同類數(shù)量少的箱組按照原先的輕壓重進行兩倍位間的整體轉移交換。

②交換算子M2(xr,i,j)

在配載方案xr中，若同類同貝的多個層中的箱子都可以交換，則隨機選擇一層中可交換的i和j進行交換。

③交換算子M3(xr,i,j)

在配載方案xr中，若同類同貝的多個層中的箱子都可以交換，則將所有層中可交換的i和j進行交換。

交換后的解仍然滿足預配和輕壓重約束，通過交換即可產(chǎn)生一個鄰域解，由i到i′的交換示意如圖4所示。

圖4 解的交換示意圖

（3）候選解集

在當前狀態(tài)的鄰域解集中選取一定數(shù)量的較優(yōu)解構成候選解集CandidateSet。

（4）評價函數(shù)

取模型目標函數(shù)作為評價函數(shù)，其中不可行解的評價函數(shù)包括懲罰函數(shù)penalty(x)。

（5）禁忌對象

為了獲得較大搜索范圍，選擇解的簡單變化，即箱-位的一個全排列作為禁忌對象。

（6）禁忌長度

將禁忌長度設為一個常數(shù)TabuLength。

（7）藐視準則

選擇基于適配值的準則作為藐視準則。

（8）終止準則

最后設定最大迭代步數(shù)為一個常數(shù)MaxIterNum，同時，若在一定迭代次數(shù)（Maxfreq）內當前最優(yōu)解無優(yōu)化趨勢，則提前跳出搜索過程。

5.2 算法步驟

以初始基本解即當前初始箱-位匹配為例。首先設置模型與算法參數(shù)，假設算例中集裝箱數(shù)為Container-Num，則確定算法的最大迭代次數(shù)MaxIterNum，禁忌長度TabuLength，候選解個數(shù)CandidateNum，候選解集CandidateSet為空，最后設定空禁忌表TL，具體的迭代步驟如下：

步驟1 輸入初始基本解xb，置當前迭代次數(shù)d=1，當前最優(yōu)解無優(yōu)化迭代次數(shù)freq=0，進入步驟2。

步驟2 判斷xb是否滿足船舶箱槽重量約束和箱區(qū)作業(yè)約束，是則進入步驟4，否則進入步驟3（Swap）。

步驟3 隨機選擇一種交換算子，進入步驟3.1。

步驟3.1 若選擇交換算子M1，根據(jù)交換規(guī)則進行交換，進入步驟4；否則，進入步驟3.2。

步驟3.2 若選擇交換算子M2，根據(jù)交換規(guī)則進行交換，進入步驟4；否則，進入步驟3.3。

步驟3.3 若選擇交換算子M2，根據(jù)交換規(guī)則進行交換，進入步驟4。

步驟4 置初始解x0=xb，當前解x=xb，當前最優(yōu)解BSF=x0，計算當前最優(yōu)解對應的最優(yōu)值BV=GetValue(BSF),FreqValue=BV，進入步驟5。

步驟5 判斷當前d是否小于MaxIterNum，是，多次執(zhí)行步驟3（Swap），將得到的可行鄰域解置于CandidateSet中，直至CandidateSet中的候選解數(shù)目達到CandidateNum，計算各候選解的目標值V=GetValue（each xinCandidateSet），進入步驟7；否則，進入步驟6。

步驟6 返回BSF、BV，記錄當前箱位匹配對應的最優(yōu)配載方案及其對應的目標函數(shù)值，再將在場箱列表中的倒數(shù)第二個集裝箱與預配計劃箱位列表中的最后一個箱位對應（箱-位平滑移動匹配，如圖5所示），以此向前截取連續(xù)的在場箱列表，滿足與預配計劃箱位列表的全部箱位一一對應，返回步驟1，直至在場箱列表中的第一個集裝箱與預配計劃箱位列表中的最后一個箱位對應，選擇一個目標函數(shù)值最小的配載方案作為最終的最優(yōu)配載方案，算法結束。

圖5 箱-位平滑移動匹配

步驟7 判斷min(V)是否小于BV，是，令BSF=x，x置于TL中，更新TL；否則，將x置為鄰域中非禁忌的最優(yōu)x，x置于TL中，更新TL，進入步驟8。

步驟8 判斷FreqValue是否小于等于BV，是則freq=freq+1，進入步驟 9；否則，F(xiàn)reqValue=BV，freq=0，進入步驟10。

步驟9 判斷freq是否大于等于Maxfreq，是則返回步驟6；否則，進入步驟10。

步驟10d=d+1，返回步驟5。

6 算例分析

6.1 箱區(qū)作業(yè)均衡因素對配載結果的影響

將上海洋山港區(qū)某集裝箱碼頭配載所需的數(shù)據(jù)分為9 組，生成規(guī)模大小不同的9 個算例I1～I9，算例數(shù)據(jù)如表1所示。其中，箱量表示該算例中的在場箱總箱數(shù)（預配箱數(shù)等于在場箱數(shù)），卸貨港數(shù)表示該算例中的在場箱分別屬于幾個卸貨港，T堆棧數(shù)表示該算例中的在場箱中，一堆只有1 個集裝箱的堆棧數(shù)，2T、3T和4T以此類推。

根據(jù)該碼頭的實際作業(yè)情況確定模型中的部分參數(shù)，其中，箱區(qū)單位小時的最大作業(yè)箱量qb=15 箱，箱位p的開始裝箱時間由已知的CWP確定，鑒于ACT在場箱分布相對分散，取集裝箱i從其所在的堆場箱區(qū)到最終的箱位p所對應的船舶倍位的水平運輸時間τip=3 min，箱區(qū)內一次翻箱時間σ1=3 min，箱區(qū)不均衡程度較小時不一定導致作業(yè)等待，但是不均衡程度較大時很有可能造成等待，因此綜合考慮，取不均衡可能導致的等待的懲罰時間σ2=2 min，模型參數(shù)確定后，在MatLab R2016b中利用算法對模型進行求解。實驗使用的電腦配置為Win7 64位操作系統(tǒng)，4 GB運行內存，處理器為Inter?Core? i5-320M，CPU頻率為2.6 GHz。算法的相關參數(shù)定義：候選解個數(shù)CandidateNum=50，禁忌長度TabuLength取大于ContainerNum0.5的最小整數(shù)，算法迭代的最大次數(shù)MaxIterNum=200，允許當前最優(yōu)解無優(yōu)化趨勢的最大迭代次數(shù)Maxfreq=50。

表1 算例數(shù)據(jù)說明

對于每個算例，同時取不均衡可能導致的等待的懲罰時間σ2=0，即不考慮箱區(qū)作業(yè)均衡因素對配載結果的影響，在得出各案例最優(yōu)配載方案后，計算各配載方案的箱區(qū)作業(yè)不均衡程度（箱），與σ2=2 min 時的結果進行比較，分析箱區(qū)作業(yè)均衡因素對配載結果的影響。在參數(shù)k=λ1∶λ2=1∶10的情況下，計算結果如表2和表3所示。

由表2 可以看出，9 個算例中，禁忌算法都能夠在21～1 200 s 的時間之內求解出結果，而Cplex 只能解決箱量為20、50、100、150箱的案例，但求解質量較差由此可見Cplex在求解復雜的大規(guī)模配載問題時效率較差，相比之下，本文算法對求解大規(guī)模集裝箱碼頭配載問題有著很好的求解效果和求解效率。

表2 算例結果

表3 均衡因素對配載結果的影響

由表3可以看出，各案例在不考慮箱區(qū)作業(yè)均衡因素時得到的箱區(qū)作業(yè)不均衡箱量比考慮箱區(qū)作業(yè)均衡因素時得到的箱區(qū)作業(yè)不均衡箱量分別高出0%，0%，23.1%，20.0%，22.6%，8.3%，29.3%，34.1%和22.4%，平均高出17.8%。高出的不均衡箱量勢必影響船舶裝船作業(yè)效率，因此在自動化集裝箱碼頭配載時亟需考慮箱區(qū)作業(yè)均衡因素。

完整的船舶配載計劃由在場箱裝船作業(yè)順序以及合理的倍位船圖構成，在場箱裝船作業(yè)順序已由CWP確定，因此圖6 展示了集裝箱、船箱位與場箱位的對應關系（該配載結果取自算例I9），其中船舶53 倍位的這些集裝箱分別來自第10 箱區(qū)57 倍位、50 箱區(qū)29 倍位、56箱區(qū)43倍位、64箱區(qū)23倍位和72箱區(qū)65倍位，如位于 64 箱區(qū) 23 倍位 5 排 1 層的在場箱 CAIU6122728 被安排在了船上53倍位08排04層的箱位。

6.2 橋吊作業(yè)時間不確定性對配載結果的影響

圖6 集裝箱、船箱位與場箱位的對應關系

依然選擇前一節(jié)的數(shù)據(jù)進行算例分析，并選擇該船的17 艙66 倍位中的出口箱為例。預配船圖如圖7 所示。該碼頭的所有在場箱堆存信息已知，包括集裝箱號、尺寸、箱重、卸貨港、場箱位（箱區(qū)、倍位、排位和層位），共涉及147個在場待裝集裝箱。需要說明的是，在17 艙 66 倍位中，計劃配載箱位數(shù)為 90 個 40′箱，而滿足該倍位的卸貨港配載要求的在場箱共有147個40′箱，通過平滑移動的方法選取90個在場箱并安排到預配箱位中，完成配載方案。

為了分析魯棒水平對配載方案和目標函數(shù)中各項指標的值的影響，分別對Γij取[0，90]中間隔為10 的不同值，同時部分參數(shù)取值如下：k=λ1∶λ2=1∶1 ，σ1=3，，得到的結果如表4所示。

從表4可以看出，隨著Γij取值的不斷增大，相比于總目標函數(shù)值，表明隨著保守系數(shù)Γij取值的增大，雖然求得的解在部分橋吊作業(yè)時間在其取值區(qū)間任意變化時，均為可行解，但是會對目標函數(shù)造成較大的影響?？傃b船時間與不均衡程度，翻箱量也呈現(xiàn)大幅增長的趨勢，當=Γij=|P|=90 時的翻箱量已經(jīng)比Γij=0 的翻箱量多出了2 000%，主要原因如下：

圖7 17艙位66倍位預配船圖

表4 魯棒水平（Γij 值）對目標函數(shù)中各項指標值的影響

顯然此時的解過于保守，因此，決策者可以通過選擇合適的Γij的值來應對橋吊作業(yè)時間的不確定性，同時獲得一個比較滿意的配載方案。另一方面，魯棒模型旨在獲得一個更優(yōu)的魯棒解，在保證解有較好魯棒性的同時，也會對配載方案的決策產(chǎn)生重要影響。表5是確定（Γij=0）與不確定情況下，17艙66倍位的集裝箱的來源堆場場地的對比。

表5 確定與不確定情況下集裝箱來源場地的對比

從表5 可以看出，不確定性情況下，算法更傾向于“集中配載”（其中箱區(qū)A2、A4與B4 這種集中效果最為顯著），即用盡可能少的箱區(qū)和箱區(qū)倍位滿足船舶倍位的配箱要求，因此將同一堆場甚至是同一倍位的在場箱配于船上同一倍位，這種“集中配載”之所以能夠使配載方案更優(yōu)，原因可由圖8進行說明。

圖8 中，“（）”里的數(shù)字表示該箱位的作業(yè)關號，a、b、c、d為4個集裝箱，4個集裝箱裝船前的箱區(qū)堆存情況以及實配船圖如圖所示，例如位于箱區(qū)第4層的集裝箱a 配載到船上2 倍位04 排02 層的位置，且作業(yè)關號為5。在確定情況下，2倍（1）（2）（3）（4）按計劃時間與順序完成裝箱，2倍（5）（6）開始時間早于10倍（3）（4）開始時間，這樣配載沒有翻箱出現(xiàn)。但是當2倍（1）（2）（3）（4）的作業(yè)時間不確定時，假設作業(yè)時間過長導致后續(xù)裝箱開始時間延遲，進而導致10倍（3）（4）先做裝船作業(yè)，則c、d裝船時就需要翻箱。

圖8 假設確定性情況下兩倍位的配載結果

如果把a、b、c、d配在同一船舶倍位里，甚至是同一根槽（其中一種可能），則即使前序作業(yè)有一定延遲，也不會造成翻箱數(shù)增加。

7 結論

針對ACT 的作業(yè)特點，說明箱區(qū)作業(yè)均衡因素與橋吊作業(yè)時間的不確定性對配載結果有著潛在的影響。針對箱區(qū)作業(yè)均衡因素，以最小化裝船作業(yè)時單位時間不同箱區(qū)出箱量的不均衡程度和總裝船時間為目標，建立考慮箱區(qū)作業(yè)均衡因素的ACT 配載混合整數(shù)規(guī)劃模型。針對橋吊作業(yè)時間的不確定性，引入“盒式”集合表達不確定因素的取值范圍，將確定性配載優(yōu)化模型轉化為考慮橋吊作業(yè)時間不確定性的船舶配載魯棒優(yōu)化模型，并設計基于編號與排序的禁忌搜索算法對模型進行求解。算例表明，同CPLEX相比，禁忌搜素算法有著很好的求解效率與效果，在不考慮箱區(qū)作業(yè)均衡因素時(σ2=0)得到的箱區(qū)作業(yè)不均衡箱量比考慮箱區(qū)作業(yè)均衡因素時（σ2=2 min）得到的箱區(qū)作業(yè)不均衡箱量分別高出平均高出17.8%，說明算法可有效降低裝船作業(yè)的箱區(qū)作業(yè)量的不均衡程度；而橋吊作業(yè)時間的不確定性直接導致“集中配載”的出現(xiàn)，這種“集中配載”能夠使配載方案更優(yōu)。

此外，由于配載的復雜性，進一步細化配載問題的相關約束并提高算法的求解速度是下一步研究的重點，從而幫助這一配載方法更好地應用到碼頭的實際生產(chǎn)作業(yè)中。