A Hybrid Genetic Algorithm for the Vehicle Routing Problem with Roaming Delivery Locations

Abstract

The Vehicle Routing Problem with Roaming Delivery Locations (VRPRDL) is a variant of the Vehicle Routing Problem (VRP) in which a customer can be present at many locations during a working day and a time window is associated with each location. The objective is to find a set of routes such that (i) the total traveling cost is minimized, (ii) only one location of each customer is visited within its time window, and (iii) all capacity constraints are satisfied. To solve the problem, we introduce a hybrid genetic algorithm which relies on problem-tailored solution representation, mutation, local search operators, as well as a set covering component exploring routes found during the search to find better solutions. We also propose a new split procedure which based on dynamic programming to evaluate the fitness of chromosomes. Experiments conducted on the benchmark instances clearly show that our proposed algorithm outperforms existing approaches in terms of stability and solution quality. We also improve 49 best known solutions of the literature.