A multi-start heuristic for the ship routing and scheduling of an oil company

In this paper, we study a real-life pickup and delivery problem that arises in a petroleum production company. The problem consists of determining the ship routing and scheduling in order to collect crude oil extracted from offshore platforms and to deliver it to ports (terminals). While several realistic constraints present in the operation are usually found in the literature on maritime routing and scheduling, such as time windows, heterogeneous fleet and limited ship capacity, other constraints are seldom studied. Some seldom studied constraints considered in this paper are: flexible draft restrictions that depend on the port and the amount of products loaded on to the ship, capacity restrictions for docking that are dependent on a combination of the type of ship and platform, multiple visits to platforms and terminals during the planning horizon, among others. The aim is to minimize transportation costs and reduce the number of consecutive dockings in the platforms and terminals. In order to solve problem instances of large realistic sizes, we propose an effective multi-start heuristic based on biased dispatching rule, insertion and exchange moves. Computational experiments in real-life problems with up to 83 pickups/deliveries and 25 ships show that the proposed heuristic provides good solutions within relatively short computation times. We also analyze the performance of the heuristic when it is adapted, with minor modifications, to be tested in benchmark problem instances of the literature.