Dynamically dealing with requests in a stochastic multi-period home healthcare problem with consistency constraints

This paper analyzes a Multi-Period Stochastic Vehicle Routing Problem in the healthcare sector. Patients with unknown locations and demands ask for domiciliary care services with unknown temporal distributions. Requests from patients arrive over time to a nurse agency that has to plan the activities of a fleet of nurses over several days. Based on daily information, the agency decides if a new patient can be accepted, earning the corresponding revenue, or assigned to an external provider. To guarantee high service satisfaction, the agency schedules the nurses' routing by guaranteeing consistency in nurse-patient assignments. The problem aims to plan nurses' routing to satisfy all requests of accepted patients while maximising the total profit measured as the difference between collected revenue and travelling costs. We propose different solution methodologies that either sequentially make short-sighted decisions or use a scenario-based strategy, leveraging historical data to predict future requests. All algorithms make use of an Adaptive Large Neighborhood Search and are validated on medium-sized instances. Managerial insights on the impact of consistency on the profit and its relation to date flexibility in patients' requests are provided. Interesting rules of thumb are derived from a case study conducted in the city of Brescia, Italy.