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

    79 Downloads (Pure)

    Abstract

    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
    JournalNetworks
    Volume72
    Issue number3
    Pages (from-to)358-381
    ISSN0028-3045
    DOIs
    Publication statusPublished - 2018

    Keywords

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

    Cite this

    Krogsgaard, Alexander ; Pisinger, David ; Thorsen, Jesper. / A flow-first route-next heuristic for liner shipping network design. In: Networks. 2018 ; Vol. 72, No. 3. pp. 358-381.
    @article{2cb9111e22cd4927a0aa5b68b41f1ef4,
    title = "A flow-first route-next heuristic for liner shipping network design",
    abstract = "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.",
    keywords = "Lagrange heuristic, Liner shipping, Local search, Multi-commodity flow, Network design",
    author = "Alexander Krogsgaard and David Pisinger and Jesper Thorsen",
    year = "2018",
    doi = "10.1002/net.21819",
    language = "English",
    volume = "72",
    pages = "358--381",
    journal = "Networks",
    issn = "0028-3045",
    publisher = "JohnWiley & Sons, Inc.",
    number = "3",

    }

    A flow-first route-next heuristic for liner shipping network design. / Krogsgaard, Alexander; Pisinger, David; Thorsen, Jesper.

    In: Networks, Vol. 72, No. 3, 2018, p. 358-381.

    Research output: Contribution to journalJournal articleResearchpeer-review

    TY - JOUR

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

    AU - Krogsgaard, Alexander

    AU - Pisinger, David

    AU - Thorsen, Jesper

    PY - 2018

    Y1 - 2018

    N2 - 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.

    AB - 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.

    KW - Lagrange heuristic

    KW - Liner shipping

    KW - Local search

    KW - Multi-commodity flow

    KW - Network design

    U2 - 10.1002/net.21819

    DO - 10.1002/net.21819

    M3 - Journal article

    VL - 72

    SP - 358

    EP - 381

    JO - Networks

    JF - Networks

    SN - 0028-3045

    IS - 3

    ER -