IDEAS home Printed from https://ideas.repec.org/a/spr/ijsaem/v9y2018i1d10.1007_s13198-016-0493-4.html
   My bibliography  Save this article

A survey of recent advances in vehicle routing problems

Author

Listed:
  • Aderemi Oluyinka Adewumi

    (University of Kwazulu-Natal)

  • Olawale Joshua Adeleke

    (Covenant University)

Abstract

A vehicle routing problem involves finding a set of optimal route for a fleet of capacitated vehicles which are available at a location to service the demands of a set of customers. In its simplest form, a customer is required to be visited once and the capacity of a vehicle must not be exceeded. In this paper, a review of four common and applicable variants of the vehicle routing problem, namely, capacitated vehicle routing problem, vehicle routing problem with time windows, periodic vehicle routing problem and the dynamic vehicle routing problem, are considered based on formulation techniques, methods of solution and areas of application. A summary table is presented for each variant to emphasis some key features that represent direction of current research.

Suggested Citation

  • Aderemi Oluyinka Adewumi & Olawale Joshua Adeleke, 2018. "A survey of recent advances in vehicle routing problems," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 9(1), pages 155-172, February.
    • Handle: RePEc:spr:ijsaem:v:9:y:2018:i:1:d:10.1007_s13198-016-0493-4
    DOI: 10.1007/s13198-016-0493-4
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s13198-016-0493-4
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s13198-016-0493-4?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Calvete, Herminia I. & Gale, Carmen & Oliveros, Maria-Jose & Sanchez-Valverde, Belen, 2007. "A goal programming approach to vehicle routing problems with soft time windows," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1720-1733, March.
    2. Lysgaard, Jens & Wøhlk, Sanne, 2014. "A branch-and-cut-and-price algorithm for the cumulative capacitated vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 236(3), pages 800-810.
    3. Marshall L. Fisher, 1994. "Optimal Solution of Vehicle Routing Problems Using Minimum K-Trees," Operations Research, INFORMS, vol. 42(4), pages 626-642, August.
    4. G. Clarke & J. W. Wright, 1964. "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points," Operations Research, INFORMS, vol. 12(4), pages 568-581, August.
    5. Qureshi, A.G. & Taniguchi, E. & Yamada, T., 2009. "An exact solution approach for vehicle routing and scheduling problems with soft time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 45(6), pages 960-977, November.
    6. Schyns, M., 2015. "An ant colony system for responsive dynamic vehicle routing," European Journal of Operational Research, Elsevier, vol. 245(3), pages 704-718.
    7. F-H Liu & S-Y Shen, 1999. "The fleet size and mix vehicle routing problem with time windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 50(7), pages 721-732, July.
    8. Azi, Nabila & Gendreau, Michel & Potvin, Jean-Yves, 2010. "An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles," European Journal of Operational Research, Elsevier, vol. 202(3), pages 756-763, May.
    9. Henke, Tino & Speranza, M. Grazia & Wäscher, Gerhard, 2015. "The multi-compartment vehicle routing problem with flexible compartment sizes," European Journal of Operational Research, Elsevier, vol. 246(3), pages 730-743.
    10. G. B. Dantzig & J. H. Ramser, 1959. "The Truck Dispatching Problem," Management Science, INFORMS, vol. 6(1), pages 80-91, October.
    11. Marti, Rafael & Laguna, Manuel & Glover, Fred, 2006. "Principles of scatter search," European Journal of Operational Research, Elsevier, vol. 169(2), pages 359-372, March.
    12. Gutiérrez-Jarpa, Gabriel & Desaulniers, Guy & Laporte, Gilbert & Marianov, Vladimir, 2010. "A branch-and-price algorithm for the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows," European Journal of Operational Research, Elsevier, vol. 206(2), pages 341-349, October.
    13. Laoucine Kerbache & T. van Woensel & N. Vandaele & Herbert Peremans, 2008. "Vehicle routing with dynamic travel times: A queueing approach," Post-Print hal-00465127, HAL.
    14. Haimovich, M. & Kan, R. & Stougie, L., 1988. "Analysis Of Heuristics For Vehicle Routing Problems," Papers ae_1-88, Universiteit Amsterdam - Institute of Actuarial Sciences and Econometrics.
    15. Van Woensel, T. & Kerbache, L. & Peremans, H. & Vandaele, N., 2008. "Vehicle routing with dynamic travel times: A queueing approach," European Journal of Operational Research, Elsevier, vol. 186(3), pages 990-1007, May.
    16. Michel Gendreau & Manuel Iori & Gilbert Laporte & Silvano Martello, 2006. "A Tabu Search Algorithm for a Routing and Container Loading Problem," Transportation Science, INFORMS, vol. 40(3), pages 342-350, August.
    17. Hemmelmayr, Vera C. & Doerner, Karl F. & Hartl, Richard F., 2009. "A variable neighborhood search heuristic for periodic routing problems," European Journal of Operational Research, Elsevier, vol. 195(3), pages 791-802, June.
    18. Ferrucci, Francesco & Bock, Stefan & Gendreau, Michel, 2013. "A pro-active real-time control approach for dynamic vehicle routing problems dealing with the delivery of urgent goods," European Journal of Operational Research, Elsevier, vol. 225(1), pages 130-141.
    19. Li, Jing-Quan & Mirchandani, Pitu B. & Borenstein, Denis, 2009. "A Lagrangian heuristic for the real-time vehicle rescheduling problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 45(3), pages 419-433, May.
    20. Lysgaard, Jens, 2010. "The pyramidal capacitated vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 205(1), pages 59-64, August.
    21. Wohlgemuth, Sascha & Oloruntoba, Richard & Clausen, Uwe, 2012. "Dynamic vehicle routing with anticipation in disaster relief," Socio-Economic Planning Sciences, Elsevier, vol. 46(4), pages 261-271.
    22. Yiannis A. Koskosidis & Warren B. Powell & Marius M. Solomon, 1992. "An Optimization-Based Heuristic for Vehicle Routing and Scheduling with Soft Time Window Constraints," Transportation Science, INFORMS, vol. 26(2), pages 69-85, May.
    23. Jin, Jianyong & Crainic, Teodor Gabriel & Løkketangen, Arne, 2012. "A parallel multi-neighborhood cooperative tabu search for capacitated vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 222(3), pages 441-451.
    24. Yu, Bin & Yang, Zhong Zhen, 2011. "An ant colony optimization model: The period vehicle routing problem with time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 47(2), pages 166-181, March.
    25. Francis, Peter & Smilowitz, Karen, 2006. "Modeling techniques for periodic vehicle routing problems," Transportation Research Part B: Methodological, Elsevier, vol. 40(10), pages 872-884, December.
    26. Zare Mehrjerdi, Yahia & Nadizadeh, Ali, 2013. "Using greedy clustering method to solve capacitated location-routing problem with fuzzy demands," European Journal of Operational Research, Elsevier, vol. 229(1), pages 75-84.
    27. Ferrucci, Francesco & Bock, Stefan, 2015. "A general approach for controlling vehicle en-route diversions in dynamic vehicle routing problems," Transportation Research Part B: Methodological, Elsevier, vol. 77(C), pages 76-87.
    28. Yamashita, Denise Sato & Armentano, Vinicius Amaral & Laguna, Manuel, 2006. "Scatter search for project scheduling with resource availability cost," European Journal of Operational Research, Elsevier, vol. 169(2), pages 623-637, March.
    29. Nguyen, Phuong Khanh & Crainic, Teodor Gabriel & Toulouse, Michel, 2013. "A tabu search for Time-dependent Multi-zone Multi-trip Vehicle Routing Problem with Time Windows," European Journal of Operational Research, Elsevier, vol. 231(1), pages 43-56.
    30. Teixeira, Joao & Antunes, Antonio Pais & de Sousa, Jorge Pinho, 2004. "Recyclable waste collection planning--a case study," European Journal of Operational Research, Elsevier, vol. 158(3), pages 543-554, November.
    31. Barrett W. Thomas, 2007. "Waiting Strategies for Anticipating Service Requests from Known Customer Locations," Transportation Science, INFORMS, vol. 41(3), pages 319-331, August.
    32. Lau, Hoong Chuin & Sim, Melvyn & Teo, Kwong Meng, 2003. "Vehicle routing problem with time windows and a limited number of vehicles," European Journal of Operational Research, Elsevier, vol. 148(3), pages 559-569, August.
    33. Marius M. Solomon & Jacques Desrosiers, 1988. "Survey Paper---Time Window Constrained Routing and Scheduling Problems," Transportation Science, INFORMS, vol. 22(1), pages 1-13, February.
    34. Tan, C.C.R. & Beasley, J.E., 1984. "A heuristic algorithm for the period vehicle routing problem," Omega, Elsevier, vol. 12(5), pages 497-504.
    35. Angelelli, Enrico & Grazia Speranza, Maria, 2002. "The periodic vehicle routing problem with intermediate facilities," European Journal of Operational Research, Elsevier, vol. 137(2), pages 233-247, March.
    36. Robert A. Russell, 1995. "Hybrid Heuristics for the Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 29(2), pages 156-166, May.
    37. Alegre, Jesus & Laguna, Manuel & Pacheco, Joaquin, 2007. "Optimizing the periodic pick-up of raw materials for a manufacturer of auto parts," European Journal of Operational Research, Elsevier, vol. 179(3), pages 736-746, June.
    38. Zhang, Zizhen & Che, Oscar & Cheang, Brenda & Lim, Andrew & Qin, Hu, 2013. "A memetic algorithm for the multiperiod vehicle routing problem with profit," European Journal of Operational Research, Elsevier, vol. 229(3), pages 573-584.
    39. Azi, Nabila & Gendreau, Michel & Potvin, Jean-Yves, 2007. "An exact algorithm for a single-vehicle routing problem with time windows and multiple routes," European Journal of Operational Research, Elsevier, vol. 178(3), pages 755-766, May.
    40. Fabri, A. & Recht, P., 2006. "On dynamic pickup and delivery vehicle routing with several time windows and waiting times," Transportation Research Part B: Methodological, Elsevier, vol. 40(4), pages 335-350, May.
    41. Homberger, Jorg & Gehring, Hermann, 2005. "A two-phase hybrid metaheuristic for the vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 162(1), pages 220-238, April.
    42. Billy E. Gillett & Leland R. Miller, 1974. "A Heuristic Algorithm for the Vehicle-Dispatch Problem," Operations Research, INFORMS, vol. 22(2), pages 340-349, April.
    43. Szeto, W.Y. & Wu, Yongzhong & Ho, Sin C., 2011. "An artificial bee colony algorithm for the capacitated vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 215(1), pages 126-135, November.
    44. Rivera, Juan Carlos & Murat Afsar, H. & Prins, Christian, 2016. "Mathematical formulations and exact algorithm for the multitrip cumulative capacitated single-vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 249(1), pages 93-104.
    45. Goel, Asvin & Gruhn, Volker, 2008. "A General Vehicle Routing Problem," European Journal of Operational Research, Elsevier, vol. 191(3), pages 650-660, December.
    46. A N Letchford & J Lysgaard & R W Eglese, 2007. "A branch-and-cut algorithm for the capacitated open vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(12), pages 1642-1651, December.
    47. J-F Cordeau & G Laporte & A Mercier, 2001. "A unified tabu search heuristic for vehicle routing problems with time windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 52(8), pages 928-936, August.
    48. Q Mu & Z Fu & J Lysgaard & R Eglese, 2011. "Disruption management of the vehicle routing problem with vehicle breakdown," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(4), pages 742-749, April.
    49. Laporte, Gilbert, 1992. "The vehicle routing problem: An overview of exact and approximate algorithms," European Journal of Operational Research, Elsevier, vol. 59(3), pages 345-358, June.
    50. Marius M. Solomon, 1987. "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, INFORMS, vol. 35(2), pages 254-265, April.
    51. Baldacci, Roberto & Mingozzi, Aristide & Roberti, Roberto, 2012. "Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints," European Journal of Operational Research, Elsevier, vol. 218(1), pages 1-6.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Maria Gulnara Baldoquin & Jairo A Martinez & Jenny Díaz-Ramírez, 2020. "A unified model framework for the multi-attribute consistent periodic vehicle routing problem," PLOS ONE, Public Library of Science, vol. 15(8), pages 1-27, August.
    2. Nadia Giuffrida & Jenny Fajardo-Calderin & Antonio D. Masegosa & Frank Werner & Margarete Steudter & Francesco Pilla, 2022. "Optimization and Machine Learning Applied to Last-Mile Logistics: A Review," Sustainability, MDPI, vol. 14(9), pages 1-16, April.
    3. Ines Sbai & Saoussen Krichen & Olfa Limam, 2022. "Two meta-heuristics for solving the capacitated vehicle routing problem: the case of the Tunisian Post Office," Operational Research, Springer, vol. 22(1), pages 507-549, March.
    4. Yuxin Liu & Zihang Qin & Jin Liu, 2023. "An Improved Genetic Algorithm for the Granularity-Based Split Vehicle Routing Problem with Simultaneous Delivery and Pickup," Mathematics, MDPI, vol. 11(15), pages 1-15, July.
    5. Malika Sadou & Louiza Bouallouche-Medjkoune, 2022. "Routing protocol based ant colony optimization system for hybrid sensor and vehicular networks," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 13(6), pages 2855-2864, December.
    6. Bombelli, Alessandro & Fazi, Stefano, 2022. "The ground handler dock capacitated pickup and delivery problem with time windows: A collaborative framework for air cargo operations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 159(C).
    7. Osicka, Ondrej & Guajardo, Mario & van Oost, Thibault, 2018. "Cooperative game-theoretic features of cost sharing in location-routing," Discussion Papers 2018/11, Norwegian School of Economics, Department of Business and Management Science.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.
    2. Pillac, Victor & Gendreau, Michel & Guéret, Christelle & Medaglia, Andrés L., 2013. "A review of dynamic vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 225(1), pages 1-11.
    3. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part II: Metaheuristics," Transportation Science, INFORMS, vol. 39(1), pages 119-139, February.
    4. Zhang, Jian & Woensel, Tom Van, 2023. "Dynamic vehicle routing with random requests: A literature review," International Journal of Production Economics, Elsevier, vol. 256(C).
    5. Bhusiri, Narath & Qureshi, Ali Gul & Taniguchi, Eiichi, 2014. "The trade-off between fixed vehicle costs and time-dependent arrival penalties in a routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 62(C), pages 1-22.
    6. Diego Cattaruzza & Nabil Absi & Dominique Feillet, 2018. "Vehicle routing problems with multiple trips," Annals of Operations Research, Springer, vol. 271(1), pages 127-159, December.
    7. Diego Cattaruzza & Nabil Absi & Dominique Feillet, 2016. "Vehicle routing problems with multiple trips," 4OR, Springer, vol. 14(3), pages 223-259, September.
    8. Sébastien Mouthuy & Florence Massen & Yves Deville & Pascal Van Hentenryck, 2015. "A Multistage Very Large-Scale Neighborhood Search for the Vehicle Routing Problem with Soft Time Windows," Transportation Science, INFORMS, vol. 49(2), pages 223-238, May.
    9. Tang, Jiafu & Yu, Yang & Li, Jia, 2015. "An exact algorithm for the multi-trip vehicle routing and scheduling problem of pickup and delivery of customers to the airport," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 73(C), pages 114-132.
    10. Luciano Costa & Claudio Contardo & Guy Desaulniers, 2019. "Exact Branch-Price-and-Cut Algorithms for Vehicle Routing," Transportation Science, INFORMS, vol. 53(4), pages 946-985, July.
    11. Schneider, M., 2016. "The vehicle-routing problem with time windows and driver-specific times," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 65941, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    12. Campelo, Pedro & Neves-Moreira, Fábio & Amorim, Pedro & Almada-Lobo, Bernardo, 2019. "Consistent vehicle routing problem with service level agreements: A case study in the pharmaceutical distribution sector," European Journal of Operational Research, Elsevier, vol. 273(1), pages 131-145.
    13. Schneider, Michael, 2016. "The vehicle-routing problem with time windows and driver-specific times," European Journal of Operational Research, Elsevier, vol. 250(1), pages 101-119.
    14. Fabien Tricoire & Nathalie Bostel & Pierre Dejax & Pierre Guez, 2013. "Exact and hybrid methods for the multiperiod field service routing problem," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 21(2), pages 359-377, March.
    15. Lahyani, Rahma & Khemakhem, Mahdi & Semet, Frédéric, 2015. "Rich vehicle routing problems: From a taxonomy to a definition," European Journal of Operational Research, Elsevier, vol. 241(1), pages 1-14.
    16. Liu, Ran & Jiang, Zhibin, 2012. "The close–open mixed vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 220(2), pages 349-360.
    17. Koç, Çağrı & Bektaş, Tolga & Jabali, Ola & Laporte, Gilbert, 2016. "Thirty years of heterogeneous vehicle routing," European Journal of Operational Research, Elsevier, vol. 249(1), pages 1-21.
    18. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms," Transportation Science, INFORMS, vol. 39(1), pages 104-118, February.
    19. Nair, D.J. & Grzybowska, H. & Fu, Y. & Dixit, V.V., 2018. "Scheduling and routing models for food rescue and delivery operations," Socio-Economic Planning Sciences, Elsevier, vol. 63(C), pages 18-32.
    20. Baals, Julian & Emde, Simon & Turkensteen, Marcel, 2023. "Minimizing earliness-tardiness costs in supplier networks—A just-in-time truck routing problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 707-741.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:ijsaem:v:9:y:2018:i:1:d:10.1007_s13198-016-0493-4. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.