Optimization of the Stochastic Home Health Care Routing and Scheduling Problem with Multiple Hard Time Windows

Home health care (HHC) aims to assist patients at home and to help them to live with greater independence, avoiding hospitalization or admission to care institutions. The patients should be visited within their availability periods. Unfortunately, the uncertainties related to the traveling and caring times would sometimes violate these time windows constraints, which will qualify the service as poor or even risky. This work addresses the home health care routing and scheduling problem (HHCRSP) with multiple hard/fixed time windows as well as stochastic travel and service times. A two-stage stochastic programming model recourse (SPR model) is proposed to deal with the uncertainty. The recourse is to skip patients if their availability periods will be violated. The objective is to minimize caregivers’ traveling cost and the average number of unvisited patients. Monte Carlo simulation is embedded into the genetic algorithm (GA) to solve the SPR model. The results highlight the efficiency of the GA, show the complexity of the SPR model, and indicate the advantage of using multiple time windows.