A multi-start heuristic for the ship routing and scheduling of an oil company. (October 2019)

• Record Type: Journal Article
• Authors: Yamashita, Denise; da Silva, Bruno Jensen Virginio; Morabito, Reinaldo; Ribas, Paulo César
• Is Part Of: Computers & industrial engineering. Volume 136(2019)
• Page Start: 464
• Page End: 476
• Publication Date: 2019-10
• Subjects: Maritime vehicle routing problem -- Pickup and delivery -- Oil industry -- Mixed-integer programming model -- Multi-start heuristics; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2019.07.039
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: We study a real-life pickup and delivery problem that arises in an oil company. Finding a feasible solution for this problem is already a challenging task. The heuristic is able to find near optimal solutions when applied to real problems. These heuristic solutions were considered of good quality by company experts. Abstract: In this paper, we study a real-life pickup and delivery problem that arises in a petroleum production company. The problem consists of determining the ship routing and scheduling in order to collect crude oil extracted from offshore platforms and to deliver it to ports (terminals). While several realistic constraints present in the operation are usually found in the literature on maritime routing and scheduling, such as time windows, heterogeneous fleet and limited ship capacity, other constraints are seldom studied. Some seldom studied constraints considered in this paper are: flexible draft restrictions that depend on the port and the amount of products loaded on to the ship, capacity restrictions for docking that are dependent on a combination of the type of ship and platform, multiple visits to platforms and terminals during the planning horizon, among others. The aim is to minimize transportation costs and reduce the number of consecutive dockings in the platforms and terminals. In order to solve problem instances of large realistic sizes, we propose an effective multi-start heuristic based on biased dispatching rule, insertion and exchange moves. Computational experiments in real-life problems with up to 83 pickups/deliveries and 25 ships show that the proposed heuristic provides good solutions within relatively short computation times. We also analyze the performance of the heuristic when it is adapted, with minor modifications, to be tested in benchmark problem instances of the literature.