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_14: 
  @cite_4: We consider a variant of the constrained shortest path problem, where the constraints come from a set of forbidden paths (arc sequences) that cannot be part of any feasible solution. Two solution approaches are proposed for this variant. The first uses Aho and Corasick's keyword matching algorithm to filter paths produced by a k-shortest paths algorithm. The second generalizes Martins' deviation path approach for the k-shortest paths problem by merging the original graph with a state graph derived from Aho and Corasick's algorithm. Like Martins' approach, the second method amounts to a polynomial reduction of the shortest path problem with forbidden paths to a classic shortest path problem. Its significant advantage over the first approach is that it allows considering forbidden paths in more general shortest path problems such as the shortest path problem with resource constraints.
  @cite_7: Shortest Path Problems are among the most studied network flow optimization problems, with interesting applications in various fields. One of such field is transportation, where shortest path problems of different kinds need to be solved. Due to the nature of the application, transportation scientists need very flexible and efficient shortest path procedures, both from the running time point of view, and also for the memory requirements. Since no "best" algorithm currently exists for every kind of transportation problem, research in this field has recently moved to the design and implementation of "ad hoc" shortest path procedures, which are able to capture the peculiarities of the problems under consideration. The aim of this work is to present in a unifying framework both the main algorithmic approaches that have been proposed in the past years for solving the shortest path problems arising most frequently in the transportation field, and also some important implementaion techniques which allow one to derive efficient procedures from the general algorithmic schema, in line with trends in current research. In the first part of the paper, afetr presenting the problem, we review those classical primal and dual algorithms which seem to be the most interesting in transportation. Promising reoptimization approaches are then discussed. The second part is devoted to dynamic shortest path problems, which arise very frequently in the transportation field. We analyse the main features and propose a general "chronological" algorithmic paradigm, called Chrono-SPT. We study several special cases, and investigate promising research avenues related to various extensions (time-windows. turn penalties, multicriteria and shortest hyperpaths).
  @cite_0: A first transistor responsive to a source of signals is coupled to a first winding of a transformer and further coupled to a gate control electrode of a semiconductor device for turning the device off in response to the signals. A second winding of the transformer is coupled to a second transistor which is also coupled to the gate control electrode such that a change from a first to a second conduction state of the first transistor causes a current to be induced in the second winding which changes the conduction state of the second transistor for enabling conduction of the gated semiconductor device.
  @cite_2: Most shortest path algorithms do not explicitly consider intersection movements in calculating best paths. However, in congested street networks, turning movement delays can be significant, and ignoring them may lead to the calculation of suboptimal or illogical paths. To reflect turning movements in practice, it is common to "explode" the network representation for use with standard shortest path algorithms. This paper proposes a considerably more efficient approach; it consists of an extension to the commonly used forward star structure to represent the network including intersection movements and movement prohibitions. A label correcting shortest path algorithm is modified to take advantage of the proposed representation and calculate the least time paths in a computationally efficient way. The approach is implemented, tested and compared with existing techniques. The application of similar modifications to time-dependent and k-shortest path algorithms is also discussed.
summary: Basically, the research directions are represented either by modifications of the underlying graph during preprocessing @cite_14 @cite_7 @cite_2 , or by adjusting a query algorithm @cite_0 @cite_4 in order to resolve simple types of restrictions during queries.