集裝箱堆場出口箱箱位分配多目標優化模型

劉嬋娟，胡志華

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

0 引 言

集裝箱運輸在全球經濟和貿易發展中發揮著重要作用.近年來隨著集裝箱港口數量的激增，港口之間的競爭日趨激烈.而堆場出口箱的堆存方式直接影響碼頭取箱裝船作業的效率和碼頭運營成本，是提升港口競爭力的關鍵.對于出口箱堆場，各集裝箱到場順序無法預知、堆場密度過高時集裝箱箱位優化空間有限、箱重信息不準、船舶配載計劃臨時改變等一些不可控隨機因素，使得堆場出口箱堆存具有一定的復雜性.

針對堆場出口箱具體箱位分配問題，各國物流方面專家學者們提出了不同的方法和策略.很多學者將堆場箱位分配問題分解為幾個階段，將其變成一個多階段決策問題.文獻［1－4］均采用兩階段法進行堆場出口箱箱位分配.其中Chen等［1］和Hu等［2］，都是在第一階段進行貝位選擇，第二階段解決具體箱位分配問題.Kim 等［3］運用兩階段法以最小化場內集卡運輸距離和最小化翻箱率為目標進行堆場出口箱箱位分配.Zhang等［4］主要以最小化翻箱率為目標，運用兩階段法進行箱位分配.Kim 等［5］以裝船前預翻箱數最少為目標，建立動態規劃模型解決堆場出口箱箱位分配問題.靳志宏等［6］以降低集裝箱堆場翻箱率為研究課題，并將此問題轉化為求解動態規劃最短路徑問題，結合啟發式算法選擇具體箱位.Kang等［7］在出口集裝箱箱重未知的情況下，利用基于模擬退火的搜索算法來獲得出口箱在堆場的堆存策略，最小化堆場作業時翻箱量.Preston等［8］和Bazzazi等［9］運用遺傳算法求解堆場出口箱箱位分配問題.Lim 等［10］以計劃期內各個箱區之間的作業量不均衡最小化為目標函數，建立整數規劃模型，對進入堆場的集裝箱進行箱位分配.郝聚民等［11］提出了混合順序堆場作業的概念，并且基于圖搜索技術及模式識別理論提出了混合順序作業貝位優化模型.文獻運用啟發式算法求解這一問題.李建忠等［12］從平衡箱區貝位箱量和最小化集卡行駛距離入手，在滾動計劃的基礎上，建立了集裝箱堆場空間動態配置模型.該模型的主要目的是提高集卡作業效率，降低裝船作業過程中堆場機械耗費成本.文獻［13－15］均運用數學規劃的方法解決堆場箱位分配問題.文獻［16］利用搜索技術理論提出了出口箱箱位合理分配及減少倒箱率的措施，其與前述文獻最大的不同之處是認為貝位中緩沖箱位的位置是固定的，這與現實操作過程不完全相符.本文中假定緩沖箱位的位置并不固定.

以上文獻多是只考慮使裝船操作過程中翻箱數最少或是只考慮在裝船操作中場內集卡行駛距離最小為目標，本文以最小化堆棧中不滿足重量約束的箱子數，最小化不滿足時間先后順序的箱子數，最小化Bay內堆存成本以及均衡各堆棧內集裝箱數量為目標，提出基于堆場出口箱堆存原則的多目標混合整數規劃模型對出口集裝箱進行具體箱位分配.

1 問題描述與假設

集裝箱堆場劃分為不同的區（Block），每個區由多個貝位（Bay）、每個貝位由若干列（Row）和層（Tier）組成.所以堆場箱位由箱區、貝位、列和層來表示.如A10112表示該箱在A1區01貝位第1列第2層；A10213表示該箱在A1區02 貝位第1列第3層.而貝位內在豎直方向堆放的一個或多個集裝箱稱為棧（Stack）.在我國，大多數集裝箱碼頭中使用輪胎龍門吊，一般情況下最常見的每個貝位由6列4層組成，即一個貝位中能堆裝24個集裝箱，見圖1.為了減少取箱裝船過程中翻箱次數，堆場在進行箱位分配時首先將出口箱按船名和重量級進行分組，本研究將出口箱按重量分為3個等級.此外，為了減少集卡及場橋移動距離，通常將要裝載到同一艘船的集裝箱盡可能同貝堆放或放在同一箱區.

圖1 集裝箱堆場貝位示意圖Fig.1 Illustration of container yard bays

出口箱堆存涉及集港計劃、堆場分類堆存計劃與安排、具體箱位優化分配、取箱順序優化等過程.本文中假定到場出口箱已按船名、目的港分類，主要研究具體箱位分配優化問題.為了便于集裝箱裝卸，通常情況下，出口箱在堆場的堆存必須遵 循 一 定 的 規 則：（1）LBH（light below the heavy）即“輕 箱 在 下，重 箱 在 上”原 則；（2）EAES（early arrive early store）即“先到場，先堆存”原則；（3）取箱裝船就近原則；（4）各堆棧內集裝箱數均衡原則.

本文按照出口箱堆場堆存原則，將堆場出口箱箱位選擇優化問題轉化為：（1）使貝位內不滿足LBH 原則的箱子數最少；（2）使貝位內不滿足EAES原則的箱子數最少；（3）使取箱裝船作業過程場內集卡運輸成本最小；（4）使每一貝位中各個堆棧箱子數盡量均衡分布.研究考慮以下假設條件：（1）不考慮集裝箱大小差異，假定所有箱子全為標準6.096m 集裝箱；（2）不考慮冷藏箱、危險品箱等特殊箱的堆存，只針對普通重箱；（3）集裝箱組別已按船名和目的港確定；（4）每組集裝箱對應的船舶配載方案已知；（5）場內集卡運輸每個集裝箱的成本只與集卡移動距離有關；（6）不同重量級集裝箱混合堆存.

2 模型建立

2.1 符號說明

（1）集合：I＝｛1，2，3，…，Ni｝，所有出口集裝箱的集合，Ni為到場集裝箱總數，通過i，j∈I索引；B＝｛1，2，3，…，Nb｝，箱區內貝位集合，Nb為箱區內貝位總數，通過b∈B索引；R＝｛1，2，3，…，Nr｝，貝位內列數的集合，Nr為貝位內總列數，通過r∈R索引；T＝｛1，2，3，…，Nt｝，貝位內層數的集合，Nt為貝位內總層數，通過t∈T索引.

（2）參數：Ei，j表示貝位內滿足EAES原則的箱子，當集裝箱i和j的放置滿足時間先后順序時Ei，j取1，否則取0；Wi，j表示貝位內滿足LBH原則的箱子，當集裝箱i和j的放置滿足重量約束時Wi，j取1，否則取0；Ob，r，t表示貝位內已被占用的箱位.

（3）決策變量：xi，b，r，t∈｛0，1｝，如果集裝箱i被放 置 在b貝r列t層 時xi，b，r，t為1，否 則 為0；yi，j，b，r，t1，t2∈｛0，1｝，如 果 集 裝 箱i和j被 分 配 到（b，r，t1）和（b，r，t2）兩個箱位時yi，j，b，r，t1，t2為1，否則為0；zwi，j，b，r，t1，t2∈｛0，1｝，如果i和j兩個集裝箱的堆存滿足LBH原則zwi，j，b，r，t1，t2為1，否 則 為0；zei，j，b，r，t1，t2∈｛0，1｝，如果i和j兩 個集裝箱的堆 存滿足EAES原則zei，j，b，r，t1，t2為1，否則為0.

2.2 模 型

2.2.1 基本模型 不滿足LBH 原則和不滿足EAES原則的箱子都會導致翻箱操作.所以，在基本模型［M1］中，目標函數表示使取箱裝船過程中翻箱次數最少，其由兩部分組成，其中fw表示貝位內不滿足LBH 原則的集裝箱數量；fe表示貝位內不滿足EAES原則的集裝箱數量.

約束條件（1）表示一個集裝箱只能占用一個箱位；（2）表示一個箱位只能放一個箱子；（3）表示某一貝位內堆存集裝箱總數不能超過貝內箱位數，文中假定每貝由6列4層構成，且有3個緩沖箱位，則貝內可堆存集裝箱數最多為21個；（4）和（5）表示決策變量yi，j，b，r，t1，t2和xi，b，r，t之間的關系，只有當集裝箱i和j分別分配給箱位（b，r，t1）和（b，r，t2）時，決策變量yi，j，b，r，t1，t2的值取1，否則為0；（6）表示箱子不能懸空放置；（7）和（8）表示決策變量zwi，j，b，r，t1，t2與yi，j，b，r，t1，t2和Wi，j之間的關系，當i放在j下面，且i比j輕 時，zwi，j，b，r，t1，t2取1，否則為0；（9）和（10）表示決策變量zei，j，b，r，t1，t2與yi，j，b，r，t1，t2和Ei，j之間的關系，當i在j下面，且i比j早到堆場時，zei，j，b，r，t1，t2取1，否則為0.

2.2.2 堆場出口箱箱位分配多目標優化模型 考慮到堆場出口箱堆存成本和使各堆棧集裝箱堆存高度均衡，在模型［M1］的基礎上，提出兩個新的目標：fb表示存儲成本；fh表示各堆棧中箱子堆存高度.建立堆場出口箱箱位分配多目標優化模型［M2］.其中Cb表示b貝位內的集裝箱在取箱裝船過程中集卡運輸成本，該成本與貝位距岸邊的距離成正比，Cb∈｛1，2，3，…，B｝，通過b∈B索引.

模型［M2］所示的多目標規劃模型無法利用已有的混合整數規劃求解器進行直接求解.因此，在模型［M2］的基礎上，提出了模型［M3］和［M4］對此問題進行優化.其中［M3］是對目標函數fh的最小值進行求解，即使貝位內各堆棧箱子數盡量均衡，避免堆存過高.［M4］是將目標函數fh和fb作為一個整體進行優化，此過程分為兩個階段.第一階段是根據［M3］求出目標函數fh的最小值，令其等于fh＊；第二階段是對目標函數fb的優化，其中α是目標函數fh的松弛系數.

3 算例證明

為驗證模型的有效性，本文應用MATLAB軟件編程，在Intel（R）－32Core（TM）i5－4300U＠1.90GHz計算機上，利用CPLEX 求解器進行求解.以實際最常見的每貝6列4層堆場為例，假定每個貝位中有3個箱位為緩沖箱位.本文所研究的堆場箱位分配范圍涉及1、2、3個貝位.

算例1 當堆場某個箱區有1個貝位時，16個集裝箱到場時間順序和重量等級分布見表1.已知所有進場集裝箱已按船名、目的港分組，這16個集裝箱需要被裝載到同一艘船上.這一貝位內集裝箱在取箱裝船作業中集卡運輸成本為1，已經被占用的箱位數Ob，r，t為0.利用MATLAB軟件編程求解上述算例，得到這16個集裝箱具體箱位分配見圖2.

表1 16個隨機到港集裝箱的時間順序和重量分布Tab.1 The time sequence and weight distribution of 16containers arriving to yard stochastically

圖2 16個集裝箱具體箱位分配Fig.2 Specific space allocation of 16containers

算例2 當堆場某個箱區有2個貝位時，18個集裝箱到場時間順序和重量分布見表2.已知這18個集裝箱同樣已按船名、目的港分組.Bay 1中集裝箱在取箱裝船作業中集卡運輸成本為1，Bay 2中集裝箱在取箱裝船作業中集卡運輸成本為2.Bay 1中第一列和Bay 2中第一列的共計8個箱位已被占用，如圖3中陰影部分所示.求解得到這18個集裝箱具體箱位分配如圖3中（a）和（b）所示.

表2 18個隨機到港集裝箱的時間順序和重量分布Tab.2 The time sequence and weight distribution of 18containers arriving to yard stochastically

圖3 18個集裝箱具體箱位分配Fig.3 Specific space allocation of 18containers

由圖3所得結果可知，當Bay 1、Bay 2 中各有4個箱位已被占用，則每個貝位內最多只能堆存17個集裝箱.Bay 1內集裝箱存儲成本為1，低于Bay 2內存儲成本，為了滿足取箱操作過程中場內集卡運輸距離最小，節約堆場作業成本，在滿足LBH 原則和EAES原則的前提下，集裝箱被優先分配在Bay 1內，存儲這18個出口箱的最低成本為26.

算例3 當堆場某個箱區有3個貝位時，20個集裝箱到場時間順序和重量分布見表3.已知這20個集裝箱同樣是已按船名、目的港分組的.Bay 1、Bay 2、Bay 3中集裝箱在取箱裝船作業中集卡運輸成本分別為1、2、3.已知Bay 1中1～3列，Bay 2中1～3列，共計24個箱位已被占用，如圖4中陰影部分所示.利用MATLAB 軟件編程求解上述算例，得到這20個集裝箱具體箱位分配如圖4（a）～（c）所示.

根據圖4結果可知，當Bay 1 和Bay 2 中 各有12個箱位已被占用，則Bay 1和Bay 2內最多只能各堆存9個集裝箱.3個貝位中Bay 1的存儲成本最小為1，其次是Bay 2為2，Bay 3中存儲成本最高，所以為了滿足取箱操作過程中場內集卡運輸距離最小，節約堆場作業成本，在滿足LBH原則和EAES原則的前提下，集裝箱被優先分配在Bay 1和Bay 2內.

表3 20個隨機到港集裝箱的時間順序和重量分布Tab.3 The time sequence and weight distribution of 20containers arriving to yard stochastically

圖4 20個集裝箱具體箱位分配Fig.4 Specific space allocation of 20containers

4 結果分析

基于以上3 組算例，本文使用MATLAB（R2013a）軟件編程對模型進行求解，得出最優解.并得到fw、fe、fh、fb，見表4.其中fw和fe均為0.這表明應用此模型對堆場出口箱進行箱位分配能夠盡可能避免取箱裝船作業過程中出現翻箱操作.

為了探究模型中的參數對實驗結果的影響，以及權衡堆場出口箱堆存的4個原則對具體箱位分配的影響，本文設計了如表5所示的3個實驗，分別對這些因素造成的影響進行研究.

基于以上3個實驗，對所得結果結合圖5～8進行分析得出以下結論：

表4 3組算例所得目標函數值Tab.4 Objective function value of three groups of examples

表5 實驗目的及配置Tab.5 Experimental purpose and settings

（1）由實驗1的結果可知，如圖5所示，參數Ob，r，t的變化對目標函數fw、fe并無影響.算 例1中，當只有1個貝位時，參數Ob，r，t的改變也不會影響目標函數fb的值.算例2中，當有2個貝位時，目標函數fb和fh的值會隨著已被占用箱位數的變化而變化.總體上，已被占用的箱位數越多，目標函數fh的值越大，即堆棧越高.集裝箱堆存太高可能發生倒塌，存在安全隱患.此外，貝內堆棧高度分布不均衡將會增加取箱裝船過程中場橋移動距離，加大機械作業成本.

（2）由實驗2的結果可知，假如不考慮各堆棧中箱子數均衡原則，即在模型［M2］中去掉fh，則箱位分配方案會發生改變，如圖6所示.兩種分配方式所得目標函數fb、fh見圖7.由實驗結果可知，在考慮各堆棧箱子數均衡原則的情況下，集裝箱堆存成本較高，為26.而不考慮各堆棧箱子數均衡原則的情況下，堆存成本只有19.相反，在考慮各堆棧箱子數均衡原則的情況下，目標函數fh的值僅為42，不考慮各堆棧箱子數均衡原則的情況下，fh的值為110，即考慮各堆棧箱子數均衡原則的情況下，集裝箱明顯地堆存于較低層.這樣不但提高了堆棧的安全性，而且有利于取箱裝船過程中減少場橋上下移動距離，降低機械作業成本.

（3）以算例2中18個集裝箱數據為例，對目標函數fh和fb進行均衡分析，結合圖8可知：當目標函數fh在0.8～2.4時，存儲成本fb幾乎呈線性減少.而當fh大于2.4時，存儲成本fb保持為19不再改變.當fb在20～26時，兩個目標可以同時優化.

（4）綜合以上分析，為減少堆場出口箱堆存的經濟成本，集裝箱進場后應該優先選擇近泊位箱區和貝位存放；為了提高堆場作業效率，盡可能避免取箱裝船過程出現翻箱并且使各堆棧中箱子數盡量均衡，集裝箱進場時應優先選取空貝位或貝位中已被占用箱位較少的貝進行堆存.

圖5 參數Ob，r，t對目標函數值的影響Fig.5 The influence of parameter Ob，r，ton the objective function value

圖6 不考慮堆棧中箱子數均衡原則下18個箱子箱位分配Fig.6 Specific space allocation of 18containers without considering the number equilibrium in each stack

圖7 兩種不同分配方式所得fb 和fhFig.7 fb and fh in two different distribution ways

圖8 fh 和fb 之間的均衡Fig.8 The tradeoff analysis between fb and fh

5 結 語

基于堆場出口箱堆存原則的多目標混合整數規劃模型，在充分考慮出口箱到場時間的隨機性和堆場貝位中不同重量級別集裝箱混裝的情況下，能夠盡可能地降低或者消除取箱裝船時翻箱操作的出現次數，且使取箱裝船過程中場內集卡運輸距離最小，從而達到提高裝船時作業效率和節約堆場機械設備耗費成本的目的.同時還可以縮短出口箱裝船時間和船舶在港停留時間，避免給船公司和港口造成較大時間損失.大量算例證明此模型能夠從整體上對堆場出口箱箱位分配進行優化.與只考慮最小化翻箱率的研究相比，此分配方案更加合理.

［1］ CHEN Lu，LU Zhi－qiang.The storage location assignment problem for outbound containers in a maritime terminal ［J］.International Journal of Production Economics，2012，135（1）：73－80.

［2］ HU Wen－bin，WANG Huan，MIN Zhen－yu.A storage allocation algorithm for outbound containers based on the outer–inner cellular automation［J］.Information Sciences，2014，281：147－171.

［3］ Kim Kap－hwan，Park Kang－tae.A note on a dynamic space－allocation method for outbound containers ［J］.European Journal of Operational Research，2003，148（1）：92－101.

［4］ ZHANG Chu－qian，LIU Ji－yin，Wan Yat－wah，et al.Storage space allocation in container terminals［J ］.Transportation Research Part B：Methodological，2003，37（10）：883－903.

［5］ Kim Kap－hwan，Park Young－man，Ryu Kwangryul.Deriving decision rules to locate export containers in container yards［J］.European Journal of Operational Research，2000，124（1）：89－101.

［6］ 靳志宏，毛 鈞，李 娜.基于混合動態規劃的集裝箱堆場貝位內翻箱作業調度優化［J］.交通運輸系統工程與信息，2011，11（6）：131－136.JIN Zhi－hong，MAO Jun，LI Na.Scheduling of relocating containers within a bay in container yard based on hybrid dynamic programming［J］.Journal of Transportation Systems Engineering and Information Technology，2011，11（6）：131－136.（in Chinese）

［7］ Kang Jae－ho，Ryu Kwang－ryel，Kim Kap－hwan.Deriving stacking strategies for export containers with uncertain weight information［J］.Journal of Intelligent Manufacturing，2006，17（4）：399－410.

［8］ Preston P，Kozan E.An approach to determine storage locations of containers at seaport terminals［J］.Computers and Operations Research，2001，28（10）：983－995.

［9］ Bazzazi M，Safaei N，Javadian N.A genetic algorithm to solve the storage space allocation problem in a container terminal［J］.Computers and Industrial Engineering，2009，56（1）：44－52.

［10］ Lim A，Xu Z.A critical－shaking neighborhood search for the yard allocation problem ［J］.European Journal of Operational Research，2006，174（2）：1247－1259.

［11］ 郝聚民，紀卓尚，林 焰.混合順序作業堆場BAY優化模型［J］.大連理工大學學報，2000，40（1）：102－105.HAO Ju－min，JI Zhuo－shang，LIN Yan.Study of optimization of a BAY of stacking［J］.Journal of Dalian University of Technology，2000，40（1）：102－105.（in Chinese）

［12］ 李建忠，丁以中，王 斌.集裝箱堆場空間動態配置模型［J］.交通運輸工程學報，2007，7（3）：50－55.LI Jian－zhong，DING Yi－zhong，WANG Bin.Dynamic space deployment model of container storage yard ［J］.Journal of Traffic and Transportation Engineering，2007，7（3）：50－55.（in Chinese）

［13］ Cordeau J F，Gaudioso M，Laporte G，etal.A memetic heuristic for the generalized quadratic assignment problem ［J］.INFORMS Journal on Computing，2006，19：433－443.

［14］ Malucelli F，Pallottino S，Pretolani D.The stack loading and unloading problem［J］.Discrete Applied Mathematics，2008，156（17）：3248－3266.

［15］ SauríS，Martín E.Space allocating strategies for improving import yard performance at marine terminals ［J］.Transportation Research Part E：Logistics and Transportation，2011，47（6）：1038－1057.

［16］ 計三有，高悅文.集裝箱堆場減少倒箱率方法研究［J］.水運工程，2006（8）：53－56，61.JI San－you，GAO Yue－wen.Reduction of rate of container transportation in container yard［J］.Port＆ Waterway Engineering，2006（8）：53－56，61.（in Chinese）