What is the algorithm used by ORS API for QGIS

What is the algorithm that ORS uses to deliver the shortest route and the fastest route? is Dijkstra, A * or CH (Contraction Hierarchies). Also, theoretically, what is the difference between the shortest and the fastest route, why could they be different?

I need some source that indicates this information. Thank you

1 Like

Normally the algorithm used is a newly developed algorithm called Core-ALT. @andrzej can probably provide some links to resources relating to that.

The difference between shortest and fastest is that the shortest takes the shortest path between the two points, whereas fastest takes the fastest. So if there is a highway with a faster speed limit nearby, it is likely that would be taken for fastest rather than a shorter route which has slower speed limits as the duration using the highway is shorter.

Please note though that our system no longer uses the “fastest” route, but a “recommended” route which also takes into account things like the type of way (for pedestrian profiles, footpaths are preferred over roads)

Thanks for your inquiry! As @adam pointed out, the difference between shortest and fastest is that the former one minimizes travel distance, whereas the latter one minimizes travel time. Besides, all profiles but car don’t actually compute the true fastest route but rather a recommended one which while being based on the fastest route additionally takes into account way suitability for a given profile.

As for the algorithm used to compute the routes we rely either on CH or C-ALT depending on the profile and if any additional filters such as avoid_features or maxspeed are enabled. C-ALT is a hybrid algorithm which has a scaling and performance similar to CH yet allows for some custom filters at query time. Unfortunately, we haven’t written up anything about our implementation of the algorithm yet, but it is based on the idea presented in https://dl.acm.org/doi/10.1145/1671970.1671976. Routing with avoid polygons is done with A*.

You said that:
“As for the algorithm used to compute the routes we rely either on CH or C-ALT depending on the profile and if any additional filters such as avoid_features or maxspeed are enabled”
My question is, what algorithm does openrouteservice use if we do not consider avoid_features or maxspeed?
For my thesis, I used openrouteservice to find the shortest path. And I have to explain, what algorithm does openrouteservice use to find the shortest path between several points (for example, ten points)?
Can you briefly explain in one paragraph?
I read your answer but I need more explanation. What is the difference between these algorithms that you mentioned and the Digestra algorithm? Do you use Digestra at all?

I downloaded the article you referred to, but there is a lot of explanation in that article. I need a brief and useful explanation paragraph.

Thankful

Without any additional constrains enabled ORS computes the optimal route using the Contraction Hierarchies (CH) algorithm which is explained for example here. In the case of multiple points the resulting route is assembled from individual segments computed separately between consecutive pairs of points on the way. If you are interested in an optimization problem of finding the order in which several points need to be visited to yield the shortest path connecting them, then have a look at the optimization endpoint.

2 Likes