0

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

  • How often that does actually happen? It seems highly unlikely. – Jakub Kania Apr 11 '15 at 9:31
  • 1
    As far as I know pgRouting takes only start and end nodes into account and you can't force it to use interim points in any other way than splitting the route. In your case your system should build two routing tasks, first from A to left side unnamed node, then from left side node to B. Perhaps, if the cost column of the graph is editable, you could try to fiddle with costs and put extremely high cost to the right hand route. With lenght as cost that is not possible. – user30184 Apr 11 '15 at 10:26
  • It happens a lot, its more about being able to force a route. This is a prime example, I could do either way, but I would prefer to route up the green climbing trail. trailforks.com/region/vedder-mountain/planner/… – Canadaka Apr 12 '15 at 1:50
  • The problem is in the example link above, there are no interim points... – Canadaka Apr 12 '15 at 1:51
1

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.

  • I think I understand your suggestion, I will try this out. So i'm basically dynamically creating a new temporary edge. The routing only chooses this because its shorter. But I guess I can also force the routing to choose it be artificially setting the cost low. I'm a bit unsure at the moment how the UNION will look, but I will try and mess around with it. – Canadaka Apr 13 '15 at 22:02
  • If I add new edges via a UNION will routing still work? doesn't pgr_createTopology() function need to be ran on the edges table for routing to work? – Canadaka Apr 14 '15 at 0:16
  • Also seems I would not only have to create edges, but also vertices which the matching source & target ids? – Canadaka Apr 14 '15 at 0:29
  • I didn't implement your suggestion, but it started be down a path to another solution that seems to work for my use-case. I now get the edge ID of the clicked segment, and then I made a UNION in the pgr_dijkstra select and manually set the cost to zero. I only do this if the users clicked spot is >30meters from a vertex. So if I click somewhere in the middle of a segment, it will almost always force the routing to go that way, since the cost will be zero. – Canadaka Apr 14 '15 at 7:50
  • Problem with that seems to be that you are no longer returning the actual cost of the route. Or perhaps you're only interested in reporting the route and not its cost? – Richard Law Apr 23 '15 at 23:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.