Optimization approaches to a routing and scheduling problem of oil tankers

Abstract This study analyzes a routing and scheduling problem of cabotage oil ships motivated by the actual operation of an oil company along the Brazilian coast. Maritime transportation costs from offshore platforms to coastal terminals are an important issue in the search for operational excellence in the oil industry, and the prospects for growth in oil exploration in Brazil have made operations more demanding for agile and effective decision support systems (DSS). This paper presents an optimization approach to deal with this problem consisting of a mixed integer linear (MIP) programming model and an MIP heuristic known as relax and fix. The problem is formulated as a pickup and delivery vessel routing with time windows and heterogeneous fleet which minimizes the costs of fuel consumption of ships and freight contracts. In addition to the usual routing constraints, it also considers specific restrictions of oil maritime transportation problems. Numerical experiments with this approach are presented for a set of real data of the company, confirming that the optimization method is able to find good solutions for moderate-size problem instances.