Computing

Metropolitan areas typically have 10 million or more inhabitants. Simulating all these inhabitants individually, as one does with an agent-based simulation, is a considerable computational challenge. We counter this challenge on several levels.

On the level of the traffic simulation, we use high performance parallel computing. This is done by segmenting the geographical area into many domains, and each domain is given to a different computer to simulate. The different computers communicate with each other via messages. Since these messages are exchanged many times per second, a high performance communication network is helpful, although useful results can also be produced on a cluster of standard PCs coupled by standard Ethernet Local Area Network technology.

Fig. 7 shows computational speed results for this kind of technology, for a queue simulation as explained in Sec. 2.2 and for the Switzerland morning rush-hour (6-9 AM) scenario as explained in Sec. 5. The left plot shows the real time ratio (RTR), i.e. how much faster than reality the simulation runs. An RTR of 200, for example, means that 24 hours of traffic can be computed in less than ten minutes - for all of Switzerland! The right plot shows speed-up, i.e. how much faster than a single-CPU simulation the parallel simulation is. As one can see from the figure, real time ratio and speed-up are related by a simple vertical shift in the logarithmic plot. One also notices that with 64 CPUs a speed-up of about 27 can be reached.

A separate problem was encountered with the hybrid approach (2D space, see Sec. 2.3) for the pedestrian simulation. Large scale scenarios, such as an area of, say, $50 km \times 50 km$, result in several millions or even billions of cells, and even several GBytes of memory are not enough to allocate memory for all those cells. We therefore implemented a lazy initialization algorithm, where the memory for the cell is only allocated on request, i.e. when for the first time a pedestrian enters the cell. Also, when a cell has not been used for a certain number of time steps, the memory is freed up again. Fig. 8 shows a demonstration scenario, and the cells which are allocated at this point in the simulation. Since typically large parts of the region are rarely or never touched by pedestrians, this approach makes it possible to use the two-dimensional cell-based approach even for large scale scenarios.

On the level of the strategic decisions (route planning, activity generation), the typical technology is to write the traffic simulation results to a file-based database and then to base the agent adaptation on this information (Raney and Nagel, 2003). Since that approach is slow when used for large scale scenarios, we are currently implementing an approach where all relevant data is permanently kept in computer memory. This implies the interaction of even more computers, some of them now being responsible for the computation of the strategic/tactical decisions. Another advantage of this approach, besides its improved speed, is that it should now be straightforward to add within-trip replanning to the parallel simulation, i.e. that agents can also make strategic decisions while they are on the road and not just in between trips (see Fig. 4 for a visual sketch of this). Preliminary results indicate that the computing time for this module for the Switzerland scenario improves from about 45 minutes to about 10 minutes. - The combined result of these two approaches is that we can indeed run metropolitan scenarios with 10 million agents, including 50 learning iterations, over night.

Figure 7: RTR (left) and speed-up (right) for the Switzerland morning rush-hour scenario on single and dual CPU machines, using Ethernet or Myrinet.

Figure 8: Dynamic memory allocation for hybrid pedestrian simulation