2016-04-20Konferenzveröffentlichung DOI: 10.18452/1440
On Computation and Application of k Most Locally-Optimal Paths in Road Networks
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.
Files in this item