丁 一，田 亮，龔 杰

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

1 引言

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

圖1 集裝箱碼頭堆場(chǎng)布局圖

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

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

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

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

2 問(wèn)題描述

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

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

3 確定性模型建立

3.1 參數(shù)

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

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

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

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

H：作業(yè)總時(shí)間內(nèi)小時(shí)段集合，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內(nèi)；

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

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

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

θp：箱位p的開(kāi)始裝箱時(shí)間，其中?p∈P；

τip：集裝箱i從其所在的堆場(chǎng)箱區(qū)到最終的箱位p所對(duì)應(yīng)的船舶倍位的水平運(yùn)輸時(shí)間，其中?i∈N,p∈P；

L：表示船上根據(jù)預(yù)配載計(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ū)內(nèi)的一次翻箱時(shí)間；

σ2：對(duì)不均衡可能導(dǎo)致的等待的懲罰時(shí)間。

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

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

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

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

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

3.2 決策變量

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

zij：0-1變量，當(dāng)集裝箱i先于j離場(chǎng)時(shí)取1，否則為0，其中

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

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

3.3 假設(shè)條件

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

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

（3）只考慮裝船情況，假設(shè)到港后進(jìn)口箱均已卸載。

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

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

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

3.4 完整模型

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

（1）最小化總裝船時(shí)間：

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

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

由此，式（2）轉(zhuǎn)化為式（5）：

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

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

s.t.

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

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

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

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

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

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

gp：箱位p的作業(yè)關(guān)號(hào)，?p∈P；

θp：箱位p的開(kāi)始裝箱時(shí)間（CWP預(yù)計(jì)值，名義值）；

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

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

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

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

其中：

此時(shí)，當(dāng)

時(shí)，必有zij=1。

如果：

時(shí)，只有當(dāng)

時(shí)，才有zij=1。

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

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

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

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

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

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

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

5 基于改進(jìn)的禁忌搜索算法

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

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

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

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

因?yàn)樵趫?chǎng)箱離場(chǎng)時(shí)間與橋吊開(kāi)始作業(yè)時(shí)間直接相關(guān)，并且翻箱量與箱-位安排即配載直接相關(guān)，因此確定了這樣的x，也就確定了模型中的決策變量xipt與zij。

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

圖2 解的形式與數(shù)據(jù)結(jié)構(gòu)示意

（1）初始解

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

圖3 初始解的獲得

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

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

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

（2）鄰域結(jié)構(gòu)

采用隨機(jī)混合鄰域結(jié)構(gòu)。輪盤賭選擇一種鄰域交換方法，獲得新的解，在迭代過(guò)程中每次都隨機(jī)選用其中的一種。

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

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

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

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

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

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

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

圖4 解的交換示意圖

（3）候選解集

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

（4）評(píng)價(jià)函數(shù)

取模型目標(biāo)函數(shù)作為評(píng)價(jià)函數(shù)，其中不可行解的評(píng)價(jià)函數(shù)包括懲罰函數(shù)penalty(x)。

（5）禁忌對(duì)象

為了獲得較大搜索范圍，選擇解的簡(jiǎn)單變化，即箱-位的一個(gè)全排列作為禁忌對(duì)象。

（6）禁忌長(zhǎng)度

將禁忌長(zhǎng)度設(shè)為一個(gè)常數(shù)TabuLength。

（7）藐視準(zhǔn)則

選擇基于適配值的準(zhǔn)則作為藐視準(zhǔn)則。

（8）終止準(zhǔn)則

最后設(shè)定最大迭代步數(shù)為一個(gè)常數(shù)MaxIterNum，同時(shí)，若在一定迭代次數(shù)（Maxfreq）內(nèi)當(dāng)前最優(yōu)解無(wú)優(yōu)化趨勢(shì)，則提前跳出搜索過(guò)程。

5.2 算法步驟

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

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

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

步驟3 隨機(jī)選擇一種交換算子，進(jìn)入步驟3.1。

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

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

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

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

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

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

圖5 箱-位平滑移動(dòng)匹配

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

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

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

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

6 算例分析

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

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

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

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

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

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

表2 算例結(jié)果

表3 均衡因素對(duì)配載結(jié)果的影響

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

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

6.2 橋吊作業(yè)時(shí)間不確定性對(duì)配載結(jié)果的影響

圖6 集裝箱、船箱位與場(chǎng)箱位的對(duì)應(yīng)關(guān)系

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

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

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

圖7 17艙位66倍位預(yù)配船圖

表4 魯棒水平（Γij 值）對(duì)目標(biāo)函數(shù)中各項(xiàng)指標(biāo)值的影響

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

表5 確定與不確定情況下集裝箱來(lái)源場(chǎng)地的對(duì)比

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

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

圖8 假設(shè)確定性情況下兩倍位的配載結(jié)果

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

7 結(jié)論

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

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