New routing engine

General talk
1

Hi everyone,

I realize there are a lot of routing engines already developed for OSM but wanted to post my own that I developed over the last few months. I have a VS2010 project up on SourceForge here (compiled on windows platform): https://sourceforge.net/projects/osmexplorer/files/. The project includes an example data file for my home state of Oregon, USA that the routing engine runs off of (along with spatial queries of individual road segments). OSM or MapQuest tiles are downloaded by the app for rendering. I’m not a developer (code mostly for school and fun) so there are definitely plenty of bugs and some messy code I’m still cleaning up. I did take the time to comment the public classes and members. My intent is to (someday) turn this into some sort of SDK. I know OsmSharp already exists, this is just my own crack at working with OSM data :).

In the interest of citing other work I used:
-Routing Engine: based on HBA* algorithm (arc-based, i.e. “Shooting-Star”, to better support turn costs), see this paper: http://www.icsi.berkeley.edu/pubs/techreports/TR-09-007.pdf. Currently supports distance, travel time, stop sign and traffic signal costs. Soon will add turn restrictions (it will make u-turns in some unusual places on occasion). Vehicle restrictions are currently flagged in the database, however I haven’t yet implemented them in the routing engine. Also does not yet output driving directions.
-Map rendering: based on C# project by Ciaran Gultnieks (not sure if on this forum or not) http://projects.ciarang.com/p/csmapcontrol/
-Spatial database: Using Volante embedded OO database by Krzysztof Kowalczyk (http://blog.kowalczyk.info/software/volante/database.html) with custom data file (created myself, very crudely). Currently the database is reasonably fast (routing engine can calculate most routes within Oregon in less than 1s, depending on data caching) but still has a lot of junk I need to clean up to reduce the size of the file. Once I get my data file parser working a little better I will upload that as a separate project so any OSM file can be parsed. I had too much trouble getting other file parsers to work in windows so I just made my own. It’s reinventing the wheel but I learn a lot more this way ;).

Anyway I welcome any feedback or contributions. I’m new on SourceForge so I haven’t yet learned how to do version control and conform to other development practices (again not a developer), but I’ll try to keep things sorted reasonably well as I make updates in the future. Thanks!

-Ryan

Edit: Forgot to mention some posts on Eric Lippert’s MSDN blog (highly recommend for .NET programming advice) that covered the basics of implementing A* in C# here: http://blogs.msdn.com/b/ericlippert/archive/2007/10/02/path-finding-using-a-in-c-3-0.aspx. The immutable Path class and PriorityQueue greatly improve performance!

2

Thanks, while I can’t use it right now, I find this an interesting topic. It would be interesting to see Maxspeed used as well.

3

I will incorporate the max speed tag, right now I’m just using a speed profile recommended on the routing email list for each road category. I forget why I didn’t include the max speed tag, might have had some trouble parsing the tag (or might have just been lazy). My initial goal was to get the class library organized and the database tuned reasonably well then start adding more features. I wanted the database to be fully contained to eliminate the need to rely on RDB servers or other software (or having to cache the entire road network in memory, not feasible for large regions). Properly tuning the OO database proved to be somewhat tricky as performance depends highly on how and when the objects are fully loaded into memory (minimizing number of slow disk reads). The road links (arcs) the router runs on load some of their members on demand (e.g. flags are only loaded if a link is added to a shortest path to compute costs, complete sets of coordinates only on the final calculated shortest path because they’re only needed for rendering). The database was a major performance bottleneck until I revised some of the object designs; initial routing was taking up to 1 min. Now it’s typically 1-2 seconds at most, but there’s still plenty more to improve. The Volante documentation is reasonably good and apparently Perst is a licensed version of the Volante source code. Overall it works well IME, the B-tree and spatial indexing are really fast if you’re careful with the object design.

4

Hey Ryan,

sounds promising!

If you want, add an entry at the OSM wiki for your software at http://wiki.openstreetmap.org/wiki/Routing or one of its subpages

And here you can announce, too:
http://wiki.openstreetmap.org/wiki/Mailing_lists → there is a special list for “Routing”

5

Thanks, I’ll try and get a wiki page up in the next couple of weeks. I just got turn costs and vehicle types incorporated into the router (currently auto, delivery truck, semi-truck, hazmat and scooter/moped) and cleaned up a bunch of code in the form app. I’ll probably condense the current data file after that, should be about half the size that it currently is (contains some pre-processing data that isn’t needed for the application). I don’t know when I’ll get my OSM file parser operational, I’m using PostGIS for an intermediate processing step and I’m having a b!tch of a time getting it to accept a bulk data load of a US-size map file :roll_eyes:. I have a slow computer so that’s probably part of the problem :(.