Yeah, that was an unpleasant surprise when I started plugging in the street map data :D
I'm experimenting with other algorithms and will post some (hopefully) more interesting results soon.
I'm experimenting with other algorithms and will post some (hopefully) more interesting results soon.
http://algo2.iti.kit.edu/documents/Dissertation_Kobitzsch_Mo...
Choice quote from page 50:
k-Shortest Path. A, at the first glance reasonable, approach to alternative routes is the k-shortest path problem [Yen71]. The basic notion behind the problem, which has been studied quite extensively (e.g. [Shi79, Epp94, Epp98, Rup97]), is that next to the shortest path itself, slightly suboptimal paths will offer good alternatives. While this idea seems valid for specific networks2, it has been described as less effective [BDGS11] in the context of alternative routes in road networks. It is rather unlikely to find a good alternative route among the first few hundred paths. Jumping off the highway at a ramp and directly returning back onto it does not take much time compared to the full journey. Doing this at every possible combination of ramps might already contribute a large number of possible paths that are only slightly worse than the original shortest path. This directly implies that we might need a very large value for k before we can report a reasonable alternative route.
Your blog could use an RSS feed or some other way to get notified of updates then ;)