A Branch-and-Price Algorithm to Solve the Ship-to-Shore Problem

After a hurricane, for example hurricane Irma at Sint-Maarten, the navy can provide aid by brining 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 efficiently such that the evacuation 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 problem and a bin-packing 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 different sizes, weight capacities, speeds and (un)loading times.

As the connectors make multiple trips and can visit the same location multiple times, a time-space network is used to model the problem. The size of the network is partially determined by the number of time periods needed, which is set using a greedy heuristic. The usage of the time-space network gives flexibility as it allows for increasing the number of big decks and beaches, adding different routes between the locations, and for replanning during an operation. Given a set of feasible loadings for the connectors, we solve the problem using a branch-and-price algorithm and compare its performance to a greedy heuristic. We use data provided by the Royal Netherlands Navy.

Zoom link: https://eur-nl.zoom.us/j/95784022173?pwd=b1J0c3lwWVhUa1FaKzcrcWFuWXhZZz09

Meeting ID: 957 8402 2173