Loading...
Publication
Execution time experiments to solve capacitated vehicle routing problem
| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 2.77 MB | Adobe PDF |
Advisor(s)
Abstract(s)
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).
Description
Keywords
Open-source Route planning Versatile algorithm
Pedagogical Context
Citation
Silva, Adriano S.; Lima, José; Pereira, Ana I.; Silva, Adrián; Gomes, Helder (2023). Execution time experiments to solve capacitated vehicle routing problem. In 23rd International Conference on Computational Science and Its Applications (ICCSA). ISSN 0302-9743. 14111, p. 273-289
Publisher
Springer Nature