Show HN: Eppstein’s k shortest paths in the web browser with OpenStreetMap (opens in new tab)

(christophercliff.com)

39 pointsctcliff9y ago6 comments

6 comments

This 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.

ctcliffOP9y ago

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.

danpat9y ago

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.

csom9y ago

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/...

pmiller29y ago

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.

detaro9y ago

> 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 ;)

j / k navigate · click thread line to collapse