COMPARISON OF THE PERFORMANCE OF THREE ALGORITHMS FOR USE IN AN AUTOMATED TRANSIT INFORMATION SYSTEM (ATIS)

This paper compares the performance of three algorithms for computing trip itineraries for use in an automated transit information system. One of the approaches (TIMEXD) is based on a time-expanded network. The other two both compute paths in a bipartite route/stop network; one algorithm (LABCOR) is based on the label-correcting approach and the other (LABSET) on the label-setting approach. The transit networks upon which the performance comparison is based are of two types: a grid network with specified, possibly non-uniform, distances between streets, and a spider web type of network. TIMEXD is fastest on all the larger networks, but it requires most computer storage and outputs paths with more transfers. LABCOR is the slowest, but is guaranteed to produce the best routing, since it always outputs an optimal path with fewest transfers. Computation time estimates extrapolated to large transit networks indicate times of 1.5 to 2.5 seconds per itinerary for TIMEXD and LABSET respectively, well within the acceptable range for such networks.

  • Supplemental Notes:
    • Sponsored in part by Urban Mass Transportation Administration, Washington, D.C.
  • Corporate Authors:

    National Bureau of Standards

    Applied Mathematics Division
    Washington, DC  USA  20234

    Urban Mass Transportation Administration

    400 7th Street, SW
    Washington, DC  USA  20590
  • Authors:
    • GILSINN, J F
    • Leyendecker, E L
    • Shier, D R
  • Publication Date: 1978-3

Media Info

  • Pagination: 164 p.

Subject/Index Terms

Filing Info

  • Accession Number: 00180660
  • Record Type: Publication
  • Source Agency: National Technical Information Service
  • Report/Paper Numbers: NBSIR-78-1426 Final Rpt.
  • Files: NTIS, TRIS, USDOT
  • Created Date: Aug 19 1982 12:00AM