Traffic assignment

The traffic assignment - or route assignment - problem can be formulated as follows: Given a set of trips via starting times, starting locations, and destinations, find a ``good'' route for each trip. This is in fact a strong simplification of the real world situation, where neither the starting times nor the trips themselves are fixed. It is however a useful starting point for analysis. Even for this simplified problem, there are many variations. Some of them will be described in the following.

Static assignment

This is the maybe best-known formulation of the problem (e.g. [1]). Instead of single trips, one assumes constant traffic streams $r_{ij}$ going from each origin $i$ to each destination $j$. The collection of $r_{ij}$ is also called the origin-destination (OD) matrix. Routes from $i$ to $j$ are numbered by $k$; $r_{ij,k} \ge 0$ is the number of trips using the $k$-th route. Let $\delta_{ij,k,a}$ be an indicator if route $ij,k$ uses link $a$. The number of trips using link $a$ then is

$$x_a = \sum_{ij} \sum_k r_{ij,k} \, \delta_{ij,k,a} \ .$$

The link travel time (link cost) is normally defined via a function $t_a(.)$. The trip time of a route in consequence is

$$T_{ij,k} = \sum_a t_a(.) \, \delta_{ij,k,a} \ .$$

The problem specification now is that $r_{ij,k}$ need to be found such that

$$\sum_k r_{ij,k} = r_{ij}$$

and such that all used routes have the same travel time and no unused route has a faster ($=$ better) travel time.

If one assumes that $t_a$ depends on the flow $x_a$ only (i.e. neither on other aspects of traffic flow nor on traffic on other links), and if $t_a(x_a)$ is strictly monotonic, then it can be shown that the static assignment problem has a unique solution, and in consequence a method with a fast convergence rate should be selected. Since the problem is typically non-linear, these methods are relaxation methods, that is, a partial solution is constructed, which is continuously improved through the algorithm.

Dynamic OD matrices

In static assignment, the basic assumption is that the traffic streams $r_{ij}$ are constant. In reality, however, these traffic streams are time dependent; for example, traffic streams in the morning are clearly different from traffic streams in the evening. A possibility to deal with this in the framework of static assignment is to have different $r_{ij}(t)$ for different time periods, and to solve separate static assignment problems for each time period. Each of these separate static assignment problems solves the problem as if the $r_{ij}(t)$ were constant; in consequence, such an approach is valid only when real-world traffic is sufficiently steady-state over a longer period of time.

Static spatially extended queues

If, for a bottleneck, demand is larger than capacity, the result is that a queue forms upstream of the bottleneck. Under steady state conditions such as in static assignment, the waiting time in queues is a component of the travel time. In standard static assignment, as explained above, queues are assumed to have no spatial extension (``point queues''), and as long as the network has enough overall capacity, there will be an equilibrium solution. The ``enough overall capacity'' constraint is automatically fulfilled with link cost functions which admit arbitrarily high link flows (albeit at a high cost), such as the BPR link cost function.

The situation changes dramatically once links have hard capacity constraint, and traffic forms spatially extended queues upstream of bottlenecks. Although steady state equilibrium solutions to such scenarios are possible, they may not be unique, and possibly one solution does fulfill the demand set by the OD matrix and another one does not [2]. That is, with spatially extended queues already the static problem leaves the area of where a good mathematical foundation is available.

Dynamic spatially extended queues

None of the problem formulations so far deals with the problem of dynamic queues, i.e. the dynamic reality that queues grow and shrink. Dynamic queues leave the framework of static assignment, and one normally resorts to simulation. In order to solve the resulting dynamic traffic assignment (DTA) problem, one uses a relaxation method: All travelers select a route, the simulation is run, some travelers adjust their route, the simulation is run again, etc., until some convergence criterion is fulfilled.

Interestingly, this is still similar to typical static assignment solution procedures: there is a routing procedure which gives routes to each individual traveler, and there is a simulation (``network loading'') which returns the link travel times $t_a$ based on the routes. Since a simulation is used to generate those links travel times, one is however much less restricted in terms of the choice of the particular traffic dynamics than with traditional static assignment.

There is much less knowledge about the types of solutions that such an approach will generate. One way to look at such iterated systems is to treat them as time-discrete dynamical systems [3]. A state is the trajectory of the simulation through one day; an iteration is the update from one day (period) to the next (Fig. 1.1). As such, one can search for fix points (for deterministic systems), steady state densities (for stochastic systems), multiple basins of attraction, strange attractors, etc. Typically, one would first analyze the steady state behavior, and then the transients. Under certain conditions the existence of a unique steady state can be proven [4], although for the computationally feasible number of iterations the possible occurrence of ``broken ergodicity'' [5] needs to be taken into account. Broken ergodicity is the property of a system to be mathematically ergodic but to remain in parts of the phase space for long periods of time.

Figure 1.1: Schematic representation of the mapping generated by the feedback iterations. Traffic evolution as a function of time-of-day can be represented as a trajectory in a high dimensional phase space. Iterations can be seen as mappings of this trajectory into a new one.

Human behavior and agent-based simulation

So far, the assumption was that we attempt to find a Nash equilibrium, although the situation has become more and more complex. It is however not automatically clear that reality fulfills a Nash equilibrium; rather, we have many travelers making individual decisions which may or may not lead to a Nash equilibrium. In agent-based simulations, it is possible to implement this directly: The simulations have individual travelers, and they behave according to certain rules. Now, convergence to Nash equilibrium is a possible outcome of the dynamics, not a requirement.

Also, as indicated in the introduction, route choice is in fact only a subset of all possible decisions that a traveler is faced with. When adding other choice dimensions, such as activity selection or even housing choice, the situation becomes even more complicated, and the framework of route assignment can no longer be maintained. For example, the housing market is never relaxed, and thus a behavioral modeling of the transients is a necessity [6]. Also, increasingly more complex aspects of the human decision-making means that we are not able to compute a ``best'' solution - and we suspect that humans in the real world do not do this, either. All this points to the use of multi-agent simulations, where agents are represented by behavioral rules, which can be changed directly. Aspects of such simulations will be discussed in the next sections.