IDEAS home Printed from https://ideas.repec.org/a/spr/operea/v21y2021i3d10.1007_s12351-019-00521-0.html
   My bibliography  Save this article

Efficient implementation of the genetic algorithm to solve rich vehicle routing problems

Author

Listed:
  • Bochra Rabbouch

    (Université de Tunis)

  • Foued Saâdaoui

    (King Abdulaziz University)

  • Rafaa Mraihi

    (Université de Manouba)

Abstract

The aim of this paper is to further study the rich vehicle routing problem (RVRP), which is a well-known combinatorial optimization problem arising in many transportation and logistics settings. This problem is known to be subject to a number of real life constraints, such as the number and capacity limitation of vehicles, time constraints including ready and due dates for each customer, heterogeneous vehicle fleets and different warehouses for vehicles. A Genetic Algorithm (GA)-based approach is proposed to tackle this highly constrained problem. The proposed approach efficiently resolves the problem despite its high complexity. To the best of our knowledge, no GA have been used for solving multi-depot heterogeneous limited fleet VRP with time windows so far. The new algorithm has been tested on benchmark and real-world instances. In fact, promising computational results have shown its good cost-effectiveness.

Suggested Citation

  • Bochra Rabbouch & Foued Saâdaoui & Rafaa Mraihi, 2021. "Efficient implementation of the genetic algorithm to solve rich vehicle routing problems," Operational Research, Springer, vol. 21(3), pages 1763-1791, September.
    • Handle: RePEc:spr:operea:v:21:y:2021:i:3:d:10.1007_s12351-019-00521-0
    DOI: 10.1007/s12351-019-00521-0
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s12351-019-00521-0
    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/s12351-019-00521-0?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. Thibaut Vidal & Teodor Gabriel Crainic & Michel Gendreau & Nadia Lahrichi & Walter Rei, 2012. "A Hybrid Genetic Algorithm for Multidepot and Periodic Vehicle Routing Problems," Operations Research, INFORMS, vol. 60(3), pages 611-624, June.
    2. 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.
    3. Jian Li & Yang Li & Panos M. Pardalos, 2016. "Multi-depot vehicle routing problem with time windows under shared depot resources," Journal of Combinatorial Optimization, Springer, vol. 31(2), pages 515-532, February.
    4. Eskandarpour, Majid & Ouelhadj, Djamila & Hatami, Sara & Juan, Angel A. & Khosravi, Banafsheh, 2019. "Enhanced multi-directional local search for the bi-objective heterogeneous vehicle routing problem with multiple driving ranges," European Journal of Operational Research, Elsevier, vol. 277(2), pages 479-491.
    5. Jean-Yves Potvin & Samy Bengio, 1996. "The Vehicle Routing Problem with Time Windows Part II: Genetic Search," INFORMS Journal on Computing, INFORMS, vol. 8(2), pages 165-172, May.
    6. J-F Cordeau & G Laporte & A Mercier, 2004. "Improved tabu search algorithm for the handling of route duration constraints in vehicle routing problems with time windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(5), pages 542-546, May.
    7. Jean-Yves Potvin & Tanguy Kervahut & Bruno-Laurent Garcia & Jean-Marc Rousseau, 1996. "The Vehicle Routing Problem with Time Windows Part I: Tabu Search," INFORMS Journal on Computing, INFORMS, vol. 8(2), pages 158-164, May.
    8. Houda Derbel & Bassem Jarboui & Rim Bhiri, 2019. "A skewed general variable neighborhood search algorithm with fixed threshold for the heterogeneous fleet vehicle routing problem," Annals of Operations Research, Springer, vol. 272(1), pages 243-272, January.
    9. Tilk, Christian & Drexl, Michael & Irnich, Stefan, 2019. "Nested branch-and-price-and-cut for vehicle routing problems with multiple resource interdependencies," European Journal of Operational Research, Elsevier, vol. 276(2), pages 549-565.
    10. 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.
    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. Fang Zhao & Bingfeng Si & Zhenlin Wei & Tianwei Lu, 2023. "Time-dependent vehicle routing problem of perishable product delivery considering the differences among paths on the congested road," Operational Research, Springer, vol. 23(1), pages 1-23, March.

    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. Schneider, Michael & Schwahn, Fabian & Vigo, Daniele, 2017. "Designing granular solution methods for routing problems with time windows," European Journal of Operational Research, Elsevier, vol. 263(2), pages 493-509.
    2. Derigs, U. & Kaiser, R., 2007. "Applying the attribute based hill climber heuristic to the vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 177(2), pages 719-732, March.
    3. İbrahim Muter & Ş. İlker Birbil & Güvenç Şahin, 2010. "Combination of Metaheuristic and Exact Algorithms for Solving Set Covering-Type Optimization Problems," INFORMS Journal on Computing, INFORMS, vol. 22(4), pages 603-619, November.
    4. 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.
    5. Joaquín Pacheco & Rafael Caballero & Manuel Laguna & Julián Molina, 2013. "Bi-Objective Bus Routing: An Application to School Buses in Rural Areas," Transportation Science, INFORMS, vol. 47(3), pages 397-411, August.
    6. Bo Sun & Ming Wei & Senlai Zhu, 2018. "Optimal Design of Demand-Responsive Feeder Transit Services with Passengers’ Multiple Time Windows and Satisfaction," Future Internet, MDPI, vol. 10(3), pages 1-15, March.
    7. Fulin Xie & Chris N. Potts & Tolga Bektaş, 2017. "Iterated local search for workforce scheduling and routing problems," Journal of Heuristics, Springer, vol. 23(6), pages 471-500, December.
    8. 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.
    9. Puca Huachi Vaz Penna & Anand Subramanian & Luiz Satoru Ochi & Thibaut Vidal & Christian Prins, 2019. "A hybrid heuristic for a broad class of vehicle routing problems with heterogeneous fleet," Annals of Operations Research, Springer, vol. 273(1), pages 5-74, February.
    10. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2014. "A unified solution framework for multi-attribute vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 234(3), pages 658-673.
    11. 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.
    12. Sumanta Basu & Ghosh, Diptesh, 2008. "A review of the Tabu Search Literature on Traveling Salesman Problems," IIMA Working Papers WP2008-10-01, Indian Institute of Management Ahmedabad, Research and Publication Department.
    13. Schmid, Verena & Doerner, Karl F. & Laporte, Gilbert, 2013. "Rich routing problems arising in supply chain management," European Journal of Operational Research, Elsevier, vol. 224(3), pages 435-448.
    14. repec:iim:iimawp:14638 is not listed on IDEAS
    15. Michelle Dunbar & Simon Belieres & Nagesh Shukla & Mehrdad Amirghasemi & Pascal Perez & Nishikant Mishra, 2020. "A genetic column generation algorithm for sustainable spare part delivery: application to the Sydney DropPoint network," Annals of Operations Research, Springer, vol. 290(1), pages 923-941, July.
    16. Liu, Fuh-Hwa Franklin & Shen, Sheng-Yuan, 1999. "A route-neighborhood-based metaheuristic for vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 118(3), pages 485-504, November.
    17. Sana Jawarneh & Salwani Abdullah, 2015. "Sequential Insertion Heuristic with Adaptive Bee Colony Optimisation Algorithm for Vehicle Routing Problem with Time Windows," PLOS ONE, Public Library of Science, vol. 10(7), pages 1-23, July.
    18. Paraskevopoulos, Dimitris C. & Laporte, Gilbert & Repoussis, Panagiotis P. & Tarantilis, Christos D., 2017. "Resource constrained routing and scheduling: Review and research prospects," European Journal of Operational Research, Elsevier, vol. 263(3), pages 737-754.
    19. Nabil Absi & Diego Cattaruzza & Dominique Feillet & Sylvain Housseman, 2017. "A relax-and-repair heuristic for the Swap-Body Vehicle Routing Problem," Annals of Operations Research, Springer, vol. 253(2), pages 957-978, June.
    20. Russell Bent & Pascal Van Hentenryck, 2004. "A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 38(4), pages 515-530, November.
    21. Ghosh, Diptesh & Sumanta Basu, 2011. "Diversified Local Search for the Traveling Salesman Problem," IIMA Working Papers WP2011-01-03, Indian Institute of Management Ahmedabad, Research and Publication Department.

    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:operea:v:21:y:2021:i:3:d:10.1007_s12351-019-00521-0. 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.