Abstract:
This study addresses the home health care routing and scheduling problem (HHCRSP), considering the high randomness in patient service time and caregiver travel time, coupled with the differentiated priorities among patient groups. Traditional deterministic optimization approaches struggle to balance the robustness and efficiency in scheduling under such conditions. To tackle these challenges, this study proposes innovative solutions at both modeling and algorithmic levels. At the modeling level, a distributionally robust optimization (DRO) framework is introduced to construct an ambiguity set based on first-order moments and absolute deviation moments, where the distributional uncertainty of random variables are captured. This allows the establishment of a DRO model that maximizes total priority-based revenue while controlling time-related risks, without relying on exact probability distributions. At the algorithmic level, an exact solution approach is designed to address the computational difficulties arising from the complex constraints. By efficiently generating cutting planes and implementing convergence strategies, the algorithm enhances solving efficiency and solution stability. Through comprehensive numerical experiments, the proposed DRO model is compared against classical stochastic programming and deterministic models. Results demonstrate that the DRO model exhibits superior robustness under uncertainty. It effectively balances service efficiency and risk control by adjusting confidence levels, enabling decision-makers to achieve a trade-off between service quality and operational costs based on actual risk preferences. Furthermore, the proposed exact algorithm exhibits notably superior efficiency over commercial solvers in test cases involving complex parameter combinations, providing efficient and reliable decision support for HHCRSP.