NSGAII enhanced with a local search for the vehicle routing problem with time windows and synchronization constraints

Syrine Roufaida Ait Haddadene (1) , Nacima Labadie (1) , Caroline Prodhon (1)

1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels

In the field of Home Health Care (HHC), the vehicle routing problem with time windows, synchronization, and precedence constraints (VRPTW-SP) involves finding the lowest-cost set of routes to visit patients requesting one or more services in a specific time window and during a fixed time service. Each patient has preference weights associated to the vehicles who are available to provide the requested service. To solve the problem, different variations for multi-objective met a-heuristic based on the Non-dominated Sorting Genetic Algorithm (NSGAII) are proposed. The considered objectives are the minimization of travel costs and the maximization of patients preferences. This problem was solved in a previous work as a single-objective variant, despite the conflicting nature of these two criteria. Numerical results are presented for instances with up to 73 patients. Metrics such as spacing, hyper-volume and the number of non dominated solutions are used to measure the quality of solutions.

Domaines: Recherche opérationnelle [math.OC]

Syrine Roufaida Ait Haddadene, Nacima Labadie, Caroline Prodhon. NSGAII enhanced with a local search for the vehicle routing problem with time windows and synchronization constraints. 8th IFAC Conference on Manufacturing Modelling, Management and Control MIM 2016, Jun 2016, Troyes, France. pp.1198-1203, ⟨10.1016/j.ifacol.2016.07.671⟩. ⟨hal-02735776⟩