OsmSharp
Highway Hierarchies
I'm working on a new feature for OsmSharp because routing is just-too-slow. This shows part of the pre-processing algorithm to calculate a highway hierarchy that can be quickly 'queried' for a shortest route.
This will have the advantage of lightning fast routing, both point-to-point and many-to-many, but there will be no quick minutely updates of the road network anymore and the preprocessing result will only be valid for a limited number of vehicle types.
OsmSharp - v2.0!
Version 2 of the OsmSharp library is released! Among many improvements the most important are several performance improvements. I did some tests to verify the them with each change I made.
| Test | Measured (Seconds) | Percentage |
| Unmodified | 11.22 | 0.00% |
| Modified code for resolving points to use smaller increases in search raduis. | 10.72 | 4.46% |
| Modified short distance calculations using Equirectangular approximation | 10.54 | 6.06% |
| Modified the graph class to take into account the exceptions before weight calculations. | 9.05 | 19.34% |
| Modified the graph class to check turnrestrictions before weight calculations. | 8.17 | 27.18% |
| Removed double checks in graph interpreter. | 8.12 | 27.63% |
| Changed the to-list in dykstra to a hashset. | 5.87 | 47.68% |
| Changed the sortedset collection to the .NET 4 variant. | 6.25 | 44.30% |
| Changed the sortedset collection to an hashset. | 6.12 | 45.45% |
| Improved the Equirectangular approximation and removed some castings. | 5.78 | 48.48% |
| Change the regular graph into a sparse graph. | 3.025 | 73.04% |
These test are averages of 10 test runs using only a small test instance. I have noticed even better increase in perfomance when testing on large instances. The code for executing these tests is on sourceforge!
Another improvement is checking if a point is reachable before routing to it, important for error-checking the osm data. More about this later.
I also started creating basic tutorials to help usage of the library for developers. See the osm wiki!
Anyway, here is the new version:
Latest: OsmSharp_v2.0.4340.zip
Wiki: http://wiki.openstreetmap.org/wiki/OsmSharp
SourceForge: http://sourceforge.net/projects/osmsharp/
Don't hesistate to contact me if you have any questions!
Using OsmSharp: Calculate a vehicle's range
Along each point in the route the range of the vehicle is recalculated and the points that can be reached are shown using the little black points. A convex hull alorithm is used to display the area polygons. This can be updated to show a more realistic area.
Update: The demo project generating these images/movie can be found here:
http://osmsharp.svn.sourceforge.net/viewvc/osmsharp/trunk/Demos/RangeApp/
OsmSharp - v0.3
Added a filter for changesets based on a bounding box.
For now only a custom oracle database scheme can be used as the target database. Data sources can be the regular osm xml format (also zipped), simple pgsql, api pgsql and again the custom oracle database scheme.
Updated the M-TSP code
- Updated the M-TSP code and it's best placement algorithm. It can now be used with or without a depot and a crucial bug was fixed
- Created a M-TSP generator to initialize the population of the GA applied specifically for a problem with maximum and mimum time constraints per round
- Created a M-TSP preprocessing step to estimate an upper bound the number of required vechicles
- Some minor bug fixes
Some of this is based on research from different sources:
- A Hybrid Algorithm for the Vehicle Routing Problem with Time Window
- Route Planning in Road Networks with Turn Costs
- A Hybrid Genetic Algorithm for the Travelling Salesman Problem
- ...
Missing Features -> New Features
Lot's of functionality is still missing from the OsmSharp library:
- Support for turn restrictions
http://wiki.openstreetmap.org/wiki/Relation:restriction
- Support for turn weights
In short this means that in europe for example (except for the UK) turning right is more convienient than turning left. This can make a big difference when calculating shortest, or should I say efficient, routes.
This requires converting nodes that have the weights into extra ways. In the algorithm(s) I use only the ways can have weights. More on this later.
- Better overall support
This means supporting different OSM data sources; PostgreSQL, OSM API, XML.
I also needed to implement a mechanism that synchronizes a local PostgreSQL-db with the main OSM servers (by downloading the changesets) BUT only for a given bounding box. Something that is not supported by osmosis. I think because of the need to query the target database to determine where the changesets are located.
Missing features can be turned into upcoming features. I can say that support for turn restrictions is present, support for the turn weights should be supported by adding the turn restriction functionality but remains untested. I first need some good heuristics to test with.
Better overall support is something that get's implemented purely because I need it myself.
A few more weeks and everything should be tested and veryfied. I will consider this version 1.0 of the library.
