Nested iterated local search algorithm with set partitioning for the multi-compartment vehicle routing problem

This paper addresses the Multi-Compartment Vehicle Routing Problem (MCVRP), where vehicles with multiple compartments must deliver different products under capacity constraints. We propose a hybrid metaheuristic combining Iterated Local Search (ILS), Simulated Annealing (SA), and Large Neighborhood Search (LNS). The method follows an ILS framework with a Metropolis-based acceptance criterion to explore non-improving solutions, while diversification is achieved through an LNS ruin-and-recreate mechanism. Additionally, a set partitioning model is solved over a pool of routes generated during the search, enabling effective recombination of high-quality routes. This integration enhances solution quality by intensifying the search in promising regions. Computational experiments on benchmark instances show that the proposed approach produces high-quality solutions within competitive computational times, highlighting the effectiveness of combining ILS, SA, LNS, and set partitioning for the MCVRP.