A GRASP × ILS for the vehicle routing problem with time windows, synchronization and precedence constraints
Résumé
Efficient use of resources while ensuring quality services points the attention of Home Health Care structures (HHC). HHC structures propose keeping at home patients who do not necessarily need full hospitalization, and enabling people who suffered serious illnesses to follow the care from their own home. Habitually, asked services have to be performed at specific times, and may require the intervention of several qualified caregivers related by precedence constraints. These structures have the concern to reduce product consumption costs, limit losses and provide high quality services. Their main budgetary item is defined by the personal salary, which is incompressible. So, costs should be reduced on other posts. In this context, personal travel cost has a major importance in the spending of the institutions, which seems necessary to optimize. Moreover, patient satisfaction is also a significant criterion in improving the service quality of such structures. Therefore, developing an effective caregivers planning require the use of optimization methods and decision tools. In this article, this issue is modeled as a particular variant of vehicle routing problem with time windows and timing constraints, where some patients ask for more than one visit simultaneously or in a given priority order, called as the VRPTW-SP. Timing constraints handled in this paper make the problem realistic that are more difficult to solve than VRPTW. The VRPTW-SP is a challenging and novel optimization problem, whose objective is the minimization of the caregivers travel cost added to the non preferences toward caregivers. To solve this problem, a Mixed Integer Linear Program, a greedy heuristic, two local search strategies and three metaheuristics are proposed, one being a hybridization of the two others. Experiments are conducted on new instances derived from the literature. As the metaheuristics share the same components the positive contribution of the hybridization is proved on the VRPTW-SP by statistical tests.