A flow‐first route‐next heuristic for liner shipping network design. Issue 3 (10th April 2018)

• Record Type: Journal Article
• Authors: Krogsgaard, Alexander; Pisinger, David; Thorsen, Jesper
• Is Part Of: Networks. Volume 72:Issue 3(2018)
• Page Start: 358
• Page End: 381
• Publication Date: 2018-04-10
• Subjects: Lagrange heuristic -- liner shipping -- local search -- multi‐commodity flow -- network design; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21819
• Languages: English
• ISSNs: 0028-3045

Abstract

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.