This page contains the introduction and the summary of my dissertation. A PDF version is available here.
Over the last decades, the world economy has constantly grown resulting in a continuously increasing demand for transportation. This is true for both goods and people. Mobility, as a sign of independence, is commonly regarded as one of the most important factors of the quality of life. In 1995, there were 40.4 million vehicles registered in Germany which corresponds to one vehicle for every other citizen. It is not surprising that traffic has become an important factor in our daily lives.
Lately, however, we have been experiencing more and more of the downside of vehicular traffic. As street networks have not been extended at such a pace as the demand for transportation, the occurrence of traffic jams has become a major problem in densely populated areas. The resulting delay has direct and indirect consequences:
Time spent on the road can generally not be used for productive work. People who have to travel professionally lose part of their income through traffic jams. Also, there is an indirect economic effect: being confined to a car in a traffic jam is a stressful situation which reduces the ability to work efficiently once the work place has been reached.
Vehicles stalled in traffic jams use additional fuel. This is not only another cost factor to drivers, but also causes damage to the environment through pollution.
Recurrent congestion largely restricts the independence of drivers. Instead of adjusting trips to activities, drivers have started to plan their activities carefully in order to avoid congestion.
Since the construction of new streets is either financially not affordable or politically unsupportable (This is especially true for European countries). it has become more and more important to use the existing network more efficiently. There are three different time-scales at which one can influence the efficiency:
Long term considerations (over years) refer to the construction of new infrastructure. Here, it is important to decide where to add the infrastructure to obtain the best overall benefit.
On smaller time-scales like days or weeks, one can try to analyze the impact of temporary measures such as road constructions or road blocks. Moreover, sudden, non-recurrent peaks of the demand structure can be investigated: additional traffic caused by simultaneous cultural events (i.e. concerts or sports events).
The lower end of the time-scale is dominated by decisions made just before or during a trip. So-called Advanced Traffic Management/Information Systems (ATMS/ATIS) analyze the current traffic situation and give advice to drivers on how to avoid traffic jams.
In all cases, traffic simulation has proven to be an important tool to model and analyze the traffic state. In this thesis, we will concentrate on different aspects of traffic simulation on modern computer architectures.
In Chapter 2 we will describe models handling traffic on a single multi-lane street segment. The Cellular Automaton (CA) model for traffic flow on a link developed by Nagel and Schreckenberg will serve as a starting point. The CA rule-set will be extended to allow for multi-lane traffic to capture lane-changes. We will present results obtained from simulations of traffic on loops with periodic boundary conditions.
In Chapter 3 the CA multi-lane traffic segment will be used as one of the building blocks of the micro-simulation PAMINA for traffic in street networks. We will also present the structure of other components, such as highway junctions and city intersections. As a first test we will use a route-set consisting of individual routes generated for the TRANSIMS case-study to drive the simulation. Traffic lights and speed-limits will serve as switches to influence the fidelity of the simulation. We will investigate the phenomenon of grid-locks and how they are influenced by the choice of fidelity.
PAMINA will be used in Chapter 4 to iteratively adapt route-sets from a given initial route-set based upon an origin-destination matrix. The link travel-times generated by the micro-simulation will serve as feedback to improve the dynamic performance estimate for each individual link. We will see that the speed of the relaxation process can be monitored effectively by inspecting the overall travel time of all vehicles in the simulation area (called study-area). We will identify parameters that accelerate the relaxation process without having an impact on the final state. Two artifacts which occurred during some iterations and their remedies will be pointed out. The chapter will be concluded by a comparison of three micro-simulations processing route-sets for the same study-area.
In Chapter 5 the previously generated route-sets will be used to conduct an experiment of online routing. During a simulation run a certain fraction of all drivers will be allowed to access online information. If a driver forecasts an increased trip time due to an impending congestion, a shortest path algorithm computes a sufficiently good alternative route. The main issues of this chapter will be the questions, (a) how much the quality of the re-routing process will depend on the market saturation of the online service, and (b) how much impact (both positive and negative) the system will have on drivers who do not have access to the re-routing service.
The computational aspects of traffic simulation will be the main issue of Chapter 6. Based upon simple parameters which can be obtained from the street network and the underlying hardware, an upper bound for the parallel efficiency will be derived. Also, this chapter we will present benchmark results of the PAMINA micro-simulation both for dynamic load-balancing and static load-balancing with external load feedback.
In Chapter 7 we will summarize the work presented in this thesis and discuss the results obtained from the simulation runs. Whenever applicable, we will give suggestions as to how the micro-simulation can be improved in future experiments.
There are two appendices. The first appendix deals with the technical implementation of the PAMINA micro-simulation. The second one contains details related to traffic simulation and the iterative process used in Chapter 4.
In this work we have presented different aspects of modern traffic simulation. Starting with the simulation of traffic on a single link, we extended the model to include network traffic. The simulation PAMINA was used to create self-consistent route-sets which finally served as basis for the online re-routing experiments.
The traffic on a simulated two-lane road exhibits new characteristics compared to the simple single-lane model. As in real-world traffic, the passing of vehicles is a major component of driving dynamics. Chapter 2 contained a rule extension with three parameters defining a basic lane changing process. The symmetric version treats left-to-right and right-to-left changes equally. The asymmetric version favors the right lane over the left lane, which mimics driving guidelines on highways in many countries. Fundamental diagrams of the flow-density relationship are similar to those found in real-world traffic. We also showed that the artifact of ping-pong lane-changes could be significantly reduced by introducing an additional lane-changing probability.
The look-back parameter was found to be essential for the continuity of traffic flow. Reducing the parameter from the usual sites to zero destroyed the laminar flow, especially in the asymmetric case. In real-world traffic, egoistic lane-changing maneuvers increase the risk of accidents considerably. Therefore, though the cellular automaton does not model traffic accidents explicitly, the amount of flow disruption can be taken as a measure how safe a modeled traffic state is.
In Chapter 3 the two-lane model was used as a basis for the micro-simulation PAMINA. By combining simple network elements to composite structures, we were able to model both highway networks (or Autobahn networks, respectively) and city traffic. The complete Autobahn network of Germany with 75,000 kilometers of road-way was used for a feasibility test. The initial design included a feature that became more and more important in later versions: the execution of individual route-plans. Initially, however, the route-plans were chosen at random.
The first tests of PAMINA using route plans were done in the context of the TRANSIMS Dallas/Fort Worth case-study. Both the network and the plan-set were preliminary at that point: The network did not include any local streets; and the plansets were unbalanced in the sense that drivers did not attempt to avoid congestion.
A first series of runs investigated the influence of different levels of fidelity. We defined the fidelity of the micro-simulation by activating/deactivating speed-limits and/or traffic lights. We measured the impact of these parameters by comparing the actual travel-times of the vehicles to those which were estimated by the route-planner. We found that running the simulation with activated speed-limits and deactivated traffic lights yielded the best similarity. While we did not expect the micro-simulation to reproduce expected travel times in these runs, the comparison was useful to see if, in general, the microsimulation generated faster or slower travel times than the planner; and, which fidelity level of the micro-simulation changed this, and to what degree.
During the simulation of the study-area we also encountered the phenomenon of grid-locks. These configurations, occurring at high densities, consisted of vehicles that permanently prevented each other from proceding. They were due to the fact that vehicles, so far, were not able to modify their routes. The frequency of grid-locks depended on the fidelity of the simulation: without speed-limits and without traffic-lights the simulation never grid-locked. The same was true for activated speed-limits. Activating traffic-lights had a stronger impact on the dynamics: the system grid-locked independent from the use of speed-limits. This emphasizes the phenomenon that in city-networks performance is mainly defined by throughput at intersections. Reducing the speed-limit on links has a small effect since at medium and high densities the average velocity is comparable to the speed-limit anyway.
We introduced an additional parameter for adjusting the red-phase of the traffic-lights. By varying the parameter between 0 and 1 we could continuously move the fidelity from one, without traffic-lights, to one, with fully active traffic-lights. At we noticed a transition: below , no run developed a grid-lock. Above all runs grid-locked. For the runs within the interval, the grid-locking depended on the stochasticity of the simulation.
Up to this point, the route-sets used for PAMINA originated from
TRANSIMS. In Chapter 4 we chose a more
consistent setting: both the micro-simulation and its feedback were
obtained from the same micro-simulation PAMINA. Due to the high
execution speed of PAMINA and additional improvements of the data
exchange between router and route-converter it was possible to reduce
the run-time considerably. Compared to TRANSIMS which required about
8.5 hours for one iteration of
micro-simulation — route-converter — planner,
PAMINA could process the computation in
about 35-45 minutes. This allowed us to run extensive experiments for
route adaption with micro-simulation feedback. We defined three simple
parameters that were expected to have an influence on the relaxation
of iterative process: the initial route-set, the selection scheme for
routes to be re-planned, and the re-planning fraction.
In our experiments, none of the
parameters actually had a strong impact on the final
results. The independence from the initial route-set was found to be
especially advantageous, since otherwise special
care would have to be taken to start the iteration from a good
route-set. We found, however, that the computational speed of the
relaxation could largely be reduced by using a linear-age (In
this case, the probability of a route to be re-planned increases
linearly with its age, which is the number of iterations since its
last re-planning). approach for
selection. The accumulated re-planning fraction (The
accumulated re-planning fraction corresponds to the sum of all
individual re-planning fractions used up to a given iteration).
should be at least two to allow for sufficiently stable
results, which were measured by contemplating the overall travel-time
of all vehicles during the simulation period. For a future experiment
it will be interesting to conduct at least one run with an
accumulative re-planning to see if the
relaxation has really terminated and to determine the final
sum-travel-time.
We discovered two artifacts in the iteration process. First, the number of vehicles that were fed as input into the micro-simulation decreased by about 10%, because the planner re-planned more and more routes avoiding the study-area due to its highly increased link travel-times. By introducing a level-0 correction factor for all links outside the simulation area it was possible to reverse this effect to a certain extent. In a linear correction run the number of plans was reduced by only 5%, in another one with correction the reduction was about 7.5%. This dependency gives rise to the assumption that a factor of with i.e. can be used to arbitrarily adjust the number of vehicles inside the study-area. It also became obvious that the level-0 correction should only be applied after the iteration has been successfully relaxed. That way, one could avoid the disadvantageous loss of vehicles outside the time-window which occurred during early stages of the level-0 correction iteration.
The second artifact we observed was that up to 10,000 vehicles (Compared to approximately 15,000 vehicles in the study-area during rush hour). had queued up at the boundaries of the study-area by the end of the simulation period. This effect was caused by insufficient feedback about waiting time on feeder links to the planner. We used a correction in which the average waiting time for entering a link was added to the travel-time on the link itself. The results were promising: after an accumulated re-planning fraction , none of the iteration runs using the correction had any vehicles waiting in queues at the end of the simulation period.
Although route-sets could be assumed to be well relaxed after sufficiently large accumulated re-planning fractions (), the values for sum travel-time and the number of vehicles in the study-area still exhibited fluctuations between subsequent iterations. For a future experiment, it will be interesting to compare the amplitude of these fluctuations to the corresponding fluctuations of the link hit-rates which can be computed from the travel-time estimates provided by the planner. Such a comparison will provide insight into how many vehicles are expected to be on a link, provided that the link travel-times were not disturbed stochastically. As a preparation, this data has already been collected for most iteration runs.
We continued by conducting a comparison between three micro-simulations working on the same test-bed. The TRANSIMS micro-simulation, PAMINA, and the low-fidelity simulation SCAM were used to produce their own self-consistent route-sets. The results for the sum travel-time and the number of vehicles matched qualitatively, but there were quantitative differences. SCAM yielded results below those of PAMINA. This could easily be attributed to the fact that SCAM simulates the whole Dallas - Forth Worth area instead of the study-area only. Traffic jams outside the area that cannot occur in PAMINA or TRANSIMS give rise to a lower number of vehicles inside the area. The curves of the TRANSIMS runs were equivalent for small accumulation re-planning fractions (). During the iteration () the PAMINA curves eventually dropped below TRANSIMS curves. From this we can assume that the TRANSIMS route-set was still not sufficiently relaxed. In future comparisons one should see to it that only well-relaxed route-sets are used.
So far the comparisons concentrated on values that had been aggregated in both space and time. In order to investigate more detailed differences between the micro-simulations, we also considered less aggregated data. First, we looked at the time-dependent travel-speed into the study-area for both PAMINA and TRANSIMS. As before, the curves showed a qualitative similarity: starting from high traveling speeds during early morning hours, the speed drops to a minimum during the rush hour. Afterwards, they recover again. The absolute variation of the average speeds, however, is larger for PAMINA than it is for TRANSIMS. At a first glance, this may be surprising since the TRANSIMS runs have a smaller average vehicle density in the study-area during rush-hour and the speed limits are computed the same way. In the future the PAMINA runs may have to be repeated using the same deceleration probability for the CA rule set as TRANSIMS. Originally, had been selected which reduces the ability to accelerate fast. At medium and high densities, lower have a direct impact on the sustained throughput.
This effect also raises the question of how to generally define the speed-limit for the simulation links. Due to the granularity of CA velocity the limit can only be adjusted in steps of approximately 24 [km/h]. Using the deceleration probability to fine-tune the maximum speed of CA also changes its behavior at low velocities.
In a second experiment we compared the turn counts for a selected number of intersections inside the study-area. The similarity between the TRANSIMS run and PAMINA are satisfactory. In general, the counts are lower for PAMINA due to the lower vehicle density in the study-area for TRANSIMS. Both simulations, however, show considerable differences compared to actual traffic counts provided by the NCTCOG. Probable reasons follow. First, the O-D matrix which served as input for the activity list (year 1990) did not match the street network (year 1996) that was used for the simulation. Changes of the infrastructure can be expected to result in equivalent changes in the O-D matrix. Second, both simulations consider insufficient penalty for making turns at intersections. A more realistic representation for the inconvenience of turns should reduce the excess number of counts compared to reality. This will be part of future work. All in all, it must be noted that the approaches described in this thesis yielded some of the first simulation results ever, that were realistic enough to be compared to real-world data.
In Chapter 5 we used PAMINA with the previously computed route-sets to conduct an investigation of online re-routing. We assumed that the fleet of drivers can be split into two separate groups: those who have access to an online route guidance system, and those without access. The fraction of drivers with access is called market saturation, the drivers themselves are subscribers, all others are non-subscribers.
A typical run was done as follows. At a constant update interval, all subscribers tried to estimate their remaining travel-time. Subscribers were allowed to use the current link-travel times of all links of remaining portion of their route-plan up to a certain planning horizon. If the current estimate was worse (by a certain fraction) than the original estimate provided by the router, a new route was computed using a standard shortest path Dijkstra algorithm limited to the planning horizon. If the new route was sufficiently better than the current route the driver accepted the new one. This was called a re-routing event.
The first experiment was done using a route-set with an accumulated re-planning fraction of . The street conditions were not changed with respect to the one that the route-set is based on. The results are summarized as follows:
During rush hour about half of all subscribers regularly try to obtain a new estimate. Half of those receive a new (potentially better) route.
Upon arrival at their destination, subscribers have a (up to 28%) lower average travel-time than if they had not been re-routed. The advantage decreases with increasing market saturation: With a saturation of 50% the gain diminishes to about 6%. This effect is disadvantageous to the providers of the re-routing service. On the one hand one would like to reach high market penetration in order to use any installed hardware more cost-effectively. On the other hand, it is reasonable to assume that the incentive to buy a guidance system (or to subscribe to a service) will increase with the potential benefit.
The quality of the re-routing process improves when a vehicle is re-routed more than once. Quality was measured by comparing the actual arrival time of a subscriber to another run in which the route guidance system had been switched off. This suggests how re-routing schemes may have to work: upon receiving a new route the driver starts into the general direction of prescribed by the suggestion. Subsequent requests will refine the route as the driver proceeds through the network.
Up to a market saturation of 40%, re-routing has a beneficial effect on both subscribers and non-subscribers. This was determined by looking at the number of executed routes (overall throughput through the study-area) and the overall average travel-time. For a market saturation of 40% the reduction of average travel-time was about 6%. For higher saturation the situation has an overall negative effect: although in principle some runs showed an improvement, in general the variance of travel-times is much larger. Re-routing at high market saturation in undisturbed networks makes the system more unstable.
Increasing the update-interval has a small negative effect. This is quite intuitive, since the shortest path search is based upon the current condition of the links and not on a projection of the future condition. Increasing the update interval also widens this gap.
We re-ran the experiment with exactly the same parameters but used a route-set with . As mentioned before, route-sets of later iterations used the traffic network more efficiently. Presumably, online re-routing is less likely to produce better routes in a more relaxed network. The results support this assumption: (a) the advantage of subscribers over non-subscribers diminishes by a factor of five; and (b), there is no overall benefit for all drivers for small market saturation but, as before, a larger variance for higher saturation.
The question is now: how well relaxed is a real-world traffic system? If it resembles the case , it will be very difficult to profit from the re-planning scheme presented here. Some improvement may be brought about by trying to extrapolate the travel-time on links for future times. This could be done by referring to data bases of standard traffic configurations forecast by the micro-simulation for the planning area, such as the day of the week or weather conditions. This approach, however, must be handled with care since it will be difficult to reproduce the startint point of a forecast as an evolution of a given route-set.
In the last experiments we tried to investigate a more realistic traffic configuration by looking at non-recurring congestion. We disturbed one link between 8:00am and 9:00am by reducing its maximum speed given in CA units from the usual 4 to 1[site/sec]. In reality this may have been caused by a traffic accident or a road construction. The important factor is that * none of the drivers knew* of this obstruction beforehand. Therefore, there was no way that the external router could have adapted to the situation. Simulation results show that the reduced throughput on one link already reduces the overall throughput noticeably by about 8%. A modest re-routing alleviates the problem but, as before, increasingly high market saturations worsened the situation.
We then increased the number of disturbed links from one to ten for the same time interval. This time the system had considerably lower throughput for market saturations up to 20%. Above that, online planning improved the throughput considerably. Even for higher market saturations, the positive trend continues. We obtain increasingly lower average travel-times up to a market saturation of 90%. In this respect, the heavily disturbed traffic system significantly differs from all other cases above. It could be argued that ten simultaneous disturbances are unrealistic for such a small area. However, even if reality lies somewhere between one and ten disturbances, we show that, within the current framework, the amount of non-recurrent congestion appears to be a key prerequisite for the success of an intelligent route guidance system in terms of throughput. Possible benefits for drivers not familiar with the area and the congestion structure have not been investigated. In fact, all drivers in the simulation correspond to experienced drivers.
In the last chapter we shifted the focus to the computational aspects of traffic simulation. The implementation of PAMINA is based upon a domain decomposition of the street network. By looking at simple map parameters (i.e. the number of intersections and links) and hardware parameters (i.e. communication bandwidth and latency) we were able to derive an upper limit for the theoretical parallel efficiency. It turns out that on a bus communication network, which is implemented in many of today’s shared memory computers, the simulation reaches high efficiencies for medium-sized computers (less than 64 CPUs). Further improvement can only be achieved on computers that use a two-dimensional communication grid or similar scalable communication structures.
The next step in optimizing the iterative adaptive process described in Chapter 4 will be to integrate the components route-planner, route-converter, and micro-simulation into a compatible parallelization scheme. So far, both the route-planner and the route-converter are only available in a sequential version and the data exchange between route-converter and micro-simulation is still strictly serialized. Moreover, the micro-simulation will have to be adapted to link with parallelized versions of emission evaluation models and, ultimately, climate simulations models.
The Appendix A contains a description of the Parallel Toolbox which was used for the parallelization with a domain decomposition approach and PVM as message library. The first implementation was run on a 16-CPU SGI Power-Challenge, but the approach also permitted the port to a workstation-cluster of 12 SUN Sparc5 which yielded approximately the same performance. It was the first time that a traffic network of the size of the German Autobahn network could be simulated in real-time. The toolbox also handles the dynamic load-balancing and allows the dynamic insertion and deletion of CPUs during the run-time of the simulation.
It should be noted that in spite of increasingly more powerful computers, traffic simulation still requires a huge amount of computation time. For the results of Chapters 4 and 5 alone we needed about 630 hours of parallel execution on 6 CPUs and 130 hours of sequential execution on one CPU. If the simulation had not been parallelized, the overall sequential execution time on one CPU with 250 [MHz] would have amounted to 3900 hours. This is equivalent to about 5.5 months of continuous computation.