Agent-based traffic simulation modules

We will now move on to an agent-based modeling of traffic. In this section, we will describe the fundamental modules of a traffic simulation package, as already presented in the Introduction. As pointed out before, for people with a Complex Systems background it is clear what to do here: Program a version of the real-world spatial substrate, consisting of roads and intersections, and then populate it with agents which follow increasingly sophisticated rules. We will however also point out one case where the optimal computer-science soluation works better than a complex systems heuristic; and we will describe the standard solutions on which researchers have settled down. In this section, these modules are presented as stand-alone; the issues of module interaction, which results in adaptation and learning, is then treated in the following section.

Traffic micro-simulation

In order to define a simulation, one first needs to define the spatial substrate. In the case of transportation simulations, this is conventionally a network, consisting of links/edges (roads) and vertices/nodes (intersections).

On these elements, one will have dynamics. There should be pedestrians and cars and buses, etc., and they should drive around according to plausible rules. For car driving alone, the set of absolutely necessary rules is not very large [3], but when including other modes, quite a lot of work is necessary. As a result of this process, one can imagine a virtual reality micro-simulation, such as depicted in Fig. 2.

Sometimes, such an implementation is too much work, and it becomes computationally too slow. It is then possible to replace the virtual reality micro-simulation by something much simpler, which just takes care of moving the travelers through the system and to compute some minimal congestion effects [4,5].

For the purpose of this paper, the exact nature of the micro-simulation does not matter, as long as it will fulfill some minimum specifications, the most important ones being: (1) vehicles in the traffic micro-simulation follow plans; and (2) the traffic micro-simulation runs computationally fast also on large problems. Although these specifications are currently fulfilled by only very few micro-simulations, let us nevertheless put that problem aside and move on to the other modules.

Figure 2: Virtual reality representation of simulated traffic in Portland/Oregon. Including visualization of plans server capability, see Sec. 5.2.

Route generation

Having travelers move around randomly is not enough. For example, if a car approaches an intersection, the driver needs to decide the turning direction. A traditional method is to use turn counts, meaning that there is empirical data with the information about what fraction of the traffic goes into which direction. For any kind of transportation planning question, this is not enough information. The most drastic example is the addition of a new road: There would be no information available of how the traffic at the connecting intersection redistributes when the new road becomes connected. One would also assume that turn counts at other intersections change, since some of the traffic would adapt to use the new road.

This means that for transportation planning simulations it is indispensable to know the destinations, and to have routes for each vehicle. In this way, when a new road or a railway connection is added, every traveler can consider to adapt their routing in order to use this new connection. The route generation module of the transportation planning simulation should be multi-modal (i.e. include other modes besides cars), although some of the mode decision is better done in the demand generation module (see next).

A typical method for route generation is a time-dependent fastest path algorithm. Given a starting time $t_0$, an origin $i$ and a destination $j$, and, for each link, information how long it will take to traverse the link when entering at a specific time, this algorithm will compute the fastest path from $i$ to $j$ when starting at time $t_0$. The time-dependent Dijkstra algorithm, which solves this problem, is with a heap implementation of complexity $M \log N$, where $M$ is the number of links and $N$ is the number of nodes (intersections). This is in fact a very fast algorithm, and it is difficult to construct a heuristic which is significantly faster [6].

Activity generation

For many questions, having the routes adaptive while the activities remain fixed is not enough. For example, making travel faster usually results in people making more trips. This is called induced traffic. Conversely, increasing congestion levels will eventually suppress trips which would otherwise be made, although it is not always clear which trips are suppressed and what congestion level is necessary to have that effect.

In order to deal with these and other effects, one has to make demand generation adaptive to congestion. A recent method for this is activity generation, meaning that, for each individual in the simulation, one generates a list of activities (such as sleeping, eating, working, shopping) plus locations and times (Fig. 3). Since in this method each traveler is treated individually, it is possible to use arbitrary decision rules, which means that arbitrary methods can be investigated. The currently best-accepted methods are based on random utility theory and are called discrete choice models [7]. These models lead typically to a form of

$$p_i \propto \exp\big( - \vec b \cdot \vec x_i \big)$$

for the probability to choose option $i$, where $\vec x_i$ is a vector of attributes. The attributes can refer to the person - e.g. income, gender, marital status, etc. - or to the option - e.g. time spent waiting, time on bus or car, cost of option, etc. They can also be combinations of both; in fact, time on bus or car, say, will depend on where I live. The parameter vector $\vec b$ weighs those different attributes; in general the entries of $\vec b$ are obtained via estimation from surveys and remain fixed for a typical study, while the entries for $\vec x_i$ are taken from the person under consideration and the option under consideration.

As stated above, activity generation needs to be done in conjunction with mode decisions. For example, having a car clearly changes the list of preferable destinations for a given activity, or may even make other activities more desirable. In general, there are no completely clear dividing lines between modules - often, decisions can reasonably be placed in more than one module. It is the task of adaptation and learning (Sec. 4) to consolidate possible inconsistencies between modules.

Figure 3: Example of a sequence of activities for a person in Portland/Oregon. From R.J. Beckman.

Housing, land use, freight, life style, et al

Transportation planning does not stop at activities. For example, making commuting roads faster by increasing capacity usually results in more people moving to the suburbs. That is, housing decisions are closely related to transportation system performance. Similarly, questions of land use (e.g. residential vs. commercial vs. industrial) clearly influence and interact with transportation. Freight traffic needs to be considered. Life style choices (e.g. urban life style, often without car ownership, vs. rural life style, usually with car ownership) need to be considered; such long-term commitments have strong influence on activity selection and modal/route choice.