丁 一 龔 杰 林國(guó)龍

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

0 引 言

20世紀(jì)初，以高效率、高協(xié)作和多式聯(lián)運(yùn)為特點(diǎn)的國(guó)際集裝箱運(yùn)輸業(yè)得到迅速發(fā)展?，F(xiàn)如今，船舶大型化乃至超大型化的趨勢(shì)逐步顯現(xiàn)，世界集裝箱海運(yùn)量的快速增長(zhǎng)和船舶的大型化，一方面提高了船舶公司的規(guī)模效益，另一方面卻給碼頭的生產(chǎn)運(yùn)作帶來(lái)了極大的挑戰(zhàn)。在此背景下，自動(dòng)化集裝箱碼頭ACT(Automated Container Terminal)應(yīng)運(yùn)而生，由于其在節(jié)省碼頭人力成本、提高港口通過(guò)能力、降低設(shè)備能源消耗、提升港口形象等方面具有顯著的優(yōu)勢(shì)，ACT已成為未來(lái)集裝箱碼頭發(fā)展的必然趨勢(shì)。ACT裝卸船作業(yè)的設(shè)備及運(yùn)作流程如圖1所示。在船舶大型化與碼頭自動(dòng)化背景下，碼頭作業(yè)成本與效率日益受到人們的關(guān)注。影響碼頭作業(yè)成本與效率的因素較多，其中一個(gè)不容忽視的因素就是船舶配載的合理性。一方面，配載必須滿足船舶的運(yùn)輸要求，即船舶的航行安全、集裝箱及其貨物的運(yùn)輸質(zhì)量和船舶營(yíng)運(yùn)的經(jīng)濟(jì)效益。另一方面，也應(yīng)兼顧集裝箱碼頭裝卸工藝和操作方式，使碼頭能合理、有序、有效地組織生產(chǎn)。配載后每個(gè)集裝箱與船舶箱位一一對(duì)應(yīng)，每個(gè)船箱位都可用貝位(Bay)、排位(Row)和層位(Tier)唯一表示，每個(gè)特種箱都要符合船舶規(guī)范，配載要力求科學(xué)合理，使其具有很強(qiáng)的操作性，從而保證連續(xù)高效的裝船作業(yè)并滿足船期要求[1]。

圖1 ACT作業(yè)設(shè)備及運(yùn)作流程

船舶公司和碼頭管理者同時(shí)參與船舶的配載過(guò)程，船舶公司根據(jù)訂艙資料在滿足預(yù)配載原則的基礎(chǔ)上制定預(yù)配方案。預(yù)配通常為粗計(jì)劃，用以確定箱位分布及箱位的類別屬性與卸貨港等，其中類別屬性包括20/40/45英尺箱位和具體箱型等信息。預(yù)配的目的是希望碼頭兼顧整條航線卸貨港的裝卸要求來(lái)制定配載方案，是碼頭計(jì)劃員制定實(shí)配的參考依據(jù)，船舶預(yù)配載示意圖如圖2所示。實(shí)配則是為在場(chǎng)箱一一確定具體的船箱位。

圖2 集裝箱貝位預(yù)配船圖示意圖

目前學(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)題中的有效性；而Parreo等[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è)時(shí)，同一時(shí)間各箱區(qū)作業(yè)量一旦出現(xiàn)較大的不均衡，就會(huì)導(dǎo)致部分箱區(qū)軌道吊RMG(Rail-Mounted Gantry Crane)作業(yè)效率偏低以及自動(dòng)導(dǎo)引運(yùn)輸車AGV(Automated Guided Vehicle)和橋吊QC(Quay Crane)的等待，這樣勢(shì)必影響總裝船效率和船期，因此引入ACT箱區(qū)作業(yè)均衡性這一因素就顯得尤為重要。但目前以ACT為背景的配載研究較少，缺乏ACT箱區(qū)的作業(yè)均衡對(duì)實(shí)際積載作業(yè)影響的研究。故本文從碼頭角度出發(fā)，在考慮上述常規(guī)配載約束的基礎(chǔ)上，優(yōu)化配載方案，使得裝船作業(yè)過(guò)程中各箱區(qū)的作業(yè)量盡量趨于均衡，減少不均衡導(dǎo)致的作業(yè)等待時(shí)間，進(jìn)而提高裝船效率，縮短船期。

1 問(wèn)題描述

從根本上來(lái)說(shuō)，船舶配載問(wèn)題可以劃分為兩個(gè)子問(wèn)題：

(1) “When”問(wèn)題，即在場(chǎng)箱何時(shí)離場(chǎng)，也即裝船作業(yè)順序(loading sequence)問(wèn)題。如果在堆場(chǎng)中，配載船圖上先裝船的集裝箱被后裝船的集裝箱壓在下面，就需要先移開(kāi)其他的集裝箱才能獲取要裝船的集裝箱，顯然該操作將產(chǎn)生堆場(chǎng)翻箱作業(yè)。圖3 給出了一個(gè)處于中間層的集裝箱B取箱時(shí)的翻箱過(guò)程：RMG對(duì)頂層集裝箱A上鎖，隨后將該集裝箱移開(kāi)至鄰近位置并解鎖，接著RMG將指定集裝箱B移走并將頂層的集裝箱A放回原來(lái)位置。

圖3 堆場(chǎng)集裝箱的翻箱過(guò)程示意圖

做配載時(shí)，待裝船的在場(chǎng)箱的場(chǎng)箱位已知，是否翻箱或有多少翻箱完全取決于配載的結(jié)果，即配載船圖。例如在圖4中，i和j是兩個(gè)待裝船的在場(chǎng)箱，j剛好在i的上方，這時(shí)候在船上，如果把j配在i所在的同一根箱槽，且位于i的上方，那么在i和j的裝船作業(yè)時(shí)，i必須先于j出場(chǎng)，這時(shí)翻箱就不可避免?！癢hen”問(wèn)題的結(jié)果就是最優(yōu)的裝船作業(yè)順序。

圖4 變量說(shuō)明

(2) “Where”問(wèn)題，即該箱離場(chǎng)后去往何處，即被安排在某一船箱位，“Where”問(wèn)題的結(jié)果就是配載的貝位船圖。同時(shí)，ACT船舶配載問(wèn)題又是一個(gè)耦合問(wèn)題，除了與船舶密切相關(guān)，還與堆場(chǎng)密切聯(lián)系。一方面需要考慮常規(guī)實(shí)配原則，即船舶航行安全要求，并減少堆場(chǎng)的翻箱，另一方面則需要考慮實(shí)配裝箱過(guò)程中堆場(chǎng)箱區(qū)的作業(yè)能力與作業(yè)均衡。

傳統(tǒng)的集裝箱碼頭堆場(chǎng)布局和ACT堆場(chǎng)布局如圖5所示。在傳統(tǒng)集裝箱碼頭堆場(chǎng)中，堆場(chǎng)箱區(qū)平行于碼頭岸線布置，箱區(qū)龍門吊大多使用的是輪胎吊RTG(Rubber-Tyred Gantry Crane)。輪胎吊的運(yùn)行軌跡也平行于碼頭岸線，且輪胎吊可以跨箱區(qū)作業(yè)，收取箱點(diǎn)不固定。而在ACT堆場(chǎng)中，堆場(chǎng)箱區(qū)垂直于碼頭岸線布置，箱區(qū)龍門吊大多使用軌道吊，且軌道吊的運(yùn)行軌跡也垂直于碼頭岸線，箱區(qū)與箱區(qū)之間一般沒(méi)有作業(yè)區(qū)域(設(shè)有懸臂吊的箱區(qū)除外)，只設(shè)有海側(cè)和陸側(cè)交換區(qū)作為收取箱點(diǎn)，因此收取箱點(diǎn)固定，屬于單側(cè)作業(yè)模式。

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

如果同一時(shí)間內(nèi)部分ACT箱區(qū)裝卸量偏小，而部分ACT箱區(qū)裝卸量偏大，即作業(yè)不均衡，對(duì)于裝卸量偏大的箱區(qū)，一方面這些箱區(qū)的軌道吊連續(xù)作業(yè)時(shí)間過(guò)長(zhǎng)，從而導(dǎo)致軌道吊司機(jī)的疲乏，其工作積極性與作業(yè)效率必然降低，并且作業(yè)量的大小直接影響到軌道吊的壽命。另一方面，不均衡就意味著個(gè)別箱區(qū)裝卸任務(wù)過(guò)于集中，而單位時(shí)間內(nèi)單臺(tái)海側(cè)軌道吊的作業(yè)能力有限，一旦某個(gè)箱區(qū)的發(fā)箱指令過(guò)于集中，就會(huì)造成某一段時(shí)間內(nèi)該箱區(qū)作業(yè)量過(guò)大，必然產(chǎn)生軌道吊作業(yè)沖突。這樣AGV和岸橋的等待時(shí)間就會(huì)增加，從而影響港口作業(yè)效率，影響總裝船時(shí)間，進(jìn)而影響船期，因此發(fā)箱時(shí)考慮箱區(qū)之間的作業(yè)均衡至關(guān)重要。

船舶配載的目標(biāo)在于減少船舶在港時(shí)間，繼而減少船舶的碼頭作業(yè)費(fèi)用?？傃b船時(shí)間可以分為場(chǎng)內(nèi)、場(chǎng)到船和船上作業(yè)時(shí)間三部分，總裝船作業(yè)時(shí)間構(gòu)成如圖6所示。

圖6 總裝船作業(yè)時(shí)間構(gòu)成

而在制定橋吊作業(yè)計(jì)劃CWP(Crane Working Planning)(橋吊的作業(yè)貝位與時(shí)間的對(duì)應(yīng)關(guān)系)階段，每個(gè)橋吊分配到的貝位裝箱任務(wù)已經(jīng)明確，因此船上作業(yè)時(shí)間在此不作考慮。相比于RMG就位和取箱時(shí)間，堆場(chǎng)翻箱時(shí)間取決于堆場(chǎng)取箱時(shí)的先后順序，且占據(jù)了絕大部分場(chǎng)內(nèi)作業(yè)時(shí)間。通過(guò)合理的配載計(jì)劃能夠切實(shí)減少場(chǎng)內(nèi)作業(yè)時(shí)間，進(jìn)而減少裝船時(shí)間，最終最小化總裝船時(shí)間簡(jiǎn)化為最小化翻箱時(shí)間與水平運(yùn)輸時(shí)間之和。

因此，本文的研究問(wèn)題就是在給定船舶預(yù)配總圖、 CWP和待裝船的在場(chǎng)箱信息后，考慮常規(guī)船舶配載約束，如輕壓重約束、箱槽最大承載重量約束與船舶穩(wěn)性約束等。同時(shí)考慮堆場(chǎng)軌道吊作業(yè)量約束，以最小化總裝船時(shí)間，即翻箱時(shí)間與水平運(yùn)輸時(shí)間之和。并且盡可能使堆場(chǎng)箱區(qū)作業(yè)均衡，即最小化同時(shí)段內(nèi)箱區(qū)最大與最小作業(yè)量的差額，建立混合整數(shù)規(guī)劃模型以確定最優(yōu)的集裝箱裝船作業(yè)順序，進(jìn)而制定合理的貝位船圖，即完整的船舶配載方案。

2 數(shù)學(xué)模型構(gòu)建

2.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表示第3小時(shí)內(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={1,…,|L|}；

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

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

Δi：表示與集裝箱i在同一箱區(qū)同一堆棧(同箱區(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，如果IFIBib=0，則說(shuō)明集裝箱i無(wú)論如何不可能從箱區(qū)b離場(chǎng)，那么xipt=0，因此有關(guān)系式：xipt≤IFIBib；

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

2.2 決策變量

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

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

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

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

2.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í)裝船造成的翻箱。

2.4 完整模型

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

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

(1)

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

(2)

為了便于計(jì)算，可將式(2)線性化，定義：

(3)

(4)

于是，式(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ù)：

(6)

于是可得完整模型如下：

(7)

(8)

(9)

xipt≤IFIPip?i∈N,p∈P,t∈T

(10)

xipt=0 ?i∈N,p∈P,t≠TIPip

(11)

(12)

(13)

(14)

(15)

?i∈N,j∈Δi

(16)

(17)

(18)

xipt,zij=0或1 ?i,j∈N,p∈P,t∈T

(19)

式(7)表示目標(biāo)函數(shù)最小化實(shí)配過(guò)程的集裝箱裝船作業(yè)時(shí)間和最小化不同箱區(qū)作業(yè)量的不均衡程度。式(8)、式(9)為匹配約束，即一個(gè)集裝箱只能被安排到一個(gè)且僅一個(gè)船箱位中，而一個(gè)箱位也只能放一個(gè)集裝箱。式(10)表示集裝箱與船箱位的匹配需要滿足預(yù)配要求。式(11)表示在場(chǎng)箱離場(chǎng)須符合CWP作業(yè)時(shí)間安排。式(12)為輕壓重約束，即船上同一根箱槽的集裝箱，重箱一定位于輕箱的下層。式(13)為船舶單根箱槽的裝載重量約束，規(guī)定每一根箱槽堆碼的總重量不允許超過(guò)設(shè)定的最大值，且依據(jù)Monaco等[10]盡量按船舶的穩(wěn)性要求設(shè)定所有箱槽的裝載總重量的分布，以簡(jiǎn)化船舶穩(wěn)性約束。式(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)表示決策變量類型。

3 基于禁忌搜索的模型求解算法

本文所研究的集裝箱船舶配載問(wèn)題是一個(gè)多目標(biāo)、多約束的組合優(yōu)化問(wèn)題，更是一個(gè)NP-hard問(wèn)題[13-14]。當(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ì)了基于禁忌搜索的模型求解算法。

禁忌搜索算法TS(Tabu Search)由美國(guó)科羅拉多大學(xué)系統(tǒng)科學(xué)家Glover[15]教授于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)、禁忌表、禁忌長(zhǎng)度、候選解、藐視準(zhǔn)則、禁忌對(duì)象和終止準(zhǔn)則等環(huán)節(jié)。

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

配載所需數(shù)據(jù)包括具體的在場(chǎng)箱與船箱位、在場(chǎng)箱的場(chǎng)箱位與船上箱位位置、各自對(duì)應(yīng)的卸貨港與尺寸以及船箱位的橋吊開(kāi)始作業(yè)時(shí)間等。將配載所需數(shù)據(jù)進(jìn)行了羅列與詳細(xì)梳理，如圖7所示，“i”行的集裝箱與“p”行的船箱位一一對(duì)應(yīng)，用來(lái)表示計(jì)劃配載的結(jié)果，解的形式如下所示：

(20)

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

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

下面說(shuō)明禁忌搜索的重要參數(shù)設(shè)計(jì)。鄰域的獲得采用多點(diǎn)交換或者說(shuō)是多貝位交換的方式，即將同類同貝同層中的任意兩集裝箱進(jìn)行交換(Swap)。交換后的解仍然滿足預(yù)配和輕壓重約束，通過(guò)交換即可產(chǎn)生一個(gè)鄰域解，由i到i’的交換示意如圖8所示。在當(dāng)前狀態(tài)的鄰域解集中選取一定數(shù)量的較優(yōu)解構(gòu)成候選解集CandidateSet；適配值函數(shù)取目標(biāo)函數(shù)；為了獲得較大搜索范圍，選擇解的簡(jiǎn)單變化，即箱-位的一個(gè)全排列作為禁忌對(duì)象；將禁忌長(zhǎng)度設(shè)為一個(gè)常數(shù)TabuLength；選擇基于適配值的準(zhǔn)則作為藐視準(zhǔn)則；設(shè)定最大迭代步數(shù)為一個(gè)常數(shù)MaxIterNum，同時(shí)，若在一定迭代次數(shù)(Maxfreq)內(nèi)當(dāng)前最優(yōu)解無(wú)優(yōu)化趨勢(shì)，則提前跳出搜索過(guò)程。

圖8 解的交換示意圖

TS對(duì)于初始解具有較強(qiáng)的依賴性，一個(gè)較好的初始解可使TS在解空間中搜索到更好的解。為了獲得一個(gè)較好初始解，需要先對(duì)所有在場(chǎng)箱和船箱位進(jìn)行編號(hào)，再進(jìn)行排序。具體的排序規(guī)則是：按卸貨港、箱位尺寸進(jìn)行升序排序，對(duì)于同一卸貨港和箱位尺寸的箱位再根據(jù)箱位位置進(jìn)行排序，具體是按貝位、層位和排位進(jìn)行升序排序。給在場(chǎng)箱進(jìn)行編號(hào)后，同樣先根據(jù)卸貨港、箱位尺寸進(jìn)行升序排序，對(duì)于同一卸貨港和箱位尺寸的集裝箱再根據(jù)集裝箱重量進(jìn)行排序?？紤]到箱位的排序和輕壓重約束，需要對(duì)重量作降序排序，得到一個(gè)基本的箱-位安排，即一個(gè)基本解，這樣的解滿足預(yù)配和輕壓重約束。如果滿足所有的約束，那么就可確定為一個(gè)初始可行解。如果不是一個(gè)初始可行解，就需要將屬性相同(類型、尺寸與卸貨港都相同)的兩箱位間的集裝箱進(jìn)行交換，以獲得初始可行解。

3.2 算法步驟

在對(duì)禁忌搜索算法中的一些要素進(jìn)行定義并得到基本解之后，就可以利用算法對(duì)基本解進(jìn)行迭代優(yōu)化。首先獲得初始基本解，然后通過(guò)迭代得到初始可行解，最后通過(guò)迭代獲得能夠接受的最優(yōu)解，具體的迭代步驟如下：

Step1設(shè)置模型與算法參數(shù)，假設(shè)案例中集裝箱數(shù)為ContainerNum，則確定算法的最大迭代次數(shù)MaxIterNum、禁忌長(zhǎng)度TabuLength、候選解個(gè)數(shù)CandidateNum、候選解集CandidateSet為空，最后設(shè)定空禁忌表TL，進(jìn)入Step 2。

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

Step3判斷xb是否滿足船舶箱槽重量約束和箱區(qū)作業(yè)約束，即是否是可行解，是，進(jìn)入Step 5，否則進(jìn)入Step 4 (Swap)。

Step4進(jìn)入Step 4.1。

Step4.1將同卸貨港同尺寸大小的集裝箱(箱位)作為同一類別集裝箱(箱位)進(jìn)行處理，提取當(dāng)前輸入數(shù)據(jù)的集裝箱的所有類別SingleClass，在每一個(gè)類別中，提取該類別中的所有貝位ShipBayColUni和層位ShipTierColUni，進(jìn)入Step 4.2。

Step4.2依次選擇一個(gè)貝和層，將同類同貝同層的集裝箱篩選出來(lái)，如果當(dāng)前層至少有兩個(gè)集裝箱，則說(shuō)明該層可交換，記錄可交換的層Tier，進(jìn)入Step 4.3。

Step4.3在Tier中任選一個(gè)層號(hào)，隨機(jī)生成兩交換點(diǎn)的位置，將x的對(duì)應(yīng)位置的兩集裝箱進(jìn)行交換，得到新的箱-位全排列，返回Step 3。

Step5置初始解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)，F(xiàn)reqValue=BV，進(jìn)入Step 6。

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

Step7返回BSF，BV，算法結(jié)束。

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

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

Step10判斷freq是否大于等于Maxfreq，如是，返回Step 7；否則，進(jìn)入Step 11。

Step11d=d+1，返回Step 6。

4 案例分析

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

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

根據(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ù)確定后，利用IBM ILOG CPLEX Optimization Studio 12.2對(duì)模型進(jìn)行求解。實(shí)驗(yàn)使用的電腦配置為Win 7 64位操作系統(tǒng)，4 GB運(yùn)行內(nèi)存，處理器為Inter(R) Core(TM) i5-2520M，CPU頻率為2.5 GHz。對(duì)于可能出現(xiàn)的因問(wèn)題復(fù)雜性較大而導(dǎo)致的Cplex無(wú)法求解的問(wèn)題，設(shè)定Cplex的最大運(yùn)行時(shí)間為1 h。同時(shí)在MATLAB R2016b中利用算法對(duì)模型進(jìn)行求解，算法的相關(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。

在參數(shù)k=λ1∶λ2=1∶1的情況下(如無(wú)特殊說(shuō)明，圖或表數(shù)據(jù)中均在k=1∶1的條件下求得)，算法求得各案例的初始解的結(jié)果如表2所示。

表2 案例初始解結(jié)果

表2的初始解結(jié)果包括裝船時(shí)間、翻箱量、不均衡程度及其組成的總目標(biāo)函數(shù)值。算法與Cplex的求解的最終解結(jié)果如表3所示。在表3中，由于Cplex求解算法的限制，將Cplex的求解時(shí)間設(shè)定為1 h，求解結(jié)束后返回目標(biāo)值，若超過(guò)1 h，則無(wú)最優(yōu)結(jié)果。此外，也對(duì)Cplex與算法的求解時(shí)間作了對(duì)比，從表3可以看出，箱量從20～400箱的9個(gè)案例，算法的計(jì)算時(shí)間在21～1 200 s之間，而Cplex只能解決箱量為20箱的案例I1，且計(jì)算時(shí)間也接近0.5 h。由此可見(jiàn)，Cplex在求解復(fù)雜的大規(guī)模配載問(wèn)題時(shí)效率較差，相比之下算法卻有著很好的求解效果和求解效率。由問(wèn)題描述可知，完整的船舶配載計(jì)劃由在場(chǎng)箱裝船作業(yè)順序以及合理的貝位船圖構(gòu)成。本文中的在場(chǎng)箱裝船作業(yè)順序已由CWP確定，圖9展示了集裝箱、船箱位與場(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層的箱位。

表3 案例優(yōu)化結(jié)果

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

針對(duì)本模型的多目標(biāo)性質(zhì)，設(shè)計(jì)了三組λ1與λ2的比值k1=10∶1，k2=1∶1，k3=1∶10，分別將案例I3～I(xiàn)9中的λ1:λ2替換為這三組比值再次求解，得到的結(jié)果如圖10和圖11所示。由圖10可以看出，除箱量較少的案例I3外，隨著該比值的增大，翻箱量呈逐漸上升趨勢(shì)。相反，由圖11可以看出，除箱量較少的案例I3與I4外，隨著該比值的增大，不均衡程度卻呈逐漸下降趨勢(shì)。由此可見(jiàn)，該比值一定程度上反應(yīng)了配載時(shí)對(duì)翻箱量與不均衡程度的重視程度，如果實(shí)配過(guò)程中碼頭方更關(guān)注翻箱量，其應(yīng)選擇較大的λ1，如果是不均衡程度，則選擇較大的λ2。因此，碼頭計(jì)劃員做配載時(shí)應(yīng)充分考慮到翻箱量與箱區(qū)作業(yè)均衡程度二者之間的權(quán)衡關(guān)系，從而較為合理地做好配載工作，提高實(shí)配過(guò)程中的裝船效率，縮短船期。

圖10 權(quán)重系數(shù)的變化對(duì)翻箱量的影響

圖11 權(quán)重系數(shù)的變化對(duì)不均衡程度的影響

圖12列出了算法對(duì)各案例不均衡程度的優(yōu)化結(jié)果，I3～I(xiàn)9各案例的初始解的不均衡程度分別為19箱、29箱、38箱、41箱、52箱、55箱、57箱。優(yōu)化后，I3～I(xiàn)9各案例的不均衡程度分別為16箱、28箱、35箱、39箱、44箱、50箱、51箱，最大優(yōu)化程度達(dá)15.8%。通過(guò)較大幅度地降低箱區(qū)作業(yè)的不均衡程度，減少不均衡可能造成的等待時(shí)間，提高裝船效率，縮短裝船時(shí)間，繼而縮短船期，為碼頭和船方創(chuàng)造更大利益。

圖12 算法對(duì)初始不均衡程度的優(yōu)化

5 結(jié) 語(yǔ)

傳統(tǒng)碼頭與ACT在堆場(chǎng)箱區(qū)布局、作業(yè)機(jī)械與作業(yè)工藝等方面的不同，導(dǎo)致ACT在制定配載方案時(shí)需要避免出現(xiàn)不均衡帶來(lái)的機(jī)械設(shè)備與作業(yè)等待等問(wèn)題。因此，本文以最小化裝船作業(yè)時(shí)單位時(shí)間不同箱區(qū)出箱量的不均衡程度和總裝船時(shí)間為目標(biāo)，考慮基本的配載約束和單位小時(shí)箱區(qū)作業(yè)量約束，建立了ACT配載問(wèn)題模型，并設(shè)計(jì)基于禁忌搜索的模型求解算法對(duì)模型進(jìn)行求解，分別用本文設(shè)計(jì)的算法與Cplex對(duì)設(shè)計(jì)的9組案例進(jìn)行求解與對(duì)比。結(jié)果表明，本文設(shè)計(jì)的基于禁忌搜索的模型求解算法可以使得模型初始解的不均衡程度最大減少15.8%，總裝船時(shí)間平均減少15.1%，翻箱量平均減少69.2%，且計(jì)算時(shí)間都在21～1 200 s之間。無(wú)論是在求解效率還是在求解效果方面，該模型與算法都能夠有效解決ACT配載問(wèn)題，同時(shí)提高裝船作業(yè)均衡性，縮短碼頭裝船時(shí)間與船舶靠泊時(shí)間，對(duì)船公司與碼頭方都有較大實(shí)際意義，也豐富了集裝箱碼頭配載理論。此外，由于配載的復(fù)雜性，進(jìn)一步細(xì)化配載問(wèn)題的相關(guān)約束并提高算法的求解速度是下一步研究的重點(diǎn)，從而幫助這一配載方法更好地應(yīng)用到碼頭的實(shí)際生產(chǎn)作業(yè)中。