A flow-first route-next heuristic for liner shipping network design

Alexander Krogsgaard, David Pisinger*, Jesper Thorsen

*Corresponding author for this work

    Research output: Contribution to journalJournal articleResearchpeer-review

    270 Downloads (Pure)


    Having a well-designed liner shipping network is paramount to ensure competitive freight rates, adequate capacity on trade-lanes, and reasonable transportation times.The most successful algorithms for liner shipping network design make use of a two-phase approach, where they first design the routes of the vessels, and then flow the containers through the network in order to calculate how many of the customers’demands can be satisfied, and what the imposed operational costs are. In this article, we reverse the approach by first flowing the containers through a relaxed network, and then design routes to match this flow. This gives a better initial solution than starting from scratch, and the relaxed network reflects the ideas behind a physical internet of having a distributed multi-segment intermodal transport. Next, the initial solution is improved by use of a variable neighborhood search method, where six different operators are used to modify the network. Since each iteration of the local search method involves solving a very complex multi-commodity flow problem to route the containers through the network, the flow problem is solved heuristically by use of a fast Lagrange heuristic. Although the Lagrange heuristic for flowing containers is 2–5% from the optimal solution, the solution quality is sufficiently good to guide the variable neighborhood search method in designing the network. Computational results are reported, showing that the developed heuristic is able to find improved solutions for large-scale instances from LINER-LIB, and it is the first heuristic to report results for the biggest WorldLarge instance.
    Original languageEnglish
    Issue number3
    Pages (from-to)358-381
    Publication statusPublished - 2018


    • Lagrange heuristic
    • Liner shipping
    • Local search
    • Multi-commodity flow
    • Network design


    Dive into the research topics of 'A flow-first route-next heuristic for liner shipping network design'. Together they form a unique fingerprint.

    Cite this