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.
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.
@cite_9 @cite_10 @cite_12
1991924366 2091662631 1482690689
We study approaches for the exact solution of the NP-hard minimum spanning tree problem under conflict constraints. Given a graph (G(V,E) ) and a set (C E E ) of conflicting edge pairs, the problem consists of finding a conflict-free minimum spanning tree, i.e. feasible solutions are allowed to include at most one of the edges from each pair in (C ). The problem was introduced recently in the literature, with several results on its complexity and approximability. Some formulations and both exact and heuristic algorithms were also discussed, but computational results indicate considerably large duality gaps and a lack of optimality certificates for benchmark instances. In this paper, we build on the representation of conflict constraints using an auxiliary conflict graph ( G (E,C) ), where stable sets correspond to conflict-free subsets of (E ). We introduce a general preprocessing method and a branch and cut algorithm using an IP formulation with exponentially sized classes of valid inequalities for both the spanning tree and the stable set polytopes. Encouraging computational results indicate that the dual bounds of our approach are significantly stronger than those previously available, already in the initial LP relaxation, and we are able to provide new feasibility and optimality certificates. 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 Dijkstras 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 Bogotas 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. 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 m