A relax-and-fix and fix-and-optimize algorithm for a Maritime Inventory Routing Problem

摘要

The Maritime Inventory Routing Problem (MIRP) has gained attention in combinatorial optimization in the last decades. The problem has several variations, mostly originated from real-world problems. This work presents a literature review of the solution approaches proposed for different MIRP variations, focusing on matheuristic methods that combine heuristic and optimal approaches and are frequently used to solve MIRPs. This work also studies the use of Relax-and-Fix and Fix-and-Optimize matheuristics for solving a specific MIRP variant proposed in the literature. The proposed algorithms were tested over two discrete-time formulations for which different components such as valid inequalities and additional constraints were proposed. Several computational tests were performed to evaluate the contribution of the formulation components and algorithms features on the solution quality and processing time. An automatic configuration tool was used to define the parameter values for the algorithms, as well as the choice of the formulation components to be used in the tests. The results demonstrated that the proposed algorithms are potentially effective for solving the MIRP when applied to a public dataset, obtaining three new best-known solutions from a total of twenty-eight instances.