A Heuristic Algorithm Based on Beam Search and Iterated Local Search for the Maritime Inventory Routing Problem

This work uses a pure heuristic approach to address the deterministic Maritime Inventory Routing Problem (MIRP). The method combines a Beam Search algorithm, guided by a greedy heuristic and refined by an Iterated Local Search (ILS) with local search procedures. A novel solution representation and auxiliary data structures are introduced to ensure feasibility and efficiency during the search. Computational experiments on MIRPLib's Group 2 instances show that the approach yields high-quality solutions within reasonable times, improving best-known results for ten out of 72 instances. The method is flexible, tuned to available runtime, and competitive with state-of-the-art matheuristics, especially for large-scale instances.