This thesis treats traffic as flow in static and dynamic networks. Thismay be any kind of traffic; cars, information etc. Two flows are ofparticular interest: The system optimum, which minimizes total travel timefor all traffic, and the user equilibrium, in which all traffic withcommon origin and destination experiences the same cost. The systemoptimality problem is given globally as a minimization problem, whereasthe user equilibrium is given locally on the flow of eachorigin-destination pair.A network consists of a directed graph G = (V, A) where each arc has atransition time, or latency function, dependent on the amount of flowalong it. In addition arcs may have flow capacities. Some of the verticesalso have supplies or demands, and a flow needs to satisfy all constraintsin the network.
The static networks are allowed to have convex non-decreasing latencyfunctions, which makes finding the system optimum or the user equilibriumfor a given network a convex optimization problem in general. The thesisalso treats some special cases.The main results in this area are :(1) A system optimality criterion given locally on the flow of eachorigin-destination pair, similar to the criterion for a user equilibrium.This makes checking for optimality simple, and can in some cases simplifyfinding the system optimum.(2) An algorithm for determining taxes on the arcs of a static networksuch that the system optimum when considering only latency costs and theuser equilibrium when considering latencies and taxes coincide. This canfor instance be used to determine taxes that will make vehicle traffic incities distribute itself in a system optimum, minimizing the total amountof time spent in traffic by all vehicles.
The dynamic networks are restricted to having only constant latencyfunctions on the arcs. This allows discretizing the the network along thetime axis, which again allows for a linear optimization formulation of thedynamic system optimality problem.The main result in this area is an algorithm for finding the dynamicsystem optimum without discretizing the network, and thus reducing therequired computational time by a large amount. This algorithm is based onthe Successive Shortest Path algorithm for finding minimum cost staticflows, and has the same running time as this algorithm.The resulting dynamic flow is one that consists of different extremestatic flows at different time intervals. Combining this result with (2)from the static flow work ultimately results in a method for computing adynamic system optimal flow and turning this into a user equilibrium byadding time dependent taxes along the arcs of the network.