Simultaneous Bus Transit Route Network and Frequency Setting Search Algorithm
Publication: Journal of Transportation Engineering, Part A: Systems
Volume 145, Issue 4
Abstract
A simultaneous bus route network design and frequency setting model is formulated as the weighted sum multiobjective genetic algorithm optimization. It aims to search for a near-optimum set of routes and corresponding frequencies while minimizing both user and operator costs. It is a nondeterministic polynomial time complete optimization problem, and searching the entire space through metaheuristic algorithms is impractical. It does require narrowing down the search space into some feasible regions. In this paper, two strategies are implemented, offering a distinct advantage in the finding of near-optimum solutions. First, a set of constraints are imposed on resources defined through experience and route generation and filtration algorithms are implemented to increase the quality of the candidate solution pool. Second, in order to increase the probability of selecting better performing set of routes and reducing genetic algorithm’s degree of randomness, a specially designed transfer minimization operator is implemented within the optimization procedure. Results are then compared on the basis of Mandl’s network that has been used as the benchmark by various researchers. Further, the sensitivity of the model to different rules and parameters is carried out. Obtained solutions perform better as compared to the previous techniques.
Get full access to this article
View all available purchase options and get full access to this article.
References
Agrawal, J., and T. V. Mathew. 2004. “Transit route network design using parallel genetic algorithm.” J. Comput. Civ. Eng. 18 (3): 248. https://doi.org/10.1061/(ASCE)0887-3801(2004)18:3(248).
Alt, B., and U. Weidmann. 2011. “A stochastic multiple area approach for public transport network design.” Public Transp. 3 (1): 65–87. https://doi.org/10.1007/s12469-011-0042-0.
Amiripour, S. M. M., A. S. Mohaymany, and A. Ceder. 2015. “Optimal modification of urban bus network routes using a genetic algorithm.” J. Transp. Eng. 141 (3): 04014081. https://doi.org/10.1061/(ASCE)TE.1943-5436.0000741.
Arbex, R. O., and C. B. da Cunha. 2015. “Efficient transit network design and frequencies setting multi-objective optimization by alternating objective genetic algorithm.” Transp. Res. Part B: Methodol. 81 (2): 355–376. https://doi.org/10.1016/j.trb.2015.06.014.
Baaj, M. H., and H. S. Mahmassani. 1991. “An AI-based approach for transit route system planning and design.” J. Adv. Transp. 25 (2): 187–209. https://doi.org/10.1002/atr.5670250205.
Baaj, M. H., and H. S. Mahmassani. 1995. “Hybrid route generation heuristic algorithm for the design of transit networks.” Transp. Res. Part C: Emerging Technol. 3 (1): 31–50. https://doi.org/10.1016/0968-090X(94)00011-S.
Belegundu, A. D., and T. R. Chandrupatla. 2011. “Optimization concepts and applications in engineering.” New York: Cambridge University Press.
Bielli, M., M. Caramia, and P. Carotenuto. 2002. “Genetic algorithms in bus network optimization.” Transp. Res. Part C: Emerging Technol. 10 (1): 19–34. https://doi.org/10.1016/S0968-090X(00)00048-6.
Blum, C., and A. Roli. 2003. “Metaheuristics in combinatorial optimization: Overview and conceptual comparison.” Comput. Surv. 35 (3): 268–308. https://doi.org/10.1145/937503.937505.
Blum, J. J., and T. V. Mathew. 2011. “Intelligent agent optimization of urban bus transit system design.” J. Comput. Civ. Eng. 25 (5): 357–369. https://doi.org/10.1061/(ASCE)CP.1943-5487.0000095.
Carrese, S., and S. Gori. 2002. “An urban bus network design procedure transportation planning.” Vol. 64 of Applied optimization, 177–195. New York: Springer.
Ceder, A. 1987. “Methods for creating bus timetables.” Transp. Res. Part A: General 21 (1): 59–83. https://doi.org/10.1016/0191-2607(87)90024-0.
Ceder, A. 2016. Public transit planning and operation: Modeling, practice and behavior. Boca Raton, FL: CRC Press.
Ceder, A., and Y. Israeli. 1998. “User and operator perspectives in transit network design.” Transp. Res. Rec. 1623 (1): 3–7. https://doi.org/10.3141/1623-01.
Ceder, A., and N. H. Wilson. 1986. “Bus network design.” Transp. Res. Part B: Methodol. 20 (4): 331–344. https://doi.org/10.1016/0191-2615(86)90047-0.
Chakroborty, P. 2003. “Genetic algorithms for optimal urban transit network design.” Comput.-Aided Civ. Infrastruct. Eng. 18 (3): 184–200. https://doi.org/10.1111/1467-8667.00309.
Chakroborty, P., K. Deb, and P. S. Subrahmanyam. 1995. “Optimal scheduling of urban transit systems using genetic algorithms.” J. Transp. Eng. 121 (6): 544–553. https://doi.org/10.1061/(ASCE)0733-947X(1995)121:6(544).
Chakroborty, P., and T. Dwivedi. 2002. “Optimal route network design for transit systems using genetic algorithms.” Eng. Optim. 34 (1): 83–100. https://doi.org/10.1080/03052150210909.
Chien, S. I. J., B. V. Dimitrijevic, and L. N. Spasovic. 2003. “Optimization of bus route planning in urban commuter networks.” J. Public Transp. 6 (1): 53–79. https://doi.org/10.5038/2375-0901.6.1.4.
Chien, S. I. J., Z. Yang, and E. Hou. 2001. “Genetic algorithm approach for transit route planning and design.” J. Transp. Eng. 127 (3): 200–207. https://doi.org/10.1061/(ASCE)0733-947X(2001)127:3(200).
Chriqui, C., and P. Robillard. 1975. “Common bus lines.” Transp. Sci. 9 (2): 115–121. https://doi.org/10.1287/trsc.9.2.115.
Chua, T. A. 1984. “The planning of urban bus routes and frequencies: A survey.” Transportation 12 (2): 147–172. https://doi.org/10.1007/BF00167373.
Ciaffi, F., E. Cipriani, and M. Petrelli. 2012. “Feeder bus network design problem: A new metaheuristic procedure and real size applications.” Procedia: Social Behav. Sci. 54 (4): 798–807. https://doi.org/10.1016/j.sbspro.2012.09.796.
Cipriani, E., S. Gori, and M. Petrelli. 2012. “Transit network design: A procedure and an application to a large urban area.” Transp. Res. Part C: Emerging Technol. 20 (1): 3–14. https://doi.org/10.1016/j.trc.2010.09.003.
Deb, K. 1998. Optimization for engineering design: Algorithms and examples. New Delhi, India: Prentice-Hall.
Deng, L. B., W. Gao, W. L. Zhou, and T. Z. Lai. 2013. “Optimal design of feeder-bus network related to urban rail line based on transfer system.” Procedia: Social Behav. Sci. 96 (6): 2383–2394. https://doi.org/10.1016/j.sbspro.2013.08.267.
Desaulniers, G., and M. D. Hickman. 2007. “Public transit.” Chap. 2 in Handbooks in operations research and management science, 69–127. London: Elsevier.
Dijkstra, E. W. 1959. “A note on two problems in connexion with graphs.” Numerische Mathematik 1 (1): 269–271. https://doi.org/10.1007/BF01386390.
Dubois, D., G. Bel, and M. Llibre. 1979. “A set of methods in transportation network synthesis and analysis.” J. Oper. Res. Soc. 30 (9): 797–808. https://doi.org/10.1057/jors.1979.190.
Euchi, J., and R. Mraihi. 2012. “The urban bus routing problem in the Tunisian case by the hybrid artificial ant colony algorithm.” Swarm Evol. Comput. 2 (1): 15–24. https://doi.org/10.1016/j.swevo.2011.10.002.
Fan, L., and C. L. Mumford. 2010. “A metaheuristic approach to the urban transit routing problem.” J. Heuristics 16 (3): 353–372. https://doi.org/10.1007/s10732-008-9089-8.
Fan, W., and R. B. Machemehl. 2004. Optimal transit route network design problem: Algorithms, implementations, and numerical results. College Station, TX: Southwest University Transportation Center, Univ. Texas at Austin, Center for Transportation Research.
Fan, W., and R. B. Machemehl. 2006. “Optimal transit route network design problem with variable transit demand: Genetic algorithm approach.” J. Transp. Eng. 132 (1): 40–51. https://doi.org/10.1061/(ASCE)0733-947X(2006)132:1(40).
Fan, W., and R. B. Machemehl. 2008. “Tabu search strategies for the public transportation network optimizations with variable transit demand.” Comput.-Aided Civ. Infrastruct. Eng. 23 (7): 502–520. https://doi.org/10.1111/j.1467-8667.2008.00556.x.
Farahani, R. Z., E. Miandoabchi, W. Y. Szeto, and H. Rashidi. 2013. “A review of urban transportation network design problems.” Eur. J. Oper. Res. 229 (2): 281–302. https://doi.org/10.1016/j.ejor.2013.01.001.
Goldberg, D. E. 1989. Genetic algorithms in search, optimization and machine learning. 1st ed. Boston: Addison-Wesley Longman.
Guihaire, V., and J. K. Hao. 2008. “Transit network design and scheduling: A global review.” Transp. Res. Part A: Policy Pract. 42 (10): 1251–1273. https://doi.org/10.1016/j.tra.2008.03.011.
Han, A. F., and N. H. M. Wilson. 1982. “The allocation of buses in heavily utilized networks with overlapping routes.” Transp. Res. Part B: Methodol. 16 (3): 221–232. https://doi.org/10.1016/0191-2615(82)90025-X.
Jiang, Y., W. Szeto, and T. Ng. 2013. “Transit network design: A hybrid enhanced artificial bee colony approach and a case study.” Int. J. Transp. Sci. Technol. 2 (3): 243–260. https://doi.org/10.1260/2046-0430.2.3.243.
Jie, Z., H. Lu, and L. Fan. 2010. “The multi-objective optimization algorithm to a simple model of urban transit routing problem.” In Vol. 6 of Proc., 6th Int. Conf. on Natural Computation, 2812–2815. New York: IEEE.
Johar, A., S. S. Jain, and P. K. Garg. 2016. “Transit network design and scheduling using genetic algorithm: A review.” Int. J. Opt. Control: Theories Appl. 6 (1): 9–22. https://doi.org/10.11121/ijocta.01.2016.00258.
Kalaga, R. R., R. N. Datta, and K. S. Reddy. 2001. “Allocation of buses on interdependent regional bus transit routes.” J. Transp. Eng. 127 (3): 208–214. https://doi.org/10.1061/(ASCE)0733-947X(2001)127:3(208).
Kechagiopoulos, P. N., and G. N. Beligiannis. 2014. “Solving the urban transit routing problem using a particle swarm optimization based algorithm.” Appl. Soft Comput. 21 (1): 654–676. https://doi.org/10.1016/j.asoc.2014.04.005.
Kepaptsoglou, K., and M. Karlaftis. 2009. “Transit route network design problem: Review.” J. Transp. Eng. 135 (8): 491–505. https://doi.org/10.1061/(ASCE)0733-947X(2009)135:8(491).
Kidwai, F. A. 1998. Optimal design of bus transit network: A genetic algorithm-based approach. Kanpur, India: Indian Institute of Technology Kanpur.
Lampkin, W., and P. D. Saalmans. 1967. “The design of routes, service frequencies, and schedules for a municipal bus undertaking: A case study.” J. Oper. Res. Soc. 18 (4): 375–397. https://doi.org/10.1057/jors.1967.70.
Lang, F., C. L. Mumford, and D. Evans. 2009. “A simple multi-objective optimization algorithm for the urban transit routing problem.” In Proc., IEEE Congress on Evolutionary Computation (CEC’09), 1–7. New York: IEEE.
Lobo, F. G., and D. E. Goldberg. 2004. “The parameter-less genetic algorithm in practice.” Inf. Sci. 167 (1): 217. https://doi.org/10.1016/j.ins.2003.03.029.
Mandl, C. E. 1980. “Evaluation and optimization of urban public transportation networks.” Eur. J. Oper. Res. 5 (6): 396–404. https://doi.org/10.1016/0377-2217(80)90126-5.
Marguier, P. H. J., and A. Ceder. 1984. “Passenger waiting strategies for overlapping bus routes.” Transp. Sci. 18 (3): 207–230. https://doi.org/10.1287/trsc.18.3.207.
Mauttone, A., and M. E. Urquhart. 2009. “A route set construction algorithm for the transit network design problem.” Comput. Oper. Res. 36 (8): 2440–2449. https://doi.org/10.1016/j.cor.2008.09.014.
Miandoabchi, E., R. Z. Farahani, W. Dullaert, and W. Y. Szeto. 2011. “Hybrid evolutionary metaheuristics for concurrent multi-objective design of urban road and public transit networks.” Networks Spatial Econ. 12 (3): 441–480. https://doi.org/10.1007/s11067-011-9163-x.
Nayeem, M. A., M. K. Rahman, and M. S. Rahman. 2014. “Transit network design by genetic algorithm with elitism.” Transp. Res. Part C: Emerging Technol. 46 (1): 30–45. https://doi.org/10.1016/j.trc.2014.05.002.
Nikolic, M., and D. Teodorovic. 2013. “Transit network design by bee colony optimization.” Expert Syst. Appl. 40 (15): 5945–5955. https://doi.org/10.1016/j.eswa.2013.05.002.
Pattnaik, S. B., S. Mohan, and V. M. Tom. 1998. “Urban bus transit route network design using genetic algorithm.” J. Transp. Eng. 124 (4): 368–375. https://doi.org/10.1061/(ASCE)0733-947X(1998)124:4(368).
Poorzahedy, H., and F. Safari. 2011. “An ant system application to the bus network design problem: An algorithm and a case study.” Public Transp. 3 (2): 165–187. https://doi.org/10.1007/s12469-011-0046-9.
Ruisanchez, F., L. dell’Olio, and A. Ibeas. 2012. “Design of a tabu search algorithm for assigning optimal bus sizes and frequencies in urban transport services.” J. Adv. Transp. 46 (4): 366–377. https://doi.org/10.1002/atr.1195.
Santos, L., J. Coutinho-Rodrigues, and J. R. Current. 2007. “An improved solution algorithm for the constrained shortest path problem.” Transp. Res. Part B: Methodol. 41 (7): 756–771. https://doi.org/10.1016/j.trb.2006.12.001.
Shih, M. C., H. Mahmassani, and M. Baaj. 1998. “Planning and design model for transit route networks with coordinated operations.” Transp. Res. Rec. 1623 (1): 16–23. https://doi.org/10.3141/1623-03.
Shimamoto, H., N. Murayama, A. Fujiwara, and J. Zhang. 2010. “Evaluation of an existing bus network using a transit network optimisation model: A case study of the Hiroshima city bus network.” Transportation 37 (5): 801–823. https://doi.org/10.1007/s11116-010-9297-6.
Silman, L. A., Z. Barzily, and U. Passy. 1974. Planning the route system for urban buses. Haifa, Israel: Faculty of Industrial and Management Engineering, Technion–Israel Institute of Technology.
Spiess, H., and M. A. Florian. 1989. “Optimal strategies: A new assignment model for transit networks.” Transp. Res. Part B: Methodol. 23 (2): 83–102. https://doi.org/10.1016/0191-2615(89)90034-9.
Szeto, W. Y., and Y. Wu. 2011. “A simultaneous bus route design and frequency setting problem for Tin Shui Wai, Hong Kong.” Eur. J. Oper. Res. 209 (2): 141–155. https://doi.org/10.1016/j.ejor.2010.08.020.
Tarajo, B. A., and L. S. Lee. 2016. “Urban transit network design problems: A review of population-based metaheuristics.” Pertanika J. Scholarly Res. Rev. 2 (1), 86–99
Tom, V. M., and S. Mohan. 2003. “Transit route network design using frequency coded genetic algorithm.” J. Transp. Eng. 129 (2): 186–195. https://doi.org/10.1061/(ASCE)0733-947X(2003)129:2(186).
Wang, J. Y., and C. M. Lin. 2010. “Mass transit route network design using genetic algorithm.” J. Chin. Inst. Eng. 33 (2): 301–315. https://doi.org/10.1080/02533839.2010.9671619.
Yadan, Y., Z. Liu, Q. Meng, and Y. Jiang. 2013. “Robust optimization model of bus transit network design with stochastic travel time.” J. Transp. Eng. 139 (6): 625–634. https://doi.org/10.1061/(ASCE)TE.1943-5436.0000536.
Yang, Z., B. Yu, and C. Cheng. 2007. “A parallel ant colony algorithm for bus network optimization.” Comput.-Aided Civ. Infrastruct. Eng. 22 (1): 44–55. https://doi.org/10.1111/j.1467-8667.2006.00469.x.
Yen, J. Y. 1971. “Finding the shortest loopless paths in a network.” Manage. Sci. 17 (11): 712–716. https://doi.org/10.1287/mnsc.17.11.712.
Zhao, F., and X. Zeng. 2008. “Optimization of transit route network, vehicle headways and timetables for large-scale transit networks.” Eur. J. Oper. Res. 186 (2): 841–855. https://doi.org/10.1016/j.ejor.2007.02.005.
Zhao, H., W. A. Xu, and R. Jiang. 2015. “The memetic algorithm for the optimization of urban transit network.” Expert Syst. Appl. 42 (7): 3760–3773. https://doi.org/10.1016/j.eswa.2014.11.056.
Zhou, Y., J. C. Thill, and Z. Huang. 2011. “Design of a user-centric decision support tool for fixed-route bus travel planning.” Appl. Geogr. 31 (3): 1173–1184. https://doi.org/10.1016/j.apgeog.2011.03.005.
Zhu, Z., X. Guo, J. Zeng, and S. Zhang. 2017. “Route design model of feeder bus service for urban rail transit stations.” Math. Prob. Eng. 2017 (1): 6. https://doi.org/10.1155/2017/1090457.
Information & Authors
Information
Published In
Journal of Transportation Engineering, Part A: Systems
Volume 145 • Issue 4 • April 2019
Copyright
©2019 American Society of Civil Engineers.
History
Received: Dec 3, 2015
Accepted: Sep 28, 2018
Published online: Feb 15, 2019
Published in print: Apr 1, 2019
Discussion open until: Jul 15, 2019
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.