考慮箱區作業均衡的ACT船舶配載研究

丁 一 龔 杰 林國龍

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

0 引 言

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

圖1 ACT作業設備及運作流程

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

圖2 集裝箱貝位預配船圖示意圖

目前學者們主要從兩個視角對船舶配載問題進行研究，一是從船舶公司的視角，另一種是從碼頭視角。從船舶公司的角度，主要解決的問題是如何減少裝卸箱時由于多裝貨港與多卸貨港貨物的存在導致的倒箱。其次是考慮船舶的航行安全，如Delgado等[2]考慮20/40英尺箱的混裝、冷藏箱等特種箱的配載以及船舶積載強度等因素，以最小化倒箱目標，建立解決集裝箱船舶配載中的貝位計劃(master planning)子問題的整數規劃模型與解決箱配(slot planning)子問題的約束規劃模型，并證明約束規劃在求解此類問題中的有效性；而Parreo等[3]在Delgado等[2]的基礎上，以最小化漏配箱數、倒箱為目標，建立新的整數規劃模型，并設計GRASP方法，重點解決配載的箱位分配子問題。

在追加考慮船舶穩性的因素后，Ambrosino等[4]將單卸貨港貝位計劃問題延伸到多卸貨港貝位計劃問題，以最小化靠泊時間為目標，設計求解問題的MIP啟發式方法；而Pacino等[5]則以同樣的目標，分別建立貝位計劃問題的整數規劃模型和單個集裝箱的箱位問題的約束規劃模型；Ding等[6]則將目標換成最小化倒箱；汪圓圓等[7]在保證倒箱量為零的策略下，以船舶中縱剖面彎矩值、重心橫向偏移、初穩性高為目標，以船舶吃水差值為約束條件，優化集裝箱配載；孫俊清等[8]將船舶穩定性作為約束條件，以最小化集裝箱船舶在整個航線所有港口的倒箱量為目標，設計了求解問題的改進遺傳算法。

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

通過對文獻的系統梳理可以發現，目前學者們在研究集裝箱船舶配載問題時，大多從船舶公司角度出發，較少從碼頭角度出發，所考慮的因素主要有以下幾點：

(1) “重不壓輕”、“遠不壓近”約束，即重箱在下，輕箱在上，遠卸貨港箱在下，近卸貨港箱在上；

(2) 偶數貝位集裝箱箱槽內20英尺與40英尺箱的混裝約束(甲板或艙內的同貝位同排位不同層位的所有箱位同屬一根箱槽)；

(3) 特種箱的配載約束；

(4) 吃水差、穩性和船體強度約束等。

鑒于ACT箱區單側作業的特殊性以及對裝船效率的要求，僅考慮以上這些常規約束制定出的配載已滿足不了ACT的實際生產需要。ACT箱區作業時，同一時間各箱區作業量一旦出現較大的不均衡，就會導致部分箱區軌道吊RMG(Rail-Mounted Gantry Crane)作業效率偏低以及自動導引運輸車AGV(Automated Guided Vehicle)和橋吊QC(Quay Crane)的等待，這樣勢必影響總裝船效率和船期，因此引入ACT箱區作業均衡性這一因素就顯得尤為重要。但目前以ACT為背景的配載研究較少，缺乏ACT箱區的作業均衡對實際積載作業影響的研究。故本文從碼頭角度出發，在考慮上述常規配載約束的基礎上，優化配載方案，使得裝船作業過程中各箱區的作業量盡量趨于均衡，減少不均衡導致的作業等待時間，進而提高裝船效率，縮短船期。

1 問題描述

從根本上來說，船舶配載問題可以劃分為兩個子問題：

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

圖3 堆場集裝箱的翻箱過程示意圖

做配載時，待裝船的在場箱的場箱位已知，是否翻箱或有多少翻箱完全取決于配載的結果，即配載船圖。例如在圖4中，i和j是兩個待裝船的在場箱，j剛好在i的上方，這時候在船上，如果把j配在i所在的同一根箱槽，且位于i的上方，那么在i和j的裝船作業時，i必須先于j出場，這時翻箱就不可避免。“When”問題的結果就是最優的裝船作業順序。

圖4 變量說明

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

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

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

如果同一時間內部分ACT箱區裝卸量偏小，而部分ACT箱區裝卸量偏大，即作業不均衡，對于裝卸量偏大的箱區，一方面這些箱區的軌道吊連續作業時間過長，從而導致軌道吊司機的疲乏，其工作積極性與作業效率必然降低，并且作業量的大小直接影響到軌道吊的壽命。另一方面，不均衡就意味著個別箱區裝卸任務過于集中，而單位時間內單臺海側軌道吊的作業能力有限，一旦某個箱區的發箱指令過于集中，就會造成某一段時間內該箱區作業量過大，必然產生軌道吊作業沖突。這樣AGV和岸橋的等待時間就會增加，從而影響港口作業效率，影響總裝船時間，進而影響船期，因此發箱時考慮箱區之間的作業均衡至關重要。

船舶配載的目標在于減少船舶在港時間，繼而減少船舶的碼頭作業費用。總裝船時間可以分為場內、場到船和船上作業時間三部分，總裝船作業時間構成如圖6所示。

圖6 總裝船作業時間構成

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

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

2 數學模型構建

2.1 參 數

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

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

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

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

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

qb：每一小時段內箱區b的最大集裝箱作業量；

fb：箱區b內待裝船的集裝箱總數；

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

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

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

L：表示船上根據預配載計劃所形成的集裝箱箱槽的集合，L={1,…,|L|}；

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

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

Δi：表示與集裝箱i在同一箱區同一堆棧(同箱區同貝位同排位不同層位的集裝箱所屬同一堆棧)且位于i之上的集裝箱的集合，Δi?N,?i∈N；

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

σ1：箱區內的一次翻箱時間；

σ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位于箱區b，則矩陣對應元素IFIBib=1，否則為0，如果IFIBib=0，則說明集裝箱i無論如何不可能從箱區b離場，那么xipt=0，因此有關系式：xipt≤IFIBib；

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

λ1、λ2：權重系數；

M：一個極大正數。

2.2 決策變量

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

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

Ωh：第h小時各箱區出箱量的最小值；

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

2.3 假設條件

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

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

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

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

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

2.4 完整模型

目標函數：

1) 最小化總裝船時間：

(1)

2) 最小化各箱區作業量的不均衡程度：

(2)

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

(3)

(4)

于是，式(2)轉化為：

(5)

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

(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)表示目標函數最小化實配過程的集裝箱裝船作業時間和最小化不同箱區作業量的不均衡程度。式(8)、式(9)為匹配約束，即一個集裝箱只能被安排到一個且僅一個船箱位中，而一個箱位也只能放一個集裝箱。式(10)表示集裝箱與船箱位的匹配需要滿足預配要求。式(11)表示在場箱離場須符合CWP作業時間安排。式(12)為輕壓重約束，即船上同一根箱槽的集裝箱，重箱一定位于輕箱的下層。式(13)為船舶單根箱槽的裝載重量約束，規定每一根箱槽堆碼的總重量不允許超過設定的最大值，且依據Monaco等[10]盡量按船舶的穩性要求設定所有箱槽的裝載總重量的分布，以簡化船舶穩性約束。式(14)、式(15)為箱區作業約束，式(14)表示同一時間段內從該箱區離場的最大集裝箱數量，式(15)表示從堆場一箱區離場的集裝箱總數量。式(16)表示在場箱離場先后順序與翻箱的關系。式(17)、式(18)用來求取每一時間段內各箱區作業量的最小值和最大值，同目標函數一起達成箱區作業均衡的目標。式(19)表示決策變量類型。

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

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

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

3.1 參數設置與初始解

配載所需數據包括具體的在場箱與船箱位、在場箱的場箱位與船上箱位位置、各自對應的卸貨港與尺寸以及船箱位的橋吊開始作業時間等。將配載所需數據進行了羅列與詳細梳理，如圖7所示，“i”行的集裝箱與“p”行的船箱位一一對應，用來表示計劃配載的結果，解的形式如下所示：

(20)

圖7 解的形式與數據結構示意

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

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

圖8 解的交換示意圖

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

3.2 算法步驟

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

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

Step2輸入初始基本解xb，設置當前迭代次數d=1、當前最優解無優化迭代次數freq=0，進入Step 3。

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

Step4進入Step 4.1。

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

Step4.2依次選擇一個貝和層，將同類同貝同層的集裝箱篩選出來，如果當前層至少有兩個集裝箱，則說明該層可交換，記錄可交換的層Tier，進入Step 4.3。

Step4.3在Tier中任選一個層號，隨機生成兩交換點的位置，將x的對應位置的兩集裝箱進行交換，得到新的箱-位全排列，返回Step 3。

Step5置初始解x0=xb，當前解x=xb，當前最優解BSF=x0，計算當前最優解對應的最優值BV=GetValue(BSF)，FreqValue=BV，進入Step 6。

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

Step7返回BSF，BV，算法結束。

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

Step9判斷FreqValue是否小于等于BV，是，freq=freq+1，進入Step 10；否則，FreqValue=BV，freq=0，進入Step 11。

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

Step11d=d+1，返回Step 6。

4 案例分析

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

表1 案例數據說明

根據該碼頭的實際作業情況確定模型中的部分參數，其中，箱區單位小時的最大作業箱量qb=15箱，箱位p的開始裝箱時間由已知的CWP確定。鑒于ACT在場箱分布相對分散，取集裝箱i從其所在的堆場箱區到最終的箱位p所對應的船舶貝位的水平運輸時間τip=3 min，箱區內一次翻箱時間σ1=3 min。箱區不均衡程度較小時不一定導致作業等待。但是不均衡程度較大時很有可能造成等待。因此綜合考慮，取不均衡可能導致的等待的懲罰時間σ2=2 min，模型參數確定后，利用IBM ILOG CPLEX Optimization Studio 12.2對模型進行求解。實驗使用的電腦配置為Win 7 64位操作系統，4 GB運行內存，處理器為Inter(R) Core(TM) i5-2520M，CPU頻率為2.5 GHz。對于可能出現的因問題復雜性較大而導致的Cplex無法求解的問題，設定Cplex的最大運行時間為1 h。同時在MATLAB R2016b中利用算法對模型進行求解，算法的相關參數定義如下：候選解個數CandidateNum=50，禁忌長度TabuLength取大于ContainerNum0.5的最小整數，算法迭代的最大次數MaxIterNum=200，允許當前最優解無優化趨勢的最大迭代次數Maxfreq=50。

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

表2 案例初始解結果

表2的初始解結果包括裝船時間、翻箱量、不均衡程度及其組成的總目標函數值。算法與Cplex的求解的最終解結果如表3所示。在表3中，由于Cplex求解算法的限制，將Cplex的求解時間設定為1 h，求解結束后返回目標值，若超過1 h，則無最優結果。此外，也對Cplex與算法的求解時間作了對比，從表3可以看出，箱量從20～400箱的9個案例，算法的計算時間在21～1 200 s之間，而Cplex只能解決箱量為20箱的案例I1，且計算時間也接近0.5 h。由此可見，Cplex在求解復雜的大規模配載問題時效率較差，相比之下算法卻有著很好的求解效果和求解效率。由問題描述可知，完整的船舶配載計劃由在場箱裝船作業順序以及合理的貝位船圖構成。本文中的在場箱裝船作業順序已由CWP確定，圖9展示了集裝箱、船箱位與場箱位的對應關系(該配載結果取自案例I9)，其中船舶53貝位的集裝箱分別來自第10箱區57貝位、50箱區29貝位、56箱區43貝位、64箱區23貝位和72箱區65貝位，如位于64箱區23貝位5排1層的在場箱CAIU6122728被安排在了船上53貝位08排04層的箱位。

表3 案例優化結果

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

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

圖10 權重系數的變化對翻箱量的影響

圖11 權重系數的變化對不均衡程度的影響

圖12列出了算法對各案例不均衡程度的優化結果，I3～I9各案例的初始解的不均衡程度分別為19箱、29箱、38箱、41箱、52箱、55箱、57箱。優化后，I3～I9各案例的不均衡程度分別為16箱、28箱、35箱、39箱、44箱、50箱、51箱，最大優化程度達15.8%。通過較大幅度地降低箱區作業的不均衡程度，減少不均衡可能造成的等待時間，提高裝船效率，縮短裝船時間，繼而縮短船期，為碼頭和船方創造更大利益。

圖12 算法對初始不均衡程度的優化

5 結 語

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