An Exact and Heuristic Approach for the Ship-to-Shore Problem

Mette Wagenvoort, Paul Bouman, Martijn van Ee, Tim Lamballais Tessensohn, Krzysztof Postek

Research output: Working paperAcademic

18 Downloads (Pure)

Abstract

After a hurricane, for example hurricane Irma in Sint-Maarten, the navy can provide aid by bringing supplies, helping to clear roads and evacuating victims. If the destinations cannot be reached over land via a port, resources can be transported using smaller ships and helicopters, called connectors. This has to be done eciently so that the supply provision can start as soon as possible. Planning such an operation is known as the ship-to-shore problem, which is a combination of a heterogeneous vehicle routing and a bin-packing problem, which we prove to be an NP-hard problem. The aim is to schedule the connector trips to the shore and determine what resources should be loaded onto the connectors for each of their trips while minimising the duration of the operation. Connectors have dierent sizes, weight capacities, speeds and (un)loading times. Scheduling such an operation is currently done manually, which we mimic using a greedy heuristic. We aim to determine the quality of the greedy heuristic and determine in what cases it performs well and in what cases improvements can be found. To determine the quality, we solve the problem using a branch-and-price algorithm in which we take a set of ways to feasibly load the connectors as input. We use data provided by the Royal Netherlands Navy to construct 98 instances and nd that the greedy heuristic can nd an optimal solution in the majority of the cases. However, when the problem is less constrained in terms of the equirements regarding the order in which the resources should be delivered, the greedy heuristic is more likely to choose a suboptimal trip and can result in a solution that is far from optimal.
Original languageEnglish
PublisherEconometric Institute, EUR
Publication statusPublished - Apr 2022

Publication series

SeriesEconometric Institute Research Papers
NumberEI 2022-05

Fingerprint

Dive into the research topics of 'An Exact and Heuristic Approach for the Ship-to-Shore Problem'. Together they form a unique fingerprint.

Cite this