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  United States  20234

  Urban Mass Transportation Administration

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

Media Info

• Pagination: 164 p.

Subject/Index Terms

• TRT Terms: Algorithms; Alternatives analysis; Automated vehicle control; Information systems; Needs assessment; Networks; Public transit; Rapid transit; Routing; Urban transportation
• Uncontrolled Terms: User needs
• Old TRIS Terms: Automated transit system; Rapid transit railways
• Subject Areas: Highways; Operations and Traffic Management; Planning and Forecasting; Public Transportation;

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