910. Design of PVRP heuristic for parcel deliveries in a metropolitan area
Invited abstract in session TE-29: Last Mile Delivery, cluster Location, Network Design, and Routing.
Tuesday, 16:15-17:45Room: FENH302
Authors (first author is the speaker)
| 1. | Juan Cantillana
|
| Universidad de Chile/Nezasa | |
| 2. | Cristian E. Cortes
|
| Universidad de Chile, ISCI | |
| 3. | Fernando Ordonez
|
| Universidad de Chile | |
| 4. | Claudio Cerda
|
| Agrosuper S.A. |
Abstract
The Periodic Vehicle Routing Problem (PVRP) considers multiple visits to a set of locations over a planning horizon, typically of multiple days, leading to large, difficult to solve routing problems. To address this challenge, we propose a heuristic approach dividing the PVRP into two parts: a daily routing problem and a scheduling problem. By using well-known and fast routing solutions, we can efficiently solve the routing problem. The scheduling problem determines the locations to be visited each day of the planning horizon, aiming to minimize an approximate routing cost estimate for each day.
On small instances, our heuristic method has, on average, a 16.9% gap to the best bound, where 9% of this gap is explained by the scheduling problem. We also tested our method on a real-world, large food producer, with over 30,000 stops per month, comparing our method to the current company solution and to using a routing solution with the current daily customer assignment. Our heuristic solution achieved savings of 32% compared to the current company solution and 11% with respect to using a routing solution in the case of high demand. In a scenario with low demand, we achieved savings of 35% compared to the current company solution and 1% with respect to using a routing solution. Our method makes use of VRP algorithms already in use in the industry, making it a practical and accessible solution for real-world applications.
Keywords
- Optimization Models and Methods
- VRP
- Logistics
Status: accepted
Back to the list of papers