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