Show HN: Eppstein’s k shortest paths in the web browser with OpenStreetMap
christophercliff.com
Show HN: Eppstein’s k shortest paths in the web browser with OpenStreetMap
1–7 of 7 posts
Re: Show HN: Eppstein’s k shortest paths in the web browser with OpenStreetMap
#2This demo is useful in showing how useless KSP is for finding meaningful alternate routes. Basically, brute force enumeration requires generating massive numbers of paths before you get anything with any sort of spatial differentiation. Until then, all you get are tiny variations on the shortest path.
Other methods are much more effective at finding locally optimal spatially diverse alternate routes with much much less effort. Gateway shortest paths are one such example.
Re: Show HN: Eppstein’s k shortest paths in the web browser with OpenStreetMap
#3This demo is useful in showing how useless KSP is for finding meaningful alternate routes. Basically, brute force enumeration requires generating massive numbers of paths before you get anything with any sort of spatial differentiation. Until then, all you get are tiny variations on the shortest path. Other methods are much more effective at finding locally optimal spatially diverse alternate routes with much much le…
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.
Re: Show HN: Eppstein’s k shortest paths in the web browser with OpenStreetMap
#4This demo is useful in showing how useless KSP is for finding meaningful alternate routes. Basically, brute force enumeration requires generating massive numbers of paths before you get anything with any sort of spatial differentiation. Until then, all you get are tiny variations on the shortest path. Other methods are much more effective at finding locally optimal spatially diverse alternate routes with much much le…
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.
> will post some (hopefully) more interesting results soon.
Your blog could use an RSS feed or some other way to get notified of updates then ;)
Re: Show HN: Eppstein’s k shortest paths in the web browser with OpenStreetMap
#5This demo is useful in showing how useless KSP is for finding meaningful alternate routes. Basically, brute force enumeration requires generating massive numbers of paths before you get anything with any sort of spatial differentiation. Until then, all you get are tiny variations on the shortest path. Other methods are much more effective at finding locally optimal spatially diverse alternate routes with much much le…
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.
you may want to look at:
Alternative Routes in Road Networks
Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck
https://www.microsoft.com/en-us/research/wp-content/uploads/...
Re: Show HN: Eppstein’s k shortest paths in the web browser with OpenStreetMap
#6This demo is useful in showing how useless KSP is for finding meaningful alternate routes. Basically, brute force enumeration requires generating massive numbers of paths before you get anything with any sort of spatial differentiation. Until then, all you get are tiny variations on the shortest path. Other methods are much more effective at finding locally optimal spatially diverse alternate routes with much much le…
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.
A plug for one of my co-workers who recently finished his PhD on alternative route finding:
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.
Re: Show HN: Eppstein’s k shortest paths in the web browser with OpenStreetMap
#7This demo is useful in showing how useless KSP is for finding meaningful alternate routes. Basically, brute force enumeration requires generating massive numbers of paths before you get anything with any sort of spatial differentiation. Until then, all you get are tiny variations on the shortest path. Other methods are much more effective at finding locally optimal spatially diverse alternate routes with much much le…
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.
You can also change the definition of "shortest" by weighting roads by speed limit. I don't know if the data for that is easy to come by, but you can always use some arbitrary weights to get roughly the same effect.