14k.be

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
• ...

I updated the OsmSharp project with a little reorganisation:
 

• I abstracted the usage of a specific technique to solve the TSP from the actual OsmSharp library and moved it into the Tools library. The tools library is now also capable of solving TSP problems not related to OSM. I will be expanding on this by adding a solver for calculating exact solutions for smaller problem sizes. The usage of a genetic algorithm is not needed in this case and it quarantees an exact solution every time! (Again, only for SMALL problem sizes)

• I added a data processor similar to osmosis but only including xml in and output files and an oracle database for loading osm data. In the future this data processor will be able to filter changesets based on bounding boxes. I need this myself. It will also include the default osm simple schema as a target database.

Feature updates are going slow because it's a big job for one developer!
 

First of all I created an XSD and generated corresponding C# code for OSM XML data: all this can be found here!

Creating a stream of OSM objects and writing them to an XML file may seem easy to do in C# using a .NET XmlSerializer class. It's not. Using the XmlSerializer class and serializing full XML documents is no problem but generating XML for only one node, relation or way means omitting the Xml Declaration and the XSD and XSI namespaces.

I found a very nice solution to this problem here:

http://www.hanselman.com/blog/XmlFragmentWriterOmitingTheXmlDeclarationAndTheXSDAndXSINamespaces.aspx

This comes down to:

The regular serialisation result is:

<?xml version="1.0" encoding="utf-8"?>

<node xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSchema" 
lat="51.020881" lon="3.965331" user="vassloff" uid="5080" visible="true" changeset="175959" 
timestamp="2006-12-30T15:58:46Z">

<tag k="created_by" v="almien_coastlines" />

<tag k="source" v="PGS(could be inacurately)" />

</node>

What we want is:

<node lat="51.020881" lon="3.965331" user="vassloff" uid="5080" visible="true" changeset="175959" 
timestamp="2006-12-30T15:58:46Z">

<tag k="created_by" v="almien_coastlines" />

<tag k="source" v="PGS(could be inacurately)" />

</node>

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.

Preprocessing step for optimisation of multiple points. Used in the OsmSharp library to calculate solutions to the TSP and M-TSP problem.

I've been doing a lot of recent edits on my SourceForge project related to OSM.

A first version of the working code that produced the results I've shown before is commited to the svn repository.

As always, feedback, comments or even contributions are welcome!

http://sourceforge.net/projects/osmsharp/

I put a first version of my C# library online by creating a sourceforge project. http://sourceforge.net/projects/osmsharp/ It does not include everything yet, but it will soon. It's far from perfect so any comments on any possible improvements are more than welcome!

At the company that I work for at the moment I'm involved in a project to use OpenStreetMap (OSM) data for implementing mapping and routing services. Up to this point we implemented several useful OMS-tools in a C# library. C# is the language and .NET is the framework used at this company. But yesterday, for the fist time, we got some first feedback from the users in the field to update the actual maps. To optimize delivery rounds users sometimes go into the field to write down the housenumbers for entire streets. The way addresses can be located in the system can be optimized. This is an excellent way to provide feedback of useful information to OSM and in a way contribute back to the project and the data we are using. They also take a GPS-tracing device (GT-31) so adding the streets they visited can also be done. About the licence; I have a signed consent form stating that changes can be made to OSM based on the information gathered by the employees here!