The Time-Dependent Shortest Path and Vehicle Routing Problem
1 : Laboratoire CIRRELT Université Laval Quebec
(CIRRELT)
-
Website
* : Corresponding author
Université Laval Pavillon Palasis-Prince, bureau 2642 2325, rue de la Terrasse Québec (Québec) G1V 0A6 CANADA -
Canada
Many of today's logistics systems are based on variants of the well-known vehicle routing problem (VRP). In VRP one needs to answer a simple question: in which sequence should we visit a set of clients in order to minimize mainly the total distance. Advances in communications and real-time data acquisition technologies have made it possible to collect a huge amount of data on vehicles such as their driving speed and CO2 emission. This has led to what is known as the time-dependent VRP, in which the time (or cost) to move from one customer to another change depending on the starting time.
In this work we integrate the time-dependent shortest path within the time-dependent VRP to create a more general and realistic problem called the time-dependent shortest path and vehicle routing problem (TDSPVRP). TDSPVRP effectively determines the path to take when visiting customers by considering both the real underlying street map and the real travel time to each them. We provide a mathematical formulation for the problem and also develop valid inequalities to strengthen this formulation which significantly improve the lower bounds. Given the size and difficulty of the problem, a heuristic based on the local search and simulated annealing is proposed. Finally, we provide a sensitivity analysis that highlights the importance of incorporating traffic in routing models and how ignoring traffic data can impose substantial delays.
| Subject : | : | Abstracts |
| Topics | : | Special Session: Time-Dependent Vehicle Routing Problem (organized by Emanuela Guerriero) |
| Keywords | : | Time Dependent Shortest Path ; Time Dependent Vehicle Routing Problem ; Traffic and congestion ; City logistics ; Heuristic ; Simulated annealing |
| PDF version | : |  PDF version |
