The Home Care Scheduling Problem: A modeling and solving issue

Abstract

The Home Care Scheduling Problem (HCSP) consists of designing a set of routes for medical service suppliers to visit a number of patients located at different places and asking for a set of medical tasks. The object of the HCSP is to define the required set of routes where the assigned workforce will travel in order to minimize the overall travelled distance. Therefore, the solution will define first the teams (crew) that will travel together for serving particular subset of patients. Then, the route of each team is defined. The problem shows a hierarchical nature where the solving algorithm should build first the service team that defines partially the set of potential customers to serve and then look for the routes to follow. In this paper, we studied and solved the HCSP after reviewing the literature on the HCSP. We modeled the HCSP as a multilevel (hierarchical) combinatorial optimization problem. Then, we focused on particular variant of the HCSP which is the Multiple Traveling Salesman Problem with Time windows (MTSPTW) where we implemented a Tabu Search based heuristic to solve a modified version of Solomons instances. The obtained results are reported, commented and validated.