Efficient Algorithms for Earliest and Fastest Paths in Public Transport Networks
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913336352833536 |
|---|---|
| author | Srikanth, Mithinti Ramakrishna, G. |
| author_facet | Srikanth, Mithinti Ramakrishna, G. |
| contents | Public transport administrators rely on efficient algorithms for various problems that arise in public transport networks. In particular, our study focused on designing linear-time algorithms for two fundamental path problems: the earliest arrival time (\textsc{eat}) and the fastest path duration (\textsc{fpd}) on public transportation data. We conduct a comparative analysis with state-of-the-art algorithms. The results are quite promising, indicating substantial efficiency improvements. Specifically, the fastest path problem shows a remarkable 34-fold speedup, while the earliest arrival time problem exhibits an even more impressive 183-fold speedup. These findings highlight the effectiveness of our algorithms to solve \textsc{eat} and \textsc{fpd} problems in public transport, and eventually help public administrators to enrich the urban transport experience. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_19422 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Efficient Algorithms for Earliest and Fastest Paths in Public Transport Networks Srikanth, Mithinti Ramakrishna, G. Data Structures and Algorithms Public transport administrators rely on efficient algorithms for various problems that arise in public transport networks. In particular, our study focused on designing linear-time algorithms for two fundamental path problems: the earliest arrival time (\textsc{eat}) and the fastest path duration (\textsc{fpd}) on public transportation data. We conduct a comparative analysis with state-of-the-art algorithms. The results are quite promising, indicating substantial efficiency improvements. Specifically, the fastest path problem shows a remarkable 34-fold speedup, while the earliest arrival time problem exhibits an even more impressive 183-fold speedup. These findings highlight the effectiveness of our algorithms to solve \textsc{eat} and \textsc{fpd} problems in public transport, and eventually help public administrators to enrich the urban transport experience. |
| title | Efficient Algorithms for Earliest and Fastest Paths in Public Transport Networks |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2404.19422 |