We study an important practical aspect of the route planning problem in real-world road networks -- maneuvers. Informally, maneuvers represent various irregularities of the road network graph such as turn-prohibitions, traffic light delays, round-abouts, forbidden passages and so on. We propose a generalized model which can handle arbitrarily complex (and even negative) maneuvers and extend traditional Dijkstra's Algorithm in order to solve route planning queries in this model without prior adjustments of the underlying road network graph. Finally, we also briefly evaluate practical performance of our approach (as compared to ordinary Dijkstra on an amplified network graph).
Publié le : 2012-08-10
Classification:  68, 68R10, 05C85
@article{cai1007,
     author = {Petr Hlin\v en\'y; Masaryk University, Faculty of Informatics, Botanick\'a 68a, 602 00 Brno and Ondrej Mori\v s; Masaryk University, Faculty of Informatics, Botanick\'a 68a, 602 00 Brno},
     title = {Generalized Maneuvers in Route Planning for Computing and Informatics},
     journal = {Computing and Informatics},
     volume = {28},
     number = {1},
     year = {2012},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai1007}
}
Petr Hliněný; Masaryk University, Faculty of Informatics, Botanická 68a, 602 00 Brno; Ondrej Moriš; Masaryk University, Faculty of Informatics, Botanická 68a, 602 00 Brno. Generalized Maneuvers in Route Planning for Computing and Informatics. Computing and Informatics, Tome 28 (2012) no. 1, . http://gdmltest.u-ga.fr/item/cai1007/