Collaborative scheduling and routing of home healthcare service across multiple communities

As an important home health care mode in China, the home-community service mode focuses on the impact of healthcare centers in each community and coordinates the medical resources between communities. In this paper, we propose a new collaborative home health care routing and scheduling problem in multiple service centers (C-HHCRSP). In addition to the traditional routing and scheduling decisions, C-HHCRSP also assigns a working center for each highly qualified caregiver who can provide health services across multiple communities. This problem is challenging due to the presence of complex, realistic constraints such as time windows, mandatory lunch breaks, synchronized visits, and downgrading of services. We first formulate the problem as a mixed integer programming model, which is solved by CPLEX. Then, we propose an adaptive large neighborhood search (ALNS) algorithm that integrates new problem-specific destroy and repair operators. To further improve the performance of ALNS, we propose two post-optimization techniques, which are based on heuristic strategies and a set partitioning model, respectively, resulting in the enhanced algorithms ALNS-HS and ALNS-SP. Tested on 104 benchmark instances, ALNS-HS shows a competitive performance with CPLEX on small instances. For large instances, CPLEX fails to find feasible solutions, and we compare our heuristic algorithms with a classic large neighborhood search algorithm to demonstrate their superiority. Additional analyses are performed to verify the roles of the components of the proposed algorithms.