[GIS] pgrouting pgr_dijkstra forcing route along a selected edge

pgroutingpostgispostgresql

I have routing working where a user clicks 2 points on the map, I find the closest vertex to those 2 clicked locations and pass that to a pgr_dijkstra function.

What I would like is give the edge a user clicks a dynamically lower cost, which would force the route to go that way, even if there is another route that is the same cost, or maybe even less.

So given this image, a user clicks A & B, the route could go either way, as the length/cost is the same. But since the user clicked the "B" on the left edge, that should be given priority.

enter image description here
Is this possible?

This is my query now:

SELECT id, geom, trailid, cost, reverse_cost, source, target, ST_Reverse(geom) AS flip_geom 
FROM pgr_dijkstra(
   'SELECT id, source::int, target::int, length::float AS cost, reverse_cost::float AS reverse_cost 
   FROM edge_table 
   WHERE ST_Contains(bbox, 4326), geom)', 
source, target, false, true), edge_table 
WHERE id2 = id ORDER BY seq;

This is a prime example, I could do either way, but I would prefer to route up the green climbing trail.
http://www.trailforks.com/region/vedder-mountain/planner/?waypoints=49.076580,-121.986912:49.070167,-122.000207

Best Answer

You could do the following:

  1. Find the nearest edge to A and B
  2. Then use ST_LineLocatePoint und you get a ratio of where the nearest point lies on that edge.
  3. With ST_LineInterpolatePoint you get the coordinates of each point on their nearest edge and with ST_LineSubstring you could also get the partial geometries, but that's not necessary for the shortest path query. It may be useful for drawing your result.
  4. Now you add 4 new edges with these two points as start/end points using ID's that are not used yet as source and target. You don't need to add them to the table. You could just append them to your network SELECT statement (first argument of pgr_dijkstra) using UNION for example. If your cost parameter depends on the length of the edge, then you should also decrease it based on the ratio you obtained before.

Then the shortest path search uses A and B as start and end node and you will receive the shortest route.

I thought it would be nice to have such a functionality in pgRouting, but it's not as easy to add as it looks like and it increases the amount of functions to maintain. There are two other issues:

  • It's not so easy to make a generic function that works for any data
  • For large networks it may take more time to query the max. node ID than to run the actual shortest path query.

Of course contributions are welcome, if someone has a generic solution or can fund the development.

Related Question