Path computation algorithms for advanced traveller information system (ATIS)
- 30 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. iiii, 31-39
- https://doi.org/10.1109/icde.1993.344080
Abstract
Three path-planning algorithms for single-pair path computation are evaluated. These algorithms are the iterative breath-first search, Dijkstra's single-source path-planning algorithm, and the A* single-path planning algorithm. The performance of the algorithms is evaluated on graphs representing the roadmap of Minneapolis. In order to get an insight into their relative performance, synthetic grid maps are used as a benchmark computation. The effects of two parameters, namely path length and edge-cost-distribution, on the performance of the algorithms are examined. The effects of implementation decisions on the performance of the A* algorithm are discussed. The main hypothesis is that estimator functions can improve the average-case performance of single-pair path computation when the length of the path is small compared to the diameter of the graph. This hypothesis is examined using experimental studies and analytical cost modeling.Keywords
This publication has 12 references indexed in Scilit:
- A spanning tree transitive closure algorithmPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- A suitable algorithm for computing partial transitive closures in databasesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Advanced driver information systemsIEEE Transactions on Vehicular Technology, 1991
- Extensions to query languages for graph traversal problemsIEEE Transactions on Knowledge and Data Engineering, 1990
- Extending SQL with general transitive closure and extreme value selectionsIEEE Transactions on Knowledge and Data Engineering, 1990
- Efficient management of transitive relationships in large data and knowledge basesPublished by Association for Computing Machinery (ACM) ,1989
- Alpha: an extension of relational algebra to express a class of recursive queriesIEEE Transactions on Software Engineering, 1988
- The processing and evaluation of transitive closure queriesPublished by Springer Nature ,1988
- A study of transitive closure as a recursion mechanismPublished by Association for Computing Machinery (ACM) ,1987
- On the optimality of A∗Artificial Intelligence, 1977