text: 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 outline how to enhance Dijkstra's algorithm in order to solve route planning queries in this model without prior adjustments of the underlying road network graph.
  @cite_9: In real road networks, the presence of no-left, no-right or no U-turn signs, restricts the movement of vehicles at intersections. These turn prohibitions must be considered when calculating the shortest path between a starting and an ending point in a road network. We propose an extension of Dijkstra’s algorithm to solve the shortest path problem with turn prohibitions. The method uses arc labeling and a network structure with low memory requirements. We compare the proposed method with the dual graph approach in a set of randomly generated networks and Bogota’s large-scale road network. Our computational experiments show that the performance of the proposed method is better than that of the dual graph approach, both in terms of computing time and memory requirements. We co-developed a Web-based decision support system for computing shortest paths with turn prohibitions that uses the proposed method as the core engine.
  @cite_10: The purpose of this paper is to describe the dual graph technique developed by the authors to represent transport networks. The method is intended to simplify the coding of complex transport networks to a considerable degree, particularly when there are turning restrictions, or when multiple transfers between modes or transit lines must be taken into account. A first section presents the traditional form in which transport networks are analytically represented, and describes the main problems that are confronted. In particular, the difficulty to represent prohibited turns is shown to be a major problem; when such a restriction is introduced, the representation of the network becomes increasingly complex and intractable, requiring a large number of fictitious links and nodes. A second section describes the dual graph technique in general terms, and shows how the network code remains simple, even if prohibited turns are introduced, completely avoiding fictitious links and the possibility of errors. A third section describes the way in which dual networks are constructed in formal terms. It is shown that the process of constructing the dual graph can be automated easily, becoming completely transparent to the model user. In a fourth section the method is extended to represent transit routes or, in general, multiple operators and modes. This is achieved by introducing further dimension to the dual network (multidimensional networks); the dual of very complex transit networks can also be automated, avoiding the need for fictitious nodes and links to represent transfer points. A final section draws the main conclusions and points out that dual graphs can be very useful for detailed traffic models. Brief references are made to other known methods to represent turn restrictions.
  @cite_12: 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.
summary: The first, and seemingly the simplest, solution is commonly used as it makes a road network graph maneuver-free and so there is no need to adjust the queries in any way. Unfortunately, it can significantly increase the size of the graph @cite_12 ; for instance, replacing a single turn-prohibition can add up to eight new vertices in place of one original @cite_9 . A solution like this one thus conflicts with the aforementioned (graph-size) objectives. Another approach @cite_10 uses so-called dual graph representation instead of the original one, where allowed turns are modeled by dual edges.