Execution Time Experiments to Solve Capacitated Vehicle Routing Problem Chapter Conference Paper uri icon


  • 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/50020/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.

publication date

  • 2023