[GIS] How to find the Shortest Path between two coordinates points using pgrouting A-Star

gpsosm2popgrouting

In PostGIS I have two tables: an osm road network and a table that contains the start and end coordinate points of each path (i.e. userid, start_x1, start_y1, end_x2, end_y2). I would like to know:
1) how to create an osm road network that can be used for implementing the Astart algorithm with pgrouting (I actually have an osm road network which I obtained using osm2po and that works fine Dijkstra shortest path algorithm using pgrouting layer plugin)
2) how to find the shortest path of each start and end coordinate points using A-star.
Thank you, Selini

Best Answer

Have you read the pgRouting workshop chapter about A-Star? It should answer your questions.

Related Solutions

[GIS] Shortest Path using interpolated OSM points

We solved the same problem with temporary edges and vertices. We snapped our GPS coords to an edge e from v1 to v2 and got an offset between 0 and 1:

segOffset := line_locate_point(geom(e), Point(coords);

With this we created a new Point() and out of this a new vertex v_tmp:

line_interpolate_point(geom(e), segOffset);

We than split our edge e1 into two new edges e_tmp1 from v1 to v_tmp and e_tmp2 from v_tmp to v2. (You could need to split it in into 4 temp endges...)

With our target we did the same. Than we started pgrouting with our new vertices v_tmp_source, v_tmp_dest and thats it.

[GIS] the difference between Astar and Dijkstra algorithms in Pgrouting

A* is a generalised form of the Dijkstra search algorith. There are good descriptions of both on Wikipedia (A*, Dijkstra) including nice graphical representations.

Essentially A* is faster, and will find the "best" solution given some reasonable assumptions. Dijkstra (i.e. A* without heuristic) is better conditioned. I usually choose Dijkstra until the problem space grows too large and I need something faster.

For the one-way question, just see the documentation on this aspect of pgRouting.

Best Answer

Related Solutions

[GIS] Shortest Path using interpolated OSM points

[GIS] the difference between Astar and Dijkstra algorithms in Pgrouting

Related Question