A Hybrid Genetic Algorithm for the Vehicle Routing Problem with Time Windows

PDF

Authors
  1. Berger, J.
  2. Salois, M.
Corporate Authors
Defence R&D Canada - Valcartier, Valcartier QUE (CAN)
Abstract
A variety of hybrid genetic algorithms has been recently proposed to address the vehicle routing problem with time windows (VRPTW), a problem known to be NP-hard. However, very few geneticbased approaches exploit implicit knowledge provided by the structure of the intermediate solutions computed during the evolutionary process to explore the solution space. This report presents a new hybrid genetic algorithm for the VRPTW. It investigates the impact of using explicitly domain knowledge and prior knowledge/characteristics about typical solutions expected from the recombination and mutation phases of the algorithm. Basic principles borrow from recent hybrid and standard genetic algorithms, and features of well-known heuristics to drive the search process. Designed to support time-constrained reasoning tasks, the procedure is intended to be conceptually simple, easy to implement, and allow fast computation of near-optimal solution. A computational experiment has been conducted to compare the performance of the proposed algorithm with similar and standard techniques.

Il y a un résumé en français ici.

Keywords
Genetic algorithms;vehicle routing problem with time windows;VRPTW;optimization;heuristics
Report Number
DRDC-VALCARTIER-TR-2002-162 — Technical Report
Date of publication
01 Jun 2004
Number of Pages
34
DSTKIM No
CA024546
CANDIS No
522185
Format(s):
Hardcopy;CD ROM

Permanent link

Document 1 of 1

Date modified: