Finding optimal hyperpaths in large transit networks with realistic headway distributions

Qianfei Li, (Will) Chen, Peng and (Marco) Nie, Yu

European Journal of Operational Research, 2015, vol. 240, issue 1, 98-108

Abstract: 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 the exponential distribution. Accordingly, we propose to model headway using the Erlang distribution 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 a small number 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 and (2) the heuristic greedy method provides near optimal solutions in all tested cases.

Keywords: Hyperpath; Headway distribution; Greedy method; Enumeration; Erlang distribution (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221714005499
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:240:y:2015:i:1:p:98-108

DOI: 10.1016/j.ejor.2014.06.046

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().