張文韜　韓曉龍

摘要：

為提高岸橋裝卸集裝箱的作業(yè)效率，研究單岸橋同步裝卸問題。建立岸橋同步裝卸優(yōu)化模型，利用遺傳算法進行求解，優(yōu)化集裝箱船的裝卸順序，最大化地減少岸橋作業(yè)時間。算例結果表明，與傳統(tǒng)岸橋同步作業(yè)模式相比，利用該模型岸橋作業(yè)效率有較大提升。結果證明了算法的有效性，所建模型有利于岸橋作業(yè)效率的提高。

關鍵詞：

同步裝卸;?岸橋作業(yè)序列;?遺傳算法

中圖分類號：U691.34

文獻標志碼：A

Optimization?of?quay?crane?operation?sequence?considering

synchronous?loading?and?unloading

ZHANG?Wentao，?HAN?Xiaolong

（

Institute?of?Logistics?Science?&?Engineering，?Shanghai?Maritime?University，?Shanghai?201306，?China）

Abstract：

In?order?to?improve?the?operation?efficiency?of?loading?and?unloading?containers?by?quay?cranes，?the?problem?of?synchronous?loading?and?unloading?of?a?single?quay?crane?is?studied.?The?optimization?model?of?synchronous?loading?and?unloading?of?the?quay?crane?is?established?and?solved?by?the?genetic?algorithm?to?optimize?the?loading?and?unloading?sequence?of?container?ships?and?minimize?the?operation?time?of?the?quay?crane.?The?result?of?an?example?shows?that，?compared?with?the?traditional?synchronous?operation?mode?of?the?quay?crane，?the?operation?efficiency?of?the?quay?crane?by?the?model?is?greatly?improved.?The?result?shows?that?the?algorithm?is?effective?and?the?model?is?beneficial?to?the?improvement?of?quay?crane?operation?efficiency.

Key?words：

synchronous?loading?and?unloading;?quay?crane?operation?sequence;?genetic?algorithm

收稿日期：?2018-10-17

修回日期：?2019-05-05

基金項目：

國家自然科學基金（71471110）;上海市科學技術委員會創(chuàng)新項目（16DZ1201402，16040501500）;上海市科學技術委員會工程中心能力提升項目（14DZ2280200）;上海海事大學研究生學術新人培育計劃（YXR2017014）

作者簡介：

張文韜（1994—），男，寧夏銀川人，碩士研究生，研究方向為港口設備作業(yè)優(yōu)化，（E-mail）377499493@qq.com;

韓曉龍（1978—），男，上海人，副教授，碩導，博士，研究方向為物流與供應鏈管理，（E-mail）xlhan@shmtu.edu.cn

0?引?言

隨著經濟全球化和集裝箱船大型化的發(fā)展趨勢，我國大型集裝箱碼頭的吞吐量日益增加。如何提高船舶的裝卸效率，保證船舶船期已經成為我國大型港口亟待解決的問題。在傳統(tǒng)的“先裝后卸”作業(yè)模式下，岸橋有一半時間處在“空閑”狀態(tài)，岸橋資源未得到充分利用。為提高岸橋作業(yè)效率，“同步裝卸”作業(yè)模式被提出，在該模式下進口集裝箱與出口集裝箱裝卸作業(yè)同步進行，岸橋作業(yè)效率得到了提高。

近年來，在集裝箱裝卸及相關作業(yè)設備調度問題上取得了較為豐富的研究成果。國外的研究成果主要有：KIM等[1]研究了岸橋裝卸順序問題，設計貪心隨機自適應搜索法進行求解;LEE等[2]以出口集裝箱倒箱量最少為目標建立了整數(shù)規(guī)劃模型，應用近鄰搜索算法求解出口集裝箱裝船前的預倒箱問題;ZHANG等[3]以最短行駛路線為目標，優(yōu)化了龍門吊在堆場間的行駛路線;BISH[4]將神經網(wǎng)絡與模擬退火算法相結合，給出了多岸橋背景下集卡調度的可行方案;ZHEN等?[5]建立了混合整數(shù)規(guī)劃模型并應用粒子群算法進行求解，解決了岸橋與集卡的聯(lián)合調度問題。國內的研究成果主要有：韓曉龍等[6]將岸橋作業(yè)動作進行分解，對港口資源進行仿真優(yōu)化，得到了岸橋最優(yōu)調度方案;盧毅勤等[7]建立了最大化集卡的利用效率與最小化集卡碳排放的多目標整數(shù)優(yōu)化模型，并應用粒子群算法進行了求解;周鵬飛等[8]應用禁忌搜索算法，在出口集裝箱隨機進場的情況下給出了貝和貝內箱位的分配方法;高鵬等[9]建立了堆場進口集裝箱提箱作業(yè)雙層規(guī)劃模型，采用路徑搜索算法得到最優(yōu)倒箱路徑;魏航[10]通過分析碼頭取箱時間窗機制，建立了進口集裝箱取箱時間窗優(yōu)化模型，并設計了遺傳算法進行求解;曾慶成等[11]將神經網(wǎng)絡與模擬退火算法相結合，建立了雙層規(guī)劃模型，給出了岸橋、集卡和場橋的集成調度方案;祝慧靈等[12]研究了考慮船舶穩(wěn)定性、吃水深度的船舶全航線配積載問題，并應用啟發(fā)式算法得到初始可行解，利用遺傳算法對初始可行解進行優(yōu)化。

近年來在岸橋同步裝卸作業(yè)方面具有代表性的研究有：GOODCHILD等[13]通過理論分析和數(shù)學演算證明了同步裝卸的可行性，并將流水線原理應用于岸橋同步裝卸作業(yè)中;ZHANG等[14]考慮集裝箱船的實際裝載情況，以岸橋最小作業(yè)循環(huán)次數(shù)為優(yōu)化目標建立了混合整數(shù)規(guī)劃模型，并應用智能算法進行了求解;常祎妹等15]研究了不確定條件下的岸橋同步裝卸問題，并應用傳統(tǒng)的遺傳算法與蒙特卡洛法相結合的混合遺傳算法進行了求解。

本文在上述研究的基礎上，研究帶有艙蓋的集裝箱船的岸橋同步裝卸問題，以最小化岸橋作業(yè)完成時間為目標，建立整數(shù)規(guī)劃模型，并設計遺傳算法進行求解。

1?問題描述

岸橋同步裝卸作業(yè)模式主要是為了解決岸橋空駛問題，以及這一過程中裝卸集裝箱列的順序問題。

岸橋同步裝卸示意圖見圖1：岸橋在完成船艙內任意列的進口集裝箱卸載工作后，在返回的過程中從集卡上提取一個出口集裝箱，將其放置在船艙內已經完成卸載的集裝箱列的箱位上，再從剩余集裝箱列的箱位上提取一個進口集裝箱，將其放置在岸邊等候的集卡上。該種作業(yè)模式的優(yōu)勢在于：一方面，能有效降低岸橋的空閑率，使岸橋處于滿負荷工作狀態(tài);另一方面，能降低集卡的空載率，并縮短集卡等待岸橋的時間。

岸橋同步裝卸主要遵循以下規(guī)則：

（1）岸橋先進行進口集裝箱卸船作業(yè)，后進行出口集裝箱裝船作業(yè)。在裝卸順序上，進口集裝箱由列的頂層至下層依次進行卸船作業(yè)，出口集裝箱由列的底層至上層依次進行裝船作業(yè)。對于同一箱位來說，先進行進口集裝箱卸載作業(yè)，再進行出口集裝箱裝船作業(yè)。

（2）對于已經配對進行同步裝卸的列，若該配對列所需裝卸的進口與出口集裝箱數(shù)量不相等，則剩余的需要進行裝載或卸載的集裝箱采用單循環(huán)作業(yè)模式，不再參與后續(xù)同步裝卸作業(yè)，只進行單獨的裝卸作業(yè)。

2?模型建立

本文建立的數(shù)學模型優(yōu)化目標為最小化岸橋作業(yè)完成時間，整個模型限定為多輛集卡配合單臺岸橋進行作業(yè)。整個作業(yè)過程的完成時間，以完成集裝箱船上最后一個出口集裝箱裝載的時間點作為岸橋作業(yè)的完成時間點。

岸橋同步裝卸優(yōu)化模型的建立主要基于假設：（1）在裝船過程中沒有新集裝箱進場。（2）碼頭方已提前知曉船舶的積載情況、進港時間和箱位數(shù)量。（3）只考慮單岸橋作業(yè)模式。（4）碼頭集卡數(shù)量充足，不存在岸橋等待集卡的情況。（5）所裝卸的集裝箱尺寸相同，只考慮船舶單個艙位的裝卸。

2.1?模型符號與決策變量

I為艙蓋上需要裝載的集裝箱列的集合;I′為艙內需要裝載的集裝箱列的集合;li為第i列需裝載的集裝箱數(shù)量，ui為第i列需卸載的集裝箱數(shù)量;sui為岸橋卸載第i列集裝箱的開始時間;eui為岸橋卸載第i列集裝箱的結束時間;sli為岸橋裝載第i列集裝箱的開始時間;eli為岸橋裝載第i列集裝箱的結束時間;a為岸橋一個裝或卸作業(yè)過程的用時;T為岸橋總作業(yè)完成時間。

模型的決策變量有：xij，若第i列在第j列之前卸載，則xij=1，否則xij=0;yij，若第i列在第j列之前裝載，則yij=1，否則yij=0。

2.2?數(shù)學模型

式（1）為目標函數(shù)，即最小化岸橋作業(yè)完成時間;式（2）為對目標函數(shù)的定義;式（3）為單列集裝箱卸載結束時間;式（4）為艙蓋上單列集裝箱的裝載結束時間;式（5）規(guī)定艙內單列集裝箱裝卸順序，即先卸后裝;式（6）規(guī)定艙蓋上與艙內集裝箱的卸載順序，即艙蓋上整體卸載完畢后，艙內方可進行卸載;式（7）規(guī)定艙蓋上與艙內集裝箱的裝載順序，即艙內整體裝載完成后，艙蓋上方可開始裝載作業(yè);式（6）～（9）對決策變量xij和yij進行了定義;式（10）～（13）保證每列集裝箱裝載或卸載只有一個緊前作業(yè)和一個緊后作業(yè);式（14）～（15）為決策變量的取值。

[2]LEE?Yusin，?HSU?Nai-Yun.?An?optimization?model?for?the?container?pre-marshalling?problem[J].?Computers?&?Operations?Research，?2007，?34（11）：?3295-3313.?DOI：?10.1016/j.cor.2005.12.006.

[3]ZHANG?Chuqian，?WAN?Yat-wah，?LIU?Jiyin，?et?al.?Dynamic?crane?deployment?in?container?storage?yards[J].?Transportation?Research?Part?B，?2002，?36（6）：?537-555.?DOI：?10.1016/s0191-2615（01）00017-0.

[4]BISH?E?K.?A?multiple-crane-constrained?scheduling?problem?in?a?container?terminal[J].?European?Journal?of?Operational?Research，?2003，?144（1）：?83-107.?DOI：?10.1016/s0377-2217（01）00382-4.

[5]ZHEN?Lu，?YU?Shucheng，?WANG?Shuaian，?et?al.?Scheduling?quay?cranes?and?yard?trucks?for?unloading?operations?in?container?ports[J].?Annals?of?Operations?Research，?2019，?273：?455-478.?DOI：?10.1007/s10479-016-2335-9.

[6]韓曉龍，?丁以中.?集裝箱港口裝卸作業(yè)仿真系統(tǒng)[J].?系統(tǒng)仿真學報，?2006，?18（8）：?2366-2369.?DOI：?10.3969/j.issn.1004-731X.2006.08.079.

[7]盧毅勤，?楊斌，?黃有方.?兼顧碳排放量和效率的集卡調度多目標優(yōu)化[J].?計算機仿真，?2015，?32（6）：?386-389.?DOI：?10.3969/j.issn.1006-9348.2015.06.085.

[8]周鵬飛，?方波.?動態(tài)環(huán)境下集裝箱碼頭堆場出口集裝箱箱位分配建模與算法研究[J].?控制與決策，?2011，?26（10）：?1571-1576.?DOI：?10.13195/j.cd.2011.10.134.zhoupf.005.

[9]高鵬，?金淳，?韓慶平.?提箱作業(yè)優(yōu)化問題的嵌套啟發(fā)式算法[J].?系統(tǒng)管理學報，?2008，?17（2）：?203-209.

[10]魏航.?集裝箱碼頭堆場取箱時間窗優(yōu)化研究[J].?管理科學學報，?2011，?14（9）：?21-36.

[11]曾慶成，?楊忠振.?集裝箱碼頭集成調度模型與混合優(yōu)化算法[J].?系統(tǒng)工程學報，?2010，?25（2）：?264-270.

[12]祝慧靈，?計明軍.?集裝箱船舶全航線配載優(yōu)化模型與改進遺傳算法[J].?交通運輸工程學報，?2014，?14（5）：?59-67.

[13]GOODCHILD?A?V，?DANGAZO?C?F.?Crane?double?cycling?in?container?ports：?planning?methods?and?evaluation[J].?Transportation?Research?Part?B，?2007，?41（8）：?875-891.?DOI：?10.1016/j.trb.2007.02.006.

[14]ZHANG?Haipeng，?KIM?K?H.?Maximizing?the?number?of?dual-cycle?operations?of?quay?cranes?in?container?terminals[J].?Computers?&?Industrial?Engineering，?2009，?56（3）：?979-992.?DOI：?10.1016/j.cie.2008.09.008.

[15]常祎妹，?朱曉寧.?不確定因素下的集裝箱碼頭車船間裝卸作業(yè)集成調度[J].?交通運輸工程學報，?2017，?17（6）：?115-124.?DOI：?10.3969/j.issn.1671-1637.2017.06.013.

（編輯?賈裙平）