2774. A multi-neighborhood, lexicographic local search algorithm for the Integrated Healthcare Timetabling Competition 2024
Invited abstract in session MD-10: Integrated Healthcare Timetabling Competition III, stream Automated Timetabling.
Monday, 14:30-16:00Room: Clarendon SR 1.06
Authors (first author is the speaker)
| 1. | Ahmad Mahir Othman
|
| Dept. of Mathematics & Computer Science, University of Southern Denmark | |
| 2. | Marco Chiarandini
|
| Dept. of Mathematics & Computer Science, University of Southern Denmark |
Abstract
The Integrated Healthcare Timetabling Competition 2024 (IHTC-2024) focused on the integration of three decision-making tasks: patient admission scheduling, operating theater planning and nurse-to-room assignment. The algorithm we submitted builds upon the ROAR-NET API specification and consists of a classical local search heuristic that uses multiple, small-scale neighborhood structures to address the different decision tasks and handles hard and soft constraint violations lexicographically.
Efficiency has been the primary guideline for the implementation. The search space is reduced by adopting a solution representation that implicitly satisfies some hard constraints. Patients are restricted to only be admitted on dates and rooms that satisfy the hard constraints affecting them independently from other decisions. Neighboring solutions are assessed incrementally over all neighborhood structures. Finally, Python was replaced by C++ after the first draft of the solver.
The high-level search strategy shares the run time between simulated annealing, first, for exploration and iterated local search, later, for exploitation. To take advantage of the 4-threads made available by the rule of the competition, we selected, offline, a set of four algorithm configurations and schedules by solving optimally a sequence of set covering problems with cardinality constraints. Our entry ranked among the best five out of 32 submissions.
Keywords
- Metaheuristics
- Combinatorial Optimization
- Scheduling
Status: accepted
Back to the list of papers