Keyword: network design


Green Liner Shipping Network Design

Hellsten, Erik; Pisinger, David; Sacramento, David; Vilhelmsen, Charlotte

Green Liner Shipping Network Design refers to the problems in green logistics related to the design of maritime services in liner shipping with a focus on reducing the environmental impact. This chapter discusses how to more efficiently plan the vessel services with the use of mathematical optimization models. A brief introduction to the main characteristics of Liner Shipping Network Design is given, as well as the different variants and assumptions that can be considered when defining this problem. The chapter also includes an overview of the algorithms and approaches that have been presented in the literature to design such networks.

Book chapter in Psaraftis H. (eds) Sustainable Shipping / 2019
Go to book

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

Krogsgaard, Alexander; Pisinger, David; Thorsen, Jesper

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.

Networks, 72(3) / 2018
Go to paper

Competitive Liner Shipping Network Design

Karsten, Christian Vad; Brouer, Berit Dangaard; Pisinger, David

We present a solution method for the liner shipping network design problem which is a core strategic planning problem faced by container carriers. We propose the first practical algorithm which explicitly handles transshipment time limits for all demands. Individual sailing speeds at each service leg are used to balance sailings speed against operational costs, hence ensuring that the found network is competitive on both transit time and cost. We present a matheuristic for the problem where a MIP is used to select which ports should be inserted or removed on a route. Computational results are presented showing very promising results for realistic global liner shipping networks. Due to a number of algorithmic enhancements, the obtained solutions can be found within the same time frame as used by previous algorithms not handling time constraints. Furthermore we present a sensitivity analysis on fluctuations in bunker price which confirms the applicability of the algorithm.

DTU Management Engineering / 2015
Go to report

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

Brouer, Berit D; Alvarez, J Fernando; Plum, Christian Edinger Munk; Pisinger, David; Sigurd, Mikkel M.

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.

Transportation Science Vol. 48, No. 2 / 2014
Go to paper