Finding Optimal Hyperpaths in Large Transit Networks with Realistic Headway Distributions

This paper implements and tests a label-setting algorithm for finding optimal hyperpaths in large transit networks with realistic headway distributions. It has been commonly assumed in the literature that headway is exponentially distributed. To validate this assumption, the empirical headway data archived by Chicago Transit Agency are fitted into various probabilistic distributions. The results suggest that the headway data fit much better with Loglogistic, Gamma and Erlang distributions than with exponential distributions. Accordingly, the authors propose to model headway using Erlang distributions in the proposed algorithm, because it best balances realism and tractability. When headway is not exponentially distributed, finding optimal hyperpaths may require enumerating all possible line combinations at each transfer stop, which is tractable only for very small numbers of alternative lines. To overcome this difficulty, a greedy method is implemented as a heuristic and compared to the brute-force enumeration method. The proposed algorithm is tested on a large scale CTA bus network that has over 10,000 stops. The results show that (1) the assumption of exponentially distributed headway may lead to sub-optimal route choices; (2) the heuristic greedy method provides optimal solutions in all tested cases.

• Supplemental Notes:
  • This paper was sponsored by TRB committee ADB30(9) Paper Reveiw Group #5.
• Corporate Authors:

  Transportation Research Board

  500 Fifth Street, NW
  Washington, DC  United States  20001
• Authors:
  • Li, Qianfei
  • Chen, Peng
  • Nie, Yu (Marco)
• Conference:
  • Transportation Research Board 93rd Annual Meeting
  • Location: Washington DC
  • Date: 2014-1-12 to 2014-1-16
• Date: 2014

Language

• English

Media Info

• Media Type: Digital/other
• Features: Figures; References; Tables;
• Pagination: 18p
• Monograph Title: TRB 93rd Annual Meeting Compendium of Papers

Subject/Index Terms

• TRT Terms: Algorithms; Bus transit; Headways; Networks; Public transit; Route choice; Traffic distribution; Traffic flow
• Uncontrolled Terms: Erlang distribution (Traffic flow); Greedy algorithms; Hyperpaths
• Geographic Terms: Chicago (Illinois)
• Subject Areas: Operations and Traffic Management; Planning and Forecasting; Public Transportation; I70: Traffic and Transport;

Filing Info

• Accession Number: 01519769
• Record Type: Publication
• Report/Paper Numbers: 14-2230
• Files: TRIS, TRB, ATRI
• Created Date: Mar 26 2014 10:11AM