0

I am in the process of creating a routing engine. I have encountered the following problem. Lets say the user gives a point A and point B and expects to get the A->B shortest path. I am using simple Dijkstra for now.

Let's say that I can somehow find the (latitudeA, longitudeA) and (latitudeB, longitudeB) coordinates, which are the closest coordinates to the A and B points that the user inputted. From those coordinates I could then also find the nodeA_ID and nodeB_ID on the graph. The problem is that for those nodes it is very likely that the A->B path doesn't exist at all. For example, if node A was only part of a one-way road that went to the opposite direction that the user wanted to go to.

However, a A' and B' must exist, very close to A and B respectively, so that the A'->B' path exists. So the routing engine should try and find that A'->B' path instead.

Also, that A'->B' path might not even be optimal. There could have been a A''->B'' path, where A'' and B'' were only a couple of meters away from A and B. So the routing engine should find the A''->B'' optimal path instead.

How do routing engines handle this situation ?

3
  • 1
    Same question was also posted on Help OSM: help.openstreetmap.org/questions/49117/…
    – mmd
    Apr 9, 2016 at 16:20
  • @mmd I thought I would post it on that website too. Why ? Is it wrong ? Its not related to stackexchange, is it ?
    – dimitris93
    Apr 9, 2016 at 16:24
  • 1
    If you post the same question on several sites, you're wasting everyones time. That's why it is generally frowned upon and considered bad etiquette.
    – mmd
    Apr 9, 2016 at 16:25

2 Answers 2

2

You can get rid of such subnetworks otherwise it is harder as you'll need to decide for a 'cost factor' such distances need to be multiplied with.

E.g. if you have A' and A'' and B' and B'' there are obviously 4 possible combinations with different distances and 4 potential different paths with different costs (e.g. distance, time or fuel costs) so you have different units which you need to multiply with the cost factor to include both in the calculation to get the 'best' overall path.

For example, if node A was only part of a one-way road that went to the opposite direction that the user wanted to go to.

IMO the intend of the user should be specified e.g. with a heading or a previously tracked GPS point. Judging just from the resulting path(s) is really hard as outlined above especially for motorways where a minor GPS flaw could result in completely different results.

0

If the implementation of Dijkstra have good performance for the data in use, You may try to:

  • get n nodes closest to A;
  • get n nodes closest to B;

For each collection, points could be on different segments with some buffer. For (a sql) example: ST_DWithin Order by ST_Distance LIMIT n...)

Calculate n*n Dijkstra possibles routes e keep the best one.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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