A multi-neighborhood, lexicographic local search algorithm for the Integrated Healthcare Timetabling Competition 2024

Our entry to the Integrated Healthcare Timetabling Competition 2024 (IHTC-2024) is a heuristic, local search algorithm that uses multiple neighborhoods and manages hard and soft constraint violations lexicographically. Our approach has been largely structured around the ROAR-NET API specification, although with some modifications focusing on efficiency. The search space consists of both infeasible and feasible solutions. We preprocess the instance to discard some provably infeasible assignments. The algorithm then employs two metaheuristics in sequence: Simulated Annealing followed by Iterated Local Search. Both make use of multiple neighborhoods to navigate the search space and efficiently evaluate moves. Because the algorithm takes parameters as input, it can be run with different parameter values, giving rise to various possible configurations. Our final submission exploits the four thread limit of the competition by running a portfolio of four complementary configurations in parallel and then returning the best solution found. In the first phase of the competition, on the 30 public instances, our algorithm achieved the best results, obtaining 13 of the best-known competition upper bound results. In the second and final phase, on the 30 hidden instances, our algorithm ranked second overall and first in the open-source category.