Issue |
RAIRO-Oper. Res.
Volume 40, Number 2, April-June 2006
ROADEF 03
|
|
---|---|---|
Page(s) | 169 - 194 | |
DOI | https://doi.org/10.1051/ro:2006015 | |
Published online | 12 October 2006 |
The periodic Vehicle routing problem: classification and heuristic
Problème de tournées de véhicules multipériodiques : classification et heuristique pour la planification tactique
Laboratoire de
Mathématiques Appliquées de Bordeaux (MAB), Université Bordeaux 1,
33405 Talence Cedex, France;
Received:
31
December
2005
Periodic Vehicle Routing Problem: classification and heuristic for tactical planning. The Periodic Vehicle Routing Problem (PVRP) consists in assigning customer visits to vehicle routes in some periods of a time horizon so as to satisfy some service level requirements that can take the form of frequency of visit, constraint on time lag between visits, or pre-defined visit patterns. We present different variants of this problem and propose a classification. Then, we consider a model for tactical planning for which we propose a heuristic: we optimise the planning of customer visits to achieve both workload balancing and regionalisation of the routes. The objective of regionalisation reflects a desire to specialize routes to restricted geographical area. The standard minimisation of distance travelled is left for the underlying operational decision making model. Our heuristic achieves practical solutions for an industrial instance with 16658 visits to schedule over a horizon of 20 days.
Résumé
Le problème de tournées de véhicules multipériodiques consiste à planifier des visites clients sur un horizon de temps donné en les affectant à des tournées de véhicules. Les fréquences de visites ou espacements entre elles sont prescrits. Ces contraintes peuvent prendre la forme de scénarios de visites admissibles. Nous étudions les différentes variantes de ce problème et proposons une classification. Nous nous restreignons ensuite aux décisions tactiques et présentons un algorithme heuristique pour la planification des visites qui optimise la répartition de la charge et la régionalisation des tournées (qu'on désire spécialisées
© EDP Sciences, 2006
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.