HIGH PERFORMANCE COMPUTATION OF SHORTEST ROUTES FOR INTELLIGENT TRANSPORTATION SYSTEMS APPLICATIONS

The authors consider the computation of shortest routes in traffic networks within the context of intelligent transportation systems. Such information is usually a necessity for route guidance systems operating in real-time and also for traffic simulation packages. Basically, the problem can be stated as follows. Given the current travel times associated with link and turning movements, one wants to find the shortest routes from the start end of every link to all destinations. These will be used by drivers to choose alternative routes for the remaining parts of their trips. To be amenable to a real-time implementation, the shortest routes component must enjoy a sufficiently fast response time. Unfortunately, the current serial computers do not offer enough speed to tackle real-life, large-scale transportation networks. The advent of parallel computing platforms presents an opportunity to achieve reasonable delays for processing shortest routes. However, this requires a fundamental change in the way solution methods are designed and implemented. Algorithms must be adapted to take advantage not only of the structure of the problem but also to use adequately the architecture of parallel machines. In the paper, the basic parallel computing architectures are presented along with examples of commercially available parallel computers. The basic concepts of parallel programming are also introduced. The authors follow by presenting various implementations of shortest routes algorithms. These illustrate the methodologies of parallel programming. For instance, investigators show how Dijkstra's type algorithms can be implemented differently on distributed environments, shared memory multiprocessors, and distributed memory multiprocessors. Also demonstrated are the efficiencies of these approaches to solve large-scale traffic networks. The preliminary results indicate that parallel computers constitute a positive answer to fast response time issues. In particular, the following parallel machines have been investigated: a network of SUN stations operated throughout PVM, a SUN 1000 shared memory multiprocessor machine with multithreading features, and a network of 16 MEIKO Transputers serving as a dedicated distributed memory multiprocessors computer.

  • Supplemental Notes:
    • Five volumes of papers and one volume of abstracts comprise the published set of conference materials.
  • Corporate Authors:

    VERTIS

    TORANOMOM 34 MORI BUILDING 1-25-5
    TORANOMON, MINATOKU, TOKYO 105  Japan 
  • Authors:
    • Florian, M
    • Chabini, I
  • Conference:
  • Publication Date: 1995-11

Language

  • English

Media Info

  • Pagination: p. 2021

Subject/Index Terms

Filing Info

  • Accession Number: 00724446
  • Record Type: Publication
  • Report/Paper Numbers: Volume 4
  • Files: TRIS
  • Created Date: Aug 20 1996 12:00AM