A memetic algorithm for the vehicle routing problem with time windows

Issue		RAIRO Oper. Res. Volume 42, Number 3, July-September 2008


Page(s)		415 - 431
DOI		10.1051/ro:2008021
Published online		20 August 2008

RAIRO-Oper. Res. 42 (2008) 415-431
DOI: 10.1051/ro:2008021

A memetic algorithm for the vehicle routing problem with time windows

Nacima Labadi, Christian Prins and Mohamed Reghioui

Inst. Charles Delaunay, Univ. Technologie Troyes, FRE CNRS 2848, BP 2060, 10010 Troyes Cedex, France; nacima.labadi@utt.fr, christian.prins@utt.fr, mohamed.reghioui_hamzaoui@utt.fr

Received July 27, 2007. Accepted April 01, 2008 Published online 20 August 2008

Abstract
This article deals with the vehicle routing problem with time windows (VRPTW). This problem consists in determining a least-cost set of trips to serve customers during specific time windows. The proposed solution method is a memetic algorithm (MA), a genetic algorithm hybridised with a local search. Contrary to most papers on the VRPTW, which minimize first the number of vehicles, our method is also able to minimize the total distance travelled. The results on 56 classical instances are compared to those of the best metaheuristics. The efficiency of the MA is similar for the classical criterion, but it becomes the best algorithm available for the total distance, being much faster and improving 20 best-known solutions.

Résumé
Cet article concerne le problème de tournées de véhicules avec fenêtres horaires (Vehicle Routing Problem with Time Windows ou VRPTW). Ce problème consiste à déterminer un ensemble de tournées de coût total minimal pour servir des clients dans des fenêtres horaires spécifiques. Nous proposons un algorithme mémétique (MA, algorithme génétique hybridé avec une recherche locale) pour le résoudre. Contrairement à la plupart des articles sur le VRPTW, qui minimisent en priorité le nombre de véhicules, notre méthode peut aussi minimiser la distance totale parcourue. Les résultats sur 56 problèmes-tests classiques sont comparés à ceux des meilleures métaheuristiques. Pour le critère classique, le MA offre des performances similaires, mais il devient le meilleur algorithme disponible pour la distance totale, en étant bien plus rapide et en améliorant 20 des meilleures solutions connues.

Mathematics Subject Classification. 90B06.

Key words: memetic algorithm, vehicle routing problem, time window.

© EDP Sciences, ROADEF, SMAI 2008

What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.

If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.