- Forward


Equilibrium Route Choice
An Introduction


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Motivation
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back SMYC Forward
  • Economics:
    • Supply-Demand Equilibria
    • Game-Theoretic Equilibria
  • Physics, Mechanical/Structural Engineering, Electrical Engineering:
    • Equilibria of Forces
    • Electrical/Magnetic Equilibria
Equilibrium in Various Disciplines (cont.)
Back SMYC Forward
  • Chemistry, Chemical Engineering
    • Reaction Equilibria
    • Thermal Equilibria
  • Biology:
    • Physical Balance Equilibria
    • Genetic Equilibrium
    • Osmotic Equilibrium
Equilibrium Models of Route Choice
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • 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
Back SMYC Forward
  • Additional Simplifying Assumptions:
    • There are exactly two routes
  • What We Need:
    • Plots of \(c\) versus \(n\)
A Graphical Solution Technique (cont.)
Back SMYC Forward
  • Travel Times (in Minutes):
    • \(t_1(n_1) = 5 + n_1\)
    • \(t_2(n_2) = 10 + 1.5 \cdot n_2\)
  • Value of Time:
    • $15.00 per hour (i.e., 25 cents per minute)
  • Demand:
    • 20
A Graphical Solution Technique (cont.)
Back SMYC Forward

A Failed Attempt

images/route-choice-equilibrium_individual-route-costs.png
A Graphical Solution Technique (cont.)
Back SMYC Forward
  • An Important Observation:
    • \(n_1 + n_2 = D\)
  • Solving for \(n_2\):
    • \(n_2 = D - n_1\)
  • Implications:
    • \(t_2(n_2) = t_2(D - n_1) = 10 + 1.5 \cdot (20 - n_1)\)
    • So, we can plot both routes on one graph
A Graphical Solution Technique (cont.)
Back SMYC Forward

Equilibrium

images/route-choice-equilibrium_both-routes-used.png
A Graphical Solution Technique (cont.)
Back SMYC Forward

Other Interesting Examples

images/route-choice-equilibrium_nonlinear.png
A Graphical Solution Technique (cont.)
Back SMYC Forward

Other Interesting Examples (cont.)

images/route-choice-equilibrium_unused.png
A Graphical Solution Technique (cont.)
Back SMYC Forward

Other Interesting Examples (cont.)

images/route-choice-equilibrium_discontinuous.png
A Graphical Solution Technique (cont.)
Back SMYC Forward

Other Interesting Examples (cont.)

images/route-choice-equilibrium_nonunique.png
A Graphical Solution Technique (cont.)
Back SMYC Forward

Other Interesting Examples (cont.)

images/route-choice-equilibrium_capacity.png
Stability
Back SMYC Forward
  • An Observation:
    • An equilibrium can be stable or unstable
  • Examples:
    • A ball at the peak of a hill
    • A ball at the bottom of a valley
  • For Route Choice Equilibria:
    • It's a complicated question, but they tend to be stable
There's Always More to Learn
Back -