Neighborhood-reduction local search for large-scale patient path scheduling in multi-department examinations

Wang, Yang, Zhang, Huan, Wei, Zequn, Wilbaut, Christophe, Hanafi, Saïd
OR Spectrum · Springer Nature · 2026-09-05 · DOI: 10.1007/s00291-026-00873-y

Abstract

The patient path scheduling problem studied in this work is inspired by a real-world case from a large comprehensive hospital in China, where patients must visit multiple medical departments, requiring efficient scheduling of their examination paths. We introduce a new large-scale patient path scheduling problem that minimizes patient non-treatment time, reflecting the perspective of patient satisfaction. We consider the time patients spend walking between departments and waiting for treatment outside the departments, as well as environmental factors that may influence patients’ waiting experience. We first present a mixed integer programming model and solve it via the Gurobi optimization solver. To address large-scale benchmark instances with up to 1000 patients and 6 types of examinations, we propose an effective neighborhood reduction based local search algorithm. The algorithm distinguishes itself by employing an original neighborhood reduction strategy to avoid unpromising neighboring solutions and a dedicated rollback strategy to intensify the search. Computational results on 60 benchmark instances demonstrate that our algorithm is competitive compared to the Gurobi solver and three greedy algorithms used in real-world hospital settings. The key components of the algorithm are analyzed to understand its behavior. Moreover, we show how hospitals can leverage this study under different patient numbers, demonstrating that our approach is particularly beneficial in large-scale settings.

Read at publisher →

Similar articles