TY - UNPB

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

AU - Wagenvoort, Mette

AU - Bouman, Paul

AU - van Ee, Martijn

AU - Lamballais Tessensohn, Tim

AU - Postek, Krzysztof

PY - 2022/4

Y1 - 2022/4

N2 - 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.

AB - 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.

M3 - Working paper

T3 - Econometric Institute Research Papers

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

PB - Econometric Institute, EUR

ER -