Improved MILP Formulation for Home Healthcare Scheduling and Routing with Multiple Depots

Abstract

Despite extensive research on home healthcare scheduling and routing problems (HHCSRP), a critical gap persists between mathematically optimal solutions and operationally feasible implementations. This paper demonstrates that constraints often considered redundant in vehicle routing formulations are essential for HHCSRP, where worker-depot assignments cannot be arbitrarily changed. We validate a widely cited multidepot HHCSRP MILP formulation using 42 real-world instances, revealing that 77.8% of optimal solutions contain operational violations, workers incorrectly assigned to arbitrary depots and unproductive direct depotto-depot routes without patient visits. Our main contribution is a refined formulation with explicit operational feasibility constraints that eliminate these violations, while improving computational efficiency on average by 40%. Comparative analysis using GUROBI and CPLEX solvers reveals instance-dependent performance patterns, with GUROBI achieving faster solving times for small to medium resource-constrained instances, and CPLEX producing superior solutions for large-scale, over-resourced problems. These findings underscore that operational validation must extend beyond standard optimisation metrics to verify real-world practicability, a persistent gap contributing to the scarcity of successful HHCSRP deployments in practice.