Execution Time Experiments to Solve Capacitated Vehicle Routing Problem | SpringerLink
Skip to main content
Springer Nature Link
Log in

Execution Time Experiments to Solve Capacitated Vehicle Routing Problem

  • Conference paper
  • First Online:
Computational Science and Its Applications – ICCSA 2023 Workshops (ICCSA 2023)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14111))

Included in the following conference series:

Abstract

Studies dealing with route optimization have received considerable attention in recent years due to the increased demand for transportation services. For decades, scholars have developed robust algorithms designed to solve various Vehicle Routing Problems (VRP). In most cases, the focus is to present an algorithm that can overcome the shortest distances reported in other studies. On the other hand, execution time is also an important parameter that may limit the feasibility of the utilization in real scenarios for some applications. For this reason, in this work, a Guided Local Search (GLS) metaheuristic available in open-source OR-Tools will be tested to solve the Augerat instances of Capacitated Vehicle Routing Problems (CVRP). The stop criterion used here is the execution time, going from 1 s (standard) to 10 s, with a last run of 360 s. The numerical results demonstrate that increasing the execution time returns significant improvement in distance optimization. However, the optimization found considering high execution times can be expensive in terms of time, and not feasible for situations demanding faster algorithms, such as in Dynamic Vehicle Routing Problems (DVRP). Nonetheless, the GLS has proven to be a versatile algorithm for use where distance optimization is the main priority (high execution times) and in cases where faster algorithms are required (low execution times).

This work has been supported by FCT - Fundação para a Ciência e Tecnologia within the R&D Units Project Scope: UIDB/05757/2020, UIDP/05757/2020, UIDB/00690/2020, UIDB/50 020/2020, and UIDB/00319/2020. Adriano Silva was supported by Doctoral Grant SFRH/BD/151346/2021 financed by the Portuguese Foundation for Science and Technology (FCT), and with funds from NORTE 2020, under MIT Portugal Program.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 12583
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 15729
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

References

  1. Abdelatti, M.F., Sodhi, M.S.: An improved GPU-accelerated heuristic technique applied to the capacitated vehicle routing problem. In: Proceedings of the 2020 Genetic and Evolutionary Computation Conference, pp. 663–671 (2020). https://doi.org/10.1145/3377930.3390159

  2. Augerat, P., Naddef, D., Belenguer, J., Benavent, E., Corberan, A., Rinaldi, G.: Computational results with a branch and cut code for the capacitated vehicle routing problem (1995)

    Google Scholar 

  3. Braekers, K., Ramaekers, K., Van Nieuwenhuyse, I.: The vehicle routing problem: state of the art classification and review. Comput. Indust. Eng. 99, 300–313 (2016). https://doi.org/10.1016/j.cie.2015.12.007

    Article  Google Scholar 

  4. Breed, A.K., Speth, D., Plötz, P.: \(\text{ CO}_{{2}}\) fleet regulation and the future market diffusion of zero-emission trucks in Europe. Energy Policy 159, 112640 (2021). https://doi.org/10.1016/j.enpol.2021.112640

    Article  Google Scholar 

  5. Dantzig, G.B., Ramser, J.H.: The truck dispatching problem. Manage. Sci. 6(1), 80–91 (1959). https://doi.org/10.1287/mnsc.6.1.80

    Article  MathSciNet  Google Scholar 

  6. Desaulniers, G., Errico, F., Irnich, S., Schneider, M.: Exact algorithms for electric vehicle-routing problems with time windows. Oper. Res. 64(6), 1388–1405 (2016). https://doi.org/10.1287/opre.2016.1535

    Article  MathSciNet  Google Scholar 

  7. Dhanya, K.M., Kanmani, S., Hanitha, G., Abirami, S.: Hybrid crow search-ant colony optimization algorithm for capacitated vehicle routing problem. In: Zelinka, I., Senkerik, R., Panda, G., Lekshmi Kanthan, P.S. (eds.) ICSCS 2018. CCIS, vol. 837, pp. 46–52. Springer, Singapore (2018). https://doi.org/10.1007/978-981-13-1936-5_5

    Chapter  Google Scholar 

  8. Dohn, A., Rasmussen, M.S., Larsen, J.: The vehicle routing problem with time windows and temporal dependencies. Networks 58(4), 273–289 (2011). https://doi.org/10.1002/net.20472

    Article  MathSciNet  Google Scholar 

  9. Dubois, F., Renaud-Goud, P., Stolf, P.: Capacitated vehicle routing problem under deadlines: an application to flooding crisis. IEEE Access 10, 45629–45642 (2022). https://doi.org/10.1109/ACCESS.2022.3170446

    Article  Google Scholar 

  10. Haghani, A., Jung, S.: A dynamic vehicle routing problem with time-dependent travel times. Comput. Oper. Res. 32(11), 2959–2986 (2005). https://doi.org/10.1016/j.cor.2004.04.013

    Article  Google Scholar 

  11. Hannan, M., Akhtar, M., Begum, R., Basri, H., Hussain, A., Scavino, E.: Capacitated vehicle-routing problem model for scheduled solid waste collection and route optimization using PSO algorithm. Waste Manag. 71, 31–41 (2018). https://doi.org/10.1016/j.wasman.2017.10.019. https://www.sciencedirect.com/science/article/pii/S0956053X17307675

  12. Jia, Y.H., Mei, Y., Zhang, M.: Confidence-based ant colony optimization for capacitated electric vehicle routing problem with comparison of different encoding schemes. IEEE Trans. Evol. Comput. 26(6), 1394–1408 (2022). https://doi.org/10.1109/TEVC.2022.3144142

    Article  Google Scholar 

  13. Jozefowiez, N., Semet, F., Talbi, E.G.: Multi-objective vehicle routing problems. Eur. J. Oper. Res. 189(2), 293–309 (2008). https://doi.org/10.1016/j.ejor.2007.05.055

    Article  MathSciNet  Google Scholar 

  14. Mehmood, T.: Does information technology competencies and fleet management practices lead to effective service delivery? Empirical evidence from e-commerce industry. Int. J. Technol. Innov. Manag. (IJTIM) 1(2), 14–41 (2021). https://doi.org/10.54489/ijtim.v1i2.26

  15. Mohammed, M.A., et al.: Solving vehicle routing problem by using improved k-nearest neighbor algorithm for best solution. J. Comput. Sci. 21, 232–240 (2017). https://doi.org/10.1016/j.jocs.2017.04.012

    Article  Google Scholar 

  16. Montoya, A., Guéret, C., Mendoza, J.E., Villegas, J.G.: The electric vehicle routing problem with nonlinear charging function. Transport. Res. Part B: Methodol. 103, 87–110 (2017). https://doi.org/10.1016/j.trb.2017.02.004

    Article  Google Scholar 

  17. Pillac, V., Gendreau, M., Guéret, C., Medaglia, A.L.: A review of dynamic vehicle routing problems. Eur. J. Oper. Res. 225(1), 1–11 (2013). https://doi.org/10.1016/j.ejor.2012.08.015

    Article  MathSciNet  Google Scholar 

  18. Pisinger, D., Ropke, S.: A general heuristic for vehicle routing problems. Comput. Oper. Res. 34(8), 2403–2435 (2007). https://doi.org/10.1016/j.cor.2005.09.012

    Article  MathSciNet  Google Scholar 

  19. Praveen, V., Keerthika, P., Sivapriya, G., Sarankumar, A., Bhasker, B.: Vehicle routing optimization problem: a study on capacitated vehicle routing problem. Mater. Today: Proceed. 64, 670–674 (2022). https://doi.org/10.1016/j.matpr.2022.05.185

    Article  Google Scholar 

  20. Silva, A.S., et al.: Solving a capacitated waste collection problem using an open-source tool. In: Gervasi, O., Murgante, B., Misra, S., Rocha, A.M.A.C., Garau, C. (eds.) Computational Science and Its Applications - ICCSA 2022 Workshops. ICCSA 2022. Lecture Notes in Computer Science, vol. 13378, pp. 140–156. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-10562-3_11

  21. Silva, A.S., et al.: Dynamic urban solid waste management system for smart cities. In: Simos, D.E., Rasskazova, V.A., Archetti, F., Kotsireas, I.S., Pardalos, P.M. (eds.) Learning and Intelligent Optimization. LION 2022. Lecture Notes in Computer Science, vol. 13621, pp. 178–190. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-24866-5_14

  22. Silva, A.S., et al.: Capacitated waste collection problem solution using an open-source tool. Computers 12(1), 15 (2023). https://doi.org/10.3390/computers12010015. https://www.mdpi.com/2073-431X/12/1/15

  23. Siskos, P., Moysoglou, Y.: Assessing the impacts of setting \(\text{ CO}_{{2}}\) emission targets on truck manufacturers: a model implementation and application for the EU. Transport. Res. Part A: Policy Pract. 125, 123–138 (2019). https://doi.org/10.1016/j.tra.2019.05.010

    Article  Google Scholar 

  24. Tian, J., Yang, D., Zhang, H., Liu, L.: Classification method of energy efficiency and \(\text{ CO}_{{2}}\) emission intensity of commercial trucks in china’s road transport. Procedia Eng. 137, 75–84 (2016). https://doi.org/10.1016/j.proeng.2016.01.236. Green Intelligent Transportation System and Safety

  25. Toth, P., Vigo, D.: The vehicle routing problem. SIAM (2002). https://doi.org/10.1137/1.9780898718515

  26. Vidal, T., Laporte, G., Matl, P.: A concise guide to existing and emerging vehicle routing problem variants. Eur. J. Oper. Res. 286(2), 401–416 (2020). https://doi.org/10.1016/j.ejor.2019.10.010

    Article  MathSciNet  Google Scholar 

  27. Voudouris, C., Tsang, E.P., Alsheddy, A.: Guided local search. In: Gendreau, M., Potvin, JY. (eds.) Handbook of Metaheuristics. International Series in Operations Research & Management Science, vol. 146, pp. 321–361. Springer, MA (2010). https://doi.org/10.1007/978-1-4419-1665-5_11

Download references

Author information

Authors and Affiliations

  1. Research Centre in Digitalization and Intelligent Robotics (CeDRI), Instituto Politécnico de Bragança, 5300-253, Bragança, Portugal

    Adriano S. Silva, José Lima & Ana I. Pereira

  2. Centro de Investigação de Montanha (CIMO), Instituto Politécnico de Bragança, 5300-253, Bragança, Portugal

    Adriano S. Silva & Helder T. Gomes

  3. Laboratório Associado para a Sustentabilidade e Tecnologia em Regiões de Montanha (SusTEC), Instituto Politécnico de Bragança, 5300-253, Bragança, Portugal

    Adriano S. Silva, José Lima, Ana I. Pereira, Adrián M. T. Silva & Helder T. Gomes

  4. Laboratory of Separation and Reaction Engineering - Laboratory of Catalysis and Materials (LSRE-LCM), Faculty of Engineering, University of Porto, Porto, Portugal

    Adriano S. Silva & Adrián M. T. Silva

  5. ALiCE - Associate Laboratory in Chemical Engineering, Faculty of Engineering, University of Porto, Porto, Portugal

    Adriano S. Silva

Authors
  1. Adriano S. Silva
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. José Lima
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ana I. Pereira
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Adrián M. T. Silva
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Helder T. Gomes
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Adriano S. Silva .

Editor information

Editors and Affiliations

  1. University of Perugia, Perugia, Italy

    Osvaldo Gervasi

  2. University of Basilicata, Potenza, Italy

    Beniamino Murgante

  3. University of Minho, Braga, Portugal

    Ana Maria A. C. Rocha

  4. University of Cagliari, Cagliari, Italy

    Chiara Garau

  5. University of Basilicata, Potenza, Italy

    Francesco Scorza

  6. University of Massachusetts Medical School, Worcester, MA, USA

    Yeliz Karaca

  7. Polytechnic University of Bari, Bari, Italy

    Carmelo M. Torre

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Silva, A.S., Lima, J., Pereira, A.I., Silva, A.M.T., Gomes, H.T. (2023). Execution Time Experiments to Solve Capacitated Vehicle Routing Problem. In: Gervasi, O., et al. Computational Science and Its Applications – ICCSA 2023 Workshops. ICCSA 2023. Lecture Notes in Computer Science, vol 14111. Springer, Cham. https://doi.org/10.1007/978-3-031-37126-4_19

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-37126-4_19

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-37125-7

  • Online ISBN: 978-3-031-37126-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics