Route Swapping

Route Swapping
An Introduction

Computer Science Department

bernstdh@jmu.edu

Motivation

Review:
- We know how to find "shortest" paths given travel times/costs/distance
- We understand how congestion impacts travel times/costs
An Obvious Issue:
- If everyone takes the "shortest" path, it will become congested and not be the "shortest"
The Question:
- How might people change their behavior on a day-to-day basis?

Dynamic vs. Static Models

Dynamic Models:
- Describes how a system changes over time (which may be discrete or continuous)
Static Models:
- Do not explicitly incorporate time

Types of Dynamic Models

Time-Based Models:
- Describe the system at every point in time regardless of whether the state of the system changes
Event-Based Models:
- Describe the system only at times when specific events (which cause a transition between states) occur

Our Concern

The Type of Model:
- A time-based (day-to-day) model of route swapping in response to actual conditions encountered
An Important Issue:
- Does the model "settle down" over time

Nerd Humor

(Courtesy of xkcd)

"Settling Down"

Trajectory:
- The state of the system over time
Steady State:
- A system is in a steady state if the trajectory is unchanging over time (e.g., a ball that rolls to the bottom of a hill)
Stability:
- A trajectory is stable if it does not change much under small perturbations (e.g., a planet in orbit around the sun)

A Probabilistic Model of Route Swapping

The Idea:
- People choose the route to use on day \(t+1\) based only on the route they used on day \(t\)
- They "roll a die" (or use some other random mechanism) to determine which route to take
Possible Explanations:
- This is what people are actually doing because they can't find a pattern in congestion levels
- The modeler doesn't know what the people are actually doing, but this is consistent with the empirical data

A Probabilistic Example

A Probabilistic Example (cont.)

One Set of Probabilities:
- A person on route 1 will switch to route 2 with probability 1/2 and will stay on route 1 with probability 1/2
- A person that is on route 2 will switch to route 1 with probability 1/3 and will stay on route 2 with probability 2/3
The Transition Matrix:
- It is convenient to represent the transition probabilities in a matrix, as follows:
- \(\mathbf{P} = \left[ \begin{array}{c c} \frac{1}{2} & \frac{1}{2} \\ \frac{1}{3} & \frac{2}{3} \end{array} \right] \)
An Observation:
- Each row must sum to 1

A Probabilistic Example (cont.)

After About 10 Days:
- There will be 40 people on route 1 and 60 people on route 2
From Day 10 On:
- There will be 40 people on route 1 and 60 people on route 2 (i.e., the system will be in steady state)

A Probabilistic Example (cont.)

A Different Transition Matric:
- \(\mathbf{P} = \left[ \begin{array}{l l} 0& 1 \\ 1& 0 \end{array} \right] \)
What Happens Over Time:
- People bounce back and forth between the two routes forever

A Deterministic Model of Route Swapping

The Idea:
- On day \(t+1\), a (fixed) portion of the people switch from the route they used on day \(t\) to the "best" route on day \(t\)
Possible Explanation:
- People get reports about other routes at the end of the day (from the radio, friends, the WWW, etc.)
- A (fixed) portion are set in their ways
Notation:
- \(n_i\) denotes the number of vehicles using route \(i\)

A Deterministic Example

The Network:
- Two routes connecting one origin-destination pair
Travel Times/Costs:
- \(t_1(n_1) = 5 + n_1\)
- \(t_2(n_2) = 10 + 1.5 \cdot n_1\)
Initial Conditions:
- \(n_1 = 0\)
- \(n_2 = 20\)

A Deterministic Example (cont.)

A Deterministic Example (cont.)

Other Deterministic Models

State-Dependent Swapping Rates:
- The portion of people that swap depends on the difference in times/costs
Multiple Targets:
- People don't just swap to the "best" route, the swap to all "better" routes

There's Always More to Learn