Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Weird routing problem via 'small' custom shapefile network #1321

Closed
Svantulden opened this issue Dec 24, 2014 · 14 comments

Comments

Projects
None yet
5 participants
@Svantulden
Copy link

commented Dec 24, 2014

Hi,

First of all, thanks for your amazing work on OSRM! I find it truly fascinating that such a solid routing engine is open source and actively contributed to.

Now, I want to use OSRM to route via a relatively small route network shapefile. The way I accomplish this is by converting the shapefile to OSM, consisting of nodes and ways. It is a closed network, so we can assume it is fully routable. Then I add the highway=customnetwork tag to the ways, to set a speed constant and use it in the routing profile.

I extract and prepare the OSM file and the routing works about 80% without issues. Though in some cases, I get weird results. To illustrate this, I made this tiny extract of the OSM file.

Wrong
^^ - Here it goes wrong. This uses this API call. At the second waypoint, it searches the nearest 'fork', to 'turn' and go the same way back to the 3rd waypoint.
Right
^^ - Here it goes right (the other direction). This uses this API call.

In some cases, when I have three waypoints, routing from the 2nd to the 3rd, it takes a long detour to find the nearest turning circle or fork in the road where it can 'turn'. This is unexpected, especially because when routing the other way around, it routes normally between the junction nodes. Because of this, I thought it might had something to do with the engine assuming oneway. So I explicitly added the oneway=false tag, but the results were the same.

Have you got any idea if I am doing something wrong here, or that it can be a bug in OSRM?

PS. To reproduce the problem, you can download the small OSM extract I made of the network and use the same API calls beneath the screenshots.

@DennisOSRM

This comment has been minimized.

Copy link
Contributor

commented Dec 24, 2014

Are you placing the via location right at the turn?

@Svantulden

This comment has been minimized.

Copy link
Author

commented Dec 24, 2014

Yes, the via locations are placed almost exactly on the connecting nodes. Though the problem also occurs when placing via locations a little bit off the connecting nodes (placing it before every connecting node). For example this API call:

With waypoints slightly off connecting nodes

@woodbri

This comment has been minimized.

Copy link

commented Dec 24, 2014

@Svantulden I'm interested in your tool to convert a shapefile to OSM. Is this something you can share? A while ago, I created software to convert data directly to the OSRM exract file, but that was too hard to keep synchronized with the OSRM source. See: https://github.com/woodbri/osrm-tools. I think having a general purpose tool for migrating data would be very useful.
See also: #825

@Svantulden

This comment has been minimized.

Copy link
Author

commented Dec 24, 2014

@woodbri I am currently using JOSM and it's plugin OpenData (see here for an SVN mirror of the source) to load the shapefile into JOSM and saving the layer as OSM (I think JOSM handles their projects in OSM format already).

I also tried to use shp-to-osm, but this is very outdated and converts connected ways to separate ways (having double nodes at each connection). It would make sense to make a general purpose tool for migrating data though. I was already thinking of making a java command-line tool for this as it is a bit cumbersome to use JOSM for this workflow. Though I don't know if I have time to make this any time soon. If I do though, I will opensource it and let you know!

@DennisOSRM

This comment has been minimized.

Copy link
Contributor

commented Dec 29, 2014

I have always entertained the idea of writing a shape file converter that is efficient even for large files. IIRC, shapefiles don't have internal IDs but reference everything via coordinates only. The challenge is to efficiently translate distinct coordinates into disctinct IDs. Most of the tools out there (i.e those I know) fail doing this translation on large files.

@emiltin

This comment has been minimized.

Copy link
Contributor

commented Dec 29, 2014

efficiently translating coordinates to ID sounds basically like a nearest neighbour algorithm, expect you don't need nearest, only exact match

@woodbri

This comment has been minimized.

Copy link

commented Dec 30, 2014

We do this in pgrouting and its a little more complicated. Our basic strategy is this:

  1. create a table like node_id, location and put a spatial index on location for nearest neighbor and make node_id the primary key.
  2. take each edge start and end point and match it to the node_id table location with a small tolerance
  3. if it does not match then add it to the table
  4. assign the node_id to the that end of the edge
  5. repeat for the other end
  6. repeat for all edges

This assumes that you have data that is properly noded. If not then you need to pre-process the data by intersecting all edges and splitting all intersected edges at the intersection point so the network of edges is properly noded.

@DennisOSRM

This comment has been minimized.

Copy link
Contributor

commented Dec 30, 2014

@woodbri yep. Sounds like a reasonable approach.

@Svantulden

This comment has been minimized.

Copy link
Author

commented Jan 5, 2015

Does this mean that the original issue in this OP is because JOSM (and OpenData) handles the converting process wrong? I am still wondering where the issue lies in the weird routing I am perceiving.

@DennisOSRM

This comment has been minimized.

Copy link
Contributor

commented Jan 5, 2015

It's because of the fact that you place a location directly at the intersection. It's undefined which road segment the nearest one is in this case.

@Svantulden

This comment has been minimized.

Copy link
Author

commented Jan 5, 2015

Sorry, I can understand that this could be the case when placing the locations exactly on the connecting nodes, but as I mentioned above, the problem also occurs when I place the locations not on the intersections themselves, but on a road segment before/after it.

Because the routing is perfect for 80% of the time (both on and off intersections), I have a feeling there is some small quirk in the OSM extract or in OSRM that causes this.

Would you have an explanation for this?

@DennisOSRM

This comment has been minimized.

Copy link
Contributor

commented Jan 5, 2015

Would you have an explanation for this?

At this point we don't have a good explanation. Only things that come to mind are related to oneway streets and turn restrictions.

@Svantulden

This comment has been minimized.

Copy link
Author

commented Jan 5, 2015

Alright, thank you for looking into this. I will experiment some more with different OSM extracts to hopefully pinpoint where the issue lies. I'll report back here when I make some progress.

@daniel-j-h

This comment has been minimized.

Copy link
Member

commented Jan 12, 2016

Closing here --- if you are still seeing issues, feel free to open a new issue; also try out the latest 4.9 release just to be sure that it isn't already fixed.

@daniel-j-h daniel-j-h closed this Jan 12, 2016

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.