THE MODULES

The modules which are important for this study are the traffic micro-simulation, the route generator (``router''), and the feedback mechanism, which controls the interaction between the micro-simulation and the router.

Queue Micro-Simulation

As a traffic micro-simulation we use an improved version of a so-called ``queue simulation'' (43). The improvements are an implementation on parallel computers, and an improved intersection dynamics, which ensures a fair sharing of the intersection capacity among incoming traffic streams (26). The details of the traffic simulation are not particularly important for this paper; we expect many traffic simulations to reproduce similar results. The important features of our simulation are:

Plans following. The feedback framework generates individual route plans for each individual vehicle, and the traffic simulation needs to have travelers/vehicles which follow those plans. This implies that the traffic simulation needs to be microscopic, that is, all individual travelers/vehicles are resolved. Beyond that, however, it does not prescribe the dynamics; everything is possible from smooth particle hydrodynamics (e.g. (20,21)) to virtual reality micro-simulations (e.g. (22)).

Computational speed. We need to run many simulations of 24-hour days -- usually about 50 for a single scenario. This means that a computational speed of 100 times faster than real time on a road network with several thousands of links (road segments) and several millions of travelers is desirable. Our queue simulation demonstrates that this is feasible.

Congestion build-up and queue spillback. Although this is not a requirement for the framework in general, the results of the present paper depend on the fact that congestion normally starts at bottlenecks (i.e.demand is higher than capacity), but then spills backwards into the system and across intersections. Once such congestion is there, it takes a long time to dissolve. The model should reflect this, and it should reflect the physical space that the queued vehicles occupy in the system.

Router

In addition, we need a router, i.e.module that generates paths that guide vehicles/travelers through the network from a given origin to a given destination. In addition, the vehicles/travelers have starting times, and the router needs to be sensitive to congestion so that it tends to avoid congested links.

The router we have used for the present study is based on Dijkstra's shortest-path algorithm, but ``shortness'' is measured by the time it takes an agent to travel down a link (road segment) in the network. These times depend on how congested the links are, and so they change throughout the day. This is implemented in the following way: The way a Dijkstra algorithm searches a shortest path can be interpreted as expanding, from the starting point of the trip, a network-oriented version of a wave front. In order to make the algorithm time-dependent, the speed of this wave front along a link is made to depend on when this wave front enters the link (e.g. (44)).

That is, for each link $l$ we need a function $c_l(t)$ which returns the link ``cost'' ($=$ link travel time) for a vehicle entering at time $t$. This information is taken from a run of the traffic simulation. In order to make the look-up of $c_l(t)$ reasonably fast, we aggregate over 15-min bins, during which the cost function is kept constant. That is, all vehicles entering a link between e.g.am and 9:15am will contribute to the average link travel time during that time period.

Feedback

Finally, we need the feedback mechanism to couple the router and the traffic simulation. Initially, we feed the traffic simulation with plans based only on free speed travel times. Every time a traffic simulation run completes, the router uses the simulation output to update the travel-time (cost of utilization) associated with each link in the network. After the router updates its view of the network, it generates new plans for a subset (typically a randomly selected 10%) of the drivers, and the entire updated and merged plan-set is fed back into the micro-simulation for another run. We repeat this process as many times as necessary (about 50) until the system ``relaxes''. Relaxation is as of now not measured by a quantitative criterion, but via judging visualizer output. This will eventually change.

Figures 1(a) and 1(b) illustrate the improvement in the system due to this iterative scheme. Each figure shows a snapshot of vehicle positions in the Gotthard scenario, described in Sec. 5. Figure 1(a) shows a snapshot during the initial (0th) iteration, three hours after the simulation started. Congestion is not known in this iteration, so each traveler assumes free speed travel times, and chooses a route as if it is the only driver in the network. They all choose the freeways, and do not explore alternative routes. Figure 1(b) shows the same situation, but 49 iterations later. Here, the drivers have taken into account the congestion caused by other vehicles on the roadways, so they use many more routes.

Figure 1: (a)-(b): Example of relaxation due to feedback. (a) Iteration 0 at 9:00 -- all travelers assume the network is empty. (b) Iteration 49 at 9:00 -- travelers take more varied routes to try to avoid one another. (c)-(e): A freeway and side roads with the different travel time feedback method at 19:00 (left) and 20:00 (right). (c) Original method. The side roads contain many vehicles while the freeway contains very few or none. (d) Combined offset time bins with maximum travel time strategy. The side roads are finally empty, while the freeway now contains vehicles. This is what is expected from the scenario. (e) Agent database method. As with method (b), the side roads are emptying, while the freeway contains vehicles. This shows the agent database is a robust solution to the freeway problem.

[] [width=0.49]common_it0_0900_all-fig.eps [] [width=0.49]avg_it49_0900_all-fig.eps

[] [] []