[Profile picture of Ruben Verborgh]

Ruben Verborgh

Decentralized Publication and Consumption of Transfer Footpaths

Harm Delva, Julián Rojas Meléndez, Pieter Colpaert, and Ruben Verborgh

Users expect route planners that combine all modes of transportation to propose good journeys to their destination. These route planners use data from several sources such as road networks and schedule-based public transit. We focus on the link between the two; specifically, the walking distances between stops. Research in this field so far has found that computing these paths dynamically is too slow, but that computing all of them results in a quadratically scaling number of edges which is prohibitively expensive in practice. The common solution is to cluster the stops into small unconnected graphs, but this restricts the amount of walking and has a significant impact on the travel times. Moreover, clustering operates on a closed-world assumption, which makes it impractical to add additional public transit services. A decentralized publishing strategy that fixes these issues should thus (i) scale gracefully with the number of stops; (ii) support unrestricted walking; (iii) make it easy to add new services and (iv) support splitting the work among several actors. We introduce a publishing strategy that is based on the Delaunay triangulation of public transit stops, where every triangle edge corresponds to a single footpath that is precomputed. This guarantees that all stops are reachable from one another, while the number of precomputed paths increases linearly with the number of stops. Each public transit service can be processed separately, and combining several operators can be done with a minimal amount of work. Approximating the walking distance with a path along the triangle edges overestimates the actual distance by 20% on average. Our results show that our approach is a middle-ground between completeness and practicality. It consistently overestimates the walking distances, but this seems workable since overestimating the time needed to catch a connection is arguably better than recommending an impossible journey. The estimates could still be improved by combining the great-circle distance with our approximations. Alternatively, different triangulations could be combined to create a more complete graph.

full text BibTeX other citation formats

Published in 2019 in Proceedings of the First International Workshop on Semantics for Transport.

Read this article online

Cite this article in your work

Cite this article easily using its BibTeX entry: 

@inproceedings{delva_sem4tra_2019,
  author = {Delva, Harm and Rojas Mel\'endez, Juli\'an and Colpaert, Pieter and Verborgh, Ruben},
  title = {Decentralized Publication and Consumption of Transfer Footpaths},
  booktitle = {Proceedings of the First International Workshop on Semantics for Transport},
  year = 2019,
  month = sep,
  url = {https://hdelva.be/articles/decentralized-footpaths/},
}

Alternatively, pick a reference of your choice below:

ACM
Harm Delva, Julián Rojas Meléndez, Pieter Colpaert, and Ruben Verborgh. 2019. Decentralized Publication and Consumption of Transfer Footpaths. In Proceedings of the First International Workshop on Semantics for Transport.
APA
Delva, H., Rojas Meléndez, J., Colpaert, P., & Verborgh, R. (2019, September). Decentralized Publication and Consumption of Transfer Footpaths. Proceedings of the First International Workshop on Semantics for Transport.
IEEE
H. Delva, J. Rojas Meléndez, P. Colpaert, and R. Verborgh, “Decentralized Publication and Consumption of Transfer Footpaths,” in Proceedings of the First International Workshop on Semantics for Transport, 2019.
LNCS
Delva, H., Rojas Meléndez, J., Colpaert, P., Verborgh, R.: Decentralized Publication and Consumption of Transfer Footpaths. In: Proceedings of the First International Workshop on Semantics for Transport (2019).
MLA
Delva, Harm, et al. “Decentralized Publication and Consumption of Transfer Footpaths.” Proceedings of the First International Workshop on Semantics for Transport, 2019.

Discuss this article