Time-Dependency of Guided Local Search to Solve the Capacitated Vehicle Routing Problem with Time Windows

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

http://hdl.handle.net/10198/30332

Use this identifier to reference this record.

Name:	Description:	Size:	Format:
Time-Dependency of Guided Local Search.pdf		1.84 MB	Adobe PDF	Download

Send Feedback

Authors

Abstract(s)

Research have been driven by the increased demand for delivery and pick-up services to develop new formulations and algorithms for solving Vehicle Routing Problems (VRP). The main objective is to create algorithms that can identify paths considering execution time in real-world scenarios. This study focused on using the Guided Local Search (GLS) metaheuristic available in OR-Tools to solve the Capacitated Vehicle Routing Problem with Time Windows using the Solomons instances. The execution time was used as a stop criterion, with short runs ranging from 1 to 10 s and a long run of 360 s for comparison. The results showed that the GLS metaheuristic from OR-Tools is applicable for achieving high performance in finding the shortest path and optimizing routes within constrained execution times. It outperformed the best-known solutions from the literature in longer execution times and even provided a close-to-optimal solution within 10 s. These findings suggest the potential application of this tool for dynamic VRP scenarios that require faster algorithms.

Keywords

VVRP Metaheuristic Scheduling Problems

URI

http://hdl.handle.net/10198/30332

Citation

Silva, Adriano S.; Lima, José; Silva, Adrián M. T.; Gomes, Helder T.; Pereira, Ana I. (2024). Time-Dependency of Guided Local Search to Solve the Capacitated Vehicle Routing Problem with Time Windows. In 3rd International Conference on Optimization, Learning Algorithms and Applications (OL2A 2023). Cham: Springer Nature, Vol. 1, p. 93–108. ISBN 978-3-031-53024-1.