Shortest path problem from A to B on routing engines

Question

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 ?

Answer 1

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.

Answer 2

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.