A Branch-and-Price Algorithm for the Liner Shipping Network Design Problem
- PDF / 1,261,783 Bytes
- 21 Pages / 439.642 x 666.49 pts Page_size
- 18 Downloads / 185 Views
A Branch-and-Price Algorithm for the Liner Shipping Network Design Problem Kristian Thun1 · Henrik Andersson1
· Magnus St˚alhane1
Received: 20 March 2020 / Accepted: 16 September 2020 / © The Author(s) 2020
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
1 Introduction Ever since man first set sails across the oceans, transporting goods between continents has been an important part of the economy. Today, maritime transportation is
This article belongs to the Topical Collection on Decomposition at 70 Henrik Andersson
[email protected] 1
Department of Industrial Economics and Technology Management, Norwegian University of Science and Technology, Gløshaugen, Alfred Getz vei 3, 7491 Trondheim, Norway
28
Page 2 of 21
SN Operations Research Forum
(2020) 1:28
the backbone of the global economy and United Nations Conference on Trade And Development (UNCTAD) has in its review of maritime transportation shown that the volumes, counted in tonnes loaded, of international maritime trade has almost doubled since 2000, from slightly above 6 · 109 tonnes loaded in 2000 to almost 12 · 109 in 2018 [18]. Many types of goods are transported and many different vessels are used to do it, but maritime transportation is traditionally divided into three segments: industrial shipping, tramp shipping, and liner shipping, [9]. An industrial operator controls its own fleet of vessels and strives to minimize the costs of transporting its own cargoes. An operator within tramp shipping has similarities with taxi services, as the vessels follow the cargoes that become available in the market. Liner shipping resembles bus line operations since the vessels follow published schedules and itineraries. UNCTAD among others divided the goods transported into four categories; tanker trade, main bulk, other dry cargo, and cont
Data Loading...