The periodic Vehicle routing problem: classification and heuristic

M. Mourgaya; F. Vanderbeck

RAIRO - Operations Research (2006)

  • Volume: 40, Issue: 2, page 169-194
  • ISSN: 0399-0559

Abstract

top
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. 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.

How to cite

top

Mourgaya, M., and Vanderbeck, F.. "The periodic Vehicle routing problem: classification and heuristic." RAIRO - Operations Research 40.2 (2006): 169-194. <http://eudml.org/doc/249770>.

@article{Mourgaya2006,
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 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. },
author = {Mourgaya, M., Vanderbeck, F.},
journal = {RAIRO - Operations Research},
language = {eng},
month = {10},
number = {2},
pages = {169-194},
publisher = {EDP Sciences},
title = {The periodic Vehicle routing problem: classification and heuristic},
url = {http://eudml.org/doc/249770},
volume = {40},
year = {2006},
}

TY - JOUR
AU - Mourgaya, M.
AU - Vanderbeck, F.
TI - The periodic Vehicle routing problem: classification and heuristic
JO - RAIRO - Operations Research
DA - 2006/10//
PB - EDP Sciences
VL - 40
IS - 2
SP - 169
EP - 194
AB - 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.
LA - eng
UR - http://eudml.org/doc/249770
ER -

References

top
  1. E. Angelelli et M.G. Speranza, The periodic vehicle routing problem with intermediate facilities. Eur. J. Oper. Res.137 (2002) 233–247.  Zbl0998.90021
  2. D. Applegate, R. Bixby, V. Chvátal et W. Cook, Concorde: A code for solving Traveling Salesman Problems. .  Zbl0904.90165URIhttp://www.math.princeton.edu/tsp/concorde.html
  3. 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).  
  4. 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).  
  5. B. Bullnheimer, R.F. Hartl and C. Strauss, An Improved Ant System Algorithm for the Vehicle Routing Problem. Ann. Oper. Res.89 (1999) 319–328.  Zbl0937.90125
  6. Chaire de recherche du Canada en distributique. Données PVRP. .  URIhttp://www.hec.ca/chairedistributique/data/pvrp/old/
  7. M. Chao, B.L. Golden and E. Wasil, An improved heuristic for the period vehicle routing problem. Networks26 (1995) 25–44.  Zbl0840.90059
  8. N. Christofides, J.E. Beasley, The period Routing Problem. Networks14 (1984) 237–256.  Zbl0541.90073
  9. J.F. Cordeau, M. Gendreau, G. Laporte, A tabu search Heuritic for periodic and multi depot vehicle routing problems, Networks30 (1997) 105–119.  Zbl0885.90037
  10. M. Gaudioso, G. Paletta, A heuritic for the periodic vehicle routing problem. Transportation Sci.26 (1992) 86–92.  Zbl0759.90025
  11. M. Gendreau et A. Hertz, G. Laporte, A tabu search heuristic for the vehicle routing problem. Management Sci.40 (1994) 1276–1290.  Zbl0822.90053
  12. S. Michel, Thèse de doctorat. Université Bordeaux 1 (2006).  
  13. 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).  
  14. R. Russel and D. Gribbin, A multiphase approach to the period routing problem. Networks21 (1991) 747–765.  Zbl0743.90044
  15. R. Russel and W. Igo, An assignment routing problem. Networks9 (1979) 1–17.  
  16. E.D. Taillard and L.M. Gambardella, M. Gendreau et J.Y. Potvin, Adaptive memory programming : a unified view of metaheuristics. Eur. J. Oper. Res.135 (2001) 1–16.  Zbl1051.90032
  17. 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.  
  18. P. Toth and D. Vigo, The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, Philadelphie (2001).  Zbl0966.90009
  19. D.S. Vianna, L.S. Ochi and L.M.A. Drummond, 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, (2001).  URIhttp://www.dashoptimization.com

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.