The ship routing and scheduling problem with pickup and delivery in the oil industry: modeling and exact solution methods

Abstract

The object of study of this doctoral research is the ship routing and scheduling problem with pickup and delivery and time windows in the oil industry. This combinatorial optimization problem belongs to the class NP-hard and solving it can be challenging in practice. In this project we aim to develop mathematical programming models to appropriately represent the problem and study exact solution methods. A case study will be developed in a Brazilian oil company which produces crude oil in offshore platforms and transport it to the terminals on the coast. To accomplish the industry requirements, further practical constraints will have to be added to the classical pickup and delivery problem, which generally make the problem harder to be solved in real situations. The main objectives of this project are: (i) propose mixed integer programming models for the specific case of the Brazilian company, (ii) develop exact methods to solve the models which will be proposed, such as branch-and-cut and branch-and-price, (iii) analyze and compare the performances of the proposed methods using instances from the literature and real-life data provided by the company. Keywords: ship routing, pickup and delivery, exact methods, branch-and-cut, branch-and-price (AU)