[Back]

S. Winter:
"Modeling the Costs of Turns in Route Planning";
GeoInformatica, 6 (2002), 4; 345 - 360.

In this paper a graph model is discussed that can handle costs of turns (edge-edge relations) in route planning. 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. Other route planning problems require to visit the same node in a network twice, which can
be also handled with an edge-edge based approach. Examples are tours or u-turns.
Turn costs can be represented by a line 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 line 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 line 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 car and pedestrian navigation, which rise to this research.

http://aleph.ub.tuwien.ac.at/F?base=tuw01&func=find-c&ccl_term=AC04404200

ftp://ftp.geoinfo.tuwien.ac.at/winter/winter02modeling.pdf