Optimizing multiship routing and scheduling with constraints on inventory levels in a Brazilian oil company

DOIhttp://doi.org/10.1111/itor.12478
Published date01 July 2018
Date01 July 2018
Intl. Trans. in Op. Res. 25 (2018) 1163–1198
DOI: 10.1111/itor.12478
INTERNATIONAL
TRANSACTIONS
IN OPERATIONAL
RESEARCH
Optimizing multiship routing and scheduling with constraints
on inventory levels in a Brazilian oil company
Am´
elia de Lorena Stanzania,Vit
´
oria Purezaa, Reinaldo Morabitoa,
Bruno Jensen Virginio da Silvaa, Denise Yamashitaaand Paulo C´
esar Ribasb
aDepartment of Production Engineering, Universidade Federal de S˜
ao Carlos, Via WashingtonLuiz, km 235,
S˜
ao Carlos – SP, Brazil
bResearch and DevelopmentCenter, PETROBRAS, Av. Hor´
acio de Macedo, 950, Ilha do Fund˜
ao, Rio de Janeiro – RJ,
Brazil
E-mail: mel.stanzani@hotmail.com [Stanzani]; vpureza@dep.ufscar.br [Pureza]; morabito@ufscar.br [Morabito];
brunojen@gmail.com [Silva]; dsyamashita@gmail.com [Yamashita];paulo.ribas@petrobras.com.br [Ribas]
Received 27 September 2015; receivedin revised form 23 August 2017; accepted 25 September 2017
Abstract
This study addresses a real-life multiship routing and scheduling application with inventory constraints that
arises in pickup and delivery operationsof different types of crude oil from various offshore oil rigs (platforms)
to coastal terminals. Oil transportation largely results from the need to maintain inventories at each supply
point (platform) between minimum and maximum levels, considering production rates in these operational
points, and to meet demands of different oils in the terminals within the planning time horizon. Routing and
scheduling of the available fleet aims to obtain solutions of minimum total costs,subject to various constraints
such as the maximum volume of cargo carried on each ship,simultaneous cargo unloading in some terminals,
conditions that rule ship docking in offshoreplatforms and terminal berths, among others. In this research, we
modify and extend inventory constrained maritime routingand scheduling models to appropriately represent
the problem of a case study at a Brazilian company and to solve small-to-moderate instances based on real
data. We also present a matheuristic to deal with larger problem instances. Solution evaluation by company
experts indicates that the model and this hybrid heuristic properly represent the problem and highlights the
potential of their application in practice.
Keywords:multiship routing and scheduling; inventory constrained maritime routing problems; crude oil transportation;
mixed-integer programming; matheuristic; oil industry; OR practice
1. Introduction
This study considers a multishiprouting and scheduling problem with constraints on inventory levels
faced by a Brazilian company engaged in the exploration, production, refining, transportation, and
C
2017 The Authors.
International Transactionsin Operational Research C
2017 International Federation of OperationalResearch Societies
Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,
USA.
1164 A. de Lorena Stanzani et al. / Intl. Trans.in Op. Res. 25 (2018) 1163–1198
Fig. 1. Illustration of part of the supply chain of the oil company with emphasis on the stagesaddressed in the present
case study (adapted from Rocha et al., 2009). [Colour figure can be viewed atwileyonlinelibrary.com]
commercialization of large volumes of crude oils and their derivatives. The oils originate from the
exploration of underground wells, 95% of which is extracted from offshore oil rigs (platforms), or
are imported from other producing countries. In either case, oils of different types are transported
by vessels to coastal transshipment units (terminals) and then shipped by oil pipelines to refineries
and consuming countries. Transportation is carried out by a heterogeneous fleet of oil tankers,
where each ship is able to carry different oil types at the same time. Figure 1 illustrates part of this
supply chain, with emphasis on the stages addressed in the present case study: the production of
crude oil at the platforms and the transportation to coastal terminals. There are dozens of ships,
platforms, and terminals, and while each platform produces few types of oil, the terminals may
demand multiple types. Each platform contains a facility that temporarily stores the production
before transportation takes place. If a terminal receives a quantity of oil that exceeds its storage
capacity, this surplus is transferred to other places.
As other maritime transportation applications, oil pickup and delivery is a very complex oper-
ation. On one hand, the high costs and long cargo loading and unloading times suggest that the
traveled distance (or rather, its travel time or cost) should be minimized and that ship docking
should occur as little as possible. On the other hand, platforms must operate continuously not
only to meet the high demand, but also because of the prohibitive opportunity costs that incur if
platform production is interrupted, which may require frequent ship visits to platforms given their
limited storage capacity. In other words, the stocks in the platforms must not exceed their stock
capacities and the platform production must not stop because of missing transportation possibili-
ties. Considering these conflicting goals, the operation should attempt to coordinate inventory and
transportation management, aiming at simultaneously determining optimal stocks at the platforms
and a strategy of distribution that meets the oil demands of the terminals within the planning time
horizon.
These characteristics define this inventory constrained routing problem (ICRP) as a particular
case of an integrated pickup and delivery inventory routing problem (IRP), for which the costs of
keeping products in stock are not considered. In addition to the heterogeneous fleet and multicom-
modity flows, this particular case also involves meeting the demands of specific oils at the terminals,
a limited number of berths at the terminals, physical limitations of berths restricting ships docking
C
2017 The Authors.
International Transactionsin Operational Research C
2017 International Federation of OperationalResearch Societies
A. de Lorena Stanzani et al. / Intl. Trans.in Op. Res. 25 (2018) 1163–1198 1165
with a maximum length and draft, ships and platforms with or without dynamic positioning (DP)
devices restricting the maximum allowable cargo on board for docking, and the minimum and
maximum stock levels at each platform, among others. Unlike classical IRPs where there is a
trade-off between inventory cost and transportation cost (Dror and Ball, 1987; Federgruen and
Simchi-Levy, 1995; Yu et al., 2008; Shiguemoto and Armentano, 2010; Archetti et al., 2014), in this
problem the capital and other costs of maintaining the oil inventory are not influenced by the oil
transportation.
In this context, this paper addresses the planning of ship routes from offshore platforms to
terminals so that the costs of fuel consumption and the costs associated with ship dockings are
minimized (variable costs) considering uninterrupted production in the platforms. Basically, the
problem is to decide how much of each crude oil should be carried by each ship from the platforms
to the terminals, subject to the inventorylevel of each oil in each platform being maintained between
certain levels that are set by the platform production rates and the storage capacities, in order to
meet the oil demands of the terminals. Although some studies in the literature focused on similar
problems, to the best of our knowledge, there is no other research that has addressed the specific
problem described here. The objective of this paper is to study and proposetwo solution approaches
for this problem:a mathematical programming formulationsolved by general-purpose optimization
software (such as CPLEX or Gurobi) and an ad hoc heuristic approach.
The mathematical programming formulation can be seen as an extensionof two known inventory
constrained maritime routing and scheduling models (Christiansen, 1999; Al-Khayyal and Hwang,
2007). Our formulation considers characteristics of these two mentioned models, as multiproduct
inventory constrained scheduling and pickup and delivery routes of a heterogeneous fleet of ships,
but with the additional practical conditions and constraints that arise in the Brazilian oil company.
The resulting formulation was then used to solve optimally small- to moderate-sized problem
instances using data collected in a case study performedat the oil company, using the solver CPLEX.
The inherent difficulties of solving larger problem instances with the model (or even obtaining
feasible solutions) using CPLEX motivated the development of a heuristic approach. As pointed
out by different authors, practical ship routing problems often pose additional complexities and
opportunities, and although the problems become harder to solve when introducing these practical
characteristics, better solutions can be obtained for real-life instances by using advanced heuristics
(Christiansen et al., 2011; Fagerholt and Ronen, 2013; Romero et al., 2013; Branchini et al., 2015).
Our heuristic consists of two main procedures: a multistart heuristic (with a constructive phase
and two improvement phases) and a local search procedure. Since the latter uses mathematical
programming techniques to produce neighbor solutions, the approach can be seen as a hybrid
method or a matheuristic.
The model and the matheuristic deal with the conflicting objectives of a push-type system rep-
resented by the continuous oil production on the offshore platforms, aiming to avoid platform
production interruptions due to storage capacity limitations, and a pull-type system represented
by the different oil demands of the terminals (which reflect the oil demands of the refineries), aim-
ing to avoid refinery supply interruptions owing to transportation capacity limitation of the fleet.
The main contributions of this study are twofold: to present a mixed-integer programming (MIP)
model that appropriately represents the problem and can be solved by an optimization solver for
small-to-moderate instances, and a matheuristic to deal with larger problem instances. The aim is
to contribute to the practice of operations research. This study also helps to improve the company’s
C
2017 The Authors.
International Transactionsin Operational Research C
2017 International Federation of OperationalResearch Societies

To continue reading

Request your trial

VLEX uses login cookies to provide you with a better browsing experience. If you click on 'Accept' or continue browsing this site we consider that you accept our cookie policy. ACCEPT