> previously-calculated optimal route. Or to calculate all possible > routes (since I believe they're pre-calculating lots of their data, > they > presumably have this option), sort by how optimal they are and then do > a > pass selecting routes with significant differences but without too much > disadvantage compared to the optimal route.
This "calculate all routes" is not possible, as there is practically indefinite number of possible routes. Also it is very easy to give a route which is near optimal: e.g. take a small detour from any crossing, this makes alternative routing to a very tricky task. It is easier to change graph parameters a bit and find then other optimal route. Idea: apply give some common penalties (multipliers) to all segments of the original best route, and the re-calculate route. It should be possible to try and find reasonable multiplier value, so new route is different enough from original, but not too different. Then repeat the same: give penalties to the second route also, recalculate, until the last found route is already ridiculous, say more than 30% longer than the first one. My initial impression is that Google's penalty (assuming that this is their approach too) looks sometimes too big, the alternative routes are avoiding original one unreasonably too much and therefore my favorite route which is just a bit different from the first suggestion is therefore not included. But really, a little bit different route is much more difficult to find than totally different one, as there are too many options how to do it. More educated strategy would be to guess that why people may want other routes. Maybe they do not like highways? Or maybe do not like big crossings, left turns, traffic lights or just average traffic in the segment? Then you can find several most optimal routes, even if they are common in big portion, and show this. Logically this sounds actually more reasonable for me, also you could use then pre-calculation of routes. Difficulty here is that there many extra parameter combinations to be taken into account and to be tested; the first strategy requires playing with just one independent value. /Jaak _______________________________________________ Routing mailing list [email protected] http://lists.openstreetmap.org/listinfo/routing
