A matheuristic for the liner shipping network design problem

Berit Dangaard Brouer, Guy Desaulniers, David Pisinger

    Research output: Contribution to journalJournal articleResearchpeer-review

    81 Downloads (Pure)


    We present an integer programming based heuristic, a matheuristic, for the liner shipping network design problem. This problem consists of finding a set of container shipping routes defining a capacitated network for cargo transport. The objective is to maximize the revenue of cargo transport, while minimizing the cost of operating the network. Liner shipping companies publish a set of routes with a time schedule, and it is an industry standard to have a weekly departure at each port call on a route. A weekly frequency is achieved by deploying several vessels to a single route, respecting the available fleet of container vessels. The matheuristic is composed of four main algorithmic components: a construction heuristic, an improvement heuristic, a reinsertion heuristic, and a perturbation heuristic. The improvement heuristic uses an integer program to select a set of improving port insertions and removals on each service. Computational results are reported for the benchmark suite LINER-LIB 2012 following the industry standard of weekly departures on every schedule. The heuristic shows overall good performance and is able to find high quality solutions within competitive execution times. The matheuristic can also be applied as a decision support tool to improve an existing network by optimizing on a designated subset of the routes. A case study is presented for this approach with very promising results. © 2014 Elsevier Ltd. All rights reserved.
    Original languageEnglish
    JournalTransportation Research. Part E: Logistics and Transportation Review
    Pages (from-to)42–59
    Publication statusPublished - 2014


    • Liner shipping
    • Network design
    • Matheuristic


    Dive into the research topics of 'A matheuristic for the liner shipping network design problem'. Together they form a unique fingerprint.

    Cite this