Ship Routing with Pickup and Delivery for a Maritime Oil Transportation System: MIP Modeland Heuristics

This paper examines a ship routing problem with pickup and delivery and time windowsfor maritime oil transportation, motivated by the production and logistics activities of an oil companyoperating in the Brazilian coast. The transportation costs from offshore platforms to coastal terminalsare an important issue in the search for operational excellence in the oil industry, involving operationsthat demand agile and effective decision support systems.

This paper presents an optimizationapproach to address this problem, based on a mixed integer programming (MIP) model and a noveland exploratory application of two tailor-made MIP heuristics, based on relax-and-fix and timedecomposition procedures. The model minimizes fuel costs of a heterogeneous fleet of oil tankersand costs related to freighting contracts.

The model also considers company-specific constraints foroffshore oil transportation. Computational experiments based on the mathematical models and therelated MIP heuristics are presented for a set of real data provided by the company, which confirmthe potential of optimization-based methods to find good solutions for problems of moderate sizes.