One-to-Many Astar

[boerngen-schmidt]

Hello everyone,

this is a feature request of a one-to-many routing algorithm using astar. First off, if it does not make sense feel free to close the issue and discard it.

Currently I'm writing my master thesis, where I do simulate gasoline refilling strategies for commuters in germany. Everytime a commuter generates a refill event I have to find the cheapest reachable refill station. Currently I use kdijkstra for this problem, but while writing my thesis I read, that the performance of Astar is much better than the one of dijkstra, so wouldn't it make sense to also have a pgr_kastar function?

• benjamin

[woodbri]

Well your statement is only partially correct. AStar is faster than Dijkstra for doing a one to one routes. AStar is in fact Dijkstra with a heuristic that allows it to search only a subset of the graph moving toward the destination node, whereas Dijkstra will solve the whole graph. But if you have many target destinations then using Dijkstra will solve all the solutions at once, and a kastar would need to solve the graph k-times which will like take longer than one dijkstra solution that gives you all your answers at once. So pgr_kdijkstra is the way to go.

There are some caveats to the above. I'm sure we can construct cases where the above would not be true, like your k target nodes are very far away and spread out geographically requiring a VERY large graph and you would probably need the same graph using AStar, but K astar solutions MIGHT be faster than Dijkstra in some small number of cases. Or where all the target nodes are clustered very close together such that the Astar solution would find all the nodes in a single pass, but as a general solution, I think pgr_kdijkstra() is probably the better solution.

[boerngen-schmidt]

Thank you Woodbri for the explanation. Since my nodes are not spread very far and I extract a part of the road network I will stick to pgr_kdijkstra().

Also I agree with kdijkstra being the better solution and I would vote for discarding my feature request, but I would vote for putting your explanation into the documentation, since it is very valuable information on how the algorithms work.

[dkastl]

Improve documentation (changed label).

[cvvergara]

@dkastl I am working on the documentation, you want the improvement on Astar, that basically has what @woodbri says?

[boerngen-schmidt]

@cvvergara I would put it in the documentation like this: On the pgr_astar: The astar algorithm uses a heuristic to find the best/shortest way from its source to its destination, whereas pgr_dijkstra solves the whole graph and then chooses the best/shortest way.

On the pgr_dijkstra page just the reverse explanation .

On pgr_kdijkstra what @woodbri has explained to me.

[cvvergara]

@boerngen-schmidt Oh, I must clarify, I am working on the 2.1 documentation, http://imaptools.com:8080/docs/pgr2.1-doc/src/dijkstra/doc/dijkstra_v3.html#pgr-dijkstra-v3 pgr_kdijkstra is not being changed for 2.1. So, if you are so kind to have a second look?

[boerngen-schmidt]

@cvvergara So what I'm aiming at is a more broad explanation of the algorithms in general, like pros and cons, as well as how they work.

A few suggestions from my side would be:

• use all the space available for the signature e.g. no forced line break
• be more clear what is the function signature and what is the result

SET OF (seq, node, edge, cost, tot_cost)
    pgr_dijkstra(text sql, bigint start_v, bigint end_v,
                 boolean directed:=true);

could be changed to:

pgr_dijkstra(text sql, bigint start_v, bigint end_v, boolean directed:=true);
   RETURNS SET OF (seq, node, edge, cost, tot_cost) OR EMTPY RESULT

Also the minimal signature has target where as all other have end_v. Maybe it could even be source_vertex and target_vertex since it is the id of the start and end vertex in the table.

For the explanation of the SQL

field	type	description
id	ANY-INTEGER	identifier of the edge.
reverse_cost	ANY-NUMERICAL	_(optional)_ the value for the reverse traversal of the edge. A negative cost will prevent the edge (target, source) from being inserted in the graph.

Flip Description of the SQL query with Description of the parameters of the signatures, since the SQL is part of the parameters. Or better make it a sub heading.

Synopsis (copy paste wikipedia... why not?!): Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later. The algorithm exists in many variants; Dijkstra's original variant found the shortest path between two nodes, but a more common variant fixes a single node as the "source" node and finds shortest paths from the source to all other nodes in the graph, producing a shortest path tree. To produce the shortest path tree, the algorithm has to solve the whole graph which results in a runtime of O(|V|²) [V being the number of vertexes in the graph]

Special variants of Dijkstra are: (correct me if I'm wrong)

• pgr_apspJohnson
• pgr_apspWarshall

Another suggestion, which could be mentioned in the documentation as well is, that it makes sense to limit the graph like:

SELECT id, source, target, cost FROM de_2po_4pgr,  (SELECT ST_Expand(ST_Extent(geom_vertex),10000) as box FROM de_2po_vertex WHERE id = %(start)s OR id = %(dest)s ) as box WHERE geom_way && box.box

The example uses an OSM2PO table with SRID:25832.

That's all

[cvvergara]

@boerngen-schmidt Right now my focus is on the documentation of the new signature

The other functions, for the 2.1 will remain the same, that is, with the bugs/issues etc. not solved. Astar falls into this category so I am setting this for to Release 2.2

About the other comments on the documentation I am continuing my response in #351

Pull requests are always welcome.

[woodbri]

agg_cost should also be acceptable as an alternative to tot_cost as postgres uses agg_* in some of the functions so it is already in the vocabulary of the database functions. This column is only a convenience regardless as it is trivial for us to compute the running accumulation of cost and it would require much more complicated SQL to compute it after the fact.

[cvvergara]

I made some experiments, and I think it is possible.

[cvvergara]

With pull request #705 to develop, pgr_aStar:

• one to one
• one to many
• many to one
• many to many pgr_aStarCost:
• one to one
• one to many
• many to one
• many to many pgr_aStarCostMatrix are implemented