The Liner Shipping Network Design Problem Strengthened formulations considering complex route structures, transhipment and transit time Marie Ameln Julie Sand Fuglum Industrial Economics and Technology Management Submission date: June 2015 Supervisor: Henrik Andersson, IØT Norwegian University of Science and Technology Department of Industrial Economics and Technology Management Problem description The purpose of this thesis is to develop new extensive mathematical formulations of the Liner Shipping Network Design Problem (LS-NDP) and to use theory and methods to strengthen the formulations. The aim of the work will be on making models that reflect a realistic situation and therefore transhipment, the cost of transhipment, a heterogeneous fleet, route dependent capacities, complex route structures and transit time will be taken into account. Since the LS-NDP is such a complex problem that cannot be solved in polynomial time there will also be a focus on strengthening the formulations through symmetry breaking constraints and valid inequalities. Preface This master thesis is the last part of our Master of Science degree at the Norwegian University of Science and Technology (NTNU), Department of Industrial Economics and Technology Management. The thesis was written during the spring semester of 2015. It is done within the field of operations research. We present new comprehensive exact formulations of the Liner Shipping Network De- sign Problem (LS-NDP) with a particular focus on enabling complex route structures, transhipment and transit time. We would like to thank our supervisors Magnus St˚alhane, Kristian Thun and Henrik Andersson for their sincere enthusiasm about our work, valuable feedback and guidance. We will surely miss our weekly discussions. We also want to thank Berit D. Brouer, who has been an inspiration for our work, and we had the pleasure to discuss the LS-NDP with at the NTNU Ocean week conference in Trondheim. At last we want to convey that working with the Liner Shipping Network Design Problem has been extremely interesting. As we have dealt with this problem now for some time its complex nature reveals more and more, and we have understood that there is no simple solution to it. However, that is also why it has been so exciting to work within this field. We are convinced that the liner shipping industry has a lot to gain from operations research. Trondheim, June 11th, 2015 Marie Ameln Julie Sand Fuglum I Sammendrag Internasjonal container linjefart er en milliardindustri, som opplever stadig lavere marginer. Likevel har det vært begrenset forskning p˚a planleggingsproblemer innen bransjen. Arbeidet som er presentert i denne rapporten er motivert av en overbevisning om at det er et stort potensiale for kostnadseffektivisering innen linjefart, ved˚a forbedre ruteplanleggingsprosessene. Det har blitt utviklet tre matematiske blandede heltallsmodeller for˚a løse linjefarts nettverk- problemet,ogs˚akalttheLinerShippingNetworkDesignProblem(LS-NDP).Modelleneblirogs˚a utvidet til˚a ta hensyn til krav om maksimal transittid p˚a lastene, noe som gjør at det totalt blir presentert seks formuleringer. I tillegg til hvorvidt formuleringene tar hensyn tid transittid eller ikke, skiller de seg fra hverandre med tanke p˚a hvilke rutestrukturer de muliggjør. M˚alet for alle modellene er˚a minimere kostnadene til et shippingselskap ved˚a utforme et ef- fektivt rutenettverk, som tilfredsstiller alle etterspørselskrav. Alle formuleringene inkluderer vesentlige funksjoner som omlasting, omlastingskostnader, et ukentlig frekvenskrav og en het- erogen skipsfl˚ate. Detstørstefokusomr˚adetiarbeidetharvært˚autvikleformuleringersom˚apnerformerfleksible rutestrukturer. Den første formuleringen, the Basic model, tillater kun enkle rutestrukturer. Dette vil si at en havn kun kan besøkes´en gang av en gitt rute i en enkelt rotasjon. De to andre modellene muliggjør forskjellige typer komplekse rutekonstruksjoner. The Flower model tillater ruter hvor ´en port kan besøkes en rekke ganger av samme rute. The Chain model muliggjør rutestrukturer hvor en flere havner kan besøkes to ganger av samme rute. Vi har ikke gjort noen kompromisser som følge av de komplekse rutestrukturene, og alle omlastingskostnadene er riktig beregnet. Utifra litteraturstudien er v˚art inntrykk at i de mest omfattende LS-NDP modellene presentert s˚a langt, er de komplekse rutene begrenset til ˚a kun kunne besøke ´en port maks to ganger, en s˚akalt butterfly route. S˚a vidt vi vet, er dette første gang eksakte løsninger av modeller med mer komplekse rutestrukturer blir presentert. Vi har studert rutenettverket til flere store shippingselskaper, og funnet at et betydelig antall av disse er komplekse. Dette har gitt oss tro p˚a at dette arbeidet kan ha praktisk relevans. III Modellene presentert i denne rapporten er av høy beregningsmessig kompleksitet, noe som gjør at de tar lang tid˚a løse. P˚a grunn av dette har vi utviklet symmetribrytende restriksjoner og gyldige ulikheter som forsøk p˚a ˚a styrke formuleringene. Testingen av flere av disse gir gode resultater, og indikerer at den generelle løsningstiden forbedres. Disse ble inkludert i videre testing av modellene. Instansene løst til optimalitet er sammenlignbare i størrelse med instansene i eksisterende lit- teratur om eksakte metoder for LS-NDP. Resultatene viser, ikke overraskende, at de komplekse modellene tas vesentlig lenger tid˚a løse til optimalitet. Resultatene fra studien viser fordelen med˚a muliggjøre komplekse rutestrukturer, og hvordan dette bidrar til en bedre allokering av skipsfl˚aten. En interessant observasjon fra studien av transittid-modellene er at det virker som fordelen av ˚a tillate komplekse rutestrukturer blir forsterket n˚ar det er strengere krav til transittid. Abstract International liner container shipping is a multibillon dollar business, experiencing increasingly pushed margins. However, there have been scarce research efforts when it comes to planning and scheduling problems within this industry. The work done in this report is motivated by the conviction that shipping companies may expect large benefits from improving the routing processes of their ships. Three extensive mathematical models for the liner shipping network design problem (LS-NDP) have been developed. The models have been extended to also take into account transit time, making it six formulations in total. Besides whether they incorporate transit time, the models differ in which route structures they enable. We take the perspective of a liner shipping company. The objective of all the models is to minimize costs by designing an efficient network of routes that satisfy all demand. All the formulationsincludeimportantfeaturesastranshipment,transhipmentcost,aweeklyfrequency requirement and a heterogeneous fleet. The key focus area has been on developing formulations that allow for more flexible route structures. The first formulation, called the Basic model, only allows simple route networks. The two other models enable different types of complex route structures. The Flower model allows the routes in the network to visit one port in the route multiple times, while the Chain model incorporates the possibility of a route visiting several ports in the route twice. No compromises have been made in allowing the complex route structures, and all transhipment costs are calculated correctly. To the best of our knowledge the most comprehensive liner shipping models in literature have restricted the routes to have at most one port that is visited at most twice, socalled butterfly routes. As far as we know, this is the first time exact solutions allowing even more complex route structures, have been presented. Studying the route-nets of the world leading liners and finding that a substantial number of the routes they provide are complex routes, have given us a belief that there is a practical relevance of this research. Since the models are of non-trivial complexity, a strong effort has been made in order to V strengthen the formulations to make them more computationally efficient. This has been done by imposing symmetry breaking constraints and valid inequalities. The testing of the strength- ening formulations show good results for several of them, and they are included in the models in further computational study. The instances solved to optimality are comparable in size to the instances in existing literature of exact methods considering the LS-NDP. The computational results show that the complex models take significantly longer time to solve to optimality. The results show the advantage of more complex route structures and how it enables a better allocation of the vessels. The results from the computational study of the transit time models indicate that the advantage of allowing more flexible route structures, is amplified as the transit time requirements get stricter.