INTRODUCTION

During the last decades, simulation has joined theory and experiment as a third method of scientific inquiry. In simulation a virtual version of the real world is reconstructed inside the computer, and scientific and engineering questions can then be addressed to that computational model. Simulation is a particularly appropriate method when analytical theory alone has little predictive power, when controlled experiments are costly or impossible, or when extracting measurement data from the real system is costly or impossible. All three criteria are fulfilled in transportation science as well as in socio-economic science in general.

In addition, a new method is particularly appropriate for the simulation of socio-economic systems: the method of multi-agent or agent-based simulations. In these methods, all entities of the system are represented as objects which have internal states and follow individual rules. This is particularly appropriate for objects which have a complicated internal structure and which all differ from each other. Again, this is true for transportation science as well as in socio-economic science in general, but it also encompasses engineering objects such as adaptive traffic signals.

The emergence of the agent-based technique would not have been possible without the emergence of modern computing. Rule-based code runs efficiently on modern PCs, making the technology widely available. In addition, agent-based code runs efficiently on modern parallel supercomputers, while it did not run well on more traditional vectorizing supercomputers such as Cray. This makes the jump in computational capabilities even larger than, say, in computational fluid-dynamics. In consequence, it is now possible to perform agent-based simulations of large metropolitan areas with $10^7$ or more travelers.

The last decades have seen considerable progress in making agent-based simulation technology applicable for transportation. Agent-based transportation simulation packages consist of many modules, including the traffic simulation itself, route generation, activity generation, housing choice, land use evolution, freight traffic, but also traffic management strategies. Most if not all groups concentrate on a subset of these modules.

The modules interact, and the interaction goes in both directions: for example, the execution of plans leads to congestion, yet the expectation of congestion influences plans. Any large scale transportation package needs to resolve this logical deadlock in a meaningful way. Reality seems to approach the issue of feedback by a slow system-wide learning process: People pre-plan major pieces of their life (like when and where they work) a long time in advance and normally only re-adjust small pieces of their schedules when needed (1). More precisely, they pre-plan and re-adjust on many time scales, where the time scale is related to the magnitude of the adjustment: workplaces and home locations are re-adjusted on time scales of several years, while the decision to make a detour to buy some ice cream may happen within seconds. In consequence, a simulation system is faced with two challenges:

1.

Modeling adaptation and learning on all time scales -- In principle, a transportation simulation should simulate several thousand days in sequence, and the decisions of the individual people should unfold on their particular time scales as pointed out above. In particular, travelers should be able to replan while en route. While this sounds simple in principle, it is difficult in practice, because one wants to avoid a large monolithic software package and thus one wants to separate the traffic flow simulation from the strategic decision-making of the travelers. This becomes particularly relevant for parallel transportation simulations, since now the strategic planning needs to be separated from the traffic simulation also for performance reasons. This is not the topic of this paper; see (2) for more information.

2.

Behavioral realism vs.relaxation -- In practice, simulating several thousand days in sequence is difficult to do because of computational resource limitations. It is also questionable if this would yield useful results without a deep understanding of the learning dynamics. As a reaction to this, mathematical modeling of transportation scenarios, as well as of economics in general, in the past has relied on the notion of a Nash or User Equilibrium (UE). As is well known, in a UE no traveler can improve by unilaterally changing her/his behavior. The advantage is that a UE prescribes a state of the system and it does not matter how the computational system arrives at it -- as opposed to a realistic modeling of the transient learning dynamics. Today, we however increasingly recognize that socio-economic systems do not operate at a User Equilibrium point; for example, for the housing market it is assumed that the system is permanently in the transients (3).

This second point is the focus of this paper. Our approach to the problem is to design a framework which admits all the different views to the problem. That is, the framework should as well converge to the User Equilibrium (assuming it is unique and an attractor -- this is a difficult discussion but again outside the scope of this paper) as it should allow for experimentation with different behavioral hypotheses. We entirely concentrate on day-to-day replanning although our results will also apply to within-day replanning. In particular, we will demonstrate that the introduction of an agent database, which keeps track of agents' past strategies and their performances, will greatly improve both plausibility and robustness of the system.

Throughout this paper we use the term agent to refer to an entity within the simulation capable of making decision about its actions (such as the route to take from point $a$ to point $b$). Since our simulation does not yet involve land use or other non-transportation activities, an agent is presently equivalent to a traveler, a person using the transportation network.

The structure of this paper is as follows: Section 2 gives a general introduction to multi-agent simulations. This is followed (Sec. 3) by an overview of existing methods to solve the dynamic traffic assignment problem, which is the example problem which was used in our investigations. Section 4 describes the specific modules we are using in this study. Section 5 introduces the traffic scenarios we are applying those modules to. Following that, Sec. 6 describes some results from the day-to-day replanning of our feedback system, which turned out to have some implausible implications. We continue the section by describing some alterations we made to the feedback mechanism to try to resolve the problems, and the results of those changes. Next we present in Sec. 7 the agent database, a completely different and more robust approach to solving the problems encountered in the previous section. This section includes results from the agent database approach. We finish with a discussion and a summary.