pgRouting as a decision-making aid for the french Fire and Rescue services

On June 17, Camptocamp participate in PG Day France 2021. This meeting, organized by the French-speaking community of PostgreSQL, was an opportunity for us to present our work about routing (road-related calculations). This work has been made for l’Agence du Numérique de la Sécurité Civile (ANSC) and its NexSIS 18-112 project.

How to save a life?

Picture this: Grand-Ma just fell off a ladder, she is lying on the floor, unconscious. Thankfully, she wasn't alone. Grand-Pa is here to call 112 (French 911) right away. As an operator takes his call, he asks for details about the situation. What are the circumstances ? Who are the victims ? Where is the situation happening ? Those details are then used to transfer the case to the competent authorities (firemen, police, …), in charge of the corresponding area.

Once the details of the call are transferred to the emergency staff, there comes the time to decide which people/vehicles to send to the location (for example: no use to send a fire truck on a heart attack), and where they should come from to be the fastest there.

Fast and Serious

Historically, the territory was divided into lists of areas surrounding fire stations. These areas were political as much as practical. When a call was received, depending on the area where it came from, it should have been assigned to the first fire station on the list. If this fire station was not available, then the list would point to the second nearest fire station, and so on, until an available fire station was found. Those lists were statically computed, without taking into account the road network evolutions or the means available at a given time.

But let’s get back to Grand-Ma and Grand-Pa. Imagine that an ambulance is on it’s way back to the fire station after a dispatch, down the road, right when Grand-Pa makes that call. This ambulance could be re-dispatch in only a few minutes. But with pre-computed lists, static by nature, it’s not possible without the manual intervention of an operator.

Routing engine to the rescue

To be able to send the fastest response possible, what we need are dynamically computed shortest paths. Granted we already have a short list of available vehicles and fire stations close to the location, we can then compute the time it would take for each of those to get there.

This computing, done by a routing engine, should be fast too, but also flexible, as emergency vehicles are not subject to the same traffic restrictions as normal vehicles.

When digging information on open source routing engines, that should be fast but flexible, with advanced capabilities, and with an active community, three candidates come to light:

After some discussions with Camptocamp colleagues, and reading a few blogs (gis-ops.com, curiosio.medium.com or jakobmiksch.eu), what we found was that to get the most flexibility, while staying fast enough (on short distances), pgRouting was the routing engine we needed.

Want some algo ? Get some algo !

pgRouting is a PostGIS extension, PostGIS being the spatial extension of PostgreSQL. It is truly a toolbox, to work with graphs, road networks or any other kind.

Many algorithms are offered, but the most relevant to our need are the ones computing a shortest path from point A to point B:

Dijkstra
It is THE shortest path algorithm. Unfortunately, it’s not really efficient on a large graph.
A*
This algorithm was first created to be the most performant to find a path from A to B, by favoring research along the axis A-B. On a homogeneous graph (which is not the case with a road network, where different road types can have large speed limit differences), the first path found is also one of the shortest.
Turn Restriction Shortest Path (TRSP)
Nearly as fast as the A*, it can take into account turn restrictions in road networks. But, for it to be interesting, these restrictions should be known accurately, and most of all, be truly restrictive, which is not always true for emergency vehicles.

We will keep the A* algorithm, as it is the most performant, and other optimization on the graph will make it homogeneous enough.

Talking about optimization

The most impacting optimization is to reduce the number of road/edges the routing engine has to inspect to find a path from A to B. The smart way to reduce this number is to select only the edges most likely to be used when searching the shortest path from A to B:

major roads with a high speed limit
minor roads near A and B

But we should be careful to keep as many roads as necessary to be able to find a path from A to B, and keep this path as short as possible.

Selecting these roads should be optimized too, thanks to the use of spatial indexes.

Among interesting optimizations, graph contraction is meant to clean a graph from unnecessary edges (dead ends), or redundant information (multiple edges to get from one point to another, when a single edge would carry the same information). Contraction is particularly interesting in our case, as selecting a sub-graph generates many redundant nodes and edges (intermediate nodes towards minor roads are now useless).

The original graph

After doing the dead end contraction operation:

After doing the linear contraction operation to the graph above:

The nodes 2, 4, 10 and 12 have been removed as they don’t carry meaningful information regarding the graph relations. For example, it’s still possible to go from node 3 to node 5, by taking the new edge -1, that carries the information of the old edges 1 and 2.

Another optimization can be found in sharing part of the resources necessary for multiple computations with the many-to-one implementation: only on request to the database to get n shortest path, and the graph is loaded only once in memory.

Finally, we should not neglect the requests to make the algorithm usable with real life data (projection of the start and end points on the edges of the network), which must also be done in an optimized way (CTE, temporary tables).

Even more flexible than Elasti-Girl

Let’s not forget our initial need: to be more realistic and dynamic than lists of pre-sorted fire stations. In this way, a great strength of pgRouting is its capability to rely on PostgreSQL, and all the possibilities of it’s SQL engine. Selecting and modifying a sub-graph can be as precise as SQL allows. Nothing prevents us from closing a road due to maintenance (predictable on a given period), or every Sunday morning for the market (predictable and recurrent), or due to a flood (unpredictable). There could also be a mechanism to modulate speed limits on certain roads (slower when the pavement is in bad shape, or on the contrary, faster because emergency vehicles don’t always follow speed limits). With the right data, there could even be traffic integration.