SIMULATION MODULES

Traffic simulations for transportation planning typically consist of the following modules (Fig. 1):

Population generation. Demographic data is disaggregated so that one obtains individual households and individual household members, with certain characteristics, such as a street address, car ownership, or household income (1). - This module is not used for our current investigations but will be used in future.

Activities generation. For each individual, a set of activities (home, going shopping, going to work, etc.) and activity locations for a day is generated (2,3). - This module is not used in our current investigations but will be used in future.

Modal and route choice. For each individual, the modes are selected and routes are generated that connect activities at different locations (see Sec. 2.1). The routing should be dynamic in order to adequately to time-dependent congestion effects.

Traffic micro-simulation. Up to here, all individuals have made plans about their behavior. The traffic micro-simulation executes all those plans simultaneously (see Sec. 2.2). In particular, we now obtain the result of interactions between the plans - for example congestion.

Feedback. In addition, such an approach needs to make the modules consistent with each other (Sec. 2.3). For example, plans depend on congestion, but congestion depends on plans. A widely accepted method to resolve this is systematic relaxation (6,4,5) - that is, make preliminary plans, run the traffic micro-simulation, adapt the plans, run the traffic micro-simulation again, etc., until consistency between modules is reached. The method is somewhat similar to the Frank-Wolfe-algorithm in static assignment, or in more general terms to a standard relaxation technique in numerical analysis.

This modularization has in fact been used for a long time; the main difference to earlier implementations is that it is now feasible to make all modules completely microscopic, i.e.traveler is individually represented in all modules.

Since this paper is a status report, not all of the above modules are currently implemented. This paper discusses results obtained with a version of the simulation system that consists of car-only versions of the router, the micro-simulation, and the feedback. These modules will be described in more detail in the preceeding sections. It should be noted that in particular the feedback system is unique in that it explicitely keeps track of many strategies of each individual traveler. Most simulation systems assume either only one strategy per traveler, or they group travelers together according to their characteristics, for example by common destination. Since the activity generation module is currently not used, demand is obtained from traditional origin-destination matrices. This will be further discussed in conjunction with the scenario, in Sec. 3.

Abbildung 1: TRANSIMS modules

Abbildung 2: Example of relaxation due to feedback. TOP: Iteration 0 at 9:00 - all travelers assume the network is empty. BOTTOM: Iteration 49 at 9:00 - travelers take more varied routes to try to avoid one another. Red (dark gray in b/w version) indicates jams, green (dark gray in b/w version) indicates free-flowing traffic, and gray indicates empty roads.

Routing

Travelers/vehicles need to compute the sequence of links that they are taking through the network. A typical way to obtain such paths is to use a shortest path Dijkstra algorithm. This algorithm uses as input the individual link travel times plus the starting and ending point of a trip, and generates as output the fastest path.

It is relatively straightforward to make the costs (link travel times) time dependent, meaning that the algorithm can include the effect that congestion is time-dependent: Trips starting at one time of the day will encounter different delay patterns than trips starting at another time of the day. Link travel times are fed back from the micro-simulation in 15-min time bins, and the router finds the fastest route based on these 15-min time bins. Apart from relatively small and essential technical details, the implementation of such an algorithm is straightforward (7). It is possible to include public transportation into the routing (8); in our current work, we look at car traffic only.

Micro-Simulation

Our main micro-simulation is the queue simulation (10,9). The intent with this simulation is to keep travelers/vehicles microscopic and to have queue spillback, but apart from this to keep the simulation as simple as possible. This is similar in spirit to traffic simulations based on the smooth particle hydrodynamics approach, such as DYNEMO (11), DYNAMIT (12), or DYNASMART (13).

In the queue simulation, streets are essentially represented as FIFO (first-in first-out) queues, with the additional restrictions that (1) vehicles have to remain for a certain time on the link, corresponding to free speed travel time; and that (2) there is a link storage capacity and once that is exhausted, no more vehicles can enter the link.

A major advantage of the queue simulation, besides its simplicity, is that it can run directly off the data typically available for transportation planning purposes. This is no longer true for more realistic micro-simulations, which need, for example, the number of lanes including pocket and weaving lanes, turn connectivities across intersections, or signal schedules.

Feedback

As mentioned above, plans (such as routes) and congestion need to be made consistent. This is achieved via a relaxation technique (6,4,5):

1.

Initially, the system generates a set of routes based on free speed travel times.

2.

The new routes are stored in a database, called the ``agent database'' (15,14), so that the travelers (``agents'') may later associate the performance of the route to it, and may choose routes based on performance.

3.

The traffic simulation is run with these routes.

4.

Each agent measures the performance of his/her route based on the outcome of the simulation. ``Performance'' at present means the total travel time of the entire trip, with lower travel times meaning better performance. This information is stored for all the agents in the agent database, along with the route that was used.

5.

10% of the population requests new routes from the router, which bases them on the updated link travel times from the last traffic simulation. The new routes are then stored in the agent database.

6.

Travelers who did not request new routes choose a previously tried route from the agent database by comparing performance values for the different routes. Specifically, they use a multinomial logit model

$$p_i \propto e^{-\beta T_i}$$

for the probability $p_i$ to select route $i$, where $T_i$ is the corresponding memorized travel time. $\beta$ was set heuristically to $1/(360~\hbox{sec})$ to obtain a fraction of about 10% non-optimal users.

7.

This cycle (i.e.(3) through (6)) is run for 50 times; earlier investigations have shown that this is more than enough to reach relaxation (16).

The result is similar to a Stochastic User Equilibrium (SUE), but it is not the same. The main difference is that in an SUE, the agents use a logit model with an externally specified noise parameter to select between options of different performance, while in our system additional noise comes from the simulation, i.e.the fluctuations between iterations.

In fact, relaxation itself, in Item [7.], is not well defined in a mathematical sense. The intended meaning is that, in the average, a relaxed system should not show any further development or drift. Since the system is stochastic at many levels, the only way in which this could be mathematically achieved is in terms of a steady-state density. If the system were Markovian, then the convergence to a steady-state density would immediately follow; the system is however not Markovian because it can potentially enlarge its phase space at each iteration by finding new routes. Alternatively, one could include all possible routes into the phase space definition. This system would be Markovian, but 50 iterations would be by far too few to explore the phase space, let alone generating a steady state density. Similarly, this enlarged system is ergodic in the sense of Cantarella and Cascetta (17), but that notion is not useful for the relatively small number of iterations that we use. More precisely: Even systems that are formally ergodic can remain in limited regions of the phase space for very long duration, certainly for much longer than for 50 iterations (e.g. 18).

A related issue is the selection of the replanning fraction. A replanning fraction of 10%, as in Item [5.], is a heuristic number that works well in practice. The important limiting considerations are: (i) Adaptation in this system works by travelers finding improved solutions for the current situation. These new solutions will only then work better than previous ones when the system behaves similar from one iteration to the next. This implies that the fraction of the population changing its behavior should not be too large. In fact, for some simpler and deterministic systems one can show that an infinitesimal best reply dynamics leads the system to a Nash Equilibrium (19). One could expect that the situation for our system here is similar, although no formal proof is available. (ii) On the other hand, when the replanning fraction becomes too small, then the relaxation process becomes too slow. For example, with a replanning fraction of 1%, one will need at least 100 iterations until each traveler has obtained a new route once, and that will probably not be enough.

Other methods, in particular the method of successive averages (MSA, see, e.g., Sheffi (20)) could be tried, although MSA has a reputation, justified from a theoretical perspective, to display rather slow convergence. In addition, some translation of MSA to a stochastic process would be necessary. For example, a traveler's potentially mixed strategy should be an average best response against the traffic pattern, and this is not necessarily the same as a best response against the average traffic pattern. It is not immediately clear how to achieve an average best response without a lot of averaging over many iterations (many more than 50).

In practice, however, Rickert (16) has looked at the sum of all travel times as an indicator for relaxation, and has found that a system which was similar to ours did not display any further drift after about 25 iterations. This observation was confirmed by visual inspection of the traffic patterns. Bottom (6) has done a much more exhaustive investigation into the same topic, with a similar result.

Note that all the above arguments imply that routes are fixed during the traffic simulation and can only be changed between iterations. Work is under way to improve this situation, i.e.allow online re-planning (21). - Further investigation of relaxation and learning issues is planned.