泊位配置研究

Aheuristics-basedsolutiontothecontinuousberthallocationandcraneassignmentproblem

MohammadHamdyElwanya,IslamAlia,YasmineAbouelseoud

abb,*

ProductionEngineeringDepartment,FacultyofEngineering,AlexandriaUniversity,Egypt

EngineeringMathematicsandPhysicsDepartment,FacultyofEngineering,AlexandriaUniversity,Egypt

Received19January2012;revised5September2013;accepted9September2013Availableonline9October2013

KEYWORDS

ContainerTerminal(CT);BerthAllocationProblem(BAP);

QuayCraneAssignmentProblem(QCAP);

SimulatedAnnealing(SA)

AbstractEffectiveutilizationplansforvariousresourcesatacontainerterminalareessentialtoreducingtheturnaroundtimeofcargovessels.Amongthescarcestresourcesaretheberthanditsassociatedcranes.Thus,twoimportantoptimizationproblemsarise,whicharetheberthalloca-tionandquaycraneassignmentproblems.Theberthallocationproblemdealswiththegenerationofaberthplan,whichdetermineswhereandwhenashiphastoberthalongsidethequay.Thequaycraneassignmentproblemaddressestheproblemofdetermininghowmanyandwhichquaycrane(s)willserveeachvessel.Inthispaper,anintegratedheuristics-basedsolutionmethodologyisproposedthattacklesbothproblemssimultaneously.ThepreliminaryexperimentalresultsshowthattheproposedapproachyieldshighqualitysolutionstosuchanNP-hardprobleminareason-ablecomputationaltimesuggestingitssuitabilityforpracticaluse.

ª2013ProductionandhostingbyElsevierB.V.onbehalfofFacultyofEngineering,Alexandria

University.

1.Introduction

Sincetheintroductionofstandardizedcontainersinfreighttransportinthe1960s,itsusehasbeenincontinuousgrowth,especiallywiththeenormousgrowthinworldtradeinthepast

*Correspondingauthor.Tel.:+201003727019.

E-mailaddresses:elwany@aucegypt.edu(M.H.Elwany),islam.ali@alexu.edu.eg(I.Ali),yasmine.abouelseoud@gmail.com(Y.Abouelseoud).PeerreviewunderresponsibilityofFacultyofEngineering,AlexandriaUniversity.

Production and hosting by Elsevier20years.Thisgrowthincontainertransportledtoincreasedservicedemandsatcontainerterminalswhonowhavetoservetensofvesselsperday,loadandunloadthousandsofcontain-ersperday,andtheyhavetodosoinatimelymannerinordertoreducethetimethatshipshavetospendattheterminalandthusgainingacompetitiveadvantageoveritsneighboringportsintheregion.Thiscompetitiveadvantagewouldhelptheterminalincreaseitscustomersandthusitsprofit.

Containerterminalsusealargevarietyofresourcesandequipmenttoserveincomingvessels.BerthandQuayCranes(QCs)arethescarcestandmostexpensiveresourcesforcon-tainerterminalsbecauseofthelargeinvestmentneededtoin-creasethecapacityofanyofthesetworesources,iftheexpansionofthesetworesourcesisphysicallyfeasibleinthefirstplace.Consequently,achievingmaximumutilizationforthesetworesourcesthroughbetterplanningiscriticalto

1110-0168ª2013ProductionandhostingbyElsevierB.V.onbehalfofFacultyofEngineering,AlexandriaUniversity.http://dx.doi.org/10.1016/j.aej.2013.09.001

672

achievetheoverallmaximumproductivityforthewholeterminal.

Twoimportantplanningproblemsthusarise,whicharetheBerthAllocationProblem(BAP)andtheQuayCraneAssign-mentProblem(QCAP).Intheformer,aberthingtimeandaberthingpositionatthequayforeachvesseltobeservedwith-inagivenplanninghorizonaredetermined.Inthelatter,asetofspecificcranesisassignedtoserveeachvessel.Thestronginterrelationshipbetweentheutilizationofthequayspacere-sourceandthequaycranesmotivatesanintegratedsolutionapproachtothetwoproblems.Thedrivingforceofthisap-proachistoanticipatevesselhandlingtimesonthebasisofcraneassignmentandcraneschedulingdecisions.Thesespeci-fiedhandlingtimesareusedwithintheberthplanningsteptodecideontheberthingtimesandberthingpositionsofvessels.TheresultingproblemisreferredtoastheBerthAllocationandCraneAssignmentProblem(BACAP).

Althoughmanystudiesconsideredberthsasdiscretere-sourcesthatcanbeallocatedtovessels,somestudieshavecon-sideredthequayasacontinuouslinethatmultiplevesselscansharewitheachotheratthesametime.Thus,whenthequayisconsideredasacontinuousline,morevesselscanbeservedsimultaneouslyataquayofaparticularlength–ofcourse,ifthevesselsareshorterinlengththanthequayside[1–4].Therearemanydifferenttypesofconstraintsthatmustbeconsideredwhendeterminingtheberthingpositionsofvessels.ExamplesincludethedepthofwateralongthequayandthemaximumoutreachofQCsinstalledatspecificpositionsonthequay.Ifthedepthofthewaterofapartofthequayisnotenough,ortheoutreachofQCsinstalledatapartofthequayisshorterthanthatnecessary,thecorrespondingvesselcannotbeassignedtothatpartofthequay.

Temporalconstraintscanrestricttheberthingtimesandthedeparturetimesofvessels.AccordingtoFrankMeisel[5],thefollowingcasescouldbedistinguished:staticarrivalsanddy-namicarrivals.Intheformercase,therearenoarrivaltimesgivenforthevesselsanditisassumedthatvesselsalreadywaitattheportandcanberthimmediately.Inthecaseofdynamicarrivals,eitherfixedarrivaltimesaregivenforthevesselsandtheycannotberthbeforetheexpectedarrivaltime,orarrivaltimesimposemerelyasoftconstraintontheberthingtimesanditisassumedthatavesselcanspeedupatacertaincostinordertomeetaberthingtimeearlierthantheexpectedarri-valtime.

Inthispaper,theproblemofallocatingvesselswithdy-namicarrivalstoacontinuousquayisconsidered–whichisamorechallengingproblemcomparedtothediscretevariantoftheproblem.Moreover,variablewaterdepthconstraintshavebeenaccountedfor.Aheuristics-basedapproachispro-posedtosolvetheBACAP.

Therestofthispaperisorganizedasfollows.Inthenextsection,aliteraturereviewontheberthallocationandcraneassignmentproblemsispresented.Section3includesthede-tailedproblemdefinitionandtherelatedassumptions.InSec-tion4,theproposedsolutiontechniqueisdescribed.Theresultsofimplementingoursolutionstrategytoasetofbench-markinstancesareshowninSection5.Section6discussesaninterestingspecialcase,whichisreferredtoasatightlypackedproblem,andproposesamethodologytohandleit.Finally,Section7concludesthepaper.

M.H.Elwanyetal.

2.Relatedwork

Inliterature,mathematicalformulationshavebeendevelopedtomodeltheberthallocationandquaycraneassignmentprob-lems.Ingeneral,theresultingmodelsaremixedintegerpro-grammingformulationsandthus,cannotbesolvedforinstancesofpracticalsize.Hence,heuristicsolutionmethodshavebeentailoredtohandlesuchproblems.Inwhatfollows,lightisshedonsomeofthesemethods.

Ageneticalgorithmhasbeenappliedin[6]tosolvetheberthallocationproblemwithdynamicarrivalsanddiscreteberthsthatcanbesharedbymorethanonevessel.Theobjec-tiveistominimizethetotaltimespentattheCTwhichin-cludestheshiphandling(orservicetime)andthewaitingtimeforberthavailability.Moreover,ithasbeenassumedthattheservicetimeisdependentontheberthwhereavesselisas-signed.Furthermore,variablewaterdepthconstraintshavebeenincorporatedinthedevelopedmathematicalmodel.

ParkandKimdevelopedamathematicalformulationforthecontinuousBACAPwithdynamicarrivals[7].Theypro-posedatwophasesolutionprocedurefortheirformulation.Inthefirstphase,theberthingtimesandpositionsaswellasthenumberofcranesassignedtoavesselduringitsservicearedetermined.Inthisphase,aLagrangianrelaxationoftheproblemissolvedusingasub-gradientoptimizationtechniquewheretheproblemisdecomposedintoseveralindependentsub-problems.Thisstepmayyieldinfeasibleberthplans.Therefore,aheuristichasbeenproposedtotransforminfeasi-blesolutionsintofeasibleones.Inthesecondphase,thespe-cificsetofcranesassignedtoeachvesselisdeterminedusingdynamicprogramming.

KimandMoonconsideredtheBAPwithdynamicarrivals[8].Theyproposedaheuristicsolutionstrategythatinsertsves-selsinthespace–timediagramaccordingtoagivenprioritylist.Vesselsatthetopofthelistaremorelikelytobemooredclosetotheirdesiredberthingpositions.Simulatedannealingisthenusedtoexplorethespaceofprioritylistsinordertosearchforimprovementsintheobjectivefunctionvalue.Theobjectivefunctionincludedtermspenalizingnon-optimalber-thinglocationsanddelayeddeparturesofvessels.

MeiselandBierwirthin[9]haveexplicitlyincorporatedtheimpactofthequaycraneresourcesasadeterminantofthehandlingtime.Factorsinfluencingthecraneproductivityhavebeenmodeledaswellaspracticalaspectsoftheproblemlikespeedingupvesselsandconsideringthecostofoperatingcranesbesidesthetraditionalservicequalitycost.Moreover,theyconsidereddynamicarrivalsofvessels.FortheresultingdynamiccontinuousBACAP,newheuristicshavebeenpre-sentedtosolvethisproblemagainaccordingtoagivenprioritylist.Theyconsideredaninitialprioritylistinwhichvesselsaresortedinascendingorderaccordingtotheirexpectedtimeofarrival;thatis,onaFCFSbasis.Theyalsosuggestedtheuseofmeta-heuristics;namely,SqueakyWheelOptimization(SWO)andTabuSearch(TS)toimprovetheresultsinitiallyobtainedbasedontheirproposedheuristics.ComputationalcomparisonsshowedthatbothSWOandTSdeliversolutionsofgoodqualityinareasonablecomputationaltime.Inthispa-per,theirinterestingworkisextendedbyconsideringanalter-nativeinitialprioritylistandbyincorporatingwaterdepthconstraintsintoourmodel.

Aheuristics-basedsolutiontothecontinuousberthberthallocationandcraneassignmentproblem673

3.Problemdefinitionandrelatedassumptions

Inthissection,variousaspectsoftheproblemaddressedinthispaperarediscussedindetail.3.1.Basicassumptions

ThefollowingassumptionsaremadeforthecontinuousBA-CAPwithdynamicarrivalsdealtwithinthispaper:

1.Ittakesnotimetoberthandtounberthvessels.

2.IttakesnotimetomoveaQCfromonevesseltoanothervessel.

3.Vesselsareservedwithoutpreemption,i.e.,oncestartedtoserveavesseltheprocessisnotinterrupteduntiltheserviceiscompleted.

4.Everycranehasthetechnicalcapabilitytoserveanyvessel.Furthermore,thecranesareidentical,i.e.,theyshowthesamemaximumproductivity.

5.Thewaterdepthisnotfixedforallberthingpositionsandhencespecialconsiderationisgiventorespectingtherequireddraftassociatedwitheachincomingvessel.

6.Allinputparameters(suchasunloadingtime)anddecisionvariables(suchastheberthingtime)aredeterministic.

3.2.Inputparameters

AterminalwithaquayoflengthL,measuredinsegmentsof10mlength,isconsidered.Thewaterdepthalongsidethequayisprovidedforeachsegment.AnumberofQQCsareavail-abletoservethevessels.TheplanninghorizonoftheBACAPisHhours,whereTisacorrespondingsetof1-htimeperiods;i.e.,T={0,1,...,HÀ1}.Withintheplanninghorizon,asetofvesselsV={1,2,...,n}isprojectedtobeserved,wherenisthetotalnumberofvessels.

Foreachvesseli,itslengthlimeasuredinsegmentsof10mlengthisgiven.ThecranecapacitydemandofvesselitofulfillallloadingandunloadingoperationsismiQC-hours.Themin-imumandmaximumnumberofQCstoassigntothevesselare

denotedbyrminiandrmax,yieldingtherangeRi¼½rminmax

󰀃anexpecteditimeofarrivalETAknown.i;r.Furthermore,i

iisBer-thingthevesselearlierthanETAiispossiblebyaspeeduponitsjourneytotheterminal.Therealizablespeedup,however,islimited.Tomodelthis,anearlieststartingtimeESTi6ETAiisestimated;i.e.,thevesselcannotbeberthedearlierthanESTi.Finally,anexpectedfinishingtimeEFTiandalatestfinishingtimeLFTiaregivenforthevessel.Importandexportcontain-ersofavesselarestoredindedicatedyardareas.Adesiredber-thingpositionb0iisspecifiedforvesseliwithinthevicinityoftheseyardareas.Inaddition,thevesseldraftDiisprovidedsothatthechoiceofaberthingpositionmustbemadesuchthatthequayshowsasufficientwaterdepthalongthevessel’slength.

3.3.Decisionvariables

ThedecisionstobemadetoderiveasolutionoftheBACAParetodetermineforeachvesseli:aberthingtimesi,aberthingpositionbi,andthenumberofQCstoassigntoitduringeach

ofitsservicetime-slotssuchthatacostmeasureisminimized.Theberthingtimesiofavesselismarkedbythebeginningofthefirsttime-slotwithcranesassigned,whereasitsdeparturetimeeiisdefinedbytheendofthelasttime-slotwithcranesassigned.Thetimespanbetweensiandeidefinesthehandlingtimeofvesseli.Theassignmentofcranestovesselsisrepre-sentedbyabinarydecisionvariableritq.Itissetto1,ifandonlyifexactlyqQCsareassignedtovesseliduringtime-slott.ToevaluateasolutiontotheBACAP,thedeviationfromthedesiredberthingpositionDbi¼jb0ETAiÀbij,thenecessaryspeedupDi=(ETAiÀsi)+,andthetardinessDEF-Ti=(eiÀEFTi)+aredeterminedforeachvesseli,wherex+=max{0,x}.InFig.1,anexampleofacompleteberthplanwithquaycraneassignmentisshown.Eachrectanglerep-resentstheregionoccupiedinthetime–spacedomainbysomevesseli,wherethelowerleftcornercorrespondstotheob-tainedoptimalpairofberthingtimeandberthingposition

ðsÃbÃ

i;iÞ.

3.4.Objectivefunction

ThesameobjectivefunctionemployedbyMeiselandBierwirthin[9]isadoptedinthispaper,whichincorporatesbothservicequalitycostsandoperationalcosts.Itisthesumofthecostsarisingfromfourfactors:

1.Assigningavesselaberthingtimeearlierthanitsexpectedtimeofarrivaladdsacostforspeedingupthevesselduetoexcessinfuelconsumption(c1exceedingiperunittime).

2.Tardinesscostincurredfortheexpectedfinishingtime(c2iperunittime).

3.Beingunabletofinishservingavesselbeforeitslatestfin-ishingtimeincursapenalty(c34.ThecostoftherequiredQC-hoursi).

forservingtheincomingvessel,whichistheoperationalcostterm(c4perQC-hour).

3.5.Productivityofquayresources

TherailmountedQCsinacontainerterminalareunabletopasseachother.AsaconsequenceinterferenceamongQCscanbemodeledintheformofunproductivecranewaitingtime.Ingeneral,themorecranesareassignedtoavesselthemoreinterferencewilltakeplaceleadingtoreducedmarginalproductivityofcranes.AccordingtoSchonfeldandSharafeldi-en,aninterferenceexponentcanbeusedtomodelthereductioninmarginalproductivityofcranes[10].Foragiveninterfer-enceexponenta(0assigningqcranestoavesselforonehourisgivenbyatotalofqaQC-hours.

Theproductivityofaterminalisalsoaffectedbythework-loadonhorizontaltransportmeans;thatis,thetrucksthatde-liver/receivecontainersto/fromtheyardareas.Thisworkloadisminimalifavesselberthsatitsdesiredberthingpositionb0desiredposition,i.Therefore,ifavesselmoorsawayfromthisthisleadstolowerproductivity.Thisproductivitylossismod-eledbyanincreaseinthevessel’sQCcapacitydemand.LetbP0denotetherelativeincreaseinQCcapacitydemandperunitofberthingpositiondeviation,calledtheberthdevia-tionfactor.Hence,avesselmooringDbiquaysegmentsawayfromitsdesiredberthingpositionrequires(1+bDbi)miQC-hourstobeserved,assuggestedin[5].

Consideringbotheffectsdescribedabove,theminimumhandlingdmin

󰀂timeneededtoserveavesseliisgivenas

ð1þbDbiÞmi󰀃i¼ðrmaxað1ÞiÞThecompletemathematicalmodelforthevariantofthe

BACAPinhandappearedinanearlierpublication[11].4.Theproposedsolutiontechnique

Inthissection,adetaileddescriptionoftheproposedheuris-tics-basedapproachtosolvethecontinuousBACAPwithdynamicarrivalsandvariablewaterdepthalongsidethequayisprovided.Thesolutioniterativelyproceedsinthreesteps.Inthefirststep,aprioritylistforthevesselsisgenerated.Inthenextstep,aheuristicprocedureisappliedtothegeneratedlisttoconstructaninitialfeasiblesolution.Inthethirdstep,tworefinementproceduresareinvokedtoseekfurtherimprove-mentsintheobjectivefunctionvalue.4.1.Prioritylistgeneration

Giventhefullinformationonthevesselsthataretobehandledduringtheplanninghorizon,aprioritylistdeterminestheorderinwhichvesselsareinsertedintheberthplan(time–spacedomain).Thevesselsatthetopofthelisthaveabetterchanceofbeingplacedatoratleastclosetothedesiredberthingposition.

Initially,thevesselsaresortedindescendingorderofthevalueoftheexpressioncli/L+(1Àc)EFTi/H,where0Inthesubsequentiterations,simulatedannealingisusedtoexplorethespaceofprioritylists.Inthesimulatedannealingmethod,thequalityofthesolutiondependsonthecontrol

M.H.Elwanyetal.

parametersandthescheduleofthetemperature.Intypicalimplementations,thesimulatedannealingapproachinvolvesapairofnestedloopsandthreeadditionalparameters,anini-tialtemperatureT0,acoolingrate0󰀅Step2.Repeatthefollowingstepsuntiloneofthestoppingconditionsbecomestrue,forexamplethetemperaturedropsbeyondathresholdornoimprovementisobtainedforsomenumberofiterations.

Step2.1.PerformthefollowingloopRtimes.

Step2.1.1.PickarandomneighboringprioritylistP’ofP.

Step2.1.2.Letd=cost(P’)Àcost(P).(Thecostisevaluatedbyapplyingtheconstructionheuristicstepandthetwolocalrefinementprocedures).

Step2.1.3.Ifd<0(downhillmove),setP=P’.Step2.1.4.IfdP0(uphillmove),generatearandomnumber,x,fromtheinterval,(0,1);ifxStep2.2.SetT=rT(Reducethetemperature).

Aneighboringprioritylistisgeneratedbyrandomlychoos-ingtwosuccessivevesselsandinterchangingtheirranksinthelist.

4.2.Constructionheuristic

Inthisstageofthesolution,afeasibleberthplanfortheincomingvesselsisgeneratedaccordingtothegivenprioritylist.Thevesselsareinsertedintotheberthplanonebyone.Theprocedureattemptstopositionavesselatitspreferredberthingpositionanditsexpectedtimeofarrival.IfthisisimpossiblebecauseitwouldcauseanoverlapwithapreviouslyinsertedvesselorduetoaninsufficientnumberofQCsavail-ableatthistimeslottoservethevesselorinappropriatewaterdepth,thenthevesselisshiftedacrossthequaylengthinordertofindafeasibleberthingspot.Moreover,thevesselisshiftedacrosstheplanninghorizonseekingabetterfeasibleberthingspotinthetime–spacedomain.ThefinishingtimeiscomputedaccordingtoEq.(1)andthenumberofcranesavailabletoserveavesselduringeachtimeslotwithinitshandlingtimeisdetermined.Thehandlingtimemaybeextendedifthere-quiredcranecapacityisnotfulfilled.Analmostuniformquaycraneassignmentisrealizedtoavoidcraneinterferenceprob-lemslikelytooccurifthenumberofcranesservingavesselisalteredfromonetimeslottoanother[5].4.3.Quaycraneresourceleveling

Vesselsatthetopoftheprioritylistarelikelytobeberthedattheirpreferredberthingpositionandtobeservedbythemax-imumnumberofQCs.Resourcelevelingtriestoovercomethisdoublepreferentialtreatment.Itinsertsthevesselsonebyoneintotheberthplanafterapplyingarestrictiononthemaxi-mumnumberofQCsservingthevessel(applyingallvalues

Aheuristics-basedsolutiontothecontinuousberthberthallocationandcraneassignmentproblem675

betweenrminandrmaxiteratively).Theresttheninsertediofthevesselsaretogeneratei

apartialberthplan.Thecurrentves-selofinterestistemporarilydeletedfromtheberthplanandsubsequentlyre-insertedafterremovingtheimposedrestric-tion.Theresourcelevelisthenfixedatthevaluethatgeneratesthebestpartialberthplanandthenextvesselishandledinthesamemanner.Theprocedureiscompletedafterallvesselshavebeendealtwith[5].

4.4.Spatialandtemporalshifts

Thisstagebeginswithidentifyingspatialandtemporalclus-ters.Spatialclustersinaberthplanaredefinedasvesselsthatarepositionedadjacenttoeachotheralongsidethequayandareservedsimultaneouslyduringatleastonetimeslot.Tempo-ralclustersaredefinedasvesselsthatareservedrightaftereachotherandeachpairofconsecutiveshipsareassignedtoatleastonecommonquayslot.Afteridentifyingtheseclusters,thespatialclustersaremovedalongthequaytowardthelowerborderandthentowardtheotherborder.Moreover,thetem-poralclustersaremovedacrosstheplanninghorizon;onceto-wardthestartingtimeoftheplanninghorizonandasecondtimetowardtheotherextreme.Thisisdoneinordertofurthersearchforberthplanswithlowercost[5].

Thefollowingflowchartsummarizesthewholealgorithm,seeFig.2.

5.Implementationandexperimentalresults

Inthissection,thetestinstancesandthealgorithmparameterssettingusedtoassesstheeffectivenessoftheproposedsolutionstrategyaredescribed.Moreover,asampleoftheobtainedre-sultsisshown.5.1.Testinstances

Fortesting,appropriatebenchmarkinstancesarerequired.ThesetoftestinstancesusedwereprovidedbyDr.FrankMei-StartGenerateapriority listApplyconstructionheuristicRefine the obtained berth plan using resource levelingSeek a better berth plan using spatial and temporal shifts No Stopping criterion metYes End Figure2Proposedheuristics-basedsolutionprocedure.Table1

Technicalspecificationsofdifferentvesselclasses.

ClasslimiDirminirmaxiFeederU[8,21]U[5,15]U[4,8]12MediumU[21,30]U[15,50]U[8,12]24Jumbo

U[30,40]

U[50,60]

U[12,18]

4

6

seluponrequest.Intheseinstances,vesselsaredistinguishedbythreeclasses:namely,feeder,medium,andjumbo.Theclas-sesdifferintheirtechnicalspecificationsandcostratesasshowninTable1,whereUdesignatesauniformdistributionofintegervaluesinthespecifiedinterval.Theonlymodifica-tiontohistestinstancesthathasbeenmadeisaddingthedraftforeachvessel.

Meiselsuggestedthefollowingmethodologyingeneratingsuitabletestinstances[5].Withineachinstance,60%ofthevesselsbelongtothefeederclass,30%belongtothemediumclass,and10%belongtothejumboclass.Theplanninghori-zonHissettooneweek(168h).TheexpectedtimesofarrivalETAiofvesselsareuniformlydistributedintheplanninghori-zon.Itisassumedthatavesselcanspeedupbyatmost10%,whichdeterminestheearlieststartingtimeESTi=0.9ETAi.TheexpectedfinishingtimeEFTiisderivedbyaddingavessel’sminimumhandlingtimetoETAi.ThelatestfinishingtimeLFTiisderivedbyadding1.5timesavessel’sminimumhan-dlingtimetoETAi.ThedesiredberthingpositionisdrawnforvesseliusingU[0,LÀli].TheterminaldataincludethequaylengthL=100(1,000m)andthenumberofQCsQ=10.ToattainmoderateQCproductivitylosses,theinter-ferenceexponentissettoa=0.9andtheberthdeviationfac-torissettob=0.01.Thelattercausesa1%increaseinthehandlingeffortperquaysegmentofberthingpositiondevia-tion.TheassumedwaterdepthalongsidethequayisshowninFig.3.

5.2.Algorithmparameterssetting

Eachproblemissolved5timeswithdifferentstreamsofran-domnumbersusedinthesimulatedannealingmodule.ThecoolingscheduleparametersaresettoT0=40,r=0.65,andR=5.Theparametercusedintheinitialprioritylistgen-erationissetequalto0.5.5.3.ResultssanitychecksTheconsistencyoftheobtainedresultsisverifiedbyplottingtheberthplanandvisuallycheckingthatnooverlapbetweenFigure3Waterdepthalongsidethequay.676Figure4Ratiooftherangeforthetestinstances.vesselrectanglesexistsandanExcelsheethasbeenusedtoas-surethevalidityoftheresultingquaycraneassignment.Moreover,foreachproblem,theratiooftherangeofobjec-tivevaluesforthefivetrialstothelowestobjectivevalue(whichisexpressedasthehighestobjectivevalueduringthefivetrialsminusthelowestobjectivevalueduringthefivetrialsdividedbythelowestobjectivevalueduringthefivetrials),iscalculated.Fig.4showstheratiooftherangeoftheobjectivevaluesforfivetrialstothelowestobjectivevalueasobtainedforthesetof20testinstancesused.Theresultsshowthattheaverageratiois5.4%,thenitcanbeconcludedthattheobjectivevaluesobtainedbythesimulatedannealingmethodareconsistentfordifferenttrials.

Furthermore,themathematicalmodeldevelopedin[5]hasbeenextendedtoincorporatewaterdepthconstraintsandithasbeenimplementedusingLINGOoptimizationsoftwarepackage.However,itonlyyieldedasolutionininstancesofverysmallsize.Insuchrestrictedproblems,ithasbeencheckedthatboththeLINGOmodelandtheproposedheuris-tics-basedapproachgiveidenticalresults.Unfortunately,theversionemployedofLINGOsoftwarehadlimitedcapabilitiesandthusevenalowerboundforourtestinstancesofpracticalsizecouldnothavebeenobtained.

Withtheaimofvalidatingourimplementationandthesoundnessoftheobtainedresults,thelowerboundsforthetestinstancesprovidedbyDr.FrankMeiselthatwereindicatedinhisdissertation[5]areused.Intheseinstances,thewaterdepthconstraintsarenotconsidered.Asampleoftheobtainedre-sultsisshowninTable2.Itisclearthattheresultsinmostin-stancesareincloseagreementwiththelowerbounds.

Furthermore,theeffectivenessoftheproposedinitialprior-itylistselectioncriterionhasbeentested.ThisisdemonstratedbytheresultsofapplyingtheconstructionheuristictothetestinstancesprovidedbyDr.FrankMeisel,asshowninTable3.6.Tightlypackedproblemsandplanninghorizonfictitiousextension

Considerthefollowingproblem.ThreevesselsareassumedtobeservedataterminalwithL=14,H=10,Q=5,c4=0.1,a=0.9,andb=0.1.Table4includesthevesseldataassoci-atedwiththestudiedexample.ThevesseldraftsareD1=5,D2=8,andD3=9.Thewaterdepthissetto6forthefirst5quaysegments,whileitreaches10forthelastsixsegments.Thewaterdepthforthesixth,seventhandeighthsegmentsis7,8and9,respectively.

M.H.Elwanyetal.Table2Benchmarkinstancesresults.NumberofvesselsCPLEX(LB)Objectivevalue(minimum)2084.085.153.9.975.280.275.879.756.856.857.657.667.575.456.15775.077.388.292.330137.7161.681.487100.9107.6.8113.3136.9161.240165.7217.2159.6185.9185.0300.8224.1357.5133.3168.7Table3Constructionheuristicresultsfordifferentinitialprioritylists.

ProblemnumberNo.VesselsObjectivevalueObjectivevalue(FCFS)(LVF)120

118.590.2260.156.1397.694.9496.496.4573.157.9657.657.6793.385.3878.978.9996.49410115.5115.51130

2162161296.793.113135119.714144.5134.715197.5197.516137.7127.817139.8113.918167.8142.619268.7228.620184.7115.82140

31731722276.9276.923550.4432.724453.3453.325239.1239.126398.9398.9273.6300.528424.2424.229334.2334.230

425.8

425.8

ThereisnoproblemsolvingtheabovetestinstanceusingLINGOtooptimalitywithoutchangingtheplanninghorizon.

Aheuristics-basedsolutiontothecontinuousberthberthallocationandcraneassignmentproblem

677

Table4Tightlypackedtestinstancevesselsdata.ilib0imirminirmaxi1374132471012356513Figure5Optimalberthplanofatightlypackedinstance.Buttryingtosolveitusingourheuristicapproach,aproblemhasbeenencounteredwhichwillbereferredtoasthe‘startupproblem’.Thisproblemmightoccurinproblemswithtightlypackedberthplans.Inthesecases,theconstructionheuristicfailstogenerateastartingfeasiblesolutionwhenitplacesthevesselsatthetopoftheprioritylistinberthingspotsthatdonotleaveroomforlatervesselstobeinsertedinthefirstplacenomatterhowtheprioritylistischanged.Aproposedremedyforthisproblemistoincreasetheplanninghorizonwithadummyperiodjusttoallowallthevesselstobeinsertedinaninitialberthplan,andbyimposingalargecostpenaltyonberthingvesselsduringthisdummyperiodthesubsequentlo-calrefinementsalwaystrytoshiftthevesselswithintheal-lowedplanninghorizon.

Intheparticularexampledescribedinthissection,toalle-viatetheaforementionedproblem,theplanninghorizonisin-creasedto15handthenitwaspossibletoreproducethesameresultsobtainedusingtheLINGOÒmodel.TheresultingberthplanisshowninFig.5.Theasterisksappearinginthisfigurerepresentthenumberofunusedquaycranesduringvar-ioustime-slotsinourplanninghorizon.7.Conclusion

Inthispaper,anintegratedheuristics-basedsolutionmethod-ologytosolvethetwomostimportantoptimizationproblemsrelatedtoseasideoperationsatacontainerterminal;namely,theberthallocationandquaycraneassignmentproblems,hasbeenpresented.Theproblemtackledinthispaperassumesacontinuousberthwithvariablewaterdepthalongthequaysideundertheassumptionofdynamicvesselsarrivals.Theproposedtechniquebeginswithfindinganinitialfeasiblesolu-tionwhichhandlesvesselsaccordingtoagivenprioritylistand

ESTiETAiEFTiLFTic1ic2ic3i2358112239102241467336thenseeksfurtherenhancementsbyapplyingtwolocalrefine-mentprocedures.Finally,simulatedannealingisusedtosearchthespaceofprioritylists.Aneffectiveinitialprioritizingcriterionhasbeenproposed,whichacceleratestheconvergenceoftheemployedheuristicstotheoptimalsolution.Theproposedsolutionalgorithmhasbeenappliedtosev-eraltestinstancesandtheconsistencyoftheobtainedresultswithallproblemconstraintshasbeenverified.ThequalityofthesolutionshasbeenassessedbycomparingthemtolowerboundsprovidedbyCPLEXoptimizationpackageandthusitisconcludedthattheemployedheuristics-basedmethodol-ogysucceededtoachievehighqualityberthplans.Yet,animportantpracticalaspectremainstobeconsidered.Thisisthestochasticnatureofsomeofthedecisionvariablesandin-putdesignparameters.Anactionplanisrequiredtodeterminehowtheberthplangeneratedbytheproposedalgorithmistobemodifiedincaseavesselfailstomeetitsberthingtimeordeparturetime.References

[1]ChristianBierwirth,FrankMeisel,Asurveyofberthallocationandquaycraneschedulingproblemsincontainerterminals,EuropeanJournalofOperationalResearch(2010)615–627.[2]AkioImai,EtsukoNishimura,StratosPapadimitriou,Thedynamicberthallocationproblemforacontainerport,TransportationResearchPartB(2001)401–417.[3]AkioImai,EtsukoNishimura,MasahiroHattori,StratosPapadimitriou,Berthallocationatindentedberthsformega-containerships,EuropeanJournalofOperationalResearch(2007)579–593.[4]AkioImai,HsiehChiaChen,EtsukoNishimura,StratosPapadimitriou,Thesimultaneousberthandquaycraneallocationproblem,TransportationResearchPartE(2008)900–920.[5]Frank.Meisel,SeasideOperationsPlanninginContainerTerminals,Physica-Verlag,Berlin,2009.[6]EtsukoNishimura,AkioImai,StratosPapadimitriou,Berthallocationplanninginthepublicberthsystembygeneticalgorithms,EuropeanJournalofOperationalResearch131(2001)282–292.[7]Young-ManPark,KapHwanKim,AschedulingmethodforBerthandQuaycranes,ORSpectrum25(2003)1–23.[8]KapHwanKim,KyungChanMoon,Berthschedulingbysimulatedannealing,TransportationResearchPartB37(2003)1–560.[9]Frank.Meisel,Christian.Bierwirth,Heuristicsfortheintegrationofcraneproductivityintheberthallocationproblem,TransportationResearchPartE45(2009)196–209.[10]P.Schonfeld,O.Sharafeldien,Optimalberthandcranecombinationsincontainerports,JournalofWaterway,Port,CoastalandOceanEngineering111(6)(1985)1060–1072.[11]IslamAlietal.,ContainerterminalberthallocationandquaycraneassignmentusingIPandsimulatedannealing,in:Proceedingsofthe41stInternationalConferenceonComputersandIndustrialEngineering,LosAngeles,USA,October2011.