首页 | 本学科首页   官方微博 | 高级检索  
     


Modeling Costs of Turns in Route Planning
Authors:Stephan Winter
Affiliation:(1) Institute for Geoinformation, Technical University Vienna, Gusshausstrasse 27–29, 1040 Vienna, Austria
Abstract:In this paper a model that handles costs of turns in route planning is defined, investigated and discussed. Costs are traditionally attached to edges in a graph. For some important route planning problems other costs can be identified, namely costs that appear when leaving one edge and entering the next. Examples are turn restrictions, the turning angle, or the simple necessity to turn. Such costs cannot be stored as attributes of nodes or edges in the graph, and they cannot be handled correctly by shortest path algorithms without modifications. Turn costs can be represented by a pseudo-dual graph in a way that shortest path algorithms run without modifications. Although the idea is not new, it has not found much interest in the literature. The pseudo-dual graph is defined here in a new way, it is systematically investigated, and some practical applications are shown. Concentrating strictly on topology, it turns out that the pseudo-dual graph is conceptually cleaner and more efficient in route planning than alternative, currently used ways to deal with turn costs. The discussed applications are from the field of pedestrian navigation, which gave rise to this research.
Keywords:shortest path algorithm  turn costs  turn restrictions  route planning  pedestrian navigation  location-based services
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号