A GRASP × ILS for the vehicle routing problem with time windows, synchronization and precedence constraints. (30th December 2016)

• Record Type: Journal Article
• Authors: Ait Haddadene, Syrine Roufaida; Labadie, Nacima; Prodhon, Caroline
• Is Part Of: Expert systems with applications. Volume 66(2016)
• Page Start: 274
• Page End: 294
• Publication Date: 2016-12-30
• Subjects: Vehicle routing problem -- Synchronization constraints -- Precedence constraints -- MILP -- Metaheuristic; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2016.09.002
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: New routing problem encountered in the field of Home Health Care is studied. Two types of synchronization constraints within a single model are modeled. Simultaneously synchronization constraints and patient preferences are handled. Our meta-heuristic is able to solve to optimality 23 of 37 benchmark instances. Three upper bounds given by Cplex Solver are improved. Abstract: 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.