An effective heuristic for computing many shortest path alternatives in road networks |
| |
| Authors: | Stéphanie Vanhove Veerle Fack |
| |
| Institution: | 1. Department of Applied Mathematics and Computer Science , Ghent University , Krijgslaan 281-S9, B-9000 , Ghent , Belgium stephanie.vanhove@UGent.be;3. Department of Applied Mathematics and Computer Science , Ghent University , Krijgslaan 281-S9, B-9000 , Ghent , Belgium |
| |
| Abstract: | We propose a simple and effective heuristic that allows fast generation of a large set of shortest path alternatives in weighted directed graphs. The heuristic is based on existing deviation path algorithms for exact k shortest paths. It precalculates a backward shortest path tree and thus avoids doing many shortest path computations, but as a result it does not necessarily find the exact set of k shortest paths. Computational results on real-world road networks are reported. Our tests show that the quality of the paths produced by the heuristic is most satisfactory: typically, the kth path found by the heuristic is less than 1% longer than the exact kth shortest path, for values of k up to 10,000. Moreover, the heuristic runs very fast. We also show how the heuristic can be enhanced to an exact k shortest paths algorithm, which performs well in comparison with the existing exact k shortest path algorithms. |
| |
| Keywords: | geographic information science route planning |
|
|
