On Computation and Application of k Most Locally-Optimal Paths in Road Networks
Holger Döbler, Björn Scheuermann · edoc Publication server (Humboldt University of Berlin) · 2016
For some applications, e.g. route planning services, it is desirable to answer a point-to-point shortest path query on a road network with a set of alternative paths. We discuss the general requirements for such sets of paths such as shortness, diversity, etcetera. As a measure to rank reasonable alternatives we propose the local optimality ratio, because it implicitly covers all of these requirements. We present an algorithm that computes the k best alternatives in terms of this measure.