1. MMC
  2. All Volumes and Issues
  3. Volume 11, Number 1, 2024
  4. A survey of the vehicle routing problem and its variants: formulations and solutions

A survey of the vehicle routing problem and its variants: formulations and solutions

MMC.
2024;
Volume 11, Number 1
: pp. 333–343
https://doi.org/10.23939/mmc2024.01.333
Received: July 17, 2023
Accepted: March 12, 2024

Khayya E., Medarhri I., Zine R.  A survey of the vehicle routing problem and its variants: formulations and solutions.  Mathematical Modeling and Computing. Vol. 11, No. 1, pp. 333–343 (2024)

Authors:
  1. E. Khayya
  2. I. Medarhri
  3. R. Zine
1
MMCS Team, LMAID Laboratory, ENSMR-Rabat
2
MMCS Team, LMAID Laboratory, ENSMR-Rabat
3
School of Science and Engineering, Al Akhawayn University in Ifrane

In the realm of industrial enterprises, enhancing logistical efficiency stands as a focal concern.  The objective lies in orchestrating an optimized service with seamless flow of goods while minimizing expenses.  A crucial component within any logistics framework is the administration and strategizing of distribution networks for vehicle fleets, commonly referred to as the Vehicle Routing Problem (VRP).  This composition delves into an exploration of VRP and its various iterations, offering categorization and depiction of prevalent formulations and algorithms prevalent in scholarly works over the past two decades.

VRP
survey
exact methods
mathematical formulation
meta-heuristics
  1. Dantzig G. B., Ramser J. H.  The truck dispatching problem.  Management Science.  6 (1), 80–91 (1959).
  2. Clarke G., Wright J. W.  Scheduling of vehicles from a central depot to a number of delivery points.  Operations Research.  12 (4), 568–581 (1964).
  3. Toth P., Vigo D.  The vehicle routing problem.  SIAM (2002).
  4. Lenstra J. K., Kan A. R.  Complexity of vehicle routing and scheduling problems.  Networks.  11 (2), 221–227 (1981).
  5. Laporte G., Nobert Y., Desrochers M.  Optimal routing under capacity and distance restrictions.  Operations Research.  33 (5), 1050–1073 (1985).
  6. Balinski M. L., Quandt R. E.  On an integer program for a delivery problem.  Operations Research.  12 (2), 300–304 (1964).
  7. Garvin W. W., Crandall H., John J., Spellman R.  Applications of linear programming in the oil industry.  Management Science.  3 (4), 407–430 (1957).
  8. Laporte G.  The vehicle routing problem: An overview of exact and approximate algorithms.  European journal of operational research.  59 (3), 345–358 (1992).
  9. Baldacci R., Hadjiconstantinou E., Mingozzi A.  An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation.  Operations Research.  52 (5), 723–738 (2004).
  10. Mirabi M., Ghomi S. F., Jolai F.  Efficient stochastic hybrid heuristics for the multi-depot vehicle routing problem.  Robotics and Computer-Integrated Manufacturing.  26 (6), 564–569 (2010).
  11. Subramanian A., Penna P. H. V., Uchoa E., Ochi L. S.  A hybrid algorithm for the heterogeneous fleet vehicle routing problem.  European Journal of Operational Research.  221 (2), 285–295 (2012).
  12. Choi E., Tcha D. W.  A column generation approach to the heterogeneous fleet vehicle routing problem.  Computers & Operations Research.  34 (7), 2080–2095 (2007).
  13. Contardo C., Martinelli R.  A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints.  Discrete Optimization.  12, 129–146 (2014).
  14. Baños R., Ortega J., Gil C., Fernández A., De Toro F.  A simulated annealing-based parallel multi-objective approach to vehicle routing problems with time windows.  Expert Systems with Applications.  40 (5), 1696–1707 (2013).
  15. Ombuki B., Ross B. J., Hanshar F.  Multi-objective genetic algorithms for vehicle routing problem with time windows.  Applied Intelligence.  24, 17–30 (2006).
  16. Lau H. C., Sim M., Teo K. M.  Vehicle routing problem with time windows and a limited number of vehicles.  European Journal of Operational Research.  148 (3), 559–569 (2003).
  17. Huerta-Muñoz D. L., Archetti C., Fernández E., Perea F.  The heterogeneous flexible periodic vehicle routing problem: Mathematical formulations and solution algorithms.  Computers & Operations Research.  141, 105662 (2022).
  18. Montané F. A. T., Galvao R. D.  A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service.  Computers & Operations Research.  33 (3), 595–619 (2006).
  19. Hornstra R. P., Silva A., Roodbergen K. J., Coelho L. C.  The vehicle routing problem with simultaneous pickup and delivery and handling costs.  Computers & Operations Research.  115, 104858 (2020).
  20. Balseiro S. R., Loiseau I., Ramonet J.  An ant colony algorithm hybridized with insertion heuristics for the time dependent vehicle routing problem with time windows. Computers & Operations Research.  38 (6), 954–966 (2011).
  21. Dabia S., Ropke S., Van Woensel T., De Kok T.  Branch and price for the time-dependent vehicle routing problem with time windows.  Transportation Science.  47 (3), 380–396 (2013).
  22. Afshar-Nadjafi B., Afshar-Nadjafi A.  A constructive heuristic for time-dependent multi-depot vehicle routing problem with time-windows and heterogeneous fleet.  Journal of King Saud University-Engineering Sciences.  29 (1), 29–34 (2017).
  23. Bettinelli A., Ceselli A., Righini G.  A branch-and-cut-and-price algorithm for the multi-depot heterogeneous vehicle routing problem with time windows. Transportation Research Part C: Emerging Technologies.  19 (5), 723–740 (2011).
  24. Lysgaard J., Letchford A. N., Eglese R. W.  A new branch-and-cut algorithm for the capacitated vehicle routing problem.  Mathematical Programming.  100, 423–445 (2004).
  25. Baldacci R., Christofides N., Mingozzi A.  An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts.  Mathematical Programming.  115, 351–385 (2008).
  26. Croes G. A.  A method for solving traveling-salesman problems.  Operations research.  6 (6), 791–812 (1958).
  27. Lin S.  Computer solutions of the traveling salesman problem.  Bell System Technical Journal.  44 (10), 2245–2269 (1965).
  28. Gmira M., Gendreau M., Lodi A., Potvin J. Y.  Tabu search for the time-dependent vehicle routing problem with time windows on a road network.  European Journal of Operational Research.  288 (1), 129–140 (2021).
  29. Lin S. W., Lee Z. J., Ying K. C., Lee C. Y.  Applying hybrid meta-heuristics for capacitated vehicle routing problem.  Expert Systems with Applications.  36 (2), 1505–1512 (2009).
  30. Ai T. J., Kachitvichyanukul V.  A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery.  Computers & Operations Research.  36 (5), 1693–1702 (2009).
  31. Chen A. L., Yang G. K., Wu Z. M.  Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem.  Journal of Zhejiang University-Science A.  7 (4), 607–614 (2006).
  32. Subramanian A., Uchoa E., Ochi L. S.  A hybrid algorithm for a class of vehicle routing problems.  Computers & Operations Research.  40 (10), 2519–2531 (2013).
  33. Yu B., Yang Z. Z., Yao B.  An improved ant colony optimization for vehicle routing problem.  European Journal of Operational Research.  196 (1), 171–176 (2009).
  34. De Oliveira F. B., Enayatifar R., Sadaei H. J., Guimarães F. G., Potvin J. Y.  A cooperative coevolutionary algorithm for the multi-depot vehicle routing problem.  Expert Systems with Applications.  43, 117–130 (2016).
  35. Pessoa A., Sadykov R., Uchoa E., Vanderbeck F.  A generic exact solver for vehicle routing and related problems.  Mathematical Programming.  183, 483–523 (2020).
  36. Achuthan N. R., Caccetta L., Hill S. P.  An improved branch-and-cut algorithm for the capacitated vehicle routing problem.  Transportation Science.  37 (2), 153–169 (2003).
  37. Calvet L., Ferrer A., Gomes M. I., Juan A. A., Masip D.  Combining statistical learning with metaheuristics for the multi-depot vehicle routing problem with market segmentation.  Computers & Industrial Engineering.  94, 93–104 (2016).
  38. Altabeeb A. M., Mohsen A. M., Ghallab A.  An improved hybrid firefly algorithm for capacitated vehicle routing problem.  Applied Soft Computing.  84, 105728 (2019).
  39. Reyes-Rubiano L., Calvet L., Juan A. A., Faulin J., Bové L.  A biased-randomized variable neighborhood search for sustainable multi-depot vehicle routing problems.  Journal of Heuristics.  26, 401–422 (2020).
  40. Escobar J. W., Linfati R., Toth P., Baldoquin M. G.  A hybrid granular tabu search algorithm for the multi-depot vehicle routing problem.  Journal of heuristics.  20, 483–509 (2014).
  41. Penna P. H. V., Subramanian A., Ochi L. S.  An iterated local search heuristic for the heterogeneous fleet vehicle routing problem.  Journal of Heuristics.  19 (2), 201–232 (2013).
  42. Polacek M., Hartl R. F., Doerner K., Reimann M.  A variable neighborhood search for the multi depot vehicle routing problem with time windows.  Journal of heuristics.  10, 613–627 (2004).
  43. Pichpibul T., Kawtummachai R.  An improved Clarke and Wright savings algorithm for the capacitated vehicle routing problem.  ScienceAsia.  38 (3), 307–318 (2012).
  44. Pecin D., Pessoa A., Poggi M., Uchoa E., Santos H.  Limited memory rank-1 cuts for vehicle routing problems.  Operations Research Letters.  45 (3), 206–209 (2017).