A novel three-stage matheuristic for the capacitated minimum spanning tree problem with time windows

This work addresses the capacitated minimum spanning tree problem with time windows (CMSTPTW), which considers capacity constraints for the subtrees and time windows. CMSTPTW belongs to the NP-hard family, making it a computational challenge to find high-quality solutions efficiently. Therefore, this work proposes a novel three-stage matheuristic (3SM) approach that combines modified Prim's algorithm, an iterated local search (ILS), and a mixed-integer linear programming (MILP) model solved with a general-purpose solver. The first stage involves generating an initial solution using Prim's algorithm adapted to the CMSTPTW. Once the initial solution is generated, the second stage consists of solving the MILP by a general-purpose solver considering a given time limit and using the best solution found by 3SM as a warm start. In the last stage, the 3SM approach employs an ILS with various perturbation and local search operators to further refine and optimize the solution. Moreover, the ILS uses two additional strategies: a set of elite solutions to preserve the best solutions throughout the algorithm's execution and a penalization procedure to navigate the infeasible solutions space. These strategies, along with effective parameter tuning, complement each other to increase the algorithm's exploration and enhance the quality of the final solution. The proposed algorithm's performance is evaluated on an existing set of instances and in two new additional sets of larger instances that are proposed. The computational results show that the 3SM approach outperforms the state-of-the-art algorithms and the general-purpose solver in terms of solution quality within a given time limit.