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  USA  20234
  • Authors:
    • GILSINN, J F
    • Saurdens, P B
    • Pearl, M H
  • Publication Date: 1975-1

Media Info

  • Pagination: 78 p.

Subject/Index Terms

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