Transport and Logistics sectors are facing huge challenges to improve their energy efficiency and reduce their environmental impacts. Route & planning optimization can help addressing both challenges. CETIC is working on algorithmic solutions to optimize routes within a reasonable amount of time. Our technology front-end is RoutaR, and it uses the route optimization algorithms developed for OscaR.cbls OscaR.

Date: 1 August 2023

Expertises:

Algorithmic and combinatorial Optimisation ⊕

Domaine: Transport & logistics ⊕

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.

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.

Number of geographic locations | Number of values in the time matrix |
---|---|

100 | 10.000 |

200 | 40.000 |

300 | 90.000 |

400 | 160.000 |

500 | 250.000 |

1000 | 1.000.000 |

1500 | 2.250.000 |

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**.

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.

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.

**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...

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.

Number of Geographic Points | Number of Values to Calculate | Calculation Time A* CH [mm:ss] | Calculation time CH Matrix [mm:ss] | Savings in computing time |
---|---|---|---|---|

100 | 10.000 | 00:12,5 | 00:00,9 | 93% |

200 | 40.000 | 00:49,4 | 00:03,0 | 94% |

300 | 90.000 | 01:52,2 | 00:07,9 | 93% |

400 | 160.000 | 03:19,4 | 00:10,5 | 95% |

500 | 250.000 | 05:08,7 | 00:16,0 | 95% |

600 | 360.000 | 09:13,9 | 00:28,2 | 95% |

700 | 490.000 | 13:47,2 | 00:45,9 | 94% |

800 | 640.000 | 18:56,8 | 00:57,5 | 95% |

900 | 810.000 | 24:38,5 | 01:13,3 | 95% |

1000 | 1.000.000 | 30:54,5 | 01:28,3 | 95% |

1100 | 1.210.000 | 40:26,8 | 01:55,8 | 95% |

1200 | 1.440.000 | 50:01,9 | 03:03,2 | 94% |

1300 | 1.690.000 | 1:00:53 | 03:14,7 | 95% |

1400 | 1.960.000 | 1:11:39 | 06:11,8 | 91% |

1500 | 2.250.000 | 1:23:07 | 07:16,5 | 91% |

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.

[1] Liu, Z., Deng, Z., Davis, S. et al. Monitoring global carbon emissions in 2022. Nat Rev Earth Environ 4, 205–206 (2023). https://doi.org/10.1038/s43017-023-00406-z