Green IT for Green Logistics

Route optimization

Our society faces the huge challenge of reducing CO2 emissions and energy consumption, notably fossil fuels. In 2022, ground transports generate around 18% of all CO2 emissions [1]. Besides, the European Commission estimates that, on average, 25% of moving trucks are empty. There is a possible progression on CO2 emission by optimizing routes of ground transport, notably trucks.

At CETIC, we develop algorithms to optimize routes. It can serve many applications:

• optimizing the cost of parcel deliveries,
• optimise the route of mobile technicians or nurses,
• identify carpooling opportunities,
• optimize local mobility such as shared taxis,
• etc.

Figure 1 shows optimized routes in Hainaut, Belgium using the RoutaR framework. This optimization problem has 10 vehicles and 100 geographic locations; each location must be reached by a vehicle, and we want to minimize the amount of time spent on the route.

Figure 1. Une optimisation de feuille de route dans le Hainaut effectuée par RoutaR

Route optimization algorithms need a lot of data

These algorithms need to know the times to travel, from each geographic location to each other geographic location, considered in the problem. Such data is called a travel time matrix.

The size of these time matrices grows quickly with the size of the problem. In the above example, solving with 100 geographic locations requires generating a matrix with 10000 values.

We cannot neglect large size problems because routing optimization works best with large size problems. It makes it possible to spare more time and energy when more points and vehicles are considered at once.

Generating Time Matrices

In order to estimate travel time and generate time matrices, algorithms compute fastest paths on a street map. Specific algorithms have been proposed to do so, the most iconic one being Dijkstra’s shortest path algorithm. Nowadays, one of the most efficient algorithms to compute shortest paths is called Contraction Hierarchies with A* (A* CH). To compute a path within Belgium, it runs in 1 or 2 milliseconds, using OSM maps.

However, in the context of vehicle routing optimization, it must be executed many times. As illustrated in the annex below, on a problem with 500 geographic locations, it takes 5 minutes. For 1000 geographic locations, it takes 30 minutes.

Such computation time are not compatible with in an interactive use.

An accelerated Matrix Contraction Hierarchies (CH)

CETIC has developed a variant of the A* CH algorithm that generates a time matrix at once. We call it the Matrix CH. It is a deep rework of the A* CH algorithm.

According to the benchmarks here below, for 500 geographic locations, it runs in 60 seconds, and for 1000 geographic locations, it runs in 1min30’’.

Figure 2 shows the run time of both A*CH and Matrix CH on instances of size 100 to 1500.

Where does “Green IT” fit in the picture?

By reducing the run time by 95%, without increasing the number of CPU cores, we reduced the amount of energy required to execute the algorithm by 95% as well.
In this case, it is also possible to reduce the run time by 95% by using 20 CPU cores. This approach would not reduce the energy footprint and would increase the hardware footprint.

Conclusion

Thanks to this new algorithm, and our other developments, we have the necessary tools to provide an adaptable, efficient and affordable routing optimization service.

The technical contribution presented in this post is particularly interesting for logistics operators where the points to be reached often change (geographical tracking of vehicles, deliveries, taxis, on-site intervention, etc.). This contribution will allow them to optimize their routes in the most efficient way, control their ecological footprint, and increase their flexibility and agility in the face of any new demand or change.

The innovation subject of this article can be supplemented by other technological solutions such as tracking and monitoring of operations in the field, as well as their performance by collecting the most relevant KPIs.

The next step in this work is to increase the maturity of the contribution and integrate it into RoutaR to provide the means for greener logistics. On the other hand, who knows, maybe there are already ideas among our researchers to further accelerate this algorithm...

Appendix: detailed benchmark data

This is a single run, not an average, on a relatively standard 2023 Intel(R) i7-8750H@2.20GHz computer with 16Gb of RAM. The geographical points are distributed over the Walloon territory and the map used is the OSM map of Belgium.

We observe that the Matrix CH algorithm is significantly faster than A*CH, about 20 times faster. There is a slight relative slowdown in the algorithm from 1400 geographical points (the gain goes from 95% to 91%) due to saturation of the available RAM memory because the CH Matrix algorithm is very memory intensive RAM.