Optimisation du système de routage

[Chatewgne]

No description provided.

[justinefricou]

The existing routing system, having been developed more than a decade ago, is now outdated and better solutions have since emerged. However, the route is calculated in the user’s browser, leading to several drawbacks:

• inability to deploy a more recent and efficient routing system (e.g. pgRouting, which will be discussed below), as such new solutions must be implemented server-side rather than browser-side;
• increased load on the browser, whose performances depend on the user’s device;
• decreased test coverage.

In order to solve the above issues, three pull requests have been opened. PR #4070 moves the route calculation from the browser to the server, while PR #4245 builds on this advancement and implements a more efficient backend routing system using pgRouting. To finish, PR #4263 builds upon this and uses a more performant routing algorithm, again using pgRouting.

PR #4070: moving the routing system from the frontend to the backend

This pull request paves the way for future improvements that will enable faster routing and the handling of a larger topological network.

This contribution focuses on relocating the routing system to the backend and assessing the performance differences related to this calculation’s location. To this end, the routing system that has been implemented server-side in this pull request had to be the same as for the browser-side one. It consists of Dijkstra's algorithm, written in JavaScript for the frontend routing, and in Python for the backend routing.

A benchmark comparing the original and the new routing systems has been conducted. It assesses the gains in performance if the project were to switch to the new calculation system. Here is the report (in French):
rapport_benchmark_routage_backend.pdf
It should be noted that further optimizations have been conducted since the writing of this report and therefore are not reflected in the time measurements it provides.

The automation of the benchmarking process discussed in the report, which facilitates the execution of numerous time-consuming measurements, has been made generic to allow for future reusability. This benchmarking system has been included into the pull request so it can help future optimization efforts. It is located in the tools/benchmarking directory, where its documentation can be found as a README.

Additionally, the necessary restructuring of the frontend code has led to several extra enhancements.

First, the user experience has been improved. When a user creates steps that lead to an impossible route, the GeoTrek-admin interface now assists them in correcting these steps. This can happen when markers are placed on paths that are not linked, as well as when they try to place a marker outside of a path.

Second, the implementation of this new system has led to the modification of the route edit process, which solved a historic bug. When a user needs to modify an existing trek, the interface has to display its route along with its editable markers. In the original system, the browser displays these markers and recomputes the route which is then displayed. This leads to an issue: if the path network has changed since the creation of the trek, it is possible for the old and the new route to be different. This is unwanted behavior: the route should not be modified without user input.
In the case of backend routing, the computation of the route no longer being done in the frontend, the display process of an existing route had to change. Instead of the browser displaying the markers and recomputing the route, it displays it thanks to its saved topology. The topology of the original trek being composed of portions of paths, the route follows its original course.

It is also worth noting that this new system gets rid of the real-time update of the route during the drag-and-drop of a marker. Keeping this feature would have involved continuously sending requests to the backend, which would be heavy on the server and demand significant network resources.
While this makes the manipulation of via-steps smoother for large routes by reducing the load on the browser, it is now required to drop the marker on a path before the route is displayed, as the preview is no longer available.

PR #4245: SQL-based route calculation using pgRouting

This pull request replaces the Python-based routing system with a database-driven one, aiming to further improve the performances in terms of both speed and data volume capacity. By performing the routing directly in the database where the paths are stored, we eliminate the need to fetch and process them with Python, which can slow down calculation.
Similarly to the previous pull request, the use of Dijkstra's algorithm has been retained. This allows for detecting performance differences solely related to the transition from Python to pgRouting.

As mentioned in the first benchmark report attached above, in order to apply Dijkstra’s algorithm, the Python implementation requires the generation of a graph and an adjacency matrix, which are cached. The SQL implementation also requires a graph, which is stored in the database. When a path is added, modified or deleted, this graph (and adjacency matrix) must be updated.
In the case of the Python implementation, they must be entirely re-generated after each modification of the path network, which can take a few seconds for an average database (approx. 8,000 paths) to a few minutes for a big database (approx. 195,000 paths).
In the case of the SQL implementation, only the portion corresponding to the affected paths is updated. This means that when the changes to the paths network are minimal, the graph update time is negligible.
For scenarios where significant modifications to the network are made, such as when importing a large quantity of paths, this pull request introduces a new command: generate_pgr_network_topology. It pre-generates the pgRouting graph to ensure that the execution time of the first routing after these modifications remains unaffected.

A performance benchmark comparing this new pull request to the first one has been completed as well. Unlike the previous benchmark, it only measures execution times at the backend level, and has been conducted in a production environment in order to take measurements using a realistic PostgreSQL configuration. It is however similar to the previous benchmark in the following ways:

• we compared the two pull requests using the same database and the same steps to include in the route;
• we conducted the same measurement 10 times to calculate the average execution time.

This graph shows the average execution times for Python and SQL routing systems, with and without a pre-generated graph (and adjacency matrix in the case of the Python implementation), for a request with 100 via-steps. Contrary to the first pull request’s benchmark, where the 100 via-steps were added one by one and thus sending 3-via-steps requests each time, this second benchmark sends a unique 100-via-steps request.
It can be observed that when the graph has not been pre-generated, the execution times are similar, with the pgRouting implementation being slightly faster (7.2 seconds vs. 7.8 seconds). However, when the graph has already been generated, the pgRouting implementation requires almost twice as less time than the Python implementation (3.5 seconds vs. 6.5 seconds).

Note that these measurements simulate cases where the whole path network has been added either with or without pre-generating the graph (by caching it for the Python implementation or by launching the generate_pgr_network_topology for the pgRouting implementation). In the case where the graph has been generated and then a few paths are later modified, the execution time of the Python implementation is the same as if the graph had never been generated. As for the pgRouting implementation, it is roughly equivalent to the scenario where the graph has been pre-generated. This is a notable difference for use cases where a few paths are added, modified or deleted regularly.

PR #4263: optimization of route calculation using the A* algorithm

This pull request retains the use of pgRouting but replaces Dijkstra’s algorithm with the A* algorithm, which is more efficient for such routing applications.

This graph shows the average routing execution times for both of these algorithms. Note that these measurements were not conducted in a production environment, unlike those for PR #4245. Therefore, they only serve to compare these two algorithms and do not reflect realistic execution times.

It can be seen that the A* algorithm is indeed faster than Dijkstra’s algorithm, with a time difference of almost 2 seconds (7.9 seconds vs. 9.7 seconds).

[camillemonchicourt]

Thanks for this big enhancement, its documentation and all the technical and performance benchmarks.
It will make routing in Geotrek a lot stronger and faster.
And it also fixes some important issues in the main time, such as #2515

Thanks to your tests and benchmark, we see that we should only keep the pgRouting A* algorithm, in order to be easier to maintain only one system.

[leplatrem]

Congrats for this work and well detailed post! It's great to see that you are still bringing changes to Geotrek's core despites its age ❤️

[gbvt]

Thank you for the job, we look forward to seeing the presentation tomorrow! It will solve many issues we experienced with new paths interfering existing treks...