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 Scientific Director, 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?