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

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.