Hybridizing a matheuristic with ALNS for the optimal collection and delivery of medical specimens

Abstract The past few years of the COVID‐19 pandemic outbreak have shown that optimal management of medical specimens is a key aspect of healthcare logistics, both for addressing the delivery of perishable items such as vaccines, and for ensuring the timely analysis of swabs and samples. Accordingly, recent optimization literature described the problem of optimal collection and delivery of medical specimens, modeled as a multitrip vehicle routing problem with time windows and a completion time objective function. Aiming to achieve good‐quality solutions in short computational times, this work describes a hybrid approach, combining a matheuristic construction phase with an adaptive large neighborhood search (ALNS). Our matheuristic relies on a clustering algorithm to yield subsets of the medical specimens that are optimally served by single vehicles of the fleet. The solutions of the matheuristic phase serve as starting points for the ALNS intensification phase. Extensive experimentation on both new and established benchmark problem instances shows that our hybrid method is able to match the optimality of the state of the art on small instances and outperforms the existing exact method by one order of magnitude on larger problems.