##### 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.