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

Transportation Science - Tập 48 Số 2 - Trang 281-312 - 2014
Berit Dangaard Brouer1, J. Fernando Alvarez2, Christian Edinger Munk Plum3, David Pisinger1, Mikkel M. Sigurd4
1DTU Management Engineering, Technical University of Denmark, 2800 Kgs. , Lyngby, Denmark
2Business Optimization, Uptimize!, Gøteborggata 9, Oslo 0566, Norway
3DTU Management Engineering, Technical University of Denmark; and Maersk Line, Esplanaden 50, København K., Denmark
4Maersk line, Esplanaden 50, 1098 København K, Denmark

Tóm tắt

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.

Từ khóa


Tài liệu tham khảo

10.1016/j.orl.2008.04.007

10.1287/trsc.1070.0205

Alderton P, 2005, Reeds Sea Transport—Operations and Economics

10.1057/mel.2009.5

10.1057/jors.2011.72

10.3138/infor.49.2.093

10.1007/s10696-011-9105-4

10.3138/infor.49.2.109

10.3138/infor.49.2.075

10.1287/trsc.1030.0036

Christiansen M, 2007, Handbooks in Operations Research and Management Sciences, 14, 189

Chu CW, 2003, J. Marine Sci. Tech., 11, 96

10.1007/0-387-25486-2_1

10.1016/j.tre.2009.05.001

10.1080/0308883042000259819

10.1080/03088830903187143

10.1016/j.tre.2009.06.004

10.1016/j.tre.2010.05.005

10.1016/j.mcm.2006.08.012

10.1016/j.tre.2009.01.002

Jepsen MK, 2011, IMECS 2011—Internat. Multiconference Engineers Comput. Scientists, 2, 1379

10.1016/j.tre.2008.05.001

10.3138/infor.49.2.139

Kjeldsen KH (2012) Routing and scheduling in liner shipping. Ph.D. thesis, Department of Economics and Business, Aarhus University, Aarhus, Denmark.

Lu HA, 2002, J. Marine Sci. Tech., 10, 61

10.1016/j.tre.2011.02.004

10.1016/j.ejor.2012.05.006

Notteboom TE, 2004, J. Internat. Trade Logist., 2, 65, 10.24006/jilt.2004.1.2.65

10.1057/palgrave.mel.9100148

10.1016/j.jtrangeo.2008.05.003

Plum CEM, Jensen PN (2007) Minimization of bunker costs. Master's thesis, DIKU, Department of Computer Science, University of Copenhagen, Copenhagen.

10.1080/03088839700000069

10.1287/trsc.25.3.201

10.1016/S0377-2217(03)00030-4

10.1016/j.tre.2005.05.003

10.1287/opre.35.2.254

10.4324/9780203891742

10.3141/2222-04

10.1016/j.tre.2011.10.011

10.1016/j.trb.2012.01.003

10.1016/j.tre.2011.12.003

10.1007/s00773-009-0059-0

Thông tin
Thông tin xuất bản

Transportation Science

Tập 48 Số 2

281-312

Thông tin tác giả