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

Abstract

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.