Labeling algorithm for the shortest path problem with turn prohibitions with application to large-scale road networks |
| |
Authors: | Eliécer Gutiérrez Andrés L Medaglia |
| |
Institution: | (1) Departamento de Ingeniería Industrial, Centro de Optimización y Probabilidad Aplicada, Universidad de los Andes, Bogota D.C., Colombia, A.A. 4976 |
| |
Abstract: | 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 Bogotá’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. |
| |
Keywords: | Shortest path problem Turn prohibitions Combinatorial optimization Geographic information systems (GIS) Road networks |
本文献已被 SpringerLink 等数据库收录! |