Taking traffic into account before route optimization: a small detail for great impacts
- February 17, 2021
- 3 mins
[CASE STUDY]
Taking into account traffic data for route optimization
Within the supply chain, the last mile is the most challenging: alone, it represents 30% of traffic in urban areas, 25% of CO2 emissions and 20% of total delivery costs.
Route optimization, by reducing costs through the optimization of resources and the reduction of the number of kilometers traveled, is the best way to meet these challenges.
However, the changing nature of the last mile makes it difficult to optimize: traffic and its variations make it difficult for carriers to meet the commitments they have made to their customers (e.g. respecting delivery times).
How do the different software solutions take into account traffic in their route optimization? What are the consequences of integrating traffic upstream versus downstream of optimization? Cédric Hervet, our Head of Innovation, answers these questions about this small detail that can have a great impact!
What is the standard method for taking traffic into account in route optimization?
Optimization algorithms base their calculations on what is called a “distance matrix”. This is the data that tells us the time and distance between each pair of points to be optimized, in one direction and in the other. The optimization algorithm will then try to find the routes that minimize the distance traveled and/or the travel time. However, the distance matrix does not depend on time in standard route optimization models. This implies that the estimate of time and/or distance between two points is unique, regardless of the start time of the trip.
It is only after the routes are optimized that the ETA calculation is adjusted by taking into account the predictive traffic at each stage of the route.
In order to anticipate that real traffic will probably increase the travel times, some adjustments are applied to the distance matrix to get a more realistic solution. But even in this case, the matrix does not depend on time since the duration between each point remains the same throughout the day.
How is this not optimal? What is the problem?
From an optimization point of view, not taking traffic into account before calculating routes is a problem since in reality, traffic has a strong impact, especially in urban areas, throughout the day. Indeed, everyone has experienced morning and evening traffic jams. On the same day, the travel time between two points can vary greatly. But while some routes will experience heavy congestion at certain times of the day, others may experience much less traffic, or at different times!
Thus, by allowing the optimization algorithm to have knowledge of the traffic evolution for each pair of points before the optimization, it allows it to make certain routes at more appropriate times and thus avoid certain heavily congested routes at certain times of the day. By calculating the impact of traffic after defining the route, we cannot anticipate these variations in the planning and we can therefore end up with routes that will encounter a lot of traffic jams, be late on some deliveries, and therefore not perform well in the end.
What is the underlying complexity of taking traffic into account before optimization?
If we want to work on a realistic estimation of the impact of traffic on travel times, we cannot consider that this impact is the same at every moment and everywhere.
Ideally, we would need to know in advance, for each pair of points to be planned, and at each moment of the day (e.g. every 10 minutes on an 8-hour workday, i.e. 48 moments). On a problem of reasonable size, where 500 points must be planned, this represents 250,000 possible routes to be identified over the 48 moments of the day, i.e. 12 million routes, which can represent several hours of computation for a distance planner, or even several days with 5,000 – 10,000 points.
Such an approach is impossible in practice, because it would mean waiting several hours before starting any optimization, which is in complete contradiction with the real-time optimization needs of the last mile delivery segment. The question is: how can we provide realistic traffic predictions, which take into account the specificities of each route and the time of day, without increasing the calculation time during route optimization?
Real-time route optimization solution
The integration of traffic fo smarter urban route planning: Kardinal’s innovative solution
Since our optimization solution is intended for the most demanding applications in last mile delivery, we have put a lot of effort into designing an optimization system that truly takes traffic into account.
Our engineers in Applied Mathematics have set up an Artificial Intelligence system capable of collecting and aggregating large-scale predictive traffic data, allowing us to estimate, upstream of the optimization, at each moment and for each trip what the duration of this trip will be, with a calculation time almost identical to an approach without traffic.
This means that we know in advance the duration of the trip with traffic between two locations A and B at 10 am on a Tuesday. The traffic prediction model is specific to this trip A to B, to this day and to this time. Thus we will not predict the same traffic impact for a trip A to C at 10am on a Tuesday, or for a trip A to B at 4pm on a Friday. Our Machine Learning algorithms refresh this data on a daily basis to provide our customers with realistic routes.
Example of a traffic pattern between two towns north of Grenoble on a very congested section of the A49 highway
The model is calculated for a Tuesday and would be different for another day of the week. We automatically refresh the models every two weeks to take into account changes, works or unexpected events (such as Covid-19, for example).
On this route, the travel time without traffic is about 15 minutes. However, this section of the A49 highway is often very busy and makes traffic difficult, especially for trucks. Thus, we can see that the travel time during the day is always between 27 and 29 minutes, with two slight peaks that match the busiest times of the day.
Example of a traffic pattern between the north and south of Grenoble, using the ring road:
These two examples prove that it is possible to monitor different traffic trends for two routes and thus understand local traffic patterns over time.
Our route optimization algorithms are natively designed to work on the basis of time-dependent distance matrices. This allows them to design routes that avoid congested roads during peak hours and take advantage of off-peak hours to deliver to urban areas when possible. Our users benefit from more efficient and reliable routes as they are more realistic.
