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

Berit D. Brouer (), J. Fernando Alvarez (), Christian E. M. Plum (), David Pisinger () and Mikkel M. Sigurd ()
Additional contact information
Berit D. Brouer: DTU Management Engineering, Technical University of Denmark, 2800 Kgs. Lyngby, Denmark
J. Fernando Alvarez: Business Optimization, Uptimize!, Gøteborggata 9, Oslo 0566, Norway
Christian E. M. Plum: DTU Management Engineering, Technical University of Denmark; and Maersk Line, Esplanaden 50, København K., Denmark
David Pisinger: DTU Management Engineering, Technical University of Denmark, 2800 Kgs. Lyngby, Denmark
Mikkel M. Sigurd: Maersk Line, Esplanaden 50, 1098 København K., Denmark

Transportation Science, 2014, vol. 48, issue 2, 281-312

Abstract: 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.

Keywords: liner shipping; mathematical programming; network design (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (73)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2013.0471 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:48:y:2014:i:2:p:281-312

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().