PATH FINDING ALGORITHMS AND DATA STRUCTURES FOR POINT-TO-POINT TRIP MANAGEMENT

This report identifies and characterizes the data base and computer software requirements of a Point-to-Point Trip Management )PTPRM) System which provides detailed transit trip itineraries in response to inquiries made by prospective passengers. The requirements fall into four categories, corresponding to successive states in processing such as inquiry: (1) reception and interpretation; (2) location and connection; (3) path calculation; and (4) report. Procedures for path calculation are discussed in detail, including techniques for improving shortest path algorithm performance both through optimized computational schemes and through special methods of representing and manipulating the data base describing transit routes and schedules. Estimates, based on step-by-step schemes presented in an appendix, indicate that computation time will be sufficiently small (less than one second per request) that on-line path computation is feasible. Since path finding represents only a fraction of the total time spend in answering a request for itinerary, a queuing model is developed to establish how many formerly lost calls would be captured by a computerized system which achieved a prescribed fractional saving in service time; illustrative application of this model indicates a sharp reduction in lost calls.

• Supplemental Notes:
  • Sponsored by Urban Mass Transportation Administration.
• Corporate Authors:

  National Bureau of Standards

  14th Between E Street and Constitution Avenue, NW
  Washington, DC  United States  20234
• Authors:
  • GILSINN, J F
  • Saurdens, P B
  • Pearl, M H
• Publication Date: 1975-1

Media Info

• Pagination: 78 p.

Subject/Index Terms

• TRT Terms: Algorithms; Computers; Databases; Daylight; Estimates; Information systems; Management; Mathematical models; Reports; Routes; Software; Travel; Travel patterns
• Uncontrolled Terms: Interpretation; Models; Reporting; Trip
• Old TRIS Terms: Data systems; Inquiry; On line computers
• Subject Areas: Administration and Management; Economics; Highways; Planning and Forecasting; Society;

Filing Info

• Accession Number: 00158089
• Record Type: Publication
• Source Agency: Urban Mass Transportation Administration
• Report/Paper Numbers: UMTA-MD-06-0013-75-2
• Contract Numbers: DOT-AT-20018
• Files: TRIS, USDOT
• Created Date: Oct 13 1977 12:00AM