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

• Author(s): Silva, Adriano S. ; Lima, José ; Silva, Adrián ; Gomes, Helder ; Pereira, Ana I.
• Date: 2024
• Persistent ID: http://hdl.handle.net/10198/30332
• Origin: Biblioteca Digital do IPB
• Subject(s): VVRP; Metaheuristic; Scheduling Problems
• Document Type: Conference paper
• Language: English
• Contributor(s): Biblioteca Digital do IPB

Description

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.