Path computation algorithms for Advanced Traveller Information System (ATIS)

Shashi Shekhar, Ashim Kohli, Mark Coyle

Research output: Chapter in Book/Report/Conference proceedingConference contribution

48 Scopus citations

Abstract

Path planning has been approached by graph-theoretic algorithms for all pair (transitive closure) and single-source (partial transitive) path computation in databases. These algorithms compute many more paths beyond the single pair path that is of interest to ATIS, and hence may not be satisfactory for ATIS due to the dynamic nature of edge costs (travel-time). We explore specialized algorithms for single-pair path computation which are designed to reduce irrelevant computation and to quickly discover the shortest paths. Our cost models and performance studies show that single pair algorithms can outperform traditional algorithms in many situations.

Original languageEnglish (US)
Title of host publication1993 IEEE 9th International Conference on Data Engineering
PublisherPubl by IEEE
Pages31-39
Number of pages9
ISBN (Print)0818635703
StatePublished - Jan 1 1993
Event1993 IEEE 9th International Conference on Data Engineering - Vienna, Austria
Duration: Apr 19 1993Apr 23 1993

Publication series

NameProceedings - International Conference on Data Engineering

Other

Other1993 IEEE 9th International Conference on Data Engineering
CityVienna, Austria
Period4/19/934/23/93

Fingerprint Dive into the research topics of 'Path computation algorithms for Advanced Traveller Information System (ATIS)'. Together they form a unique fingerprint.

Cite this