Route optimization

The importance of modelling traffic in logistic optimization

The best way to effectively plan delivery is to use a planning tool that does it for you. Such a tool must be flexible enough so that the delivery planner can include all of its delivery constraints such as truck capacity, multiple time windows, etc. In addition, the tool must be accurate enough so that the chance that the deliveries occur as planned are increased and the best possible route is chosen. A good traffic model is crucial to ensure the latter.

Most delivery and route planning tool providers do not include any traffic model while calculating the traveling time between point A and B. A few of them include a very simple traffic model where the traffic is only dependent on the time of the day, independent of where you are in the city. However, this proves to be insufficient as the traffic is heavily dependent on the time of the day, the day of the semana, the location in the city and the direction of driving. If we take the example of Santiago de Chile, the traffic around the city center is very different at 8h00 compared to the traffic near the airport at the same time of the day.

Drivin proposes a much better approach. The innovation team developed a model that allows for a far more accurate prediction of traffic. The model predicts the traffic based on:

  • the time of the day
  • the day of the semana
  • the location within the city
  • the direction of movement.

This allows Drivin to accurately predict the time in traffic between any two points in the city and improves the quality of the optimized route.

Visualizing the traffic

Let’s visualize the prediction of our model. In the video below, we show the average increase in time it would take you to travel by car at a given time across the city. We use Santiago de Chile as an example but we can train a model for any city in the world. You realize right away that including this traffic in the planning process is crucial in obtaining a feasible plan that will allow you to deliver the best service to your clients.

 

If you play the video, you will see the traffic evolving over time across the city and propagate in the morning from the residential areas towards the center of the city. At lunch time, we see that the highest traffic is in the historic city center. Therefore, our planning tool can avoid this area at lunchtime, if at all possible given the other constraints of the problem and the available number of trucks. Around the commercial areas and the historic city center, there is a huge peak in traffic starting around 18:00.

In the previous video, we did not show the direction of driving, although it is included in the model. However, this is a very important component as the traffic is very different when traveling towards the city center in the morning or away from it. In the image below, we show how different the traffic is modelled when travelling towards the commercial area of the city of away from it around peak hour.

Traffic for a specifc route in Santiago de Chile starting at 18h00 in both directions.

Optimizing the delivery route with the traffic model

Drivin includes this detailed traffic model while optimizing the delivery routes during the planning process. It is of course impossible to exactly predict the traffic that will be present the next day. However, this approach significantly improves the planning process as it accounts for variation in traveling time depending on the time of the day and the location.

In addition, this would be impossible to do this by hand, knowing all the traffic in the whole city at any time during the day. Therefore, this helps even more logistics planner to perform their job.

Standard approaches to solving the delivery route problem cannot use a traffic model. Indeed, most algorithms require a fixed time between any two points to optimize the route. Drivin’s proprietary algorithm is able to include traffic while doing the optimization, making it one of the only available SaaS to have this capability.

The model

Without entering in too much details, let us briefly explain what our traffic model does. We have a two-steps approach:

  • Temporal model: we extract typical traffic pattern during the day. For example, one pattern could be a large traffic in the morning and little traffic in the afternoon. Another pattern could be an increase in traffic at mid-day. The traffic in an area is simply the weighted sum of each component.
  • Spatial model: the weights that activate each temporal component is different in each part of the city. Using cutting-edge statistical methods, we can predict how much each component is activated for each point in the city. This model uses four dimensions: latitude, longitude, and the direction vector.

This two-steps approach allows us to understand relevant traffic patterns and to efficiently calculate the traffic at any time during the day, anywhere in the city. It is very important that this calculation is very fast and robust.

If you would like more details on how our traffic model is built and integrated with our software, please contact use by requesting a demo by clicking on the link below.

Nicolas is a R&D Engineer at Drivin where he develops traffic models and route optimization algorithms using advanced statistical methods, machine learning, and bio-inspired algorithms.Nicolas comes from Switzerland and studied bioengineering and bioinformatics at the EPFL and Harvard before working as a technology consultant for Deloitte Consulting in Zurich.