Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck
We study the problem of finding good alternative routes in
road networks. We look for routes that are substantially different from
the shortest path, have small stretch, and are locally optimal. We formally
define the problem of finding alternative routes with a single via
vertex, develop efficient algorithms for it, and evaluate them experimentally.
Our algorithms are efficient enough for practical use and compare
favorably with previous methods in both speed and solution quality.
In Proc. 9th International Symposium on Experimental Algorithms (SEA)
Publisher Springer Verlag
All copyrights reserved by Springer 2010.