Introduction

The established model for transportation planning is the four-step process, consisting of the four modules trip generation, trip distribution, modal split, and route assignment. It is well known that the traditional (static) four-step process falls short of many requirements that are desirable for modern transportation planning, for example:

1. There is no time-of-day in the static modeling approach.

2. Because there is no time-of-day, it is difficult or impossible to model any kind of time-dependent effect, such as emissions (which depend on engine temperature, which in turn depends on how long the car has been driving), or peak traffic spreading.

3. Decisions are decoupled from persons and therefore from demographic attributes.

Item 3 is, at least conceptually, easy to fix by making the first three steps of the four step process explicitly person-dependent. The most common solution to this is activity-based demand generation (ADG), which is discussed at many places (e.g. 19), and implemented at some (e.g. 24,38,8). ADG typically means the following steps:

(i)

Generation of a synthetic population by disaggregating census data into individual people. The synthetic population is a random realization of the census, that is, a census taken from the synthetic population would, within statistical limits, return the original census.

The typical data content of a synthetic population are households, which are located spatially, and which possess some attributes, such as household income, or car ownership. These households are populated with individuals, who posses additional attributes, such as gender and age.

(ii)

For each individual of the synthetic population, a complete daily activity plan is then generated. The word ``activity'' refers to actions such as ``being at home'', ``shopping'', ``working'', ``being at school'', etc. Besides the activity pattern, the activity plan also contains the location of each activity, and some timing information, such as when activities are started and ended.

(iii)

Each individual selects a mode of transportation.

It is more difficult to solve items 1 and 2, i.e. the lack of time-dependence of static assignment. The advantage of static assignment over other methods is that it has a range of mathematically proven properties, in particular the uniqueness of the solution in terms of the link volumes. Clearly, this simplifies the comparison of implementations and the interpretation of different scenarios enormously.

When making the assignment formulation dynamic (dynamic traffic assignment, DTA; e.g. 3,25,16), the extent of mathematically proven properties becomes much smaller. In particular, when the dynamic formulation includes spillback (also called physical queues), then one can construct examples of non-uniqueness, i.e. there are multiple user equilibrium solutions to the same origin-destination matrix and the same network (11). In consequence, one may have to accept that DTA with spillback is in general mathematically less well-behaved than static assignment.

Conceptually, DTA can be decomposed into two components (6): route generation, and network loading.¹ In static assignment, the network loading is done via the volume-cost function, which returns the cost of a link as a function of the trips using that link. In a dynamic context, the relationship is much more complicated, and it makes sense to look at simulation as a solution to the network loading. Simulation, as is well known, is a technique where a dynamic model is implemented on a computer, and run forward in time. Its conceptually simplest incarnation with respect to transportation planning is a representation of roads, and a way to move traffic forward along the links. Network loading models are classified according to the following criteria:

1. Resolution: Traffic can be represented by individual vehicles, but vehicles can also be aggregated into packets or cells.

2. Fidelity: The behavior of each individual entity can be more or less realistically represented.

3. Modes: The simulation can concentrate on one mode only, or can combine several modes including their interaction.

4. Time resolution/time step.

Note that at one end of this classification, one finds the traditional assignment model (resolution aggregated on link level; fidelity reduced to volume-cost-functions; car mode only; no time-dependency). Examples for more realistic, simulation-based network loading models are DYNAMIT (13), DYNASMART (14), METROPOLIS (12), TRANSIMS (35), or the queue model (18,17).

So far, this introduction discusses that demand generation can be made more realistic by moving to activities, and traffic assignment can be made more realistic by making it time-dependent and then using simulation for the network loading. Since these were discussed as separate changes, it is natural to assume that they are designed so that they are backwards compatible to the 4-step process, which means that the ADG produces origin-destination (OD) matrices as output, and the DTA takes them as input. This also means that ADG can be fed into a traditional static assignment, and DTA can take its input from the traditional demand generation.

However, in order to take account of the time dependency of the demand, the OD matrices generated by ADG are usually time dependent. This is a break with the backwards compatibility, in the sense that although the DTA models work with a traditional static OD matrix, it is difficult to relate the output to reality. METROPOLIS (12) is an exception to this since it takes static OD matrices as inputs and makes them time-dependent internally, using Vickrey's timing model (2).

An additional disadvantage of using OD matrices to couple ADG to DTA is that it gives up the connection to the individual persons - the same connection that was just gained in steps one to three of the 4-step process by moving to ADG. However, routing decisions can depend on individual attributes: The decision to use a toll road can depend on income; a person in need to catch an airplane may prefer a road with lower variability; etc. Also, activity chains have dependencies in the time direction - a delay in the morning may trigger changes in the afternoon - and the OD matrix severs this connection. It makes sense, therefore, to bypass OD matrices completely and to feed the complete information from the activity-based demand generation into the DTA. This means that throughout the whole process, including the DTA, the travelers are maintained as individual entities with individual attributes, and make individual decisions based on these attributes. This is what is meant by an agent-based or multi-agent approach (e.g. 15). And indeed, there are numerous papers related to transport that mention ``agent'' in their title (e.g. 39,1).

This paper concentrates on the multi-agent approach as an improvement of the complete 4-step process. The main differences against coupling ADG to DTA via OD matrices are:

• The DTA is completely agent-based, as discussed above. In particular, it is capable of feeding back agent-based information, not just link-based information.

• The ADG is included into the feedback process. Historically, systematic feedback is mostly between the route generation and the network loading; feedback to the demand generation was often done manually by the analysts. However, it has been said for a long time (e.g. 27) that this process should be automated.

It is useful to conceptually differentiate between a mental and a physical layer (Fig. 1):

• The mental layer represents the processes that are internal to the travelers. It is sometimes also called the strategic layer.

• The physical layer represents what the travelers actually do in the physical world. In traffic, this is normally called the network loading, or the traffic (micro-)simulation. In this paper, it will be called the mobility simulation, to stress its total independence from the mental/strategic layer.

• There are mechanisms that couple the two layers: The attempt to execute a plan causes changes in the physical layer; inability to execute the plan as intended, for example because of congestion, feeds back into the strategic layer.

Figure 1: Physical and strategic layers of the framework.

There is, to our knowledge, no simulation package that executes this approach in its entirety. Part of the challenge is that this necessitates a large number of modules and module interfaces, which in itself is quite a challenge, in particular in view of the fact that there are few programming and/or data exchange standards in the community. Another part of the challenge is that one needs parallel computing techniques for metropolitan-size scenarios, and no established technology is available to even define a viable standard for module interaction once the simulation becomes parallel (30). Some partial packages are discussed in the following.

Dynamic traffic assignment (DTA)

There is a large number of packages that do dynamic traffic assignment (e.g. 18,13,14,12). As discussed above, these packages typically take time-dependent OD matrices as input, assign routes according to user equilibrium, and return time-dependent link travel times and other link-based information as output. Although most of these packages have individual travelers inside their model, often these are not fully developed. For example, routes are calculated by the network rather than by the agent, and agent-based output is often not available. While the latter is conceptually easy to fix, the former means that making route choice dependent on agent attributes is close to impossible. This is related to the fact that those models take OD matrices as input, which contain no demographic attributes. A direct consequence is that it will not be possible to connect an agent's performance in the DTA to the demand generation, since the OD matrices sever the connection to the individual agents; it is only possible to feed aggregated information, such as link travel times, back to the demand generation modules. In summary, although the DTA models have a large number of agent-based elements, they are not fully agent-based.

TRANSIMS

TRANSIMS (35) indeed replaces the complete four-step process by an agent-based approach that as its first step disaggregates census data and then works with individual travelers in all modules. In addition, TRANSIMS uses parallel computing to tackle large scale problems. The main shortcomings of TRANSIMS, in our view, are:

• Although travelers are individually identifiable throughout all modules, agent information is spread throughout the simulation system. For example, the activity file does not contain demographic information, and the route file contains neither demographic nor activity information. This makes it rather difficult to use such ``higher level'' information in the ``lower level'' modules. It also makes it possible, for example, that an agent leaves a location before it has arrived - this is possible since the agent is not a singular entity in the simulation.

• The file formats are rather inflexible. This makes it difficult to add/modify information, for example when adding new modules to the system.

• The feedback mechanism ``forgets'' old plans and their performance. Although it is a bit difficult to see at first glance, this means that TRANSIMS plans generation modules need to fulfill rather strong requirements: For example, the routing module (``router'') does not only have to generate plausible routes, but also correct probabilities to choose between different alternatives.

• And finally, it was impossible to obtain an academic license, including source code, outside the United States. This made it impossible to improve the above aspects inside TRANSIMS.

Land use simulations

There are land use simulations, such as URBANSIM (36), ILUTE (33), or that of Hunt et al. (21), which are more or less agent-based, and which have the conceptual intention to couple to the transportation system. However, in practice this connection is not well established in those models at this point in time.

This paper will present an approach that is based on TRANSIMS but solves the above TRANSIMS shortcomings. The conceptual idea behind our approach is that we keep the agent concept consistent everywhere. The main technical improvements are in the following areas:

• The different TRANSIMS files are replaced by a single XML file format. That file contains, agent by agent, all information related to the agents, from demographic information via activities to routes.

• An agent cannot be ``divided''. This means in particular that the traffic simulation (network loading) executes daily plans, rather than just trips.

• An agent data base keeps track of agents' past plans and performance of those plans.

In the next section 2, we describe the basic design of the framework, including the agent and plan entities, the agent database, plan scoring, and iterations between the parts of the framework. Section 3 goes on to describe our current implementation of this framework, in particular introducing the XML data format that is one of the cornerstones of this framework. This is followed by a description, in Sec. 4, of the set-up of our case study for verifying the operation of this framework, including the specific behaviors of our mobility simulator, and route and time choice modules. This section also describes the utility function used by the modules to score plans, and the transportation scenario we have executed. Section 5 then explains the results obtained by our framework for this case study. Finally, we end with a discussion 6 and summary 7.