This paper presents a least cost hyperpath algorithm that captures the complexities that arise in a transit network because of the number of transfers, the standing and overcrowding penalties, the availability of walking and biking in addition to the transit modes, and the mode-specific limitations such as availability of bike parking. The problem was formulated as a mathematical program, and then a hybrid label setting–correcting algorithm was proposed as a solution. The multi-modal time- and approach-dependent algorithm does not require spatial or temporal expansion of the network; this feature results in good computational performance for large-scale applications. Scenario runs performed on the large-scale Chicago Transit Authority network, in Illinois, validate the accuracy and performance of the algorithm.
Get full access to this article
View all access options for this article.
References
1.
DijkstraE. W.A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, Vol. 1, No. 1, 1959, pp. 269–271.
2.
AhujaR. K., MagnantiT. L., and OrlinJ. B.Network Flows: Theory, Algorithms, and Applications, Prentice Hall, Englewood Cliffs, N.J., 1993.
3.
CookeK. L., and HalseyE.The Shortest Route Through a Network with Time-Dependent Intermodal Transit Times. Journal of Mathematical Analysis and Applications, Vol. 14, No. 3, 1966, pp. 493–498.
4.
BellmanR.On a Routing Problem. Quarterly of Applied Mathematics, Vol. 16, 1958, pp. 87–90.
5.
MooreE.The Shortest Path Through a Maze. In Proceedings of the International Symposium on the Theory of Switching, Part 2, The Annals of the Computation Laboratory of Harvard University, Vol. 30, Harvard University Press, Cambridge, Mass., 1957.
6.
GloverF., KlingmanD., and PhilipsN.A New Polynomially Bounded Shortest Path Algorithm. Operations Research, Vol. 33, No. 1, 1985, pp. 65–73.
7.
ZiliaskopoulosA. K., MandanasF. D., and MahmassaniH. S.An Extension of Labeling Techniques for Finding Shortest Path Trees. European Journal of Operational Research, Vol. 198, No. 1, 2009, pp. 63–72.
8.
ZiliaskopoulosA. K., and WardellW.An Intermodal Optimum Path Algorithm for Multimodal Networks with Dynamic Arc Travel Times and Switching Delays. European Journal of Operational Research, Vol. 125, No. 3, 2000, pp. 486–502.
9.
ZiliaskopoulosA. K.Optimal Path Algorithms on Multi-Dimensional Networks: Analysis, Design, Implementation and Computational Experience. PhD dissertation. University of Texas at Austin, 1994.
10.
MahmassaniH. S., and AbdelghanyK. F.Dynasmart-IP: Dynamic Traffic Assignment Meso-Simulator for Intermodal Networks. In Advanced Modeling for Transit Operations and Service Planning (LamW. H. K., and BellM. G. H., eds.), Pergamon Press, Oxford, United Kingdom, 2003.
11.
AbdelghanyK. F., and MahmassaniH. S.Dynamic Trip Assignment-Simulation Model for Intermodal Transportation Networks. In Transportation Research Record: Journal of the Transportation Research Board, No. 1771, TRB, National Research Council, Washington, D.C., 2001, pp. 52–60.
12.
ChriquiC., and RobillardP.Common Bus Lines. Transportation Science, Vol. 9, No. 2, 1975, pp. 115–121.
13.
NguyenS., and PallottinoS.Equilibrium Traffic Assignment for Large Scale Transit Networks. European Journal of Operational Research, Vol. 37, No. 2, 1988, pp. 176–186.
14.
NguyenS., and PallottinoS.Hyperpaths and Shortest Hyperpaths. Combinatorial Optimization, Lecture Notes in Mathematics, Vol. 1403, 1989, pp. 258–271.
15.
SpiessH., and FlorianM.Optimal Strategies: A New Transit Assignment Model for Transit Networks. Transportation Research Part B, Vol. 23, No. 2, 1989, pp. 83–102.
16.
De CeaJ., and FernandezE.Transit Assignment for Congested Public Transport Systems: An Equilibrium Model. Transportation Science, Vol. 27, No. 2, 1993, pp. 133–147.
17.
CominettiR., and CorreaJ.Common-Lines and Passenger Assignment in Congested Transit Networks. Transportation Science, Vol. 35, No. 3, 2001, pp. 250–267.
18.
SchmockerJ. D., BellM. G. H., and KurauchiF.A Quasi-Dynamic Capacity Constrained Frequency-Based Transit Assignment Model. Transportation Research Part B, Vol. 42, No. 10, 2008, pp. 925–945.
19.
SchmockerJ. D., FonzoneA., ShimamotoH., KurauchiF., and BellM. G. H.Frequency-Based Transit Assignment Considering Seat Capacities. Transportation Research Part B, Vol. 45, No. 2, 2011, pp. 392–408.
20.
LiQ., ChanP. W., and NieY. M.Finding Optimal Hyperpaths in Large Transit Networks with Realistic Headway Distributions. European Journal of Operational Research, Vol. 240, No. 1, 2015, pp. 98–108.
21.
NielsenL. R., AndersenK. A., and PretolaniD.Bicriterion Shortest Hyperpaths in Random Time-Dependent Networks. IMA Journal of Management Mathematics, Vol. 14, No. 3, 2003, pp. 271–303.
22.
NielsenL. R., AndersenK. A., and PretolaniD.Finding the K Shortest Hyperpaths. Computers and Operations Research, Vol. 32, No. 6, 2005, pp. 1477–1497.
23.
NohH.Capacitated Schedule-Based Transit Assignment Using a Capacity Penalty Cost. PhD dissertation. Department of Civil Engineering, University of Arizona, Tucson, 2013.
24.
HamdouchY., and LawphongpanichS.Schedule-Based Transit Assignment Model with Travel Strategies and Capacity Constraints. Transportation Research Part B, Vol. 42, No. 7-8, 2008, pp. 663–684.
25.
HamdouchY., and LawphongpanichS.Congestion Pricing for Schedule-Based Transit Networks. Transportation Science, Vol. 44, No. 3, 2010, pp. 350–366.
26.
HamdouchY., HoH. W., SumaleeA., and WangG.Schedule-Based Transit Assignment Model with Vehicle Capacity and Seat Availability. Transportation Research Part B, Vol. 45, No. 10, 2011, pp. 1805–1830.
27.
NohH., HickmanM., and KhaniA.Hyperpaths in Network Based on Transit Schedules. In Transportation Research Record: Journal of the Transportation Research Board, No. 2284, Transportation Research Board of the National Academies, Washington, D.C., 2012, pp. 29–39.
28.
Verbasİ. Ö., and MahmassaniH. S.Optimal Allocation of Service Frequencies over Transit Network Routes and Time Periods: Formulation, Solution, and Implementation Using Bus Route Patterns. In Transportation Research Record: Journal of the Transportation Research Board, No. 2334, Transportation Research Board of the National Academies, Washington, D.C., 2013, pp. 50–59.
Verbasİ. Ö., MahmassaniH. S., and HylandM. F.Dynamic Assignment-Simulation Methodology for Multimodal Urban Transit Networks. In Transportation Research Record: Journal of the Transportation Research Board, No. 2498, Transportation Research Board, Washington, D.C., 2015, pp. 64–74.
31.
Verbasİ. Ö., and MahmassaniH. S.Integrated Frequency Allocation and User Assignment in Multimodal Transit Networks: Methodology and Application to Large-Scale Urban Systems. In Transportation Research Record: Journal of the Transportation Research Board, No. 2498, Transportation Research Board, Washington, D.C., 2015, pp. 37–45.
