An adaptive large neighborhood search heuristic for fleet deployment problems with voyage separation requirements

In this paper we propose an adaptive large neighborhood search heuristic for a ship routing and scheduling problem with voyage separation requirements. The voyage separation requirement is modeled as the minimum time elapsed between two consecutive sailings on a trade, and yields solutions with voyages fairly evenly spread over the planning horizon. Voyage separation requires the schedule of each ship to be synchronized with those of the others, since the start of service of a voyage could affect the feasible start time of another voyage. The proposed heuristic is compared with an exact algorithm on several instances, and yields good quality solutions within relatively short computation times.