Decentralized Publication and Consumption of Transfer Footpaths

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

IDLab, Ghent University – imec

Open Data Publishing

What data should be published?

How should data be published?

How do we enable data reuse?

Mobility as a Service

provide a traveler with the service needed for a door-to-door travel under a single payment whilst integrating disparate modes of mobility under one travel experience

What about walking between public transit stops?

Footpaths

Terminology used in RAPTOR, CSA, ...

A footpath connects two stops
$ \iff $
You can walk between those stops

Disconnected but complete graphs

Computing Footpaths Dynamically

Even with all accelerations, the exact algorithms proposed are not fast enough for interactive applications.
It ... limits walking transfers between stops to x minutes; in this case we precompute these transfers.... Note that existing solutions often use such restrictions.

Delling, D., Dibbelt, J., Pajor, T., Wagner, D., & Werneck, R. F. (2013, June). Computing multimodal journeys in practice. In International Symposium on Experimental Algorithms (pp. 260-271). Springer, Berlin, Heidelberg.

Unrestricted Walking is Important

Wagner, D., & Zündorf, T. (2017). Public transit routing with unrestricted walking. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

Our goals

  • Time and space efficient
  • No walking restrictions
  • Open-world assumption

Delaunay Triangulation

$\mathcal{O}(n)$ edges

Easy to compute

Contains nearest-neighbors subgraph

Good approximation of complete graph

Path along triangle edges

Everything is still reachable

Triangulating public transit stops

Merging Networks



Overlapping service areas


© Ssolbergj [CC BY 3.0], via Wikimedia Commons
Paths in ♣ Paths in ♦ Missing paths
$ \begin{align} ♣ &\gets \text{Flanders} \\ ♦ &\gets \text{Brussels} \end{align} $ 107,171 7,969 2,508
$ \begin{align} ♣ &\gets \text{Flanders} \\ ♦ &\gets \text{Wallonia} \end{align} $ 107,171 94,730 4,020

Publishing the results

https://hdelva.be/stops/distances/12/2090/1370 

{
  "@context":{
    ...
  },
  "@graph":[
    {
      "@id":"http://hdelva.be/stops/distances/185463",
      "planner:source":"http://irail.be/stations/NMBS/008893179",
      "planner:destination":"https://data.delijn.be/stops/204556",
      "planner:distance":775,
      "prov:generatedAtTime":"2019-08-14T15:29:54"
    },
    {
      "@id":"http://hdelva.be/stops/distances/185464",
      "planner:source":"https://data.delijn.be/stops/200016",
      "planner:destination":"https://data.delijn.be/stops/201016",
      "planner:distance":125,
      "prov:generatedAtTime":"2019-08-14T14:01:09"
    }
  ]
}

Back to the basics

Delaunay triangulations require a metric space

$$ d(x, y) = d(y, x) $$

Euclidean distance is by far the most convenient

Approximating Walking Distance

Can a bus network be used to approximate the distance between train stations?

Next Steps

How reasonable are our overestimations?

Do you trust data that says two train stations are 200m apart?

Conclusion

Practical solutions use heuristics

Delaunay graphs seem promising

hdelva.be/slides/sem4tra2019/
hdelva.be/articles/decentralized-footpaths/