IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v195y2009i3p761-769.html
   My bibliography  Save this article

An evolutionary algorithm for the vehicle routing problem with route balancing

Author

Listed:
  • Jozefowiez, Nicolas
  • Semet, Frédéric
  • Talbi, El-Ghazali

Abstract

In this paper, we address a bi-objective vehicle routing problem in which the total length of routes is minimized as well as the balance of routes, i.e. the difference between the maximal route length and the minimal route length. We propose a meta-heuristic method based on an evolutionary algorithm involving classical multi-objective operators. To improve its efficiency, two mechanisms, which favor the diversification of the search, have been added. First, an elitist diversification mechanism is used in cooperation with classical diversification methodologies. Second, a parallel model designed to take into account the elitist diversification is proposed. Our method is tested on standard benchmarks for the vehicle routing problem. The contribution of the introduced mechanisms is evaluated by different performance metrics. All the experimentations indicate a strict improvement of the generated Pareto set.

Suggested Citation

  • Jozefowiez, Nicolas & Semet, Frédéric & Talbi, El-Ghazali, 2009. "An evolutionary algorithm for the vehicle routing problem with route balancing," European Journal of Operational Research, Elsevier, vol. 195(3), pages 761-769, June.
    • Handle: RePEc:eee:ejores:v:195:y:2009:i:3:p:761-769
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(07)01100-9
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. Michel Gendreau & Alain Hertz & Gilbert Laporte, 1994. "A Tabu Search Heuristic for the Vehicle Routing Problem," Management Science, INFORMS, vol. 40(10), pages 1276-1290, October.
    2. Rita Ribeiro & Helena Ramalhinho-Lourenço, 2001. "A multi-objective model for a multi-period distribution management problem," Economics Working Papers 532, Department of Economics and Business, Universitat Pompeu Fabra.
    3. 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.
    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. Lehuédé, Fabien & Péton, Olivier & Tricoire, Fabien, 2020. "A lexicographic minimax approach to the vehicle routing problem with route balancing," European Journal of Operational Research, Elsevier, vol. 282(1), pages 129-147.
    2. Polimeni, Antonio & Russo, Francesco & Vitetta, Antonino, 2010. "Demand and routing models for urban goods movement simulation," European Transport \ Trasporti Europei, ISTIEE, Institute for the Study of Transport within the European Economic Integration, issue 46, pages 3-23.
    3. J Euchi & H Chabchoub, 2011. "Hybrid metaheuristics for the profitable arc tour problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(11), pages 2013-2022, November.
    4. Dukkanci, Okan & Karsu, Özlem & Kara, Bahar Y., 2022. "Planning sustainable routes: Economic, environmental and welfare concerns," European Journal of Operational Research, Elsevier, vol. 301(1), pages 110-123.
    5. Mancini, Simona & Gansterer, Margaretha & Hartl, Richard F., 2021. "The collaborative consistent vehicle routing problem with workload balance," European Journal of Operational Research, Elsevier, vol. 293(3), pages 955-965.
    6. 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.
    7. Chen, Xinwei & Wang, Tong & Thomas, Barrett W. & Ulmer, Marlin W., 2023. "Same-day delivery with fair customer service," European Journal of Operational Research, Elsevier, vol. 308(2), pages 738-751.
    8. Soriano, Adria & Gansterer, Margaretha & Hartl, Richard F., 2023. "The multi-depot vehicle routing problem with profit fairness," International Journal of Production Economics, Elsevier, vol. 255(C).
    9. Soriano, Adria & Gansterer, Margaretha & Hartl, Richard F., 2022. "Reprint of: The multi-depot vehicle routing problem with profit fairness," International Journal of Production Economics, Elsevier, vol. 250(C).
    10. Qingqing Qiao & Fengming Tao & Hailin Wu & Xuewei Yu & Mengjun Zhang, 2020. "Optimization of a Capacitated Vehicle Routing Problem for Sustainable Municipal Solid Waste Collection Management Using the PSO-TS Algorithm," IJERPH, MDPI, vol. 17(6), pages 1-22, March.
    11. Joaquín Pacheco & Manuel Laguna, 2020. "Vehicle routing for the urgent delivery of face shields during the COVID-19 pandemic," Journal of Heuristics, Springer, vol. 26(5), pages 619-635, October.
    12. Feng, Bo & Jiang, Zhong-Zhong & Fan, Zhi-Ping & Fu, Na, 2010. "A method for member selection of cross-functional teams using the individual and collaborative performances," European Journal of Operational Research, Elsevier, vol. 203(3), pages 652-661, June.
    13. Naji-Azimi, Zahra & Salari, Majid & Renaud, Jacques & Ruiz, Angel, 2016. "A practical vehicle routing problem with desynchronized arrivals to depot," European Journal of Operational Research, Elsevier, vol. 255(1), pages 58-67.
    14. Liu, Ran & Xie, Xiaolan & Garaix, Thierry, 2014. "Hybridization of tabu search with feasible and infeasible local searches for periodic home health care logistics," Omega, Elsevier, vol. 47(C), pages 17-32.
    15. Rodrigo Linfati & Fernando Yáñez-Concha & John Willmer Escobar, 2022. "Mathematical Models for the Vehicle Routing Problem by Considering Balancing Load and Customer Compactness," Sustainability, MDPI, vol. 14(19), pages 1-20, October.
    16. Margaretha Gansterer & Richard F. Hartl & Sarah Wieser, 2021. "Assignment constraints in shared transportation services," Annals of Operations Research, Springer, vol. 305(1), pages 513-539, October.
    17. Halvorsen-Weare, Elin E. & Savelsbergh, Martin W.P., 2016. "The bi-objective mixed capacitated general routing problem with different route balance criteria," European Journal of Operational Research, Elsevier, vol. 251(2), pages 451-465.
    18. Ramos, Tânia Rodrigues Pereira & Gomes, Maria Isabel & Barbosa-Póvoa, Ana Paula, 2014. "Planning a sustainable reverse logistics system: Balancing costs with environmental and social concerns," Omega, Elsevier, vol. 48(C), pages 60-74.
    19. P. Matl & R. F. Hartl & T. Vidal, 2018. "Workload Equity in Vehicle Routing Problems: A Survey and Analysis," Transportation Science, INFORMS, vol. 52(2), pages 239-260, March.
    20. N. Norouzi & R. Tavakkoli-Moghaddam & M. Ghazanfari & M. Alinaghian & A. Salamatbakhsh, 2012. "A New Multi-objective Competitive Open Vehicle Routing Problem Solved by Particle Swarm Optimization," Networks and Spatial Economics, Springer, vol. 12(4), pages 609-633, December.
    21. Yu, Yang & Wu, Yuting & Wang, Junwei, 2019. "Bi-objective green ride-sharing problem: Model and exact method," International Journal of Production Economics, Elsevier, vol. 208(C), pages 472-482.
    22. Cortinhal, Maria João & Mourão, Maria Cândida & Nunes, Ana Catarina, 2016. "Local search heuristics for sectoring routing in a household waste collection context," European Journal of Operational Research, Elsevier, vol. 255(1), pages 68-79.
    23. Shah, Nirav & Kumar, Subodha & Bastani, Farokh & Yen, I-Ling, 2012. "Optimization models for assessing the peak capacity utilization of intelligent transportation systems," European Journal of Operational Research, Elsevier, vol. 216(1), pages 239-251.

    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. 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.
    2. 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.
    3. 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.
    4. Taillard, Eric D. & Gambardella, Luca M. & Gendreau, Michel & Potvin, Jean-Yves, 2001. "Adaptive memory programming: A unified view of metaheuristics," European Journal of Operational Research, Elsevier, vol. 135(1), pages 1-16, November.
    5. 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.
    6. 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.
    7. A Ghanmi, 2011. "Canadian forces global reach support hubs: facility location and aircraft routing models," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(4), pages 638-650, April.
    8. Nathan Companez & Aldeida Aleti, 2016. "Can Monte-Carlo Tree Search learn to sacrifice?," Journal of Heuristics, Springer, vol. 22(6), pages 783-813, December.
    9. 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.
    10. Sahar Validi & Arijit Bhattacharya & P. J. Byrne, 2020. "Sustainable distribution system design: a two-phase DoE-guided meta-heuristic solution approach for a three-echelon bi-objective AHP-integrated location-routing model," Annals of Operations Research, Springer, vol. 290(1), pages 191-222, July.
    11. 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.
    12. Kandula, Shanthan & Krishnamoorthy, Srikumar & Roy, Debjit, 2020. "A Predictive and Prescriptive Analytics Framework for Efficient E-Commerce Order Delivery," IIMA Working Papers WP 2020-11-01, Indian Institute of Management Ahmedabad, Research and Publication Department.
    13. 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.
    14. César Rego, 1998. "A Subpath Ejection Method for the Vehicle Routing Problem," Management Science, INFORMS, vol. 44(10), pages 1447-1459, October.
    15. 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.
    16. Tino Henke & M. Grazia Speranza & Gerhard Wäscher, 2014. "The Multi-Compartment Vehicle Routing Problem with Flexible Compartment Sizes," FEMM Working Papers 140006, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.
    17. Barbara De Rosa & Gennaro Improta & Gianpaolo Ghiani & Roberto Musmanno, 2002. "The Arc Routing and Scheduling Problem with Transshipment," Transportation Science, INFORMS, vol. 36(3), pages 301-313, August.
    18. R. Baldacci & E. Hadjiconstantinou & A. Mingozzi, 2004. "An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-Commodity Network Flow Formulation," Operations Research, INFORMS, vol. 52(5), pages 723-738, October.
    19. Müller, Juliane, 2010. "Approximative solutions to the bicriterion Vehicle Routing Problem with Time Windows," European Journal of Operational Research, Elsevier, vol. 202(1), pages 223-231, April.
    20. Yin, Yunqiang & Li, Dongwei & Wang, Dujuan & Ignatius, Joshua & Cheng, T.C.E. & Wang, Sutong, 2023. "A branch-and-price-and-cut algorithm for the truck-based drone delivery routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1125-1144.

    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:eee:ejores:v:195:y:2009:i:3:p:761-769. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.