[Routing] Feedback-Optimized Metrics

[Marcus Wolschon]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1


Hi,

I am currently fleshing out the idea of a feedback-based routing-metric.
Granted, this makes little sense for "shortest path" but could improve
"fastest route" incredibly. (Who did never get unreasonably fast ETAs
or routes that are faster in theory but not in the real world.)

assumption:
The time-to-target is the sum of:
* average waiting-times at traffic-lights
 - outside city
 - inside city on major road (green wave)
 - inside city on non-major-road
* time to do a turn
 - average real-world times summed for
   [angle, aprox.speed at entering]
* times to pass segments
 - known average times for day+night+weekend for known
   segments the user travels often
 - average time per road-class + inside/outside-city
 - weighted with a min(0, MAX-segmentLengh)*SpeedOfLastTurn

collecting data:
All these cases can have heuristics to start with and then
the estimated variables can be replaced by the averaged
known times the user had. We need different sets of values per
route-metric asked for because:
* if the user wants the fastest route (s)he wants to be fast.
* if the user wants the most fuel-efficient road (s)he will
  drive slower,...
The data can be collected easily because we own the
navigation-program that runs and collects position, speed
and current way-type while driving. We can even use older
GPS-traces to optimize with.
For very good initial valued we can even use the big load
of gps-traces in the OSM-database and through out everything
that was by foot (too slow), by plane (too fast) or too
noisy. Some auto-clustering algorithm (we are doing data-
mining next door) can very easily give reasonable vehicle-
classes and their average speed for motorways. (Motorways
are in the middle of nowhere, have no foot-ways and traces
are thus easy to match with the way the user was traveling.)

If routing for anything but fastest-time this can simply
be computed after the route is done to give a very good ETA
(maybe even with a +-X minuted ).
If routing to optimize fastest-time:
* In Dijksta I would need to change the "time of fastest route"
  every time I update the "time of fastest route to A" for A
  by recursively traversing all childs(A) who's fastest route comes
  from A. (I will never encounter the node I am at in the algorithm
  or any node with a shorter time so the algorithm should still be
  guaranteed to stop.).
* In A* I always know where I come from and where I am going, so
  using such a metric is trivial.

Why take the angle into account:
If I do have the angle of the road then I can do a metric that
takes into account that I cannot do a 170° turn within 20m
at 50Km/h. Since most routes start and end in a city and in them
travel-times are dominated by traffic-lights and turns.
The motor-way in between has no curves that affect speed nor
many traffic-lights so it is easy to estimate.

Simpler case:
Only collect average speeds for per way-types. This should
give poor results on winding mountian-roads but as the user
is likely to travel similar kinds of routes every tim I would
not be surprised by very good results compared to current
heuristics.

more complex case:
Take the angle (differennt "ele"-values) into account.

problems with the current map:
Only few traffic-lights are mapped as such.
Even fewer "ele"-tags are present even as nearly every GPX-point
does contain an alitude.

Marcus
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHAH6tf1hPnk3Z0cQRAjllAJ9ecbJR/+fRXWYHXa2ocNf8/D+AxwCgwMQs
k1c324aVg8fnW9jgrgDG6pc=
=guUS
-----END PGP SIGNATURE-----