空間和設(shè)備資源限制條件下集裝箱碼頭堆場(chǎng)空間分配兩階段優(yōu)化方法

檀財(cái)茂 黃有方 嚴(yán)偉 于航

摘要：

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

關(guān)鍵詞：

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

中圖分類號(hào)： U691.31

文獻(xiàn)標(biāo)志碼： A

收稿日期： 20151027

修回日期： 20151222

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

作者簡(jiǎn)介：

檀財(cái)茂（1989—），男，安徽安慶人，博士研究生，研究方向?yàn)楦酆轿锪飨到y(tǒng)規(guī)劃與管理，（Email） caimaotan@hotmail.com；

黃有方（1959—），男，浙江新昌人，教授，博導(dǎo)，博士，研究方向?yàn)槲锪飨到y(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è)逐漸向堆場(chǎng)發(fā)生轉(zhuǎn)移.[1]很多集裝箱碼頭經(jīng)常出現(xiàn)海側(cè)岸橋空閑，而其作業(yè)任務(wù)序列中的集裝箱仍堵在堆場(chǎng)中的現(xiàn)象.如何在場(chǎng)地和龍門吊資源有限的條件下解決碼頭作業(yè)的瓶頸問題值得深入研究.

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

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

1堆場(chǎng)空間分配模型

1.1問題描述

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

1.2第一階段模型M1

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

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

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

1.2.3模型線性化

1.3第二階段模型M2

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

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

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

2數(shù)值實(shí)驗(yàn)

2.1基礎(chǔ)信息

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

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

2.2模型求解

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

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

2.3結(jié)果分析

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

2.3.2作業(yè)均衡分析

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

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

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

2.3.3運(yùn)輸成本分析

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

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

3結(jié)論

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

參考文獻(xiàn)：

[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]嚴(yán)偉， 謝塵， 萇道方. 基于并行遺傳算法的集裝箱碼頭堆場(chǎng)分配策略[J]. 上海海事大學(xué)學(xué)報(bào)， 2009， 30（2）： 1419.

[13]顧天意， 梁承姬. 基于矩陣式遺傳算法的集裝箱碼頭堆場(chǎng)空間資源分配優(yōu)化策略[J]. 上海海事大學(xué)學(xué)報(bào)， 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.

（編輯賈裙平）