A Branch-and-Price Algorithm for the Liner Shipping Network Design Problem

Kristian Thun, Henrik Andersson () and Magnus Stålhane
Additional contact information
Kristian Thun: Norwegian University of Science and Technology
Henrik Andersson: Norwegian University of Science and Technology
Magnus Stålhane: Norwegian University of Science and Technology

SN Operations Research Forum, 2020, vol. 1, issue 4, 1-21

Abstract: Abstract Maritime transportation is the backbone of the global economy and one of its most important segments is liner shipping. To design a liner shipping network is notoriously difficult but also very important since an efficient network can be the difference between prosperity and bankruptcy. In this paper, we propose a branch-and-price algorithm for the liner shipping network design problem, which is the problem of designing a set of cyclic services and to deploy a specific class of vessels to each service so that all demand can flow through the network at minimal cost. The proposed model can create services with a complex structure and correctly calculate the transshipment cost. The formulation of the master problem strengthens a known formulation with valid inequalities. Because of multiple dependencies between ports that are not necessarily adjacent and no defining state at any of the ports, the subproblem is formulated and solved as a mixed integer linear program. Strategies to improve the solution time of the subproblem are proposed. The computational study shows that the algorithm provides significantly tighter lower bounds in the root node than existing methods on a set of small instances.

Keywords: Liner shipping; Network design; Branch-and-price (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s43069-020-00027-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:snopef:v:1:y:2020:i:4:d:10.1007_s43069-020-00027-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/43069

DOI: 10.1007/s43069-020-00027-y

Access Statistics for this article

SN Operations Research Forum is currently edited by Marco Lübbecke

More articles in SN Operations Research Forum from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().