NSGAII enhanced with a local search for the vehicle routing problem with time windows and synchronization constraints. Issue 12 (2016) - Haddadene, S.R. Ait; Labadie, N.; Prodhon, C.
Abstract: 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.