The Vehicle Routing Problem with Time Windows Part II: Genetic Search

TLDR

In evolutionary algorithms, populations of solutions evolve by mating parents to produce offspring inheriting traits. The paper extends prior work by applying novel search techniques to the vehicle routing problem with time windows. The authors introduce GENEROUS, a genetic routing system that merges two vehicle routing solutions to generate a time‑window‑feasible offspring. Experiments on standard benchmarks show that GENEROUS performs competitively with existing heuristics.

Abstract

This paper is the second part of a work on the application of new search techniques for the vehicle routing problem with time windows. It describes GENEROUS, the GENEtic ROUting System, which is based on the natural evolution paradigm. Under this paradigm, a population of solutions evolves from one generation to the next by “mating” parent solutions to form new offspring solutions that exhibit characteristics inherited from their parents. For this vehicle routing application, a specialized methodology is devised for merging two vehicle routing solutions into a single solution that is likely to be feasible with respect to the time window constraints. Computational results on a standard set of test problems are reported, and comparisons are provided with other heuristics.