A robust optimization for a home health care routing and scheduling problem with consideration of uncertain travel and service times

In today’s competitive environment, one of the most critical objectives for Home Health Care (HHC) companies is to meet the demand of patients in a timely fashion. According to the feedback from HHC companies, caregivers have to deal with some uncertainties when carrying out a given schedule to visit their patients. However, a majority of the previous work only considers the deterministic models which ignore the uncertainties, and solutions obtained by these deterministic models are usually less robust in case of any possible changes in practical situations. Inspired by this point, in this work, we formulate a model for an HHC Routing and Scheduling Problem with taking into account uncertain travel and service times, from the perspective of Robust Optimization (RO). Specifically, the non-deterministic variables are defined based on the theory of budget uncertainty, and then the arrival time of each caregiver is rewritten as a complicated recursive function. After that, Gurobi Solver, Simulated Annealing, Tabu Search, and Variable Neighborhood Search are adapted to solve the model respectively. Finally, a series of experiments have been performed to validate the proposed models and algorithms. Experimental results from Monte Carlo simulation highlight the strength of considering uncertainties when modeling the problem. Additional, the influences of other characters in instances, like the width of time-window, distributed location have also been empirically analyzed. Finally, the comparison performed between the solutions obtained by the stochastic model and the RO model also demonstrates the advantage of the RO model. This work provides a valuable framework for HHC companies to make a robust schedule when arranging the caregivers.