A Column Generation-Based Gossip Algorithm for Home Healthcare Routing and Scheduling Problems

Home healthcare (HHC) is a service that dispatches caregivers to people in need of healthcare who live in the home. The task assignment and route generation for caregivers can be formulated as an extension of the well-known vehicle routing problem with time windows (VRPTW). Currently, the most successful exact algorithms for VRPTW are based on a framework combining column generation (CG) and branching. Although such methods could be successful for HHC routing and scheduling problem (HHCRSP) as well, fast approximate algorithms are appealing, especially for large problems. In an early version of this paper, we employed a heuristic distributed gossip algorithm to solve HHCRSP. In this paper, we integrate the gossip algorithm with a local solver based on CG, which makes it an effective algorithm for larger problem instances. As it will be shown with extensive numerical experiments, for large problem instances, gossip-CG performs better than the pure CG. Note to Practitioners-The task of routing and scheduling caregivers for HHC providers can be formulated as a mathematical problem that is theoretically challenging to solve to optimality for large-scale problems involving many clients and caregivers. Although extensive research and tools for tackling this problem already exist, in practice, even in developed countries, it is still common to rely on schedules generated manually by staff. What we present in this paper is the summary of our theoretical work on tackling such problems. The benefit of the framework that we propose, the CG-based gossip method, is that it can be preempted at any time if the staff requires to obtain a good schedule as soon as possible. If ample time is available, one can let our algorithm to run for a longer period of time to generate even shorter routes.