• English
    • Norsk
  • English 
    • English
    • Norsk
  • Administration
View Item 
  •   Home
  • Det matematisk-naturvitenskapelige fakultet
  • Matematisk institutt
  • Matematikk
  • View Item
  •   Home
  • Det matematisk-naturvitenskapelige fakultet
  • Matematisk institutt
  • Matematikk
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

System optimum vs. user equilibrium in static and dynamic traffic routing

Venstad, Jon Marius
Master thesis
View/Open
VenstadMaster.pdf (718.5Kb)
Year
2008
Permanent link
http://urn.nb.no/URN:NBN:no-21228

Metadata
Show metadata
Appears in the following Collection
  • Matematikk [167]
Abstract
This thesis treats traffic as flow in static and dynamic networks. This

may be any kind of traffic; cars, information etc. Two flows are of

particular interest: The system optimum, which minimizes total travel time

for all traffic, and the user equilibrium, in which all traffic with

common origin and destination experiences the same cost. The system

optimality problem is given globally as a minimization problem, whereas

the user equilibrium is given locally on the flow of each

origin-destination pair.

A network consists of a directed graph G = (V, A) where each arc has a

transition time, or latency function, dependent on the amount of flow

along it. In addition arcs may have flow capacities. Some of the vertices

also have supplies or demands, and a flow needs to satisfy all constraints

in the network.

The static networks are allowed to have convex non-decreasing latency

functions, which makes finding the system optimum or the user equilibrium

for a given network a convex optimization problem in general. The thesis

also treats some special cases.

The main results in this area are :

(1) A system optimality criterion given locally on the flow of each

origin-destination pair, similar to the criterion for a user equilibrium.

This makes checking for optimality simple, and can in some cases simplify

finding the system optimum.

(2) An algorithm for determining taxes on the arcs of a static network

such that the system optimum when considering only latency costs and the

user equilibrium when considering latencies and taxes coincide. This can

for instance be used to determine taxes that will make vehicle traffic in

cities distribute itself in a system optimum, minimizing the total amount

of time spent in traffic by all vehicles.

The dynamic networks are restricted to having only constant latency

functions on the arcs. This allows discretizing the the network along the

time axis, which again allows for a linear optimization formulation of the

dynamic system optimality problem.

The main result in this area is an algorithm for finding the dynamic

system optimum without discretizing the network, and thus reducing the

required computational time by a large amount. This algorithm is based on

the Successive Shortest Path algorithm for finding minimum cost static

flows, and has the same running time as this algorithm.

The resulting dynamic flow is one that consists of different extreme

static flows at different time intervals. Combining this result with (2)

from the static flow work ultimately results in a method for computing a

dynamic system optimal flow and turning this into a user equilibrium by

adding time dependent taxes along the arcs of the network.
 
Responsible for this website 
University of Oslo Library


Contact Us 
duo-hjelp@ub.uio.no


Privacy policy
 

 

For students / employeesSubmit master thesisAccess to restricted material

Browse

All of DUOCommunities & CollectionsBy Issue DateAuthorsTitlesThis CollectionBy Issue DateAuthorsTitles

For library staff

Login

Statistics

View Usage Statistics
RSS Feeds
 
Responsible for this website 
University of Oslo Library


Contact Us 
duo-hjelp@ub.uio.no


Privacy policy