Agent Strategies (Plans)

As pointed out in the introduction, a simulation for particle movement is not enough to solve questions of transportation planning - a simulation of the particles' tactical and strategic behavior, such as destination choice and route selection, is also necessary. This is where this line of work deviates from standard physics and veers into the social sciences.

In fact, this last statement is only partially correct. As one will see, our work concentrates on simulations with large numbers of particles (agents), thus emphasizing statistical effects of agent interaction over detailed individual mental models. The intuition behind that is that the real world system is governed by a large number of constraints (road capacity, location of residential/commercial areas, demographic structure of the population) and that those constraints play a dominant role in the behavior of the real system. Whether this intuition is indeed correct is an open question.

Typical modules for strategy generation in a multi-agent transportation simulation are: synthetic population generation, activities generation, mode and route choice. These will be described in the following.

Synthetic Population Generation

A typical first step in giving strategies to the particles is to individualize them by generating a synthetic population. This is done by taking a model of the real environment, and populating it with synthetic agents which have the correct demographic characteristics. For example, within census blocks there will be the correct number of males or females, and the synthetic population will have the correct age structure. What is typically missing in publicly available census data is the correlation structure. For example, the number of males/females and the number of people below/above age 30 may be known (the ``marginals''), but not how many males are below/above age 30. Such correlation structure is typically given for a small sample of the population, for which much more information is made available. In return, the geographic locations of these sample households are much less precise. A technique is thus needed to merge these two pieces of information, i.e. to generate for each census block complete tables where the marginals still match the census, and the correlation structure approximates the sample data. A possible technique for this is Iterative Proportional Fitting (IPF; Beckman et al. (1996)). The population is then located along the streets in the census block. None of our current results use the synthetic population generation, but its application is planned in 2003.

Activity Generation

For each member of the synthetic population, daily activity plans are then generated. This consists of three sub-problems: The first sub-problem is activity pattern generation. An activity pattern describes the sequence of activities that an individual performs during a day. Typical examples are ``home-work-shop-home'' or ``home-university-leisure-home.''

Next comes activity location generation. Activities need to be executed at certain locations. Algorithms are necessary to generate these locations. This will use land use data in order to have information at which locations certain activities can be performed.

The last sub-problem is activity scheduling. This is the computation of when the activity chain is started and how long each activity takes. It should take into account an estimate of expected travel times between activities at different locations.

Although methods are known for the above problems (e.g. Bowman, 1998), few projects seem to have implemented this for large scale real-world applications. Most of the emphasis seems to be on the generation of activity patterns, which can be generated from travel diaries which are available for samples of the population. Activity location generation is a problem because of the large number of possible options; some heuristic reduction of the search space will probably be necessary. In contrast, activity scheduling seems to be computationally feasible; yet, there seems to be no universal agreement on cost/utility functions which are necessary to evaluate and compare different schedules (K. Axhausen, personal communication).

The activity generation problem illustrates that one should consider concepts both from computational search and from psychology. Search methods from computer science may result in optimal solutions, or may show that an exact solution of the problem is very difficult. In contrast, real people do not solve these problems optimally, but use heuristics that lead to ``good'' solutions. For example, Doherty and Axhausen (1998) point out that in reality people solve parts of the activity scheduling problem on different time scales. Approximate work hours are usually known many days in advance, and regular tasks such as bringing children to the kindergarten follow closely behind. More irregular activities such as shopping or leisure activities are planned on a shorter time scale, but usually at least a day in advance. Finally, spontaneous decisions or unexpected events (such as a sick child) can override the schedule at the last minute.

A computational method that lies in between human heuristics and exact algorithmic search are Genetic Algorithms (GAs; Goldberg (1989)). It is in fact possible to use GAs for activity generation (Charypar, 2002). These methods are however far away from being calibrated and ready to use for real-world applications.

Note that activities can be generated for vacation tourists as well as for everyday workers. An activity chain for a tourist would maybe read ``hotel - be at mountain X and enjoy view for 10 minutes - be at mountain restaurant Y and have coffee for an hour - hotel.'' In this case, the travel connecting these locations would not just be considered as a necessary nuisance, but it would contribute to positive utility. The overall concept remains similar.

None of our current real-world results use activity generation, but its application is planned in 2003.

Mode and Route Choice

Activities at different locations are connected via travel. Individuals make a mode choice (walk, bus, bicycle, car, ...) and a route choice. 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 on how long it will take to traverse the link when entering at a specific time, this algorithm computes the fastest path from $i$ to $j$ when starting at time $t_0$. The time-dependent Dijkstra algorithm, which solves this problem, is a very fast algorithm, and it is difficult to construct a heuristic which is significantly faster (Jacob et al., 1999).

Mode choice can either be seen as part of the activity generation process (after all, activity selection depends critically on the means of transportation that one selects), or it can be seen as the problem to select a good mode given the chain of activities. In the first situation, it will have to be solved along with activity generation. In the second situation, it is in fact possible to extend the time-dependent Dijkstra algorithm such that mode choice is included (Barrett et al., 2000). Another possibility is to just generate routes for several different modes and then to select between them using a random utility model.

Figure 4: Virtual reality representation of simulated traffic in Portland/Oregon. Including visualization of within-day replanning.