An improved hybrid algorithm for solving the generalized vehicle routing problem

The generalized vehicle routing problem (GVRP) is a natural extension of the classical vehicle routing problem (VRP). In GVRP, we are given a partition of the customers into groups (clusters) and a depot and we want to design a minimum length collection of routes for the fleet of vehicles, originating and terminating at the depot and visiting exactly one customer from each group, subject to capacity restrictions. The aim of this paper is to present an efficient hybrid heuristic algorithm obtained by combining a genetic algorithm (GA) with a local–global approach to the GVRP and a powerful local search procedure. The computational experiments on several benchmark instances show that our hybrid algorithm is competitive to all of the known heuristics published to date.