Spatio-Temporal Data Science for Sustainable Mobility

class: center, middle, inverse, title-slide

# Spatio-Temporal Data Science for Sustainable Mobility
## Selected Topics in Geoinformatics
### Lucas van der Meer
### University of Salzburg - Department of Geoinformatics
### 04.11.2019

---

background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center, middle

Slides of this presentation at GitHub: [github.com/luukvdmeer/stig19](https://github.com/luukvdmeer/stig19)

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center, middle

# "Data science is concerned with finding answers to questions on the basis of available data"

### E. Pebesma & R. Bivand, 2019. [Spatial Data Science](https://keen-swartz-3146c4.netlify.com/)

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center, middle

Image credit: [Esri](https://pro.arcgis.com/en/pro-app/tool-reference/space-time-pattern-mining/create-space-time-cube.htm)

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center, middle

# "Creating sustainable transportation solutions is one of the greatest challenges facing cities today."

### [World Wide Fund For Nature](https://wwf.panda.org/our_work/projects/one_planet_cities/sustainable_mobility/)

???

- Why are they saying this?
- First of all, because the urban population keeps growing --> 68% in 2050
- All these people need transportation. The goods they consume, also.
- The way we organize transport now, centered around the car, is not sustainable.
- For the following reasons.

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Environment

### Carbon emissions
"Around one-quarter of global CO2 emissions come from the transportation of people and goods" - [World Wide Fund For Nature, 2018](https://wwf.panda.org/our_work/projects/one_planet_cities/sustainable_mobility/)

### Air pollution
"9 out of 10 people worldwide breathe polluted air" - [World Health Organization. 2018](https://www.who.int/news-room/detail/02-05-2018-9-out-of-10-people-worldwide-breathe-polluted-air-but-more-countries-are-taking-action)

"Air pollution causes 800,000 extra deaths a year in Europe and 8.8 million worldwide" - [European Society of Cardioligy, 2019](https://www.escardio.org/The-ESC/Press-Office/Press-releases/Air-pollution-causes-800-000-extra-deaths-a-year-in-Europe-and-8-8-million-worldwide)

???

- Some facts.
- If we want to develop low-carbon, healty cities, action needs to be taken.
- But this is not the only thing.

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Congestion

Image credit: [ABC](https://twitter.com/darrenrovell/status/801277592980652032)

Interested? Read [The Fundamental Law of Road Congestion](https://www.nber.org/papers/w15376)

???

- Our roads are getting full. Congestion gets worse every year.
- The funny thing is, that adding more asphalt has proven to NOT work.
- It only makes people drive more.
- The road in the picture was just widened for 1.6 billion dollars.
- We need other solutions to solve this.
- Especially because the distances travelled in cities are usually very small.
- You are faster by bike!

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Space requirements

Image credit: [CycleToWorkDay](https://twitter.com/cycletoworkday/status/806826291290836992)

???

- Think about: how many people do you usually see in a car when you are in the city?

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Space requirements

Image credit: [CycleToWorkDay](https://twitter.com/cycletoworkday/status/806826291290836992)

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Space requirements

Image credit: [CycleToWorkDay](https://twitter.com/cycletoworkday/status/806826291290836992)

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Space requirements

Image credit: [CycleToWorkDay](https://twitter.com/cycletoworkday/status/806826291290836992)

???

- Just imagine what we could do with all this space!
- How much more liveable, and beautiful our cities could be.
- It is not just about moving cars, also parked cars.
- And then cities are mad about e-scooters and the space they take...

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Safety

Image credit: [SWOV](https://www.swov.nl/)

???

- This figure shows mode of transport of victim and other side of traffic accidents in NL
- Why are we accepting this?
- Why are we accepting our living space to be ruled by deadly metal frames?

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Safety

Image credit: [Kurier, 06.08.2019](https://www.pressreader.com/austria/kurier-3402/20190806)

???

- This happened last summer. Two kids got killed when a car hit a child wagon.
- Next day the Austrian newspapers talked about 'The big danger on wheels'
- A debate started about banning the child wagons!
- People even blamed the mother. She was irresponsible. Why was she not bringing here kids by car?
- But wait.. Who is actually the danger here?
- Have you noticed how fast people drive here in Austria?

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Safety

<center><blockquote class="twitter-tweet"><p lang="en" dir="ltr">Hey <a href="https://twitter.com/KURIERat?ref_src=twsrc%5Etfw">@KURIERat</a>, I fixed that for you <a href="https://t.co/mq9NY4Zjh1">pic.twitter.com/mq9NY4Zjh1</a></p>&mdash; Helge Fahrnberger (@Helge) <a href="https://twitter.com/Helge/status/1158765321689411585?ref_src=twsrc%5Etfw">August 6, 2019</a></blockquote></center> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

???

- But no one ever thinks about banning cars?
- We just accept that we live in a society where our kids cannot go to school safe.
- It shows what a holy status the car has in our society today.
- Therefore, a shift of mind is needed.

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center, middle

# "Sustainable urban mobility requires a mind shift: where transport in private cars and trucking give way to different modes of transport."

### [World Wide Fund For Nature](https://wwf.panda.org/our_work/projects/one_planet_cities/sustainable_mobility/)

???

- This shift of mind starts by acknowledging that the way we designed our cities in the past 100 years, is one of the biggest mistakes we made.
- Urban planning simply failed.
- Failed to desing cities in which livability, health and safety come in first place.

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center, middle

Image credit: [Erik Griswold](https://twitter.com/erik_griswold/status/1165482859223629824)

???

- In the past 100 years, we decided that this was a good idea.
- That this was the way forward.

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center, middle

Image credit: [Karl Jilg](https://twitter.com/fietsprofessor/status/1182628284326174720)

???

- The way we designed our cities, is like this.
- And the worst is, we have started to find it normal. This is just the way it is.
- Probably you hear me talking and think this guy is crazy
- Therefore, I challenge you. To start thinking outside of the box. Outside of our tunnel view.
- Here, you learn a lot of technical skills, but the most important thing you learn as spatial scientist is a way of thinking
- Learning to be sceptical about everything you see around you in space
- Taking nothing for granted, just because it has always been that way
- Always asking yourself: 'why is our space organised the way it is?'
- Always challenging yourself, could it not be different?
- That does not mean it is always better, but at least think about it.

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center, middle

Image credit: [Taras Grescoe](https://twitter.com/grescoe/status/1060206830071279617)

???

- An example: you know this traffic light buttons for pedestrians and bikes.
- Why not the other way around?
- You probably think it;s crazy, but think again. Why?

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center, middle

<center><blockquote class="twitter-tweet" data-conversation="none"><p lang="en" dir="ltr">It exists in Delft. The only* traffic light purposely built to break up an endless stream of cyclists and allow a random car to enter a neighbourhood. (push button not included) <br><br>*) to my knowledge <a href="https://t.co/hdr8yv8Wdx">pic.twitter.com/hdr8yv8Wdx</a></p>&mdash; Lennart Nout (@lennartnout) <a href="https://twitter.com/lennartnout/status/1060533505606799360?ref_src=twsrc%5Etfw">November 8, 2018</a></blockquote></center> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

???

- The fun thing is, it already exists!
- Here, I come to the point: the change is already happening
- I maybe told a pessimistic story, but things are really chancing.
- I would of course like to change everything in one day.
- Changes go slow, but the era of cars is over.

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center, middle

Image credit: [Birgit Hebein](https://twitter.com/BirgitHebein/status/1184804850674163712)

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center, middle

Image credit: [Birgit Hebein](https://twitter.com/BirgitHebein/status/1184804850674163712)

???

- Look at this change in Vienna.
- Oslo banned all its cars from the city center, Amsterdam and Madrid will follow in the coming years.
- New York just reserved 1.7 billion dollars in new bike infrastructure.
- We as geoinformaticians have an important role in this transition.
- We learn to get information out of spatial data, and almost all mobility related data is spatial.
- No one of us can solve everything, but dont loose hope.
- If we all do a tiny little bit, it already helps.

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center, middle

<center><blockquote class="twitter-tweet"><p lang="en" dir="ltr">”After 100 years, San Francisco is calling for an end to its disastrous pilot project for dockless personal vehicles, colloquially known as cars.” <a href="https://t.co/L45YMaEDlH">https://t.co/L45YMaEDlH</a></p>&mdash; Alexandra Sweet (@ASweetPlanner) <a href="https://twitter.com/ASweetPlanner/status/1187728624733941760?ref_src=twsrc%5Etfw">October 25, 2019</a></blockquote></center> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

???

- Please read this article.
- Now I want to present you some work I did. Very small work.
- Mainly focus on the tools, not the results.

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: inverse, center, middle

# Spatio-Temporal Forecasts for Bike Availability in Dockless Bike Sharing Systems

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# What is dockless bike sharing?

.center[
.pull-left[
### Station based systems
<img src="figures/station.png" width="70%" />
]

.pull-right[
### Dockless systems
<img src="figures/dockless.png" width="70%" />
]
]

???

- Bikesharing important to normalize image of biking as transport mode
- No need to invest in own bike / bring own bike everywhere
- Very important as first/last mile connection
- Explain station based system functionality
- Downsides of station based systems -> no station at end point
- Explain dockless systems

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# What do we need to make it a success?

.center[
.pull-left[
### Good bike infrastructure
<img src="figures/infrastructure.png" width="70%" />
]

.pull-right[
### A reliable system
<img src="figures/reliable.png" width="70%" />
]
]

???

- Putting bikes only is not enough

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# What does a reliable system mean?

.center[
.pull-left[
### Station based systems
<img src="figures/station.png" width="70%" />
]

.pull-right[
### Dockless systems
<img src="figures/dockless.png" width="70%" />
]
]

???

- Station based: available bike at start station, enough space at end station
- Dockless: available bike somewhere near starting point

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# How do forecasts increase reliability?

.center[
.pull-left[
### User perspective
<img src="figures/users.png" width="70%" />
]

.pull-right[
### Operator perspective
<img src="figures/operators.png" width="70%" />
]
]

???

- User can plan their trip effectively, beforehand
- Operator can anticipate on imbalances in supply and demand

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# What to forecast?

.center[
.pull-left[
### Station based systems
<img src="figures/station.png" width="70%" />
]

.pull-right[
### Dockless systems
<img src="figures/dockless.png" width="70%" />
]
]

???

- Station based: forecasts only needed at fixed locations in space
- Dockless: forecasts possibly needed at any location in space

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Grid based?

???

- Treat each grid cell as station
- Downsides:
- Forecasting counts limits choice of forecasting models
- Forecast depends on resolution of grid
- How to choose this resolution
- Forecast does not guarantee to forecast closest bikes

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Distance based

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Challenges

.center[
.pull-left[
### Patterns over space
<img src="figures/space.png" width="70%" />
]

.pull-right[
### Patterns over time
<img src="figures/time.png" width="70%" />
]
]

???

- Different supply of bikes at different locations in space
- Different supply of bikes at different moments in time > peak hours
- Time patterns vary over space. Spatio-temporal!

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center, middle

# The time domain

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# A time series

???

- Observations for regulary spaced moments in time

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Forecasting

???

- We want to know how this time series will continue in the future
- From a statistical perspective we say:
- We forecast the range of possible futures, called the forecast distribution
- Then, we take the mean of that distribution to be our forecast

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center, middle

# Temporal autocorrelation!

???

- Forecasting is all about temporal autocorrelation
- Temporal autocorrelation means that the value at one point in time depens on the values of near points in time
- Statisticians dont like this. Their models rely on assumption of independent observations
- But actually, autocorrelation can be very useful
- Because if the current time point depends on the time point before, the future time point depends on the current time point!
- That is, we can use past data to forecast the future!
- What we need for that is an understanding of the dependency structure in a time series
- In practice that means that we are going to formulate a model to describe this structure
- Remember: with real world data, models are never true, but a simplification of the truth
- We call this: fitting a model to the time series

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Autoregressive models of order p: AR(p)

An autoregressive model of order p is based on the assumption that the current value of a time series is a linear combination of p previous values.

`$$y_{t}=\phi_{1}y_{t-1}+\phi_{2}y_{t-2}+...+\phi_{p}y_{t-p}+\epsilon_{t}$$`

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Moving average models of order q: MA(q)

A moving average model of order q is based on the assumption that the current value of a time series is a linear combination of q previous errors.

`$$y_{t}=\epsilon_{t}+\theta_{1}\epsilon_{t-1}+\theta_{2}\epsilon_{t-2}+...+\theta_{q}\epsilon_{t-q}$$`

???

- This is less intuitive
- Errors are random
- In a AR model, the explanatory variables all depend on each other
- That is, the autocorrelation function slowly decays
- Errors dont depend on each other, they are random
- Therefore, the autocorrelation function drops fast after q lags
- This is better to model time series with shocks

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Together: an ARMA(p,q) model

AR(p) and MA(q) models can be combined into an autoregressive moving average model of order (p, q). That is, in such a model, the current value of a time series is assuned to be a linear combination of both p previous values and q previous errors.

`$$y_{t}=\phi_{1}y_{t-1}+...+\phi_{p}y_{t-p}+\theta_{1}\epsilon_{t-1}+...+\theta_{q}\epsilon_{t-q}+\epsilon_{t}$$`

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# On top of that: differencing

The first order difference (d = 1) of a time series is the series of changes from one time period to the next.

`$$\nabla y_{t} = y_{t} - y_{t-1}$$`

???

- It is important for time series to be stationary
- Stationary means the statistical properties of the data stay the same over time
- I.e. constant mean and variance
- Because if the statistical properties where the same in the past, we can easily forecast that they will stay the same in the future
- If the properties always changes in the past, how do we forecast the future?
- It turns out that replacing the raw data values by the difference of each value with the value before,
can stationarize the time series
- The new time series is also called the integrated version of the original

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# All together: ARIMA(p,d,q)

Auto Regressive Integrated Moving Average Model

`$$\nabla^{d}y_{t}=\phi_{1}\nabla^{d}y_{t-1}+...+\phi_{p}\nabla^{d}y_{t-p}+\theta_{1}\epsilon_{t-1}+...+\theta_{q}\epsilon_{t-q}+\epsilon_{t}$$`

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# But what with seasonality?

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Decomposition

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Challenges

`$$\nabla^{d}y_{t}=\phi_{1}\nabla^{d}y_{t-1}+...+\phi_{p}\nabla^{d}y_{t-p}+\theta_{1}\epsilon_{t-1}+...+\theta_{q}\epsilon_{t-q}+\epsilon_{t}$$`

.center[
.col-one[
### Accurate
<img src="figures/accurate.png" width="70%" />
]

.col-two[
### Automated
<img src="figures/automated.png" width="70%" />
]

.col-three[
### Fast
<img src="figures/fast.png" width="70%" />
]
]

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center, middle

# The space domain

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center, middle

# Spatial autocorrelation!

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Time series over space

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Spatial clusters

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# One 'model point' per spatial cluster

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Hierarchical clustering

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Hierarchical clustering of time series

Image credit: [Xiaozhe Wang](https://www.semanticscholar.org/paper/1-Characteristic-based-Clustering-for-Time-Series/0a5e8d1390f3ceb851f4a37a7ec8edb95e05f698/figure/8)

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Feature dissimilarity matrix

Image credit: [Vinícius Mourão Alves de Souza](https://www.researchgate.net/figure/The-Euclidean-distance-between-two-time-series-can-be-visualized-as-the-square-root-of_fig14_254861501)

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Spatial dissimilarity matrix

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Methodology overview

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Case study

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Time series for clustering

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Clusters

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Model points

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Cluster patterns

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Time series

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Forecast examples

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center, middle

All code on GitHub: [github.com/luukvdmeer/dockless](https://github.com/luukvdmeer/dockless)

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Interested?

## Thesis available on [ResearchGate](https://www.researchgate.net/publication/336922318_Spatio-Temporal_Forecasts_for_Bike_Availability_in_Dockless_Bike_Sharing_Systems)
## Excellent (free!) book on time series forecasting: [Forecasting, Principles & Practice](https://otexts.com/fpp2/) by Rob Hyndman

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: inverse, center, middle

# Vehicle Routing Problems

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Optimize bus routes to events

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Optimize bus routes to events

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Traveling Salesman Problem

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# 'Greedy' solution

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# But this one is better...

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Total number of solutions with 3 cities

`$$3\times2\times1=3!=6$$`

# Total number of solutions with 100 cities

`$$100\times99\times98\times...\times1=100!=...$$`

# Therefore: use 'heuristics'

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# An example

Example borrowed from [knowtex](http://www.knowtex.com/nav/vehicle-routing-and-heuristics-in-operations-research_41357)

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Initial solution

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Local search

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Better solution

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Local search

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Local and global minima

Image credit: [Yeon Byoungil](https://www.researchgate.net/figure/Example-of-local-and-global-solutions-in-an-optimization-problem_fig3_322270023)

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Local and global minima

Image credit: [Ryan Marks](https://www.researchgate.net/figure/A-3D-surface-plot-demonstrating-local-and-global-minima_fig10_305881922)

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: center

# Including more constraints

---
background-image: url('figures/zgis.png')
background-size: 80px
background-position: 50% 95%
class: inverse, center, middle

# Thank you!