Equilibrium Route Choice

Equilibrium Route Choice
An Introduction

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Motivation

Our Interest:
- Modeling the route choices of individuals when using a congestable network
Other Approaches:
- Route swapping
The Approach Considered Here:
- Do not specify the dynamics, just consider where the system "winds up"

Getting Started

Equilibrium:
- A state of balance due to the equal action of opposing forces
- Equal balance between influences
An Important Observation:
- The influences/forces need to be described but the dynamics don't have to be

Equilibrium in Various Disciplines

Economics:
- Supply-Demand Equilibria
- Game-Theoretic Equilibria
Physics, Mechanical/Structural Engineering, Electrical Engineering:
- Equilibria of Forces
- Electrical/Magnetic Equilibria

Equilibrium in Various Disciplines (cont.)

Chemistry, Chemical Engineering
- Reaction Equilibria
- Thermal Equilibria
Biology:
- Physical Balance Equilibria
- Genetic Equilibrium
- Osmotic Equilibrium

Equilibrium Models of Route Choice

What Constitutes an Equilibrium?
- Nobody has any incentive to change their route choice given the route choice of everyone else (Nash)
What Would Make Someone Want to Change?
- The existence of a "cheaper" route than the one they are using

Representing the Population

Discrete Models:
- Consider individual people/vehicles
Continuous Models:
- Allow for "fractional" people/vehicles (by working with percentages or by assuming a large number of people/vehicles)

Developing a Continuous Model

Simplifying Assumptions (which can be relaxed):
- A single origin-destination pair
- Non-overlapping routes
Notation:
- $n_i$ denotes the number of vehicles on route $i$
- $t_i(n_i)$ denotes the travel time on route $i$
- $c_i(n_i)$ denotes the travel cost on route $i$ (which typically is the travel time multiplied by the value of time plus any tolls)
- $D$ denotes the total number of vehicles ( often called the demand)
- $c^*$ denotes the minimum cost

Developing a Continuous Model (cont.)

A Definition of Equilibrium:
- All used routes have the minimum cost
- All unused routes have a cost that is greater than or equal to the minimum cost
- The total number of vehicles on all routes is equal to the demand
A Mathematical Statement:
- $\text{If } n_i > 0 \text{ then } c_i(n_i) = c^* \text{ for all } i$
- $\text{If } n_i = 0 \text{ then } c_i(n_i) \geq c^* \text{ for all } i$
- $\sum_{i} n_i = D$

Developing a Continuous Model (cont.)

An Equivalent Mathematical Statement:
- $n_i \cdot [c_i(n_i) - c^*] = 0 \text{ for all } i$
- $n_i \geq 0$
- $\sum_{i} n_i = D$
Solving:
- This is an example of a nonlinear complementarity problem and there are algorithms for solving the general case
- We're going to consider a graphical solution technique of a simple instance

A Graphical Solution Technique