空間和設備資源限制條件下集裝箱碼頭堆場空間分配兩階段優化方法

檀財茂 黃有方 嚴偉 于航

摘要：

針對集裝箱碼頭堆場空間及龍門吊設備資源緊缺時的堆場空間資源分配問題，利用整數規劃方法建立集裝箱堆場空間分配兩階段優化模型.第一階段模型（M1）對同一箱區內的航線進行組合配對，目標是最大化堆場共享箱區的數量；第二階段模型（M2）對M1中生成的航線組合進行堆場空間位置分配，目標是周期內總運輸成本最小.結合港口實際數據設計數值實驗，驗證模型的正確性和有效性.結果顯示，通過對堆場空間的分配，出口箱區和中轉箱區的利用率平均可增加18%，能較好地解決堆場資源緊張問題.

關鍵詞：

堆場空間分配； 資源限制； 整數規劃； 共享箱區

中圖分類號： U691.31

文獻標志碼： A

收稿日期： 20151027

修回日期： 20151222

基金項目： 國家自然科學基金（51409157，71602114）； 高等學校博士學科點專項科研基金（20133121110001）；上海市晨光計劃（14CG48）；上海市揚帆計劃（14YF1411200）；上海市教育委員會科研創新項目（13YZ080，14YZ112）； 上海海事大學研究生創新基金（2015ycx063）；上海海事大學優秀博士論文培育項目（2015bxlp006）

作者簡介：

檀財茂（1989—），男，安徽安慶人，博士研究生，研究方向為港航物流系統規劃與管理，（Email） caimaotan@hotmail.com；

黃有方（1959—），男，浙江新昌人，教授，博導，博士，研究方向為物流系統優化，（Email） yhuang@shmtu.edu.cn

A twostage optimization method of container yard space allocation

with space and equipment resource constraints

TAN Caimaoa， HUANG Youfanga， YAN Weib， YU Hangc

（a. Institute of Logistics Science & Engineering； b. Logistics Engineering College； c. School of Economics &

Management， Shanghai Maritime University， Shanghai 201306， China）

Abstract：

Considering the yard space allocation issue with the resource constraints of yard space and cranes in container terminals， a twostage optimization model is formulated for container yard space allocation using integer programming method. The first stage model （M1） aims at maximizing the number of sharing blocks by pairing routes in the same yard block. The second stage model （M2） is for the yard block allocation for the pairs of routes created by M1 and its objective is to minimize the total transportation cost in a cycle. The numerical experiments are designed with the actual port data to verify the correctness and effectiveness of the model. The results show that the space utilization of the blocks for outbound and transit containers can increase about 18% through the yard space allocation， and the allocation plan is good at solving the yard resource shortage problem.

Key words：

yard space allocation； resource constraint； integer programming； sharing space

0引言

近幾年隨著橋吊作業工藝及設備本身性能的不斷提高，港口作業瓶頸已經由海側逐漸向堆場發生轉移.[1]很多集裝箱碼頭經常出現海側岸橋空閑，而其作業任務序列中的集裝箱仍堵在堆場中的現象.如何在場地和龍門吊資源有限的條件下解決碼頭作業的瓶頸問題值得深入研究.

現有的港口相關文獻中不乏對港口碼頭各種作業設備的作業調度問題的研究（有單獨一種設備的作業調度[24]或者整合幾種設備的聯合調度[57]），而將堆場空間分配作為解決碼頭作業問題的重點的研究則相對有限.文獻[811]將碼頭的集裝箱堆場作為研究的重點對碼頭堆場的空間進行分配，通過為堆場的各箱區劃分子箱區的方式，將各航線分配到對應的子箱區.研究的目標一般為最小龍門吊分配數量[9]、最小運輸成本[10]和最小時段內箱區集卡數量[11].文獻[12]和[13]對堆場出口箱區的集裝箱分配策略進行研究，提出了基礎的堆場出口箱空間分配問題.文獻[1416]提出在箱區航線分配時使用“共享箱區”這一理念，通過利用不同航線的進箱規律，增加堆場箱區的利用率.文獻[14]提出兩階段分配模型，但其主要目標不是最大化共享箱區的量.文獻[15]利用共享箱區來解決碼頭航線箱量的波動問題.文獻[16]聯合考慮碼頭泊位分配與堆場空間分配，建立了泊位和堆場分配混合整數規劃模型，并設計算法求解.

相對于歐洲一些港口，亞洲很多港口的岸線資源緊缺，堆場資源非常緊張.隨著吞吐量的逐年增加，很多碼頭的實際吞吐量已經超過設計吞吐量的兩倍，碼頭堆場區域的擁擠程度可想而知.很多學者在研究了在堆場堆放的航線的出口箱進箱規律后，針對進口箱區提出了“共享箱區”這一概念，較好地緩解了堆場空間不足的問題.“共享箱區”是可供不同航線的集裝箱共用堆存的箱區，共用的大小和位置可以根據實際情況情形設置.“共享箱區”利用不同航線船期的不同，根據航線各自的集裝箱進箱規律，實現箱區的共享.

1堆場空間分配模型

1.1問題描述

本文將堆場空間分配問題分解成兩個連續的問題：第一個問題模型為航線組合配對，即確定箱區的航線配對組合情況，目標是最大化箱區的空間利用率（此時箱區只有一個大小概念并無堆場空間地理位置信息）；第二個問題模型為箱區航線指派，即將第一階段已經配對好的航線組合指派到堆場中的具體箱區.

1.2第一階段模型M1

1.2.1集合、參數與變量

1.2.2目標函數和約束條件

進行航線配對組合時，主要目標是實現箱區共享，盡量增加共享箱區數量，提高堆場的空間利用率.因此，模型的目標函數是最大化所有實際箱區共享箱區的數量.式（2）和（3）為子箱區配對航線唯一性約束.對每個子箱區有且只能分配1條固定的航線，不能分配多條航線.同時，虛擬子箱區只能分配虛擬航線.式（4）為航線子箱區數量約束.給每條航線分配的子箱區數量不能小于航線所需的最小子箱區的數量，以滿足其堆存需要.式（5）為箱區龍門吊作業限制.依照相鄰的龍門吊作業時的安全作業距離限制，同時結合碼頭作業經驗，箱區對同時作業的龍門吊數量有限制.式（6）為相鄰箱區作業限制.同一箱區內的相鄰子箱區如果同時進行裝船作業，很可能會造成龍門吊沖突和集卡擁堵情況的發生.式（7）和（8）為航線發箱點數量約束.對航線進行子箱區分配遵循“分散且集中”的原則.式（9）～（12）為變量邏輯關系約束.建立各種變量相互之間的邏輯關系，主要體現為Sri，Sli，bqm，xim之間的數學關系.式（13）～（15）為決策變量范圍約束及其他邏輯關系.

1.2.3模型線性化

1.3第二階段模型M2

1.3.1集合、參數與變量

1.3.2目標函數和約束條件

航線組合分配模型目標是周期內將航線組合分配到堆場各個箱區的總運輸費用最小，假設運輸費率一定，即實現總運輸距離最小.式（22）為箱區分配唯一性約束.對于堆場中的每個箱區，其分配的航線組合有且只能有1個，不能有多個航線組合.式（23）為航線組合分配唯一性約束.對于每個配對的航線組合，其必須分配且只能分配至堆場的某一個箱，不能分配至多個箱區.式（24）和（25）為龍門吊資源約束.由于不能在每個箱區放置固定的龍門吊，一般為每一道安排一定數量的龍門吊.式（26）～（28）為作業量均衡約束.在進行箱區分配時必須考慮堆場每個道的作業量均衡，一方面是為了避免資源過度使用而導致故障發生率提高，另一方面也是為了平衡龍門吊司機的作業量，減少員工工資差額.式（29）和（30）為變量范圍約束.

2數值實驗

2.1基礎信息

本文結合某港口的實際運營數據進行數值實驗設計，用以測試和評價本文所建模型的正確性和有效性.實驗對某集裝箱碼頭的進口箱區、出口箱區以及中轉箱區的龍門吊進行分配.堆場出口箱和中轉箱分開堆存，且不同公司集裝箱在箱區內也不混合堆放.進口箱區則按貨主、箱主混合堆放，不區分公司和航線.實驗中所使用的信息見表1，碼頭堆場部分箱區數量、位置等基本信息見圖1.

因為碼頭服務的主要對象為集裝箱班輪，其航線周期為一個星期，因此本文選取正常時期內某一周的航班數據進行計算.實驗計算中每個子箱區可與相鄰箱區共享的最大空間為20 TEU，單位共享箱區量為10 TEU，每天各道最小工作量與平均工作量之差與最大工作量之比控制在0.25以內，實驗中的其他主要參數見表2.

2.2模型求解

使用IBM ILOG CPLEX優化軟件對模型進行編程，調用相關數據計算，在處理器為Intel Xeron，RAM 32G的服務器上進行計算，計算約5 min可得計算結果，具體分配方案（方案A）見圖2.

直觀地看，方案A有如下幾個特點：（1）MSK航線的箱區集中在堆場左側，而CMA航線的箱區集中在堆場右側；（2）中轉箱區集中在堆場的離岸線較近的優勢位置，出口箱區相對靠后；（3）不同于傳統操作方案（方案B）在某幾道集中堆放進口箱，方案A中進口箱區分配在堆場的每一道.

2.3結果分析

2.3.1箱區利用率分析

2.3.2作業均衡分析

因碼頭龍門吊資源緊缺，碼頭不能在每個箱區都安排至少1臺龍門吊，只能在每一道安排一定數量的龍門吊.因此，各時段堆場每道作業點總數小于安排的龍門吊數量，盡量減少龍門吊的“跨場”次數.方案A各時段每道的作業點數見圖4.

在滿足各道作業點數約束的基礎上，堆場管理還需要均衡各道龍門吊每天的作業量，一方面可以減輕某些道的作業沖突，另一方面也可以均衡龍門吊司機的工資收入.方案A中堆場每道每天作業量見圖5.

方案A將進口箱區拆分在不同的作業道中，這與傳統方案（方案B）將進口箱在某幾道整道集中堆放不同.這是因為進口箱區在周期內的作業量相對于出口箱區和中轉箱區而言小，且作業時段分布相對平均，所以在各個時段內的作業量“小而均”.如將進口箱整道集中堆放，則堆場各道的作業量均衡性相對較差，各道的作業點數差別也會相對明顯.方案A與方案B相關結果對比見表3.

2.3.3運輸成本分析

通過限制各道的龍門吊數量同時盡量使各道的作業量均衡，碼頭方面雖然可以減少龍門吊的頻繁“跨場”以及實現龍門吊司機工資待遇的相對均衡，但可能會引起總運輸作業成本的增加.因此，有必要對堆場每道龍門吊數量和作業量均衡要求與堆場總運輸成本間的關系進行討論.兩種因素對碼頭堆場作業總成本的影響分別見表4和5.

從表4和5可知，每道固定配置的龍門吊數量減少會引起周期內運輸成本的增加，而且隨著每道固定安排的龍門吊數量的減少，總成本呈顯著上升趨勢，邊際成本迅速增加.堆場各道之間作業量均衡的要求越高雖然也會使總成本越高，但是其影響相對于龍門吊數量的影響較弱.因此，對于碼頭管理者而言，當碼頭龍門吊資源緊缺時，需綜合考慮新增龍門吊的成本與現有資源條件下調配總成本之間的關系，作出合理的決策.

3結論

本文分別通過兩個階段優化來解決碼頭資源緊缺問題：第一階段箱區航線配對利用“共享箱區”理念，解決堆場空間不足問題，增加堆場的箱區利用率；第二階段通過對堆場所有箱區的空間位置布局，應對龍門吊資源限制問題，同時還考慮了不同類型集裝箱中轉周期問題和各道作業量均衡問題.值得注意的是，能否將兩個階段融合并建立一個互相反饋的機制用以解決堆場空間分配問題是今后需要進一步研究的方向.

參考文獻：

[1]CHANG Daofang， JIANG Zuhua， YAN Wei， et al. Integrating berth allocation and quay crane assignments[J]. Transportation Research Part E： Logistics & Transportation Review， 2010， 46（6）： 975990.

[2]KIM K H， PARK Y M. A crane scheduling method for port container terminals[J]. European Journal of Operational Research， 2004， 156（3）： 752768.

[3]KIM K H， KIM K Y. An optimal routing algorithm for a transfer crane in port terminals[J]. Transportation Science， 1999， 33（1）： 1733.

[4]NISHIMURA E， IMAI A， PAPADIMITRIOU S. Yard trailer routing at a maritime container terminal[J]. Transportation Research Part E： Logistics & Transportation Review， 2005， 41（1）： 5376.

[5]IMAI A， NISHIMURA E， PAPADIMITRIOU S. Berthing ships at a multiuser container terminal with a limited quay capacity[J]. Transportation Research Part E： Logistics & Transportation Review， 2008， 44（1）：136151.

[6]HE Junliang， HUANG Youfang， YAN Wei. Yard crane scheduling in a container terminal for the tradeoff between efficiency and energy consumption[J]. Advanced Engineering Informatics， 2015， 29（1）：5975.

[7]HE Junliang， HUANG Youfang， YAN Wei， et al. Integrated internal truck， yard crane and quay crane scheduling in a container terminal considering energy consumption[J]. Expert Systems with Applications， 2015， 42（5）： 24642487.

[8]KIM K H， PARK Y M， RYU K R. Deriving decision rules to locate export containers in container yards[J]. European Journal of Operational Research， 2000， 124（1）：89101.

[9]LEE L H， CHEW E P， TAN K C， et al. An optimization model for storage yard management in transshipment hubs[J]. OR Spectrum， 2006， 28（4）： 539561.

[10]JIN J G， LEE D H， HU H. Tactical berth and yard template design at container transshipment terminals： a column generation based approach[J]. Transportation Research Part E： Logistics & Transportation Review， 2015， 73： 168184.

[11]HAN Y， LEE L H， CHEW E P， et al. A yard storage strategy for minimizing traffic congestion in a marine container transshipment hub[J]. OR Spectrum， 2008， 30（4）： 697720.

[12]嚴偉， 謝塵， 萇道方. 基于并行遺傳算法的集裝箱碼頭堆場分配策略[J]. 上海海事大學學報， 2009， 30（2）： 1419.

[13]顧天意， 梁承姬. 基于矩陣式遺傳算法的集裝箱碼頭堆場空間資源分配優化策略[J]. 上海海事大學學報， 2012， 33（2）： 4046.

[14]JIANG X， LEE L H， CHEW E P， et al. A container yard storage strategy for improving land utilization and operation efficiency in a transshipment hub port[J]. European Journal of Operational Research， 2012， 221（1）： 6473.

[15]ZHEN Lu. Container yard template planning under uncertain maritime market[J]. Transportation Research Part E： Logistics & Transportation Review， 2014， 69（3）： 199217.

[16]ZHEN Lu， CHEW E P， LEE L H. An integrated model for berth template and yard template planning in transshipment hubs[J]. Transportation Science， 2011， 45（4）： 483504.

（編輯賈裙平）