Scheduling ships with uncertain arrival times through the Kiel Canal

ContentslistsavailableatScienceDirect

Maritime Transport Research

journalhomepage:www.elsevier.com/locate/martra

Scheduling ships with uncertain arrival times through the Kiel Canal

Tina Andersen

, Joakim Høgset Hove

, Kjetil Fagerholt

, Frank Meisel

aDepartment of Industrial Economics and Technology Management, Norwegian University of Science and Technology, Trondheim, Norway

bSchool of Economics and Business, Kiel University, Germany

a r t i c le i n f o

Keywords:

Ship scheduling Matheuristic Simulation Uncertainty Time corridors

a b s t r a c t

TheKielCanalisatwo-waywaterwaythatconnectstheBalticSeaandtheNorthSea.Thecanal consistsofanalternatingsequenceofnarrowtransitsegmentsandwidersidingsegments.This callsforsolvingashipschedulingproblemtodecidewhichshipshavetowaitinsidingstolet opposingtrafficpassthroughsuchthatthetotaltraversingtimeofallshipsisminimized.This paperextendspreviousstudiesonschedulingshipsthroughtheKielCanalbyconsideringthat thearrivaltimesoftheshipsattheentrancetothecanalaresubjecttouncertainty.Thisisa majorchallengeintheplanningasitgivesfrequentneedofreplanningtomaketheschedules feasible.Weproposeamathematicalformulationfortheproblemtomitigatethenegativeeffects oftheuncertainty.Thisformulationincorporatestime-corridors,sothattheschedulewillstillbe validaslongastheshipsarrivewithintheirgiventime-corridors.Tosolvereal-sizedinstances oftheproblem,weadaptamatheuristicthataddsviolatedconstraintsiterativelytotheproblem.

Thematheuristicwastestedwithinarollinghorizonsimulationframeworktostudytheeffectof arrivaltimeuncertainty.Weshowbyexperimentthatsolutionsofthematheuristicfordifferent time-corridorwidthscanbeusedtoidentifyasuitablecorridorwidththattradesoff theaverage traversingtimeofshipsandthenumberofreschedulesrequiredintheplanning.Asimplemyopic heuristic,reflectingthecurrentschedulingpractice,wasusedtogeneratebenchmarkresults,and testsonrealdatashowedthatthematheuristicprovidessolutionswithsignificantlylessneedof replanning,whileatthesametimekeepingthetotaltraversingtimesfortheshipsshort.Wealso providesimulationstogaininsightabouttheeffectontheships’averagetraversingtimefrom upgradingthenarrowtransitsegments.

1. Introduction

Theseabornecargovolumesareconstantlygrowingalongwiththeconcernabouttheenvironmentalconsequencesofgreenhouse gasemissionsandairpollution(UNCTAD,2018).Shippingcompaniesthereforelookforwaystoreducetheirfuelcostsandemissions.

TheKielCanalcutsthroughtheNorthernpartofGermanybetweentheNorthSeaandBalticSea(bluerouteinFig.1),allowingships tosaveonaverage250nauticalmiles,andreducethefuelconsumptionaccordingly,comparedtosailingaroundtheJutlandPeninsula inDenmark(redroute),seeHeitmannetal.(2013).TheKielCanalhasanannualtrafficofabout30000ships(UCA,2019)making itthemosttraffickedcanalintheworld.Thecanalis98.7kilometerslongandhastwosetsoflocks,oneateachend,intheportal townsKielandBrunsbüttel.TheshippingcompaniesalsovaluetheproximitytotheportofHamburg,whichisthethirdlargestport inEurope(UNCTAD,2018)andcaneasilybeaccessedfromtheKielCanal’sexitinBrunsbüttel.

∗Correspondingauthor.

E-mailaddresses:kjetil.fagerholt@ntnu.no(K.Fagerholt),meisel@bwl.uni-kiel.de(F.Meisel).

https://doi.org/10.1016/j.martra.2020.100008

Received5September2020;Receivedinrevisedform7December2020;Accepted21December2020

2666-822X/© 2020TheAuthors.PublishedbyElsevierLtd.ThisisanopenaccessarticleundertheCCBY-NC-NDlicense (http://creativecommons.org/licenses/by-nc-nd/4.0/)

Fig.1. SailingroutearoundtheJutlandPeninsulaandKielCanalshortcut.MeiselandFagerholt(2019).

Fig.2. Overviewoversidings(white)andtransitsegments(grey)intheKielCanaltogetherwithpassagenumberandsegmentnumber.

ThedailyoperationsoftheKielCanalconsistofplanningsafeshipschedulesforshipstraversingthecanal.TheKielCanalismade upof23differentsegments.Italternatesbetweenwidesidingsegmentsandnarrowtransitsegments.Fig.2illustratesthesidings andtransitsegmentsoverthelengthofthecanal.Sincethetransitsegmentsarenarrow,largeshipscanonlypasseachotherinthe widersidings.Moreprecisely,formanagingthetrafficoftheKielCanal,eachsegmentisassignedapassagenumberthatexpresses itswidthandeachshipisassignedatrafficgroupnumberthatexpressesitssize.Thepassagenumberofsidingsis12.Thepassage numberofverynarrowtransitsegmentsis6andforsomewhatwidertransitsegmentsitis8,seeFig.2.Thetrafficgroupnumbers ofshipsrangefrom1(small)to6(large).Theruleformanagingthetrafficisthatopposingshipscannotmeetinatransitsegmentif thesumoftheirtrafficgroupnumbersexceedsthepassagenumberofthesegment.Insuchacase,oneoftheshipshastowaitina sidingtolettheopposingshippassthrough.

Furthermore,theships’travelspeedsaregivenbyspeedlimitsvaryingwiththesizeoftheship.Thelargestshipsmusttravelat lowerspeedsthansmallerships.This,inturn,mayleadtosmallershipsqueuingupbehindlargershipsintransitsegmentsasships canonlyovertakeothershipsinsidingsduetosafetyreasons.

SchedulingshipsthroughtheKielCanalhaspreviouslybeenstudiedbyLübbeckeetal.(2019)andMeiselandFagerholt(2019), whichproposedifferentmathematicalformulationsandheuristicmethodsthatprovidesolutionswithinanacceptabletime.Ships thataregoingthroughthecanalannouncetheirarrivalafewhoursbeforetheirExpectedTimeofArrival(ETA).Allpreviousstudies consideredthisinformationtobegivenwithcertaintyandsolvedtheshipschedulingasadeterministicproblem.Incontrasttothe thesepreviousstudies,weconsiderthattheships’actualarrivaltimesaresubjecttouncertaintyand,especially,thatshipsareoften delayed.Thisisamajorpracticalchallengeintheplanningasitgivesfrequentneedofreplanningtokeeptheschedulesfeasible.

Frequentreschedulingistimeconsumingandforcestheplannerstousesimplerulesofthumb,whichmayyieldtravelplansthat arefarfromoptimalwiththeconsequenceoflongertraversaltimesthroughthecanalfortheships.Wehavenamedtheresulting schedulingproblemShipSchedulingontheKielCanalwithUncertainArrivalTimes(SSKC-UAT).

Ourcontributionsthroughthispaperareasfollows.WeintroducetheSSKC-UATandproposeamathematicalformulationfor theproblemtomitigatethenegativeeffectsoftheuncertainarrivaltimes.Thisformulationincorporatestime-corridors,sothata schedulewillstillbevalidaslongastheshipsarrivewithintheirgiventime-corridors.Inotherwords,thetime-corridorservesasa bufferthathedgesagainstdelayedarrivaltimesofshipsatthecanal.Ifpossible,thiscorridorispreservedthroughoutaship’scanal journeysuchthatashipwhoarrivesearlywithinitstime-corridorbenefitsintermsofanearlycanalexitingtime.However,planned waitingtimesofashipinasidingconsumethecorridorassuchwaitingobviouslydelaystheearliestpossiblecanalexitingtimeofa ship.Thepresentedmodeltakescareoftheseinterdependencies.Toensurefastsolutionstoreal-sizedinstancesoftheproblem,we adaptthewell-workingmatheuristicofMeiselandFagerholt(2019)toourproblem.Thematheuristichasbeentestedwithinarolling

horizonsimulationframeworktostudytheeffectofarrivaltimeuncertaintyandtoidentifysuitablewidthsofthetime-corridorsby experiment.Asimplemyopicheuristic,reflectingthecurrentschedulingpractice,isusedtogeneratebenchmarkresults.Testson realisticdatashowthatthematheuristicprovidessolutionswithsignificantlylessneedofreplanning,whileatthesametimekeeping thetotaltraversingtimesfortheshipsatanacceptablelevel.Wealsoprovidesimulationstogaininsightabouttheeffectontheships’

averagetraversingtimefromupgradingthenarrowtransitsegments.Itshouldbenotedthateventhoughthisstudyisforscheduling shipsthroughtheKielCanal,theproposedmodelandmatheuristiccanbeadaptedforotherwaterwaysorfortrafficsystemsthat facesimilarproblems.

Theoutlineofthispaperisasfollows.Section2reviews therelevantliterature,whileSection3givesadetaileddescription oftheSSKC-UATtogether withamathematicalformulationfortheproblem.Thematheuristicsis describedin Section4, while Section5presents asimulationframeworkforevaluatingschedules.Thecomputationalstudyis giveninSection6.Concluding remarksaredrawninSection7.

2. Literaturereview

A number of studies has investigated traffic management problems for waterways all around the world. In particular, Griffiths(1995)presentqueuingmodelsforbuildingconvoysofshipsthatgothroughtheSuezCanal,Ulusçuetal.(2009)give anoptimizationmodelforsequencingshipsthatpasstheStraitofIstanbul,Sluiman(2017)presentsmethodsforsequencingships attheStraitofIstanbultooaswellasattheSundaStrait,andLalla-Ruizetal.(2018)presentanoptimizationmodelandaheuristic forschedulingshipsattheYangtzeriverdelta.Furtherstudiesaddressshipschedulingforinlandwaterwayswithoutreferringtoa particularreal-worldcase,seee.g.Alfandarietal.(2019).Allthosestudiesthataddressaparticularreal-worldwaterwaytakeinto accountthespecificlayoutoftheconsideredwaterway.Anyhow,whatallthesewaterwayshaveincommonisthatashiphastogo throughonlyoneoratmosttwonarrowtransitsegments.Therefore,thedecisionmakingistypicallytofindasequenceinwhichthe shipsarrivingateithersideofsuchasegmentareallowedtotravelthroughthisbottleneck.Incontrast,theKielCanalconsistsof23 alternatingnarrowandwidesegmentswhereeachshipgoingthroughthecanalhastopassallofthesesegments.Forthisreason,the shipschedulingdecisionsofthedifferentsegmentsareinterdependentandrequireadvancedmethodsfortrafficmanagement.

The particularities of traffic management for the Kiel Canal have been investigated in a number of recent studies.

Lübbecke(2015)andLübbeckeetal.(2019)presentafundamentalmixed-integerprogramthatdescribesthecombinatoricsofthe shipschedulingdecisionsoverthevarioussegmentsofthecanal.Thismodelisbasedontheassumptionthatshipstravelattheir maximumallowedspeedatalltime.Thisimpliesthatthetimeittakesforashiptotraverseasegmentisagivenconstantandthat havingshipswaitinsidingsistheonlywaytoavoidconflictsbetweenships.Theauthorsproposealabelingalgorithmwhichcreates afeasiblesolutionbyiterativelyaddingtheshipsin agivenorder,basedontheestimatedtimeofarrival,withtheuseofwhat theauthorsrefertoascollision-freerouting.Alocalsearchisthenappliedtosearchforalternativeshipordersthatyieldimproved schedules.Wewanttonotethatthelabelingalgorithminthesepapersdeterminestimewindowswithinwhichashipcanentera segmentwithoutcausingconflictswithotherships.Thesetimewindowsaresimilartothetime-corridorsdeterminedinourpaper.

However,thetimewindowsinLübbecke(2015)andLübbeckeetal.(2019)aremerelyameansforfeasiblyinsertingashipintoa partialschedulewithinadeterministicproblemsetting.Theproactivedimensioningoftime-corridorsasisproposedinourpaperfor derivingrobustsolutionsunderuncertainshiparrivaltimesisnotconsideredthere.MeiselandFagerholt(2019)suggestextensions forthemixed-integerprogramandanalternativeheuristicsolutionmethod.Theextensionsenrich themodel(1)byconsidering thespeedofshipsasadecisionratherthanafixedparameter,(2)byrestrictingthewaitingtimesofshipsasaninstrumentfor improvedservicequality,and(3)byincludingcapacityconstraintsthatensurethatshipswaitinginasidingsegmentdonotexceed theavailablespaceofthissegment.Theproposedsolutionmethodisamatheuristic,whichfirstrelaxesallmodelconstraintsthatare responsibleforavoidingconflictsamongshipsand,then,iterativelyaddsviolatedconstraintstoobtainafeasiblesolution.Itisshown byexperimentthattheproposedmatheuristicsolvesrealisticallysizedinstanceswithinsecondsevenfortheextendedversionsofthe problem.Furthermore,thestudyofLuy(2011)investigatestheoperationsplanningofthelocksthatarelocatedatbothendsofthe KielCanal.Whilelockoperationsandtrafficmanagementareinterdependentand,thus,mightideallybeconsideredasanintegrated problem,thetwosub-problemsareintheresponsibilityoftwodistinctcanalauthorities,whichiswhytheyaretreatedindividually inthedifferentstreamsofresearch.

Trafficmanagementproblemssimilartotheschedulingofshipsinnarrowwaterwaysarefoundinrailscheduling,inparticular iftrainstravelinginthesameorinoppositedirectioncannotmeet(orovertake)insegmentsthathaveasingletrackonly,seethe surveysofCordeauetal.(1998)andLusbyetal.(2011).Trainschedulingproblemshavebeentreatedinadeterministicsetting inmany studieslike,forexample,Castilloetal.(2011),Gafarovetal.(2015),Yangetal.(2016), Lamorgeseetal.(2017)and Zhangetal.(2019).Anyhow,alargenumberofstudieson(singletrack)railschedulinghasalsoaddressedthisproblemfroma robustnessperspective.AnoverviewofmodelingapproachestorobusttraintimetablingisprovidedbyCacchianiandToth(2012). ArecentsurveyoftheliteratureinthisfieldisgivenbyLusbyetal.(2018).Theauthorsdistinguishdifferenttypesofproblems where’timetabling’isthefieldthatcomesclosetoourresearch.Therearemanyapproachesinthisfieldthatconsidertrain-related issueslike uncertaindwelltimesin stations,traveldelays frompassengerperspectives,etc,whicharenotrelevanthere.Papers thatcomeclosetothetrafficmanagementofshipsinacanalare,forexample,thesingletrackstudiesofMengandZhou(2011), Shafiaetal.(2012),andJovanović etal.(2017).MengandZhou(2011)determinearobustmeet-passplanfortrainsattheexample ofa138kmsingletrackroutethatconnects18stationsinChina.Inthisproblem,therunningtimeoftrainsalongthesegmentsis uncertainandsegmentscanhaveacapacitybreakdown.Theuncertaintyiscapturedinasetofscenariosandthegoalistofinda solutionthatminimizesexpectedscheduledeviationswithrespecttoaninitialplanningtablethatprescribesenteringandleaving

timesatsegmentsandminimumdwelltimesatstations.Shafiaetal.(2012)considerasingletrackcorridorthatconnectsthecities ofTehranandIsfahaninIran.Theyfocusondeterminingarobust,periodictimetablethatcanbeappliedrepetitivelyandabsorb delays.Theproblemismodelledasavariantofthejobshopschedulingproblemthatalsocapturesfeatureslikestationcapacityand headwaytimeconstraints.Jovanović etal.(2017)considerabusyrailcorridorinSweden.Theypresentaknapsackformulationthat purposefullydistributesanamountofbuffertimeinagiventimetablesuchastoimprovethereliabilityandon-timeperformanceof thetrains.Tothisend,thetrainsmaybegivendifferentprioritiestoreflecttheirneedforprotectionagainstuncertainevents.

Eventually,theseproblemssharesimilaritieswiththetrafficmanagementinartificialwaterways,buttheyalsodifferwithregard tocentralfeatures.Forexample,insingletrackrailsystemsopposingtrainscannevermeetonatrackwhereastheKielCanalallows thatopposingshipscanmeetinatransitsegmentundercertainconditionsthatmustbecarefullyreflectedinthecorresponding optimizationmodelsandsolutionmethods.Also,trainsmuststopatallstationsaccordingtotheirtimetablewhereasintheship trafficmanagementitneedstobedecidedpurposefullywhichshipstopswhereandforhowlongtoletopposingtrafficpassby.

Withregardtotheabovepapersonrobusttrainscheduling,wehavetostatethattheseapproachesdiffersubstantiallyintermsof theirscope,thenatureoftheuncertainparameters,thedecisionsmade,and/orthepursuedobjective.Moreprecisely,Mengand Zhou(2011)focusonschedulerecoveryafteramajorservicedisruptionthatcomesalongwithacapacitybreakdown ofarail tracksegment,whereasbreakdownsofsegmentsarenotasourceofdisruptionforthedailytrafficmanagementoftheKielCanal.

Shafiaetal.(2012)generateperiodicschedulesthatcanbeexecutedrepetitivelyasisappropriatefortimetabledtrainoperations butirrelevantforwaterwayswhereshiptrafficdoesnotfollowrepetitivepatterns.Furthermore,theyfocusonissuesthatareof particularrelevanceintrain operationssuchasanexplicitseparationoftraindeparturesfromasamestationtoavoid crowded platforms.Suchseparationsarenotneededandevenundesirablewhenschedulingshipsinacanal.Jovanović etal.(2017)facea tacticalproblemofinsertingbuffertimesintoagiventraintimetablesuchthattheoverallcycletimeofthetimetabledoesnotchange iftrainoperationsaredelayed.Incontrast,trafficmanagementattheKielCanalisanoperationalproblemthatisaboutoptimizing shipschedules(timetables)w.r.t.time-corridors(buffertimes)wheretheuncertaintyliesintheinitialarrivaltimeoftheshipsand theobjectiveistominimizethetotalcanalexitingtimeofallshipsinsteadofanoverallcycletime.Duetothesedifferences,robust trafficmanagementfortheKielCanalclearlyrequiresspecificmodelsandmethodsonitsown.

Ofcourse,therearealsostudiesonrobustnessissuesinshipoperationsmanagement.However,suchpaperstypicallyfocuson routingdecisionsfortheconsideredships(e.g.Norlundetal.,2015)butnotonmanagingshiptrafficwithinaparticularwaterway infrastructure.Forthisreasonandbecauseallshiptrafficmanagementpapersmentionedabovefocusondeterministicproblemstoo, ourstudy’scontributionistopresentafirstapproachtorobusttrafficmanagementforinlandwaterwaysliketheKielCanal.Inthis sense,ourpaperbelongstothestreamoftrafficmanagementresearch.

3. Problemdefinitionandmathematicalmodel

GeneralaspectsofschedulingontheKielCanalaredescribedinSection3.1,whiletheShipSchedulingproblemontheKielCanal withUncertainArrivalTimes(SSKC-UAT)ispresentedinSection3.2.ModelingassumptionsandnotationaregiveninSection3.3, beforewepresentthemathematicalmodelfortheSSKC-UATinSection3.4.

3.1. GeneralaspectsofschedulingshipsthroughtheKielCanal

TheKielCanalhasbidirectionaltraffic.IfashipentersthecanalontheKiel-sideitiswestboundandifashipentersinBrunsbüttel itiseastbound.Twoshipsthattravelintheoppositedirectionareopposing,whileshipstravelinginthesamedirectionarealigned.

Theshipsarecategorizedaccordingtotheirsize,andbasedonthistheyaregivenatrafficgroupnumberrangingfrom1to6, wheretrafficgroup6consistsofthelargestships.Themaximumallowedtravelingspeedinsidethecanaldependsonthetraffic groupnumber,andis15𝑘𝑚∕ℎfortrafficgroupnumbers1–5and12𝑘𝑚∕ℎfortrafficgroupnumber6.Weassumethatallshipsfollow thisspeedlimitwithinthecanal,exceptforwhentheyhavetowaitinthesidings.Thetraversingtimethroughagivensegmentisthe timeittakesfortheshiptopassthroughthatsegment.

Afeasiblescheduleneeds tokeepcertainsafetyrestrictions.Situationsthatmightviolatethese safetyrestrictionsarecalled conflicts.IntheKielCanal,therearetwotypesofconflicts.Thefirsttypeisaligningconflicts.Eachpairofalignedshipsmaypass eachotherinsidings,whileitisnotallowedforanyalignedshipstoovertakeeachotherintransits.Therefore,thereisapossible conflictbetweentwoalignedshipsineverytransit.Inordertoavoidsuchconflicts,theshipsneedtokeepaminimumsafetydistance throughthetransit.

Theothertypeofconflictisopposingconflicts.Twoopposingshipsmaymeeteachotherinasegmentonlyifthesumoftheirtraffic groupnumberislessthanorequaltothepassagenumberofthesegment.Therefore,shipswillalwaysbeabletomeetinsidingsas thesehaveapassagenumberof12,seeFig.2.Fortransitsegmentsontheotherhand,toolargeshipswillnotalwaysbeabletopass eachotherandaconflictarises,asdemonstratedinFig.3.Toavoidconflicts,oneoftheshipsmighthavetowaitinasidingsothat theothershiphastimetocompletethetransitsegmentbeforetheothershipenters.

Toensureasafepassageoftheshipsandcomplywiththesafetyregulations,itisnecessarytocalculateacertainsafetytimethat mustbekeptbetweentheenteringoftwoshipsatatransitsegment.Suchasafetytimemustbecalculatedbothforeachpairof opposingandalignedships.Detailsonhowtocalculatesafetytimesandonhowtoderivesetofshippairs_𝑠^𝐴and_𝑠^𝑂thatcouldhave analigningoropposingconflictinasegment𝑠ofthecanalaregiveninMeiselandFagerholt(2019).

Fig.3.Demonstrationoflegalshiptraffic.

Fig.4. a)Theonlyallowedpositionforship𝑗isthepositiontheshipiscurrentlyplacedin,sincethereisnocorridorintheschedule.Ifship𝑗is delayed,theschedulewillbecomeinfeasibleasthefollowingship𝑘hastoslowdownorovertakeship𝑗.b)Ship𝑗hasacorridorandisnowallowed tobeinallpositionsinsidethiscorridor.Thetwoextremepoints,theearliestandlatestallowedposition,aremarkedwiththetwogreyships.The increasedflexibilityintheschedulecomesatthecostofforcingship𝑘totravelfurtherbehindship𝑖.

3.2. ShipschedulingintheKielCanalwithuncertainarrivaltimes

InordertofacilitatethetrafficmanagementattheKielCanal,shipcaptainsareaskedtoannouncetheirExpectedTimeofArrival (ETA)atthecanalafewhoursinadvance.Clearly,the𝐸𝑇𝐴issubjecttoacertaindegreeofuncertaintyandshipsmayarrivelater thanexpectedwithinthecanal,forexamplebecauseofloweractualtravelingspeedduetoweatherconditions,heavyshiptrafficor queuingtimebeforeenteringthelocks.

Suchdelaysmightrenderplannedschedulesinfeasibleandforcethetrafficoperatorstorescheduletoobtainnewconflict-free travelschedules.Frequentreschedulingistimeconsumingfortheoperatorsandmightforcethemtouseeitherfastheuristicap- proachesorsimplerulesofthumb.Thismayyieldtravelplansthatarefarfromoptimalwiththeconsequenceoflongertraversal timesthroughthecanal.

IntheSSKC-UAT,weconsiderthisuncertaintyinarrivaltimesandtrytoreducetheamountofreschedulingwhileatthesame timekeepingthetotaltraversingtimeforallshipsthroughthecanalaslowaspossible.Theproblemthenconsistsofgeneratinga feasibletravelscheduleforallshipsthattosomeextenthedgesagainstarrivaltimedelays,whileminimizingthetotaltraversing timeforallships.Ourapproachtoachievethisisbyintroducingatime-corridorforeachship(i.e.,atimebuffer),whichmeansthat spaceistemporarilyreservedforthatshipinthecanalsegments.Aslongastheshipentersthecanalwithinitstime-corridorand stayswithinthiscorridorthroughoutitsjourney,thescheduledtravelplanwillremainfeasible.Ifforexample,itwasplannedthat ashipentersthecanalatan𝐸𝑇𝐴of10:30andisgivenatime-corridorof20minutes,theschedulewillbefeasibleandvalidaslong astheshipentersthecanalintheinterval[10:30,10:50].

Theuseoftime-corridorsisdemonstratedinFigs.4and5.InFig.4a,ship𝑗hasnocorridorandisforcedtoremainatitsrelative positionbetweenships𝑖and𝑘withoutanyflexibility.InFig.4b,ship𝑗receivedadistancecorridorwhichgivesmoreflexibilityof theactualshippositionin-betweenships𝑖and𝑘.Thisdistancecorridorcorrespondsdirectlytoatime-corridor.Abetterillustration oftime-corridorsisobtainedfromrepresentingtheshiptravelinginatime-spacediagramasisdoneinFig.5.Fig.5arepresentsthe situationwithouttime-corridorswhereallthreeshipsmoveatasamespeed(thatcorrespondstotheslopeofthearcs)throughthe depictedcanalsegments.Theseparationofthelinesrepresentstherequiredsafetydistancesbetweentheships.Fig.5brepresentsthe situationwhereship𝑗receivesatime-corridor.Here,theactualpositionoftheshipisnolongerrelevantbutthescheduleremains feasibleaslongastheshipstayswithinitscorridor.Inotherwords,thecorridorcancompensateforuncertainenteringtimesofthe ship.Thefigurealsoshowsthatship𝑘needstobepostponedinordertoprovideacorridorforship𝑗.

3.3. Modelingassumptionsandnotation

Whenmodelingthisproblem,some assumptionshavebeenmade. Firstly,itisassumedthateachshiptraversesthecanalat aconstantspeed(exceptforwhenwaitinginthesidings)equaltothemaximumspeedbasedontheship’strafficgroupnumber.

Fig.5.a)Thetime-spacerepresentationshowsthatship𝑗hastokeepitsrelativepositionin-betweenships𝑖and𝑘.Ifship𝑗isdelayed,theschedule willbecomeinfeasibleasthefollowingship𝑘hastoslowdownorovertakeship𝑗.b)Ship𝑗hasatime-corridorandisnowallowedtoenterthe segmentatanytimewithinthecorridorwithoutmakingthescheduleinfeasible.Theincreasedflexibilityintheschedulecomesatthecostofforcing ship𝑘totravelfurtherbehindship𝑖thanwithouttime-corridors.

Furthermore,extratraversingtimeduetoaccelerationordecelerationisneglectedwhichmeansthattraveltimespersegmentare deterministicandcanbecalculatedaspartofthepre-processing.Secondly,capacitylimitsinthesidingsarenotconsideredhereas experimentsinMeiselandFagerholt(2019)showedthattheselimitsarehardlybindinginanysolutiontothetrafficmanagement problem.Lastly,weassumethatallshipstravelthroughtheentirecanal.

ThenotationthatweuseinthemathematicalformulationfortheSSKC-UATispresentedandexplainedinthefollowing.

Sets

:Setofsidings

 :Setoftransitsegments

=∪ :Setofallsegments,bothsidingsandtransitsegments

:Setofships

^𝐸 :Setofeastboundships,i.e.shipsthatenterthecanalinwestmostsegment0(Brunsbüttel)andexitthroughtheeastmost segment𝑠=22(Kiel),seeFig.2

^𝑊 :Setofwestboundships,i.e.shipsthatenterthecanalineastmostsegment𝑠=22andexitthroughthewestmostsegment0

^𝐴_𝑠 :Setofallpossiblealigningconflictsonsegment𝑠,givenasasetofpairsofships

^𝑂_𝑠 :Setofallpossibleopposingconflictsonsegment𝑠,givenasasetofpairsofships Parameters

𝑇𝐶_𝑖:Initialtime-corridorwidthgiventoship𝑖

𝐸𝑇𝐴_𝑖:Estimatedtimeofarrivalatfirstcanalsegmentforship𝑖 Δ_{𝑖,𝑗,𝑠}:Safetytimebetweenship𝑖and𝑗insegment𝑠

𝐷_𝑖,𝑠:Traversingtimeforship𝑖insegment𝑠 𝑀:Big𝑀-parameter

DecisionVariables

𝑧_{𝑖,𝑗,𝑠}:Binaryvariablethattakesvalue1ifship𝑖enterssegment𝑠beforeship𝑗,0otherwise 𝑤_𝑖,𝑠:Thewaitingtimeforship𝑖insidingsegment𝑠

𝑡𝑖,𝑠:Plannedenteringtimeforship𝑖intosegment𝑠 𝑡_𝑖,𝑠:Latestenteringtimeforship𝑖intosegment𝑠

3.4. Mathematicalmodel

Themodelaimsatmakingaschedulethatcantosomeextentwithstanddelaysinarrivaltimesbyintroducingtime-corridors.We takeupandextendthebasemodelformulationofMeiselandFagerholt(2019),whichassumedadeterministicsettingwithoutaneed tomitigateagainstuncertaintyinthearrivaltimes.ModelextensionsthatwereinvestigatedinMeiselandFagerholt(2019)like,for example,consideringshipspeedasadecisionvariable,arenotincludedhereforreasonsofbrevity.Thetime-corridorofashipis definedtobethedifferencebetweenaplannedenteringtimeandalatestenteringtimeateachsegmentandisusedtoretainspace temporarilyinthecanal,creatingafreepathfortheshipaslongasitstayswithinthegiventime-corridors.Initially,atthebeginof thecanaljourney,theETAdefinestheearliesttimeinthecorridor.Thelatestallowedenteringtimefollowsfromapresetcorridor width𝑇𝐶_𝑖thatisaddedtotheearliesttime.

Themodelusesthefollowingdecisionvariables:Thebinaryvariable𝑧_{𝑖,𝑗,𝑠}decideswhichoftwoconflictingships(𝑖,𝑗)∈_𝑠^𝐴∪_𝑠^𝑂 getstoentersegment𝑠first,where𝑧_{𝑖,𝑗,𝑠}=1ifship𝑖entersbeforeship𝑗intosegment𝑠and𝑧_{𝑖,𝑗,𝑠}=0ifship𝑗entersbeforeship𝑖into segment𝑠.Variable𝑤_𝑖,𝑠denotesthewaitingtimeforship𝑖insidingsegment𝑠.Theplannedenteringtimeforship𝑖intosegment𝑠is denotedby𝑡_𝑖,𝑠whereas𝑡_𝑖,𝑠denotesthelatestenteringtimeforship𝑖intothissegment.𝑡_𝑖,𝑠and𝑡_𝑖,𝑠spanthetime-corridorforship𝑖in segment𝑠,meaningthatthescheduleremainsfeasibleaslongastheshipentersthesegmentwithinthistimespan.Theoptimization modelisthenformulatedasfollows.

min𝑇𝑇𝑇= ∑

𝑖 𝜖^𝐸

(𝑡_𝑖,𝑠+𝐷_𝑖,𝑠−𝑡_𝑖,0)+ ∑

𝑖 𝜖^𝑊

(𝑡_𝑖,0+𝐷_𝑖,0−𝑡_𝑖,𝑠) (1)

Theobjectivefunction(1)minimizesthetotaltransittime(𝑇𝑇𝑇)fortheshipsthattraversethecanal.Theexitingtimeforashipis whentheshipleavesthelastsegment,whichis𝑡_𝑖,𝑠+𝐷_𝑖,𝑠foreastboundships,whileitis𝑡_𝑖,0+𝐷_𝑖,0forwestboundships.

𝑡_𝑖,𝑠+𝐷_𝑖,𝑠=𝑡_𝑖,𝑠+1 𝑖∈^𝐸,𝑠∈ (2)

𝑡_𝑖,𝑠+𝐷_𝑖,𝑠=𝑡_𝑖,𝑠−1 𝑖∈^𝑊,𝑠∈ (3)

𝑡_𝑖,𝑠+𝐷_𝑖,𝑠+𝑤_𝑖,𝑠=𝑡_𝑖,𝑠+1 𝑖∈^𝐸,𝑠∈∖{ 𝑠}

(4)

𝑡_𝑖,𝑠+𝐷_𝑖,𝑠+𝑤_𝑖,𝑠=𝑡_𝑖,𝑠−1 𝑖∈^𝑊,𝑠∈∖{0} (5)

Constraints(2)-(5)handletheflowoftheships.Constraints(2)settheplannedenteringtimeatthesubsequentsegmentforeach eastboundship andfor eachtransit segment.Constraints(3)dothesamefor westboundships.Constraints(4)andConstraints (5)handletheflowforthesidingsforeastboundandwestboundships,respectively.Notethatwaitingisallowedonlyinsidings.

𝑡_𝑖,0=𝐸𝑇𝐴_𝑖 𝑖∈^𝐸 (6)

𝑡𝑖,𝑠=𝐸𝑇𝐴𝑖 𝑖∈^𝑊 (7)

𝑡𝑖,0=𝐸𝑇𝐴𝑖+𝑇𝐶𝑖 𝑖∈^𝐸 (8)

𝑡𝑖,𝑠=𝐸𝑇𝐴𝑖+𝑇𝐶𝑖 𝑖∈^𝑊 (9)

𝑡𝑖,𝑠−𝑡𝑖,𝑠≥𝑡𝑖,𝑠+1−𝑡𝑖,𝑠+1 𝑖∈^𝐸,𝑠∈∖{ 𝑠}

(10)

𝑡𝑖,𝑠−𝑡𝑖,𝑠≥𝑡𝑖,𝑠−1−𝑡𝑖,𝑠−1 𝑖∈^𝑊,𝑠∈∖{0} (11)

Constraints(6)and(7)settheplannedcanalenteringtimes,foreastboundandwestboundships,respectively,equaltoaship’s estimatedtimeofarrival.Foreastboundshipsthiswillbetheenteringtimeatsegment0whileforwestbounditwillbeatsegment 𝑠.Thelatestenteringtimeissettobetheestimatedarrivaltime𝐸𝑇𝐴_𝑖plusthetime-corridor𝑇𝐶_𝑖giventotheship,asstatedin Constraints(8)and(9).Theseconstraintsestablishtheinitialwidthofeachship’stime-corridor.Asashiptravelsthroughthecanal, itsgiventime-corridormaybeconsumedifithastowaitforanothership.Thisisbecausethetime-corridorisabufferthatcatches upvariationsofshiparrivaltimeswhenenteringthecanal.Ifashipactuallyarrivesatits𝐸𝑇𝐴_𝑖,itcanfollowthetime-corridorat theearliestsegmententeringtimes𝑡_𝑖,𝑠whereasifitjustarrivesatthetime𝐸𝑇𝐴_𝑖+𝑇𝐶_𝑖itcanfollowthetime-corridoratthelatest enteringtimes𝑡_𝑖,𝑠.However,ifashipentersthecanalalreadyat𝐸𝑇𝐴_𝑖butthenhasaplannedwaitingatsomesegmentwithinthe canal,theearliestenteringtimes𝑡_𝑖,𝑠atsubsequentsegmentsareobviouslypostponedbythewaitingtime.Thiseffectsthatthecorridor shrinksaccordingtotheplannedwaitingtime.Then,ifthewaitingatsomesegmentcompletelyconsumedthetimecorridorofaship, thisshiphastofollowapathwithoutatime-corridor(asshowninFig.5a)fortherestofthecanaljourney.Afurtherexplanation oftime-corridorconsumptionisprovidedbelowattheexampleofFig.6.Eventually,thetime-corridoratasubsequentsegmentisat mostaslargeasthetime-corridoratthecurrentsegment,seeConstraints(10)and(11).

𝑡_𝑖,𝑠≤𝑡_𝑖,𝑠 𝑖∈,𝑠∈ (12)

𝑡_𝑖,𝑠+𝐷_𝑖,𝑠≤𝑡_𝑖,𝑠+1 𝑖∈^𝐸,𝑠∈∖{ 𝑠}

(13)

𝑡_𝑖,𝑠+𝐷_𝑖,𝑠≤𝑡_𝑖,𝑠−1 𝑖∈^𝑊,𝑠∈∖{0} (14)

Thetime-corridorshrinksbytheamount oftimetheshiphastowait. Iftheentiretime-corridor isconsumed,theshipwillno longerhaveacorridor.Instead,itwillhaveastricttravelschedulesimilartoasinadeterministicplanningenvironment,suchasin Lübbeckeetal.(2019)andMeiselandFagerholt(2019).Clearly,asthetime-corridorcannotbecomenegative,Constraints(12)ensure thatthelatestenteringtimeisboundedbytheplannedenteringtime.Constraints(13)and(14)thenpropagatethelatestentering timefromasiding𝑠tothenextsegment.

Fig.6. Anexampleoftheconsumptionoftime-corridors.

Fig.6showsanexampleofhowwaitingaffectsthetime-corridor.Therearethreeeastboundships𝑖,𝑗 and𝑘aswellasone westboundship𝑙.Initially,allfourshipshavetime-corridorsof20minuteseach.Inthedepictedsolution,thewestboundship𝑙has togiveprioritytoallthreeeastboundships.Forthisreason,ithastowaitineachofthesidings𝑠+5,𝑠+3,and𝑠+1.Insiding 𝑠+5,ithastowaituntilship𝑖’scorridorhasfullyleftthetransitsegment𝑠+4.Thisshrinks𝑙’stime-corridorbyabout7minutes.

Insiding𝑠+3,ithastowaituntilship𝑗’scorridorhasfullyleftthetransitsegment𝑠+2.Thiswaitingfullyconsumes𝑙’sremaining time-corridor,whichisthenofwidth0.Eventually,insiding𝑠+1,ship𝑙hastowaituntilship𝑘’scorridorhasfullyleftthetransit segment𝑠.Here,thetime-corridorof𝑙isnomoreconsumable,whichiswhythe0-widthcorridorisnowshiftedalongthetimeaxis, asishandledbyConstraints(12)to(14).Thedepictedsolutionremainscompletelyfeasibleaslongasallfourshipsarrivewithin theirrespectivetime-corridors.

𝑡𝑖,𝑠+𝐷𝑖,𝑠=𝑡𝑖,𝑠+1 𝑖∈^𝐸,𝑠∈ (15)

𝑡𝑖,𝑠+𝐷𝑖,𝑠=𝑡𝑖,𝑠−1 𝑖∈^𝑊,𝑠∈ (16)

Sinceashipcannotwaitinsideatransitsegment,thetime-corridordoesnotshrinkwhentravelingfromatransittoasiding.Thisis takencareofbyConstraints(15)and(16).

𝑡_𝑖,𝑠+Δ_{𝑖,𝑗,𝑠}≤𝑡_𝑗,𝑠+𝑀⋅(1−𝑧_{𝑖,𝑗,𝑠}) 𝑠∈,(𝑖,𝑗)∈_𝑠^𝐴 ∪ ^𝑂_𝑠 (17)

𝑡_𝑗,𝑠+Δ_{𝑗,𝑖,𝑠}≤𝑡_𝑖,𝑠+𝑀⋅𝑧_{𝑖,𝑗,𝑠} 𝑠∈,(𝑖,𝑗)∈_𝑠^𝐴 ∪_𝑠^𝑂 (18)

Constraints(17)and(18)aretheprecedenceconstraintsandareonlydefinedforthetransitsegmentsastravelinginsidingsdoes notraiseconflicts.Ifship𝑖enterssegment𝑠beforeship𝑗,i.e.𝑧_{𝑖,𝑗,𝑠}=1,Constraints(17)forcetheenteringtimeforship𝑗tobelater thanthelatestenteringtimeofship𝑖(i.e.theendof𝑖’stime-corridor)plusthesafetytimethathastoelapsetomakesurethatships 𝑖and𝑗cansafelytraversethesegment.Ifship𝑗getspriorityovership𝑖,Constraints(18)ensurethatship𝑗entersfirst.

𝑡_𝑖,𝑠,𝑡_𝑖,𝑠≥0 𝑖∈,𝑠∈ (19)

𝑤_𝑖,𝑠≥0 𝑖∈,𝑠∈ (20)

𝑧_{𝑖,𝑗,𝑠}𝜖{0,1} 𝑠∈,(𝑖,𝑗)∈_𝑠^𝐴 ∪ ^𝑂_𝑠 (21)

Constraints(19)and(20)arethenon-negativeconstraintsforthedecisionvariables.Constraints(21)settheprecedencevariablesto bebinary.

4. Iterativeconflict-Addingmatheuristic

Themixedintegerprogramming(MIP)modelprovidedinSection3.4ishardtosolveduetothelargenumberofbinaryz-variables andConstraints(17)and(18),whichareneededtoresolveallpotentialconflicts.Thesizeoftheproblemincreasesstronglywithan increaseinthenumberofshipsanditalsobecomeshardertosolvewithincreasedwidthoftime-corridors.Asaresultofthis,aMIP- solvercanonlysolvesmallprobleminstances.Wethereforeproposeamatheuristic,whichwedenoteastheIterativeConflict-Adding Matheuristic(ICAM)forsolvingtheSSKC-UAT.

ThebasicframeworkofICAMistakenfromMeiselandFagerholt(2019).WepresentthisinAlgorithm1 tomakethepaper

Input:Aprobleminstance

1.Initialization:_𝑠^𝑂←∅and_𝑠^𝐴←∅forallsegments𝑠 2.SolvetheoptimizationmodelusingastandardMIP-solver.

3.IdentifythesetofConflictsFoundinthecurrentsolutionusingAlgorithm2.

4.whileConflictsFound≠∅do

5.FirstConflicts←uptothe𝜈firstconflictsinConflictsFound 6.foralltheconflictsfc∈FirstConflictsdo

7.iffcisaconflictofopposedshipsonsegment𝑠then 8._𝑠^𝑂←^𝑂_𝑠 ∪ 𝑓𝑐

end

9.iffcisaconflictofalignedshipsonsegment𝑠then 10._𝑠^𝐴←_𝑠^𝐴∪ 𝑓𝑐

end end

11.Fixfeasiblepartofcurrentsolutionuptotheearliestconflict𝜏. 12.SolvetheoptimizationmodelusingastandardMIPsolver.

13.IdentifythesetofConflictsFoundinthecurrentsolutionusingAlgorithm2.

end

returnTheobtainedsolutionwhichisafeasibletravelplanforallships.

Algorithm1:TheIterativeConflict-AddingMatheuristic(ICAM).

self-contained.Wewanttonotethatthewidthoftime-corridorsisgivenasaninputparametertotheheuristic(andrespectedwhen solvingtheembeddedoptimizationmodel).Aplannercanreruntheheuristicforseveraldifferentwidthstoidentifytheonethat bestsuitsthearrivaltimeuncertaintyhe/sheisfacedwith.Weillustratethislaterinourcomputationalexperiments.Byintroducing time-corridors,thecomplexityofthealgorithmincreasessincetheexactpositionofeachshipisnolongerfullyknown.Thisrequires amoredetailedconflictdetectionthroughAlgorithm2,whichislaterexplained.TheideabehindICAMistofirstsolvetheproblem

Input:Currentsolution ConflictsFound←∅

forallthepairsofshipsiandjdo forallthetransitsegmentsdo

ifprecedenceconstraints(17)and(18)areviolatedthen ifshipsiandjarealigningthen

iftherealreadyisaconflictbetweenships𝑖and𝑗then checktimeofconflictsandkeepearliestone end

else

addconflicttoConflictsFound end

end

ifshipsiandjareopposingthen addconflicttoConflictsFound end

end end end

returnConflictsFound

Algorithm2:Conflictdetectionprocedure.

withemptysets^𝐴_𝑠 and_𝑠^𝑂ofalignedandopposingconflicts,asdescribedinstep2inAlgorithm1.Withoutprecedenceconstraints, theproblemsolvesquicklywithacommercialsolverasitisacontinuouslinearprogramonly.Allconflictsthatmakethesolution

Fig.7. a)Whentheformulationincludestime-corridors,theshipcanbeineitherthedarkorthelightsegmentattime75.b)Inaformulation withouttime-corridors,asusedinMeiselandFagerholt(2019),theshipcanonlybeinthelightsegmentattime75.

infeasiblearethenidentifiedandsortedinchronologicalorder.Asshowninsteps3to10inAlgorithm1,theconflictsetcalled ConflictsFoundcontainsallconflictsfoundinthecurrentsolution.Adefinednumberofconflictsarestoredtemporarilyintheset firstConflictsandtheseareaddedtoeitherthealigningortheopposingconflictssets_𝑠^𝐴and_𝑠^𝑂ofthecorrespondingsegment𝑠.The scheduleisthenfixeduptothetimeofthefirstnewconflict,whichisdenotedby𝜏.Thismeansthatsomeshipscannothaveparts oftheirschedulechangedinlateriterations,whichwillhelpreducethecomplexityoftheMIP-problemsolvedineachiteration.The problemisthenresolvedwiththeupdatedsetsofalignedandopposingconflictsandfixationofallships’schedulesuptotime𝜏.

MultiplePossibleShipPositions

Whenallshipsaregivenaninitialtime-corridor,itisnotclearinwhichparticularsegmentashipsisatagiventime.InFig.7a), thetwoblacklinesrepresenttheupperandlowerboundaryforaship’sposition.Theshiphasatime-corridoroftentimeminutes,i.e.

thelowerlineistentimeunitsbelowtheupperline.Asseenbythedottedhorizontalline,whichreferstopointintime75,theship canbeinoneoutoftwodifferentsegments.Itcanbeinthetransitsegment𝑠−1orinthesidingsegment𝑠.Thisisdifferentfrom thesituationinMeiselandFagerholt(2019),whereashiptravelsalonganexactlydefinedpathwhereitisinexactlyonesegmentat agiventime,seetheexampleinFig.7b).

Whenthewidthofaship’stime-corridorincreases,thenumberofpossiblelocationsforthisshipmayincreaseaswell.Thisresults inlargerconflictsetsandmorebinaryprecedencevariablestoresolveallpotentialconflicts.

HowconflictsaredetectedineachiterationintheICAMwithtime-corridorsfortheshipsisoutlinedinAlgorithm2.Sinceeach shipmayhaveatime-corridorinourproblem,boththeearliestandlatestplannedtimeareusedtoidentifyconflicts.Eachpairof ships𝑖and𝑗ischeckedtoseeifthereisaconflictbetweenthem.Thisisdoneonalltransitsegmentsbycheckingwhichshipenters thesegmentfirst,andtheprecedencevariables𝑧𝑖,𝑗,𝑠and𝑧𝑗,𝑖,𝑠arethentemporarilysetaccordingtothis.Furthermore,theprecedence constraints(17)and(18)arethenexaminedtoidentifypossibleconstraintviolations.Ifaconstrainthasbeenviolated,thereisa conflict,andthedirectionsoftheshipsareusedtodetermineiftheconflictisaligningoropposing.

BeforetheconflictisaddedtothesetConflictsFound,itischeckedifthesametwoshipshaveanotherconflictonanothersegment.

Inthiscase,onlytheconflictthatoccursfirstisadded.Thereasonforthisisthatiftwoaligningshipshaveaconflictonasegment (astheymovetooclosetoeachother),theywillmostlikelyhaveconflictsonallthefollowingsegmentstoo.

TheconflictdetectionalgorithmusedbyMeiselandFagerholt(2019)detectsconflictsbyrunningthroughtheships’positions atcertaintimeincrements.Sincetheshipscanbeinmultiplepossiblepositionswhenapplyingtime-corridorscheduling,thesame detectionalgorithmwasnotsuitableforourcase.ThemaindifferencebetweenMeiselandFagerholt(2019)andtheoneproposedin thispaperisthatMeiselandFagerholt(2019)’sdetectionalgorithmrunschronologicallythroughtheconflictsandstopswhenithas foundthepredefinednumberofconflicts,𝜈.Incomparisonouralgorithmfirstfindsallconflictsbeforesortingtheminachronological orderandreturnsthefirst𝜈conflicts.

MechanismsforSpeedinguptheSolutionProcess

MeiselandFagerholt(2019)haveproposedthreemechanismsforspeedingupthesolutionprocess,whicharealsoemployedin ourversionofthealgorithm.Oneapproachistoaddonlyapredefinednumberofconflictsineachiterationinsteadofalltheconflicts thataredetected.Parameter𝜈inStep5ofAlgorithm1controlshowfaraheadintimeconflictsshouldbeadded.Assuch,itcontrols thesizeandcomplexityoftheMIP-problemthatissolvedperiteration.Here,low𝜈-valuesresultinsmallMIP-subproblemstosolve butitmayrequirealargernumberofiterationstosolvetheproblemcompletely.Largervaluesof𝜈createlargersubproblemsbut requirelessiterations.Furthermore,𝜈affectstheoverallsolutionquality.Itisthereforeessentialtochooseitappropriatelytoobtain bothlowtotalsolutiontimeandsatisfactorysolutiongaps.

Fig.8. Flowchartforthesimulationframeworkwhereshiparrivaltimesareuncertain.

AnotherwaytoreducethesolutiontimeoftheICAMistofixthescheduleuptothetimeoftheearliestconflict,seeStep11of Algorithm1.Theconflicttimeisdenoted𝜏anddeterminedwhentheconflictsofthecurrentsolutionareidentified.Thetimeisset tobethetimeoftheearliestenteringtimeofthesegmentwheretheconflictoccursforthetwoships.Asweintroducetime-corridors intotheproblem,wefixinourversionofthealgorithmbothenteringtimes,theearliest𝑡𝑖,𝑠andthelatest𝑡𝑖,𝑠thatareearlierthan𝜏 foranyship𝑖andsegment𝑠.Byfixingthepartofthesolutionuptotheearliestconflict,theruntimeperiterationwillstayalmost constant,sincepreviousbinaryprecedencevariableshavealreadybeenfixed.

Finally,whensolvingtheMIP-modelinStep12ofAlgorithm1,onecanprescribeamaximumruntimeasitisnotmandatoryto solvethesubproblemstooptimalitywithinaheuristicframework.

5. Simulationframework

TheSSKC-UATisinSection3.4formulatedasastaticoptimizationproblem.However,inpracticeitisdynamicandmustbesolved overandoveragainasnewinformation(e.g.aboutdelaysleadingtoconflicts)appearsoverthecourseoftime.Therefore,wewant totesthowtheICAMheuristicworkswithinarollinghorizonsimulationframeworktostudytheeffectofarrivaltimeuncertainty.

Thissectiondescribesthesimulationframeworkinwhichthistestingisdone.

ThecurrentpracticeatthecanalisthatshipcaptainsareaskedtocallintheirestimatedETAsometimepriortothearrivalatthe canal.AtypicalannouncementleadtimeoftheETAsisaroundtwohoursaheadofthearrival.Thistimeisdenotedthenoticeperiod. Forexample,ifthenoticeperiodisexactlytwohours,ashipwithan𝐸𝑇𝐴of17:23becomesknowntothecanaloperatorsattime 15:23and,therefore,thisshipwillbepartofanyplanningthatisconductedatthistimeorlater.

Thereareseveraldifferentaspectsthatmustbeconsideredinordertocreateasimulationprocessthatrealisticallyresemblesthe real-lifeschedulingonthecanal.AflowchartforthesimulationprocesscanbefoundinFig.8.Therearefourdifferenteventsthat canoccur,numberedfrom1to4inFig.8.Someoftheseeventleadtoarescheduling,i.e.thatarevisedscheduleisobtainedfrom solvingtheSSKC-UATforallshipsknownatthecurrenttimewiththemostup-to-dateinformationavailable.

ReferringtoFig.8,ifashiparrivesonitsETA,theeventwillbeoftype1.IftheshiparriveslaterthanETAbutstillwithinits time-corridor,theeventwillbeoftype2.Neitheroftheseeventtyperequiresareschedulingiftheshipisalreadyincludedinthe currentsolutionasthisplanremainsthenfeasibleinbothcases.Anyhow,distinguishingbotheventtypeshelpstoanalyzethevalue oftime-corridors.Moreprecisely,shipsthattriggerevent1wouldbefeasibleonlyinadeterministicplanningwhereasshipsthat triggerevent2wouldmakeanon-robustsolutioninfeasible.Itisthereforetheintroductionoftimecorridorsthatkeepsthesolution feasibleinthesesituations.

Anyhow,ifashipisdelayedevenbeyonditstime-corridor,therewillbetwoeventsoftype3and4.First,whenadelayedship hasnotarrivedattheendofitstime-corridor,anevent3istriggeredatthattime(i.e.,ETAplusthelengthofthetime-corridor).The shipwillthenberemovedfromthecurrentsolutionandarescheduleisinitiatedtore-optimizetheroutesoftheotherships.When thedelayedshipfinallyarrives,aneventoftype4willinitiateareschedulingtoinsertthisshipintothesolution.

Forconductingthesimulationstudies,wegeneratedshipdataasfollows.Wehaveusedadiscretedistributionforassigningtraffic groupnumberstoeacharrivingship.Basedonhistoricaldata,wehavesettheprobabilitiesto0.005,0.03,0.495,0.25,0.21,and 0.01forships’trafficgroupnumbers1,2,3,4,5,and6,respectively.TheETAisassumedtobethetimewhentheshipisexpectedto enteritsfirstsegmentofthecanal,i.e.aftertheshiphaspassedthroughthelock.Fromanalysingreal-worlddatathatwasprovided bythecanalauthority,itwasfoundthatthearrivaltimesoftwoconsecutiveshipsarenotindependent.Thisiscausedbyhowthe

Table1

TheresultsoftheICAMcomparedtotheresultsobtainedwiththeXpressMIP-solverunderatimelimitof600seconds.Eachrowinthetable isbasedontheaverageoftentestinstances.

Xpress ICAM

# of ships in

instance 𝑇 𝐶[ 𝑚𝑖𝑛 ] Avg objective

[ 𝑚𝑖𝑛 ] # of optimal

solutions Avg gap [%] Solution

time [ 𝑠𝑒𝑐] Avgchange [%] Avg gap [%] Solution time [ 𝑠𝑒𝑐]

20 0 8257.91 9 0.15 85.60 0.16 0.31 2.26

10 8412.19 9 0.21 142.42 0.19 0.40 3.07

25 8663.10 8 0.40 239.17 0.27 0.67 3.40

Average 8444.40 8.7 0.25 155.73 0.21 0.46 2.91

30 0 12342.52 7 0.19 266.32 0.19 0.38 3.89

10 12606.40 2 0.99 519.39 0.09 1.07 5.13

25 13008.58 0 1.95 600.00 0.55 2.49 6.76

Average 12652.50 3.0 1.04 461.90 0.28 1.31 5.26

40 0 17064.40 0 3.61 600.00 -0.78 2.85 35.51

10 17588.75 0 5.32 600.00 -1.70 3.68 33.96

25 18319.81 0 7.08 600.00 -2.24 4.95 37.53

Average 17657.65 0.0 5.34 600.00 -1.57 3.83 35.66

locksareoperated,morespecificallythatseveralshipsareallowedthroughthelockssimultaneously.Agroupofshipsthatenters intothefirstcanalsegmentataroundthesametimeisreferredtoasabatch.

Weuseexponentialprobabilitydistributionstocreatetheinter-arrivaltimesbetweentwoconsecutiveshipsinsideabatch,aswell asthetimebetweentwobatches.Thedistributionsarechosensoastogivearealisticarrivalpatternandayearlytrafficofaround 30000ships.Basedonthereceivedhistoricaldata,thetrafficflowinbothdirectionsaccountsforapproximately50%eachwithan almostconstantflowofshipsinbothdirections.However,sincetheshipsarriveinbatches,itisnotpossibletorandomlydrawa directionforeachship,asthiswillnotguaranteerealisticbatchbehavior.Wethereforedrawthedirectionsofthebatchesinstead oftheindividualships.Wehavealsolookedatthehistoricaldatatocreaterealisticdistributionsonthebatchsize,whichcanvary from1to4ships.

Sincethecanaloperatorsdidnotprovidedataonshipdelays,wehaveusedestimatesforthesimulationstudy.Wehaveassumed thatthearrivaltimedelaysareindependentandidenticallydistributedamongtheships.Thepercentageofshipsthatenterthecanal punctuallyattheirETAisdenoted𝛼,whereas1-𝛼percentoftheshipsaredelayed.Thelengthsofthesedelaysaredrawnfroman exponentialdistributionwithanexpectedvalueof𝑑minutes.Thevaluesofparameters𝛼and𝑑arelatervariedinourexperimental study.

6. Computationalstudy

Thecomputationalstudyisdividedintotwoparts.InSection6.1,wesettheparametersoftheICAMmatheuristicandcompareits performancetousingthecommercialMIP-solverFICOXpressforsolvingthemodelinSection3.4directly.Afterwards,inSection6.2, thesimulationframeworkisusedtotesttheeffectofintroducingtime-corridorsinastochasticenvironment.Theobjectiveistostudy howtime-corridorsaffectthetotaltraversingtimeoftheshipsandhowmanyreschedulesneedtobeperformedduringtheplanning periods,i.e.thenumberoftimestheSSKC-UATneedstoberesolvedasascheduleturnedinfeasible.Wealsostudytheimportance ofthelengthofthenoticeperiod,i.e.,howearlyinadvancetheshipscallintheirETAs,andtheeffectofextendingcertaincanal segmentsonthetraversingtimesoftheships.

AllsimulationsareconductedonLenovoM5 computerswith3.4GHzprocessorsand512 Gbofmemory. TheBCL-libraries developedbyFICO XpresshavebeenusedtoimplementtheICAMthroughC++.Fortheheuristic,wesetthemaximumruntime periterationtobe5secondsandthenumberofconflictsaddedperiterationto𝜈=20.Theseparametersweredeterminedinapretest liketheoneconductedinMeiselandFagerholt(2019).

6.1. Evaluationoftheiterativeconflict-Addingmatheuristic(ICAM)

WenexttesthowwelltheICAMperformsandthecommercialMIP-solverperformfortestinstancesofdifferentsizeanddifferent initialtime-corridorwidthsfortheships.Tentestcaseswith20,30and40shipsweregeneratedbasedonrealhistoricaldata.Asthe yearlytrafficthroughtheKielcanalisabout30000shipsandeachshipspendsabout8hoursinthecanal,anaverageof27shipsis inthecanalatatime.Therefore,testcaseswith30shipsrepresentanaveragetrafficdensitywhereasinstanceswith20shipsare lowtrafficdensityand40shipsrepresentbusytrafficsituations.Weconsidertheinitialtime-corridorwidths𝑇𝐶of0(i.e.,thereare notime-corridors),10and25minutespership,resultinginatotalof90testinstances.Thetestdataisprovidedtootherresearchers uponrequest.

TheresultsaresummarizedinTable1,whereeachrowrepresentsaverageresultsoverteninstancesofsamesizeandcorridor width.FortheMIP-solver,theaverageobjectivevalue,thenumberofinstancessolvedtooptimality,theaveragegap,andtheaverage solutiontimeareshown.Thegapisdefinedastherelativedifferencebetweenthebestsolutionandthebestbound,wheretheXpress solverisgivenaruntimeof600secondsperinstance.FortheICAMmatheuristic,column’Avgchange’iscalculatedastherelative

differencebetweenthesolutionfoundbyICAMandtheXpressobjectivevalue(negativenumbersmeansthattheheuristicsolution isbetter),whilecolumn’Avggap’givestherelativedifferencebetweentheICAMsolutionandthebestboundobtainedfromthe MIP-solver.Inadditiontoconductingthesetestswitharuntimeof600seconds,werantwotestinstanceswith40shipseachand time-corridorsof25minutes,withtheexactsolutionmethod(XpressMIP-solver)foratotalof18hours.Thegapsforthesetwo instanceswerereducedfrom9.95%and4.41%after600secondsto6.19%and2.89%after18hours,respectively.Asthereduction ofgapsaftertheextremelongruntimeisveryminorandmostlyduetoimprovementsoflowerboundsratherthanimprovementsof theobjectivefunction,itseemsreasonabletoconductthecomparisonsoftheICAMandtheexactsolutionmethodata600seconds runtime.Itcanalsobementionedthatsincethisisanoperationalplanningproblemthathastobesolvedeverytimeanewshipis approachingthecanal,600secondscanbeconsideredasapracticalupperlimitonthemaximumallowedsolutiontime.

AsshowninTable1,theoverallperformanceoftheICAMisverygood.Fortheinstanceswith20and30ships,thematheuristic givessolutionsthatarejustslightlyworsethantheonesobtainedbytheMIP-formulationwhereas forthecaseswith40ships, ICAMperformssignificantlybetterthanMIP-SolverXpress.Regardingtheroleoftime-corridors,weobservethattheobjectivevalues increase(asexpected)andthatgapsgetsomewhatlargerforwidercorridors.Furthermore,runtimesofXpressclearlygrowwith largertime-corridorswhereasruntimesof𝐼𝐶𝐴𝑀stayalmostconstantfordifferentwidthsofcorridors.Althoughtheruntimesofthe heuristicgrowsubstantiallyforlargerinstanceshere,itismuchfasterthanXpressinallcases.Duetothisperformance,ICAMisvery wellsuitedtobeusedinthesimulationframework.

6.2. Simulationswitharrivaltimeuncertainty

Inthesubsequentexperiments,weanalyzetheeffectofintroducingtime-corridorsonthetotaltraversingtimeoftheshipsand thenumberofreschedules.Wealsoinvestigatetheeffectofthelengthofthenoticeperiod(i.e.,thetimeinadvancetheshipswill callintheirETAs)toseeifitmaybebeneficialtoseekforlongernoticeperiods.Finally,weconductananalysisonhowpossible upgradesinthecanalcanimprovetheaveragetraversingtime.

Forthesimulations,weusedadatasetofabouttwomonths(63days)ofshipstraffic.Thefirstdayistakenoutoftheperformance analysisasitservesaswarmupperiod.Thuseachsimulationhas62daysoffulltraffic.

Fourdifferentsimulationsareconductedtoanalyzetheeffectofintroducingtime-corridorsonthetotaltraversingtimesforthe shipsandthenumberofreschedules.Thefirstsimulationisrunusingaheuristicthatreflectsthecurrentschedulingpracticeto createsomebenchmarkstocomparewith.WedenotethisheuristicastheSimpleWaitingHeuristic(SWH).TheSWHsolvesconflicts chronologicallyastheyoccurbyforcingoneofthetwoshipstowait.Italwaysselectstheshipthatgetsthesmallestwaitingtime withoutconsideringconflictsthatappearlater.Thealgorithmiccomplexityofthisprocedureislow,hencethecomputationaltimeis veryshortperconflictresolution.

ThethreeothersimulationsusetheICAMasthesolutionmethodwithdifferenttime-corridorwidths𝑇𝐶of0,10and20minutes.

Thedelayparametersusedduringthesesimulationsare𝛼=0.5and𝑑=10,meaningthat50%oftheshipsareassumedtoarrivelater thantheirETAsandthattheexpecteddelayamongthedelayedshipsistenminutes.

TheresultsfromthesesimulationsaresummarizedinFig.9a).Thisfigureshows(witha95%confidenceinterval)theaverage traversingtime(𝐴𝑇𝑇)fortheshipsandthedailynumberofreschedules fromeachofthefoursimulations.Comparingthetwo heuristicswithoutanytime-corridors(width0),weseethatSWHleadstoanaveragetraversingtimeof444.82minuteswhereas ICAMachievesanaveragetraversingtimeof 437.10minutes.Thisis areductionof almost8minutes. However,amuchlarger improvementisfoundinthenumberofreschedules,whichgoesfrom496.61downto77.27.Itshouldhoweverbenotedthatthe complexityofthesetwoproceduresareverydifferent.TheICAMspendsmuchlongertimeperfullreschedulethanwhattheSWH usestoresolveaspecificconflictbetweentwoships.Nevertheless,theSWHmightbeconsideredmoretediousthantheICAMbythe trafficmanagersworkingatthecanalauthority.SincethenumberofreschedulesissomuchlargerfortheSWHthanforanyofthe ICAMresults,weremovedinFig.9b)theSWHresultstoshowmoreclearlythedifferencesamongtheresultsobtainedbytheICAM underdifferenttime-corridors.

AscanbeseeninFig.9b),theaveragetraversingtimepershipincreaseswiththewidthofthetime-corridors,asatime-corridor giventooneshipcanrestrictthetravelingofotherships.Thisincreasereflectsthe’priceofrobustness’inoursolutions.Time-corridors of10minutesleadtoanincreaseofaboutsixminutescomparedtonotime-corridorsatall.Withtime-corridorsof20minutes,the increaseof𝐴𝑇𝑇 isabout15minutes.Anyhow,theaveragetraversingtimeachievedbyICAMwithtime-corridorsof10minutesis stillslightlysmallerthantheoneobtainedwiththeSWHand,atthesametime,muchmorerobust.Ingeneral,thereisasignificant decreaseinthenumberofrescheduleswhenthewidthofthetime-corridorsincreases.Thenumberofreschedulesisreducedbymore than50%withtime-corridorsof10minutescomparedtonotime-corridors,andthenumberofreschedulesisfurtherdecreasedwhen thetime-corridorsaresetto20minutes.Basedontheresultsfromthesesimulations,itmightthereforebebeneficialtoincludeshort time-corridorsforeachshipsincethiswilldecreasetheneedforreschedulesandonlygiveamodestincreaseintheaveragetraversing time.

Tofurthertesttheeffectofthetime-corridors,wehaveconductedadditionalsimulationsforthreeconfigurationsofthedelay parametersthatrepresentdifferentsituationsregardingtheuncertaintyinarrivaltimes.Moreprecisely,weconsidersituations(a) where50%oftheshipsaredelayedandtheexpecteddelayfordelayedshipsis10minutes,(b)where50%oftheshipsaredelayed andtheexpecteddelayfordelayedshipsis20minutes,and(c)where20%oftheshipsaredelayedandtheexpecteddelayfordelayed shipsis20minutes.Forallthreesituations,wevariedthetime-corridorwidthfrom0to25minutes.Fig.10displaysthesimulation results.

Fig.9. 95%ConfidenceIntervalsforthenumberofdailyreschedulesandtheaveragetraversingtimeATT.TheSWHisexcludedinb)tomore clearlyshowthedifferencesforthesimulationswithICAMunderdifferentwidthsoftime-corridors𝑇𝐶.

Fig.10. Averagetraversingtimeanddailynumberofreschedulesfordifferentdelaysituations.

BoththeaveragetraversingtimeandthenumberofdailyreschedulessharethesamepropertiesinallthethreeplotsinFig.10.The averagetraversingtimesincreasewiththewidthofthetime-corridorsandarequitesimilaramongthethreesetsofdelayparameters.

Withtime-corridorsofzero,weseethatallthreeuncertaintysettingsgiveanaveragetraversingtimeofabout437minutes.The differencebetweenthemincreasesslightlyasthewidthofthetime-corridorsincreases,butthisdifferenceisstillsmall.Ittherefore seemsthatthewidthofthetime-corridorsaffectstheaveragetraversingtimemorethanthedifferentdelayparametersdo.

Thenumberofdailyreschedulesdecreasesforlargertime-corridors.Unlikefortheaveragetraversingtime,thedelayparameters affectthenumberofdailyreschedules.Inthecasewhere50%oftheshipsarriveontime(Figs.10a)andb)),around80reschedules willbeneededeachdayifnotime-corridorsareapplied.With80%oftheshipsarrivingontime(Fig.10c)),thisnumberdecreases to36reschedules.Basedontheseresults,itseemsthatthepreferredwidthofthetime-corridorsshouldbebasedontheexpected delay.Whichtime-corridorwidthtoselectwithinthisintervaldependsonhowtheoperatorsvaluetheaveragetraversingtimeand theburdenofrescheduling.

Table2

Delayparametersfordifferentnoticeperiodslengthsundertwodelaysettings.

Setting 1 Setting 2

Length of notice period [ 𝑚𝑖𝑛 ] Expected delay for delayed ships 𝑑 [ 𝑚𝑖𝑛 ] Expected delay for delayed ships 𝑑 [ 𝑚𝑖𝑛 ]

60 5 10

120 10 10

180 15 10

240 20 10

Fig.11. Simulationresultsfordifferentnoticeperiodlengthsundertwodifferentdelayassumptions.

Allprevioussimulationswereconductedwithanoticeperiodoftwohoursforthearrivalofaship.Itisofinteresttoseeifthe averagetraversingtimeoftheshipscanbeimprovedbyextendingthelengthofthisnoticeperiod.Toinvestigatethis,weconducted simulationsforfourdifferentnoticeperiodlengthsof60,120,180and240minutes.Time-corridorsoftenminutesareusedforall theseteststogetherwithan𝛼-valueof0.5,i.e.50%oftheshipsarriveontime.

Twodifferentsettingsregardinghowthedelaysvaryasthenoticeperiodchangeshavebeentested.Setting1isbasedonthe assumptionthattheexpecteddelayisproportionaltothelengthofthenoticeperiod.Thisassumptionisbuiltonthebeliefthatthe probabilityofexperiencingadelayincreasesbythelengthoftimetheshipisexposedtounforeseeneventsbeforeenteringthecanal.

Setting2isbasedontheassumptionthattheexpecteddelayisindependentofthelengthofthenoticeperiod.Thisassumptionfollows thefactthatcertaindelay-inducingeventshavethesameprobabilityofoccurringregardlessofhowearlytheship’sETAhasbeen announced.Forexample,shipsmustoccasionallywaitbeforetheyareallowedtoenterthelocksandthiswaitingtimeisrealizedjust uponarrivalatthecanal.Thedelaywillinthiscasebeindependentofthenoticeperiod.Table2showshowtheexpecteddelaysare setforthefourconsiderednoticeperiodsunderbothsettings.Wefurthermorekeep𝛼=0.5.

Theaveragetraversingtimesandtheaveragenumberofdailyreschedulesforthesimulationsbasedonthetwosettingsareshown inFig.11.Itcanbeseenthattheaveragetraversingtimeremainsrelativelyconstantforthedifferentlengthsofnoticeperiodsunder bothsettings.Asforthenumberofdailyreschedules,thetwosettingsaffectthisnumberdifferently.Undersetting1,thenumberof reschedulesincreaseswithincreasedlengthofthenoticeperiod.Thisseemsnaturalastheexpecteddelayoftheshipsismodeled toincreaseproportionallytothelengthofthenoticeperiod.Still,thenumberofreschedulesremainsclearlybelowthenumbers observedforthesimple𝑆𝑊𝐻heuristic,suchthatusingamoreadvancedplanningby𝐼𝐶𝐴𝑀leadstomuchmorerobustschedules evenunderthechallengingsituationofdelaysthatgrowwithlongernoticeperiods.

AsseeninFig.11b),theeffectoflongernoticeperiodsispositivewithrespecttothenumberofdailyreschedulesundersetting 2.Thisshowsthatearlyannouncementsofshiparrivalstogetherwithrelativeconstantactualdelaysissuccessfullyexploitedinour approachtoobtainevenmorerobustschedules.

Wenextanalysethewaitingofshipsinthecanal.Forthispurpose,wesimulatedshiptrafficfora2-monthperiod,whichinvolves about5000ships.Fig.12showsforeachsidingofthecanal,thetotalwaitingtimeofallships(measuredinhours),thelongest waitingtimeofanyship(measuredinminutes),andthenumberofshipsthatwaitedinthissegment.Wereporttheseresultsfor ICAMwithtime-corridorsof0,10and20minutesandforSWHwithouttime-corridorsandforanoticeperiodof2hours.Itcanbe observedthatthelargestdifferencesregardingthenumberofshipswaitingamongthedifferentsolutionmethodsareinsegments0 and22.Thetotalwaitinginthesesegmentsincreasesdramaticallywiththewidthofthetime-corridors.Thisisbecausealigningships thatarrivealmostatthesametimemustwaitforthetime-corridorfortheshipinfrontofittoend.Asthewidthofthetime-corridors increase,moreshipsmustwaitforalongertime.

BasedonFig.12,whichdisplaystheheatmapwithdifferentwaitingmeasures,itseemslikethattransitsegmentsnumber13,15, 17,19and21arerestrainingtheshipflow.Thesetransitshavepassagenumbersequalto6,whileallothertransitshavepassage numbersequalto8.Notethatsegment15haspassagenumber8inFig.2,butthisextensionwasquiterecentlywhichiswhyit haspassagenumber6inourexperiments.Sincethewaitingismuchhigherattheadjacentsidingstotransitsegmentswithpassage number6,itcanbeofinteresttoanalyzetheeffectofupgradingthesesegments.Toanalysethis,weconductedmultiplesimulations forthe2-monthperiodwithtime-corridorsoftenminuteswhere𝐼𝐶𝐴𝑀wasusedassolutionmethod.Ineachsimulationoneofthe verynarrowsegmentswaschangedtoapassagenumberof8.TheresultsarepresentedinTable3.Additionally,asimulationwhere

Fig.12. WaitingtimemeasuresforsimulatedtrafficschedulesobtainedbyICAMforthreedifferenttime-corridorwidths(0,10and20minutes) andobtainedbySWH(withouttime-corridors).Pleasenotethattheunitsdifferforthethreedifferentwaitingmeasures.

Table3

Improvementintraversingtimebyupgradingcertaintransitsfrompassagenumber6to8.

Average traversing time [ 𝑚𝑖𝑛 ] Reduction in transit time [%] Transit length [ 𝑚𝑒𝑡𝑒𝑟 ] Impact per kilometer [ 𝑚𝑖𝑛 ∕ 𝑘𝑚 ]

Original topology 443.87 - - -

Transit 13 437.92 1.34% 8170 0.728

Transit 15 438.91 1.12% 7510 0.660

Transit 17 440.37 0.79% 4406 0.794

Transit 19 440.30 0.81% 6150 0.580

Transit 21 442.76 0.25% 2412 0.460

All transits upgraded 424.39 4.39% 28 648 0.680

allthetransitshavebeenupgradedtoapassagenumberof8hasbeenconducted.Boththeaveragetraversingtimeintheoriginal layoutandtheaveragetraversingtimesaftertheupgradesarepresentedinTable3.Thereductionintraversingtimesrelativetothe originalcanallayoutarealsoshown.Thelengthofthedifferentsegmentsvariesextensivelyandsincetheupgradingcostmaybe proportionaltothelengthofthesegment,wealsoprovideinformationabouttheminutessavedperkilometerofsegmentlength.

Thegreatestimprovementcanbeobtainedbyupgradingtransit13thatgivesaroundsixminutesreductioninaveragetraversing time.Thismayseemsmall,butwithanannualtrafficof30000ships,itwillreducethetotaltraversingtimeforallshipsbyaround 3000hoursperyear.Upgradingtransitsegment17yieldsthehighestimprovementperkilometerofupgrade.Upgradingtransit segment13givesthesecondhighestimprovementperkilometerandthehighestoverallimprovementpersegment.Interestingly, transitsegment15,whichwasrecentlyextendedtopassagenumber8,onlyachievesthesecondorthirdrank,dependingonwhich performanceimprovementmeasureoneconsiders.Eventually,byjointlyupgradingallconsideredtransitsegmenttopassagenumber 8,itispossibletosavemorethan19minutesintheaveragetraversingtime.This correspondstoanestimatedreductioninthe totaltraversingtimeforallshipsofalmost10000hoursperyear.Nexttothetime-savinganalysisthatisconductedhere,upgrading segmentsisofcoursealsoanissueofconstructioncostsetc.,which,however,isbeyondthescopeofthispaper.

7. Concludingremarks

WehavestudiedtheschedulingofshipsthroughtheKielCanalwhentheships’arrivaltimesatthecanalaresubjecttouncer- tainty.Suchuncertaintiesgivefrequentneedofreplanningtokeepschedulesfeasible.Totacklethischallenge,wehaveproposed amathematicalmodelthatincorporatestime-corridors,sothatschedulesstayvalidaslongasshipsarrivewithinthegiventime- corridors.TheproblemissolvedbyanIterativeConflictAddingMatheuristic(ICAM),whichwasshowntoproduceverygoodsolutions forreal-worldinstancesinshorttime.