Relax-and-fix heuristics for the Multi-Commodity PSV Planning Problem with Order Selection and Time Window Decisions

• Published in: Computers & industrial engineering 2023-03, Vol.177, p.109040, Article 109040
• Main Authors: Chagas, Rennan Danilo Seimetz, Filho, Virgílio José Martins Ferreira
• Format: Article
• Language: English
• Subjects: Offshore logistics; Order selection; Relax-and-fix heuristic; Supply vessel planning
• ISSN: 0360-8352
• DOI: 10.1016/j.cie.2023.109040

In Brazil, large oil reserves have been discovered in deep water over the years. The distance from the Brazilian coast as well as the depth of oil reserves leads to a great logistical effort from the point of view of supply operation. The literature on platform supply vessel (PSV) operations planning is rich, but few studies have focused on the order selection problem. In this work, we present a formulation for an order selection problem, called Multi-Commodity Supply Vessel Planning Problem with Order Selection and Time Window Decisions. This is a generalized model for multi commodity order selection problem where we introduce vessel reuse and time window decisions. We present a method to generate artificial instances that can be reproducible and applied in new works to encourage further studies in this field and solve this model by comparing two different ways to implement a relax-and-fix heuristic. The results show the importance of choosing the appropriate problem decomposition for designing a relax-and-fix heuristic. Our implementation based on a two-stage decomposition compared to the route-based one, equaled or exceeded solution quality and outperformed the processing time. •A generalized model for multi commodity order selection problem.•A formalized instance generation method that can be reproduced and adapted to new applications.•Two approaches to implement a relax-and-fix heuristic evidencing how the decomposition strategy affects results.