Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-23T11:26:12.726Z Has data issue: false hasContentIssue false
  • English
  • Français

The periodic Vehicle routing problem: classification and heuristic

Published online by Cambridge University Press:  12 October 2006

M. Mourgaya  and
F. Vanderbeck
M. Mourgaya
Affiliation:
Laboratoire de Mathématiques Appliquées de Bordeaux (MAB), Université Bordeaux 1, 33405 Talence Cedex, France;
F. Vanderbeck
Affiliation:
Laboratoire de Mathématiques Appliquées de Bordeaux (MAB), Université Bordeaux 1, 33405 Talence Cedex, France;
Get access

Abstract

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 theform 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 theplanning of customer visits to achieve both workload balancing andregionalisation of the routes. The objective of regionalisation reflects a desire to specializeroutes to restricted geographical area. The standard minimisation of distancetravelled is left for the underlying operational decision making model.Our heuristic achieves practical solutions for an industrialinstance with 16658 visits to schedule over a horizon of 20 days.

Type
Research Article
Information
RAIRO - Operations Research , Volume 40 , Issue 2: ROADEF 03 , April 2006 , pp. 169 - 194
Copyright
© EDP Sciences, 2006

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Angelelli, E. et Speranza, M.G., The periodic vehicle routing problem with intermediate facilities. Eur. J. Oper. Res. 137 (2002) 233–247. CrossRef
D. Applegate, R. Bixby, V. Chvátal et W. Cook, Concorde: A code for solving Traveling Salesman Problems. http://www.math.princeton.edu/tsp/concorde.html.
M.O. Ball, Allocation/Routing: models and algorithms, in Vehicle Routing: Methods and Studies, edited by B.L. Golden et A.A. Assad, Amsterdam (1988).
M.O. Ball, T.L. Magnanti, C.L. Monna, G.L. Nemhauser, eds. Handbooks in Operations Research and Management Science. Vol. 8, Network Routing, North-Holland, Amsterdam (1995).
Bullnheimer, B., Hartl, R.F. and Strauss, C., Improved Ant System Al, Angorithm for the Vehicle Routing Problem. Ann. Oper. Res. 89 (1999) 319–328. CrossRef
Chaire de recherche du Canada en distributique. Données PVRP. http://www.hec.ca/chairedistributique/data/pvrp/old/.
Chao, M., Golden, B.L. and Wasil, E., An improved heuristic for the period vehicle routing problem. Networks 26 (1995) 25–44. CrossRef
Christofides, N., Beasley, J.E., The period Routing Problem. Networks 14 (1984) 237–256. CrossRef
J.F. Cordeau, M. Gendreau, G. Laporte, A tabu search Heuritic for periodic and multi depot vehicle routing problems, Networks 30 (1997) 105–119.
Gaudioso, M., Paletta, G., A heuritic for the periodic vehicle routing problem. Transportation Sci. 26 (1992) 86–92. CrossRef
Gendreau, M. et Hertz, A., Laporte, G., A tabu search heuristic for the vehicle routing problem. Management Sci. 40 (1994) 1276–1290. CrossRef
S. Michel, Thèse de doctorat. Université Bordeaux 1 (2006).
M. Mourgaya, Le problème de tournées de véhicules multipériodiques : planification préalable au routage. Thèse de doctorat. Université Bordeaux 1 (2004).
Russel, R. and Gribbin, D., A multiphase approach to the period routing problem. Networks 21 (1991) 747–765. CrossRef
Russel, R. and Igo, W., An assignment routing problem. Networks 9 (1979) 1–17. CrossRef
Taillard, E.D. and Gambardella, L.M., Gendreau, M. et Potvin, J.Y., Adaptive memory programming : a unified view of metaheuristics. Eur. J. Oper. Res. 135 (2001) 1–16. CrossRef
C.C.R. Tan and J.E. Beasley, A heuristic algorithm for the period vehicle routing problem. Omega Int. J. og. Mgmt. Sci. 12 (1984) 497–504.
P. Toth and D. Vigo, The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, Philadelphie (2001).
Vianna, D.S., Ochi, L.S. and Drummond, L.M.A., A parallel hybrid evolutionary metaheuristic for the period vehicle routing problem. Lec. Notes in CompuT. Sci. 1586 (1998) 183–191. CrossRef
Xpress-MP: User guide and Reference Manual, Release 12 Dash Optimization, http://www.dashoptimization.com (2001).