A Genetic Algorithm for Solving the Generalized Vehicle Routing Problem

The generalized vehicle routing problem is a variant of the well-known vehicle routing problem in which the nodes of a graph are partitioned into a given number of node sets (clusters) and the objective is to find the minimum-cost delivery or collection of routes, subject to capacity restrictions, from a given depot to the number of predefined clusters passing through one node from each clusters. We present an effective metaheuristic algorithm for the problem based on genetic algorithms. The proposed metaheuristic is competitive with other heuristics published to date in both solution quality and computation time. Computational results for benchmarks problems are reported and the results point out that GA is an appropriate method to explore the search space of this complex problem and leads to good solutions in a short amount of time.