Routing and scheduling in home health care with time slot selection

An increasing number of healthcare providers now offer patients the option of booking appointment time slots online. As patients’ preferences for time slots and caregivers vary with personal circumstances, determining which time slots to post online constitutes an emerging operational challenge. To address this issue, this study proposes to simultaneously optimize time slot selection and its subsequent dependent decisions, including healthcare providers’ routing and scheduling. The problem is formulated as a mixed-integer programming model, in which patients’ choice behavior is captured via a discrete choice model. The objective is to minimize caregivers’ routing costs and the expected penalty costs incurred when patients are not served within the designated time slots, while maximizing patient satisfaction, influenced by caregivers’ skill levels and patients’ familiarity with them. To solve the problem, a tailored Adaptive Large Neighborhood Search (ALNS) algorithm, integrated with a time-slot perturbation mechanism and several newly designed operators, is developed. Numerical experiments are conducted on instances of varying scales, and the results demonstrate that the proposed ALNS algorithm significantly improves both solution quality and computational efficiency. Furthermore, sensitivity analyses on key model parameters including the number of the time slots selected to post online, utility coefficients and maximum skill level deviation reveal that certain parameters exert a particularly strong impact on the overall system performance. These findings provide theoretical foundations and practical implications for optimizing time slot selection to enhance the cost-efficiency of healthcare services.