Joint Optimization of Service Routing and Scheduling in Home Health Care

Yi Zhang, Zhenzhen ZhangarXiv 2025 · DOI · arXiv

Abstract

The growing aging population has significantly increased demand for efficient home health care (HHC) services. This study introduces a Vehicle Routing and Appointment Scheduling Problem (VRASP) to simultaneously optimize caregiver routes and appointment times, minimizing costs while improving service quality. We first develop a deterministic VRASP model and then extend it to a stochastic version using sample average approximation to account for travel and service time uncertainty. A tailored Variable Neighborhood Search (VNS) heuristic is proposed, combining regret-based insertion and Tabu Search to efficiently solve both problem variants. Computational experiments show that the stochastic model outperforms the deterministic approach, while VNS achieves near-optimal solutions for small instances and demonstrates superior scalability for larger problems compared to CPLEX. This work provides HHC providers with a practical decision-making tool to enhance operational efficiency under uncertainty.

Introduction

As the global population ages, the demand for Home Health Care (HHC) services—such as at-home medical tests and nursing visits—is skyrocketing. Traditionally, HHC scheduling is highly rigid: patients unilaterally pick appointment times, and administrators try to build driving routes around them. This decoupled approach leads to significant routing inefficiencies.

Furthermore, real-world logistics are inherently uncertain. Traffic fluctuates, and medical tasks take unpredictable amounts of time. If a caregiver arrives early, they sit idle; if a task runs long, subsequent patients are left waiting. Both scenarios incur financial and quality-of-care penalties. This research addresses the challenge of jointly optimizing service start times and caregiver routes while explicitly accounting for the randomness of travel and service durations.

The VRASP Model and Methodology

The authors formulate the problem as the Vehicle Routing and Appointment Scheduling Problem (VRASP). The model seeks to minimize a total cost function comprising fixed scheduling costs, travel costs, overtime costs, and tardiness penalties.

Table of parameters and variables used in the VRASP model.

Handling Uncertainty

To move beyond a baseline deterministic model, the researchers utilize Sample Average Approximation (SAA). SAA uses Monte Carlo sampling to generate multiple scenarios of travel and service times. This transforms the complex stochastic problem into a deterministic equivalent that minimizes the expected cost across all sampled scenarios, leading to more robust schedules.

The Variable Neighborhood Search (VNS) Heuristic

Because VRASP is NP-hard, exact solvers like CPLEX struggle with even moderately sized instances. To solve this efficiently, a tailored VNS heuristic was designed:

  1. Initialization: Uses the Clarke-Wright savings algorithm to build initial routes.
  2. Shaking (Diversification): Destroys parts of the current solution using neighborhood strategies (e.g., removing customers with high relocation costs) and rebuilds them using a Regret-Based Insertion algorithm.
  3. Local Search (Intensification): Employs Tabu Search with 2-Opt and Swap operators to aggressively optimize routes while avoiding local optima.
The Regret-Based Insertion algorithm used in the VNS shaking phase.

Key Results and Insights

The performance of the VNS heuristic and the stochastic model was evaluated using synthetic test instances ranging from 5 to 40 patients. Key findings include:

  • Superior Scalability: For instances with 30 or 40 patients, CPLEX failed to find a solution within a 30-hour limit. In contrast, the VNS algorithm successfully solved these larger instances. For a 10-patient stochastic problem, VNS achieved a ~40x speedup over CPLEX.
  • Near-Optimal Accuracy: On small instances where exact solutions were possible, VNS showed an average optimality gap of just 0.37% for the deterministic model and 0.56% for the stochastic model.
  • The Value of Stochastic Planning: Planning for a distribution of scenarios (SAA) consistently produced lower expected total costs in practice compared to the deterministic approach, which relies on deceptive averages.
  • Efficiency through Joint Optimization: Treating scheduling and routing as interdependent variables allows providers to negotiate appointment times that drastically reduce caregiver idle time and travel distances.

Conclusion

This study demonstrates that joint optimization of routing and scheduling, combined with stochastic modeling, significantly improves HHC operational efficiency. While the current model uses fixed appointment times, future work could incorporate flexible time windows to further enhance routing options. The proposed VNS heuristic provides a scalable, high-accuracy tool for real-world healthcare logistics providers.

Summary updated

Abstract

The growing aging population has significantly increased demand for efficient home health care (HHC) services. This study introduces a Vehicle Routing and Appointment Scheduling Problem (VRASP) to simultaneously optimize caregiver routes and appointment times, minimizing costs while improving service quality. We first develop a deterministic VRASP model and then extend it to a stochastic version using sample average approximation to account for travel and service time uncertainty. A tailored Variable Neighborhood Search (VNS) heuristic is proposed, combining regret-based insertion and Tabu Search to efficiently solve both problem variants. Computational experiments show that the stochastic model outperforms the deterministic approach, while VNS achieves near-optimal solutions for small instances and demonstrates superior scalability for larger problems compared to CPLEX. This work provides HHC providers with a practical decision-making tool to enhance operational efficiency under uncertainty.
BibTeX
@misc{zhang2025joint,
  author = {Yi Zhang and Zhenzhen Zhang},
  title = {{Joint Optimization of Service Routing and Scheduling in Home Health Care}},
  year = {2025},
  eprint = {2505.20474},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.20474},
  howpublished = {arXiv},
}
Figure