Parallel traffic equilibrium applications

Traffic engineers solve for traffic equilibria to perform analyses of traffic flow on a network. Equilibrium analyses are used for planning road systems and predicting the effects of changing existing roads. Solving for traffic equilibria is computationally and memory intensive; hence, they are good applications for parallel processing. The major component of execution time for the traffic equilibrium problem is the solution of multiple-source shortest paths. Labeling algorithms are the best approach for sparse traffic networks. This thesis provides four contributions in the area of serial and parallel shortest paths and parallel traffic equilibrium algorithms: (1) Derivation of a parameter to predict poor performance of serial shortest path algorithms. The performance of some serial shortest path labeling algorithms is difficult to predict. The parameter which predicts poor performance provides a better guideline for the selection of an algorithm than generalizations based on prior research. (2) Analysis of the computation step of parallel shortest path algorithms. The best parallel shortest path algorithm is often different than the best serial algorithm for a particular network. We identify three factors which influence the performance of the parallel shortest path algorithms. (3) Development of four methods for the termination detection step of parallel shortest path algorithms for the reduction of idle time. We develop four methods for detecting termination in the parallel shortest path algorithm. An adaptive approach is best for large sub-networks and a small number of processors, but a synchronized approach is best for small subnetworks and large number of processors. (4) Determination of ideal characteristics of the network decomposition using statistical analysis. We identify five network characteristics of a good decomposition through an extensive statistical analysis. The most interesting characteristic of a good decomposition is that the number of boundary nodes per interface is large; this result is the opposite of ideal decompositions for other scientific applications.