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 ?

asked 08 Apr '16, 19:07

shiro900's gravatar image

shiro900
54449
accept rate: 0%

closed 09 Apr '16, 17:22

mmd's gravatar image

mmd
5.6k4988

1

"The problem is that for those nodes it is very likely that the A->B path doesn't exist at all. For example, if that node was part of a one-way road that went to the opposite direction that the user wanted to go to."

In such a case, the shortest route would still exist but just go in a different direction. A dead-end oneway should never exist on the ground and only rarely occur in the data as a tagging error, so I wouldn't call it "likely". Assuming the data is generally correctly-connected, there should almost always be some way to route.

(08 Apr '16, 19:29) alester

@alester It doesn't have to be a dead-end. It could be a very long oneway road that would make you drive twice as long to go to your target location

(08 Apr '16, 19:32) shiro900
1

Well if your car is on the very long oneway road going in the wrong direction then it is little use to you if the routing engine says "hey, I found a point A' very near the point you are at, and from there the way is much shorter".

(08 Apr '16, 20:44) Frederik Ramm ♦

@FrederikRamm I think you might be right here. I will see how good my routing engine works once I implement it successfully so that I can visualize the results with google maps.

(08 Apr '16, 21:46) shiro900

@shiro900: why "google maps"? Did you hear of OSM already? ;-) Please use OSM!

(08 Apr '16, 22:31) aseerel4c26 ♦

@seerel4c26 Oh yes, I will definitely try OSM! I just had the google maps already set up.

(09 Apr '16, 09:30) shiro900
showing 5 of 7 show 2 more comments

The question has been closed for the following reason "Duplicate Question: another answer for the exact same question was already accepted on GIS StackExchange." by mmd 09 Apr '16, 17:22

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Question tags:

×249
×67
×4
×4
×3

question asked: 08 Apr '16, 19:07

question was seen: 1,212 times

last updated: 09 Apr '16, 17:22

powered by OSQA