[Routing] [ANN] ocaml-osm-route: an experimental software to do some routing on OSM maps

[David MENTRE]

Hello,

I would like to announce a small software to do basic routing on Open
Street Map maps, ocaml-osm-route.

Roughly, the current code is able to:

 * Parse *.osm.bz2 XML files;

 * Extract points and ways useful for routing[1] from OSM XML and
   produce a memory data structure;

 * Save this data structure to a cache file, so as to allow much faster
   start at the next run of the program on the same *.osm.bz2 file;

 * Find the index of a point close to a given (latitude, longitude)
   couple;

 * Apply the A* algorithm between two points;

 * Colorize the routing graph to find its connected components.

The program is of course Free Software (GNU GPL v2 license) and is
programed within the OCaml language.

This is a proof of concept program. There is *no* user interface
(command line or GUI). The program is provided as-is and I don't plan to
work much more on it. You have been warned! :-) That's said, if there is
an interest in it, I am going to reply to answers and even code some
enhancements.

Here is a typical output on hexagone.osm.bz2 map (OSM map for France):

"""
Load from cache '../hexagone-latest.osm.bz2.oorcache'...done
* Statistics on compact memory structure
 nodes:1672513
 ways:184017
 max_lat:51.0808 min_lat:41.377 max_lon:9.55171 min_lon:-5.10239
* Find routing points
lat:48.1192466 lon:-1.6673883 osmid:31930060
lat:48.1223073 lon:-1.6634277 osmid:32450946
distance guehenno -> lanno: 450.236752m
** found a path **
 Take  - Rue de Fougères (Secondary)
    0.0m lat:48.1192466 lon:-1.6673883 osmid:31930060 total:0.0m 
   76.8m lat:48.1196649 lon:-1.6665670 osmid:30428522 total:76.8m
  194.6m lat:48.1203468 lon:-1.6653546 osmid:35506906 total:194.6m
  251.5m lat:48.1206998 lon:-1.6648001 osmid:33348210 total:251.5m
 Take  - Rue François Lanno (Residential)
   90.7m lat:48.1212473 lon:-1.6638961 osmid:26819278 total:342.2m 
 Take  - Rue Georges Lechartier (Residential)
   55.2m lat:48.1216045 lon:-1.6644105 osmid:32450949 total:397.4m 
   87.3m lat:48.1218011 lon:-1.6640933 osmid:32450950 total:429.6m
  125.8m lat:48.1221037 lon:-1.6638440 osmid:32450951 total:468.0m
  164.1m lat:48.1223073 lon:-1.6634277 osmid:32450946 total:506.3m
* Connected components
 Number of ways: 184017
 Number of connected components: 2722
* Timings
 route search: 0.000060s
 cache load: 1.139843s
 colorization: 1.466422s
 point search: 0.012980s
 point search: 0.009847s
"""

The program takes a little less than 3 minutes to parse the
hexagone.osm.bz2 file (2,592,950 nodes and 248,619 ways), create the
specific memory data structure and write the cache file.

You'll find the Mercurial tree and a way to get latest source archive
tarball here:
  http://www.linux-france.org/cgi-bin/hgwebdir.cgi/ocaml-osm-route/latest


Sincerely yours,
david

Footnotes: 
[1]  Currently, ways with "highway" attribute are kept, with
     corresponding points. More precisely, following ways are kept:
       | Motorway
       | Motorway_link
       | Trunk
       | Trunk_link
       | Primary
       | Primary_link
       | Secondary
       | Tertiary
       | Unclassified
       | Track
       | Residential
       | Living_street
       | Service

-- 
GPG/PGP key: A3AD7A2A David MENTRE <dmentre at linux-france.org>
 5996 CC46 4612 9CA4 3562  D7AC 6C67 9E96 A3AD 7A2A