A Base Integer Programming Model and Benchmark Suite for Liner-Shipping Network Design

Berit Dangaard Brouer, Fernando Alvarez, Christian Edinger Munk Plum, David Pisinger, Mikkel M. Sigurd

    Research output: Contribution to journalJournal articleResearchpeer-review

    5066 Downloads (Pure)


    The liner-shipping network design problem is to create a set of nonsimple cyclic sailing routes for a designated fleet of container vessels that jointly transports multiple commodities. The objective is to maximize the revenue of cargo transport while minimizing the costs of operation. The potential for making cost-effective and energy-efficient liner-shipping networks using operations research (OR) is huge and neglected. The implementation of logistic planning tools based upon OR has enhanced performance of airlines, railways, and general transportation companies, but within the field of liner shipping, applications of OR are scarce. We believe that access to domain knowledge and data is a barrier for researchers to approach the important liner-shipping network design problem. The purpose of the benchmark suite and the paper at hand is to provide easy access to the domain and the data sources of liner shipping for OR researchers in general. We describe and analyze the liner-shipping domain applied to network design and present a rich integer programming model based on services that constitute the fixed schedule of a liner shipping company. We prove the liner-shipping network design problem to be strongly NP-hard. A benchmark suite of data instances to reflect the business structure of a global liner shipping network is presented. The design of the benchmark suite is discussed in relation to industry standards, business rules, and mathematical programming. The data are based on real-life data from the largest global liner-shipping company, Maersk Line, and supplemented by data from several industry and public stakeholders. Computational results yielding the first best known solutions for six of the seven benchmark instances is provided using a heuristic combining tabu search and heuristic column generation.
    Original languageEnglish
    JournalTransportation Science
    Issue number2
    Pages (from-to)281-312
    Publication statusPublished - 2014
    Event25th European Conference on Operations Research: OR Connecting Sciences - Radisson Blu Hotel Lietuva, Vilnius, Lithuania
    Duration: 8 Jul 201211 Jul 2012
    Conference number: 25


    Conference25th European Conference on Operations Research
    LocationRadisson Blu Hotel Lietuva
    Internet address


    • Mathematical programming
    • Transportation
    • Logistics
    • Large Scale Optimization


    Dive into the research topics of 'A Base Integer Programming Model and Benchmark Suite for Liner-Shipping Network Design'. Together they form a unique fingerprint.

    Cite this