IACS-HCSP: Improved ant colony optimization for large-scale home care scheduling problems

The home care and scheduling problem (HCSP) consists on the design of a set of routes to be used by caregivers that provide daily assistance at specific times to patients located in a definite geographic area. In this study we propose a modified version of Ant Colony Optimization (ACO), called IACS-HCSP, to approach this task. In order to be used in this problem, ACO requires modifications in the problem representation and additional mechanisms to deal with constraints. We propose a dynamic neighborhood graph and an improved method that constructs the solution that improves its exploration capability over deterministic or greedy heuristic methods. This technique has been applied to a very large real world instance of HCSP for which results are available for comparison. IACS-HCSP is able to improve the previous results on this specific instance in terms of cost. At the same time it can be used to help decision making when there is a choice between competing objectives, because it finds a full range of feasible solutions with different equilibria between time and size of the required labor force.