[Routing] Feedback-Optimized Metrics
Marcus at Wolschon.biz
Mon Oct 1 05:59:25 BST 2007
-----BEGIN PGP SIGNED MESSAGE-----
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.)
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
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
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.
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
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.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
-----END PGP SIGNATURE-----
More information about the Routing