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_Moritz.pd

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_Moritz.pdf 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.