pgr_trsp not fast enough at short distances

[szilvesztererdos]

I have read that the running time of the Dijkstra based algorithms at short distances (e.g. 0-10 km) is less with an order of several magnitudes than at large distances (e.g. 100-500km).
However, with pgr_trsp (or pgr_dijkstra) I cannot reproduce that. I experience that fetching the data for the function's first parameter takes the majority of running time and properly filtering those data is a difficult thing on a 5 million edge count graph.
With some kind of filtering I could reach a running time of several hundred milliseconds at short distances and one or max two orders of magnitude more at long distances but I think it can be much less. I feel somehow that something is wrong. It seems that there is a good and fast algorithm but when we plug it into Postgresql, then the whole data thing messes up everything.

Do you have a proper method for filtering the graph?
What running times do you have in different circumstances? What was the minimum?
Do I use the pgRouting functions wrong or it is normal behaviour?

Thanks in advance.

[woodbri]

Long distance routes are particularly difficult performance wise because we need to load two many edges in the bounding box. Loading the graph costs more than solving it but this is a know limitation for the flexibility of being able to dynamically define your graph.

There are a few strategies for dealing with some of these performance problems:

1. barbell approach - load all edges within some radius of the start and end points and then only load the major road network for the are between the start and end. The idea being to decrease the total number of edges that get loaded.
2. look at https://github.com/pgRouting/pgrouting/tree/gsoc-partition this uses astar (no turn restriction support), but it dynamically loads the graph in partition chunks as needed
3. if you don't need to dynamically build routes, look at Project-OSRM, I am in the process of writing postgresql wrappers to access OSRM from directly in postgresql (Nov 2013).
4. on the code side, if you want to run multiple solutions on a single graph, load it once and then solve it multiple times.

If you are interested in jumping into the code, we would welcome pull requests that address performance issues. I have some ideas so talk with me about your ideas. Or add your ideas here.

[szilvesztererdos]

Thank you for your detailed answer.

Regarding the strategies you advised:

1. we already doing this, that was the "some kind of filtering" in my initial post
2. unfortunately we need turn restrictions, without it it's unusable in real life applications
3. I do not understand why OSRM is better than pgRouting. Can you clarify? How I suppose to know whether I need to dynamically build routes?
4. you mean like in kdijkstra? or completely different routes? btw are there any plans to make a ktrsp?

I am not good at c++, I will better stick to just reading the code :)

I just feel that something isn't right if there is a good and probably fast algorithm and loading data from a database (which is exactly for that: providing fast data access) takes way too long.
You say it is for the flexibility being able to dynamically define my graph. What if I do not want to dynamically define it? What if I create my edge table and leave it for months (if this is the opposite of dynamically defining it)? Then I shouldn't use pgRouting but some kind of C++ code reading from text files or what?

Thanks.

[woodbri]

OSRM is faster when you graph is static. For example you build it once and the costs do not change, you do not need to change from short distance to shortest time, and probably most important for you is that is only supports simple 3 node restrictions, like from_node, via_node, to_node, if you need more complex restrictions you need to wait until that gets added. OSRM has a lots of costly preprocessing that has to happen that makes it fast to extract the route.

And FYI, I am writing a package that will allow pgrouting users to access a local OSRM server via plpgsql wrappers.

Update see: https://github.com/woodbri/osrm-tools

[woodbri]

To better understand how pgRouting works (and hence some of its limitations, here is the general flow of what happens when you run any of our solver algorithms:

1. we run a SQL query to fetch edges from the database table
2. we allocate a C array and load the edges into it
3. we pass the C array to a solver usually Boost C++ code
4. the C array is used to build a graph
5. the graph is solved
6. we extract the solution into a C array
7. we return the solution to some C code that returns the records to postgresql

Step 5. is probably the fastest step, steps 1-4 take most of the time.

We have lots of constraints working inside the database. The database gives us lots of benefits like flexibility, storage management, portability, easy integration with other tools, etc. But all this generalization and flexibility comes at a cost that we will not have the performance of a specific purpose built application that does one thing very well and fast, but can not easily be changed to do something else.

I'm inclined to close this as I'm not sure that it is a fixable issue. If you have a more specific issue like: If I run query A it is fast but query B is slow and should be on par with A, or something more concrete.

[woodbri]

This is more a request for information than a bug. I'll tag it as Documentation for now as we might want to provide some additional information about performance and OSRM and OSRM-Tools in our documentation.

[cvvergara]

Work has been done for TRSP on develop branch for version 3.4 (due to be released on September/October 2022:
#2238
Please check the documentation
https://docs.pgrouting.org/dev/en/TRSP-family.html
and the migration guide:
https://docs.pgrouting.org/dev/en/trsp_migration.html

For further similar problems with TRSP functions please open a new issue with the specific function name