Liner shipping network design - a new decomposition

Research output: Chapter in Book/Report/Conference proceedingConference abstract in proceedingsResearchpeer-review

76 Downloads (Pure)


Liner shipping is the foundation for global commerce, but international shipping is responsible for about 2.7% of the global CO2 emission. It is therefore important to develop decision support tools for designing liner shipping networks, minimizing energy consumption. Formally, the liner shipping network design problem is to construct a number of routes operated on a weekly schedule such that a given set of demands can be transported at minimum operational cost. Only a few MIP models have been proposed for this problem, and generally these models are only able to solve small problems to optimality. Hence, most algorithms are based on a two-stage decomposition: First, a number of routes are constructed, and then a multi-commodity network problem is solved to flow the demands through the network. However, due to the complexity of solving large-scale multicommodity flow problems with time constraints, it is only possible to search a small subset of routes. In this talk we present a dierent decomposition based on first flowing the demand, and then constructing routes that cover the flow. The proposed relaxation is a time-constrained network design problem with edge setup costs. This problem is also NP-hard to solve, so a heuristic approach is used based on variable-size neighbourhood search. At the end of the presentation it is discussed how solutions to the relaxed problem can be used to construct routes for the original liner shipping network design problem.
Original languageEnglish
Title of host publicationProceedings of the 28th European Conference on Operational Research
Publication date2016
Publication statusPublished - 2016
Event28th European Conference on Operational Research - Poznan, Poland
Duration: 3 Jul 20167 Jul 2016
Conference number: 28


Conference28th European Conference on Operational Research
Internet address


Dive into the research topics of 'Liner shipping network design - a new decomposition'. Together they form a unique fingerprint.

Cite this