Frequency Data Compression for Public Transportation Network Algorithms (Extended Abstract)

Proceedings of the International Symposium on Combinatorial Search, 6

Volume

Vol. 6 No. 1 (2013): Sixth Annual Symposium on Combinatorial Search

Research Abstracts

Timetable information in public transportation networks exhibit a large degree of redundancy; e.g. consider a bus going from station A to station B at 6:00, 6:15, 6:30, 6:45, 7:00, 7:15, 7:30, . . . , 20:00, the very same data can be provided by a frequency-based representation as ’6:00-20:00, every 15 minutes’ in considerably less space. Nevertheless a common graph model for routing in public transportation networks is the time-expanded representation where for each arrival/departure event a single node is created. We will introduce a frequency-based graph model which allows for a significantly more compact representation of the network, resulting also in a speed-up for station-to-station queries. Moreover we will describe a new variant of Dijkstra’s algorithm, where also the labels are frequency-based. This approach allows for accelerating profile queries in public transportation networks.

10.1609/socs.v4i1.18302