Le problème de tournées de véhicules multipériodiques con-siste à 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
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.
@article{RO_2006__40_2_169_0,
author = {Mourgaya, M. and Vanderbeck, F.},
title = {Probl\`eme de tourn\'ees de v\'ehicules multip\'eriodiques : classification et heuristique pour la planification tactique},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {169--194},
publisher = {EDP-Sciences},
volume = {40},
number = {2},
year = {2006},
doi = {10.1051/ro:2006015},
zbl = {1137.90333},
language = {fr},
url = {http://www.numdam.org/articles/10.1051/ro:2006015/}
}
TY - JOUR AU - Mourgaya, M. AU - Vanderbeck, F. TI - Problème de tournées de véhicules multipériodiques : classification et heuristique pour la planification tactique JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2006 SP - 169 EP - 194 VL - 40 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro:2006015/ DO - 10.1051/ro:2006015 LA - fr ID - RO_2006__40_2_169_0 ER -
%0 Journal Article %A Mourgaya, M. %A Vanderbeck, F. %T Problème de tournées de véhicules multipériodiques : classification et heuristique pour la planification tactique %J RAIRO - Operations Research - Recherche Opérationnelle %D 2006 %P 169-194 %V 40 %N 2 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro:2006015/ %R 10.1051/ro:2006015 %G fr %F RO_2006__40_2_169_0
Mourgaya, M.; Vanderbeck, F. Problème de tournées de véhicules multipériodiques : classification et heuristique pour la planification tactique. RAIRO - Operations Research - Recherche Opérationnelle, Tome 40 (2006) no. 2, pp. 169-194. doi : 10.1051/ro:2006015. http://www.numdam.org/articles/10.1051/ro:2006015/
[1] et, The periodic vehicle routing problem with intermediate facilities. Eur. J. Oper. Res. 137 (2002) 233-247. | Zbl
[2] ,, et, Concorde: A code for solving Traveling Salesman Problems. http://www.math.princeton.edu/tsp/concorde.html.
[3] , Allocation/Routing: models and algorithms, in Vehicle Routing: Methods and Studies, edited by B.L. Golden et A.A. Assad, Amsterdam (1988). | MR
[4] ,,,, eds. Handbooks in Operations Research and Management Science. Vol. 8, Network Routing, North-Holland, Amsterdam (1995). | MR | Zbl
[5] , and, An Improved Ant System Algorithm for the Vehicle Routing Problem. Ann. Oper. Res. 89 (1999) 319-328. | Zbl
[6] Chaire de recherche du Canada en distributique. Données PVRP. http://www.hec.ca/chairedistributique/data/pvrp/old/.
[7] , and, An improved heuristic for the period vehicle routing problem. Networks 26 (1995) 25-44. | Zbl
[8] ,, The period Routing Problem. Networks 14 (1984) 237-256. | Zbl
[9] ,,, A tabu search Heuritic for periodic and multi depot vehicle routing problems, Networks 30 (1997) 105-119. | Zbl
[10] ,, A heuritic for the periodic vehicle routing problem. Transportation Sci. 26 (1992) 86-92. | Zbl
[11] et, G. Laporte, A tabu search heuristic for the vehicle routing problem. Management Sci. 40 (1994) 1276-1290. | Zbl
[12] , Thèse de doctorat. Université Bordeaux 1 (2006).
[13] , Le problème de tournées de véhicules multipériodiques : planification préalable au routage. Thèse de doctorat. Université Bordeaux 1 (2004).
[14] and, A multiphase approach to the period routing problem. Networks 21 (1991) 747-765. | Zbl
[15] and, An assignment routing problem. Networks 9 (1979) 1-17.
[16] and, M. Gendreau et J.Y. Potvin, Adaptive memory programming : a unified view of metaheuristics. Eur. J. Oper. Res. 135 (2001) 1-16. | Zbl
[17] and, A heuristic algorithm for the period vehicle routing problem. Omega Int. J. og. Mgmt. Sci. 12 (1984) 497-504.
[18] and, The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, Philadelphie (2001). | MR | Zbl
[19] , and, A parallel hybrid evolutionary metaheuristic for the period vehicle routing problem. Lec. Notes in CompuT. Sci. 1586 (1998) 183-191.
[20] Xpress-MP: User guide and Reference Manual, Release 12 Dash Optimization, http://www.dashoptimization.com (2001).
Cité par Sources :
