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

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

Wagenvoort, M.
Bouman, P.C.
van Ee, M.
Lamballais Tessensohn, T.
Postek, K.

2022

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 e_ciently 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 di_erent 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 requirements 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.

Ship-to-shore problem
Branch-and-price
Integer linear programming
Ccomputational complexity

http://resolver.tudelft.nl/uuid:588371c3-51b6-4096-a788-192bb53a8b3c

981556

Ship to Shore Econometric Institute Researh Papers EI 2022 05

conference paper