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

IDLab, Ghent University – imec

What data should be published?

How should data be published?

How do we enable data reuse?

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?

Terminology used in RAPTOR, CSA, ...

A footpath connects two stops

$ \iff $

You can walk between those stops

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.

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.

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

$\mathcal{O}(n)$ edges

Easy to compute

Contains nearest-neighbors subgraph

Good approximation of complete graph

Everything is still reachable

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 |

```
{
"@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"
}
]
}
```

Delaunay triangulations require a metric space

$$ d(x, y) = d(y, x) $$Euclidean distance is by far the most convenient

How reasonable are our overestimations?

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

Practical solutions use heuristics

Delaunay graphs seem promising

hdelva.be/slides/sem4tra2019/

hdelva.be/articles/decentralized-footpaths/