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.