檀財茂 黃有方 嚴偉 于航

摘要：

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

關(guān)鍵詞：

堆場空間分配； 資源限制； 整數(shù)規(guī)劃； 共享箱區(qū)

中圖分類號： U691.31

文獻標志碼： A

收稿日期： 20151027

修回日期： 20151222

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

作者簡介：

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

黃有方（1959—），男，浙江新昌人，教授，博導，博士，研究方向為物流系統(tǒng)優(yōu)化，（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引言

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

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

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

1堆場空間分配模型

1.1問題描述

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

1.2第一階段模型M1

1.2.1集合、參數(shù)與變量

1.2.2目標函數(shù)和約束條件

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

1.2.3模型線性化

1.3第二階段模型M2

1.3.1集合、參數(shù)與變量

1.3.2目標函數(shù)和約束條件

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

2數(shù)值實驗

2.1基礎(chǔ)信息

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

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

2.2模型求解

使用IBM ILOG CPLEX優(yōu)化軟件對模型進行編程，調(diào)用相關(guān)數(shù)據(jù)計算，在處理器為Intel Xeron，RAM 32G的服務(wù)器上進行計算，計算約5 min可得計算結(jié)果，具體分配方案（方案A）見圖2.

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

2.3結(jié)果分析

2.3.1箱區(qū)利用率分析

2.3.2作業(yè)均衡分析

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

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

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

2.3.3運輸成本分析

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

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

3結(jié)論

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

參考文獻：

[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]顧天意， 梁承姬. 基于矩陣式遺傳算法的集裝箱碼頭堆場空間資源分配優(yōu)化策略[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.

（編輯賈裙平）