Route Choice

(1)

Advanced Transportation

Planning

(2)

Route Choice

(3)

Route Choice

Zone 1

Zone 2

500 trips

• Trip Distribution

Zone 1

Zone 2

Car: 300 trips

• Mode Choice

Bus: 50 trips

Subway: 150 trips

Zone 1

Zone 2

Among 300 trips of Car

• Route Choice Route 1 : 50 trips

Route 2 : 150 trips Route 3 : 100 trips

(4)

• 100 trips

• From here

• To Sinseol-Dong Station

• Using Car

• Which Route?

Route 1

Route 2 Route 3

Source: http://map.google.com

(5)

Route Choice

• All-or-Nothing Assignment

• User Equilibrium (UE) Assignment

• System Optimal (SO) Assignment

(6)

All-or-Nothing Assignment

• All trips are assigned on the shortest route which is the minimum travel time or cost between zones

• Simple and inexpensive to perform

• Does not take account of congestion effect

– Assumes there is no travel time change due to increased traffic

– Flow patterns could be unrealistic

– Can be used for a special cases (significantly under-

saturated traffic etc.)

(7)

Link Performance Function

• Link travel time vs. Flow demand

• Travel time increases with flow demand

• Grows exponentially if the demand is larger than the capacity

• BPR (Bureau of Public Road) Function 1

: Link Travel Time

: Free Flow Travel Time : Link Flow Demand

: Capacity (Max. flow Rate) : Parameter to be calibrated

(default: 0.15)

: Parameter to be calibrated (default: 4)

0 0.2 0.4 0.6 0.8 1 1.2

/ Capacity

(8)

User Equilibrium

• Wardrop’s First Principal

– “The travel times in all routes actually used are equal and less than those which would be

experienced by a single vehicle on any unused route”

– Each user acts to minimize his/her own cost, subject to every other user doing the same – Travel times are equal on all used routes.

– Thus, at equilibrium, no one can reduce his or

her travel cost by choosing another choice set.

(9)

UE Example

 O/D Trip = 5

 The link perfomance functions

 t₁=2+x₁ and t₂=1+2x₂.

 Flow conservation:

 x₁+x₂ = 5

 UE status:

 Travel time for path 1 = Travel time for path 2

 t₁ = t₂

 2+x₁ = 1+2x₂

 Solve:

 2+5-x₂=1+2x₂

 x₂ = 2, x₁ = 3 Route 2

Route 1 t₁=2+x₁ t₂=1+2x₂

(10)

UE Formulation

(11)

SO Assignment

• System Optimal

– Purpose: Minimize the sum of total travel time of all people

• Wardrop’s Second Principal

– “At equilibrium the average journey time is minimum”

– Ideal Condition

• Each user behaves cooperatively in choosing his own route to ensure the most efficient use of the whole system

– Not a real world case

– Can be achieved using road pricing (toll) etc.

(12)

SO Assignment

 This can be formulated as a mathematical program

Min

Subject to

, for all k, and O-D pairs , for all k, and O-D pairs

Where, for all links

a a a

Z =  X t

k k

f = q



f

_k

 0

a k ak

OD K

X =   f δ

(13)

Example

 O/D Trip = 5

 The link performance functions

 t₁=2+x₁ and t₂=1+2x₂.

 Flow conservation:

 x₁+x₂ = 5 Route 2

Route 1 t₁=2+x₁ t₂=1+2x₂

• Result

X₁ X₂ T₁ T₂ Total

Travel Time

AoN 0 5 2 11 55

UE 3 2 5 5 25

SO 3.17 1.83 5.17 4.66 24.92

(14)

1. The time it takes a car to travel each road here is related to the number of other cars on the road, written in the equations next to the road as F.

One car will take (10*1)+(1+50)=61 minutes, no matter which route it takes.

Braess’ Paradox

http://www.kennislink.nl/upload/129110_276_1110806900624-file_braess_paradox.jpg

(15)

2. Adding an extra expressway going from the west side to the east side across the park shorten the trip for one car. That car can now make the journey from downtown to uptown in (10*1) + (1+10) + (10*1) = 31

minutes.

Braess’ Paradox

(16)

3. With six cars going from downtown to uptown, and no Cross Park Expressway, the commute is slower. The best drivers can do in (10*3) + (3+50) = 83. No one can switch routes without making the trip even longer.

Braess’ Paradox

(17)

4. But adding that expressway just makes matters worse. With six cars

taking each of the three available routes, the former shortcut takes (10x4) + (2+10) + (10x4) = 92 minutes-longer than it did before the expressway existed.

Braess’ Paradox

Link 1: 4 (t1=10*4= 40) Link 2: 2 (t2=2+50=52) Link 3: 2 (t3=2+10=12) Link 4: 2 (t4=2+50=52) Link 5: 4 (t5=10*4=40) Path 1: t1+t4=92

Path 2: t1+t3+t5=92 Path 3: t2+t5 = 92

(18)

Basic Concepts in

Minimization Problems

(19)

General Minimization Problem

• Object function

• Constraints

• Feasible Region

• Decision Variables

where,

(20)

General Minimization Problem

• Solution x*

(21)

Linear Programming

• 선형계획법; LP

• maximizing or minimizing a linear

function subject to linear constraints

(22)

Linear Programming

• 선형계획법; LP

• maximizing or minimizing a linear

function subject to linear constraints

(23)

Linear Programming

• Example

Max.

s.t

(24)

Linear Programming

• Example

Feasible Region

(25)

Linear Programming

• Standard Maximum Problem

Max.

s.t

(26)

Integer Programming

• Variables are integer

– Logical Requirement – Fixed Cost

– Sequencing and Scheduling requirement

• Category

– Integer Linear(Nonlinear) Programming – Mixed(Pure) Integer Programming

– Binary Integer Programming

• In many cases NP-Hard; Hard to solve

(27)

Shortest Path Problem

• Dijkstra’s Algorithm (Demo)

(28)

Nonlinear Programming

• Object functions and constraints are nonlinear

• Example

min z(x)=x

²

s.t. x≤10

x≥5

(29)

Unconstrained Minimization Programs

• First Order Condition for Minimum

(30)

Unconstrained Minimization Programs

• Convex Function

– A sufficient condition for a stationary point to be a local minimum is

– for the function to be strictly convex in the vicinity of the stationary point

– Strict convexity means “heavy in the middle”

– If the object function is convex for all x, and

x* is the local minimum then x* is the global

minimum

(31)