Parallel & Supercomputing

TB29.1 Performance Study of Parallel Shortest Path Algorithms Michelle R. Hribar, Valerie Taylor, David E. Boyce --- Northwestern Univ., 2145 Sheridan Rd., ECE Dept., Evanston, IL 60208-3118, (michelle@ece.nwu.edu)

The performance of parallel labeling shortest path algorithms is¨ affected by both the algorithm choice and the network decomposition.¨ We identify factors of the decomposition which determine the¨ performance of the different algorithms. We use these factors to¨ identify good decompositions and to predict the best algorithm for a¨ given decomposition.

TB29.2 Parallel Computation of Shortest Paths for Transportation Applications Ismail Chabini, Michael Florian, Eric Le Saux, Nicolas Tremblay --- MIT, Dept. of Civil & Environ. Eng., 77 Mass. Ave., Rm. 1-263, Cambridge, MA 02139 , (chabini@mit.edu)

We present several parallel computing implementations of static and¨ time dependent shortest path algorithms for use in network¨ equilibrium models and mesoscopic traffic simulations. The computing¨ platforms used are distributed SUN SPARC Ultra 1 workstations and a¨ SUN SPARC Center 1000 shared memory machine.

TB29.3 Parallel Computing Approaches for Real-Time Fleet Management Michel Gendreau --- Univ. de Montreal, CRT/DIRO, CP 6128, Succ. Centre-ville, Montreal, Quebec, H3C 3J7 , Canada (michelg@crt.umontreal.ca)

Situations where vehicles must be dispatched in real-time to satisfy¨ service requests over some territory are numerous and quite varied:¨ ambulance dispatching, pick-up and delivery operations, etc. We¨ discuss 2 parallel computing approaches which may be used to¨ implement in real-time sophisticated heuristic procedures for¨ managing large fleets.

TB29.4 Parallel Computation of Dynamic Elastic & Fixed Demand Traffic Network Problems Anna Nagurney, Ding Zhang --- Univ. of MA, Sch. of Mgmt., Dept. of Finance & Op. Mgmt., Amherst, MA 01003 , (nagurney@gbfin.umass.edu)

We present algorithms for the solution of dynamic traffic network¨ problems modeled as projected dynamical systems. We provide¨ convergence results as well as numerical results for the¨ implementations on the Thinking Machines' CM-5 architecture.