A Bi-objective Stochastic Hub Location-Routing Model for the Railway Rapid Transit Network Design

Document Type : Research Paper

Authors

1 PhD Candidate of Industrial Engineering, Department of Industrial Engineering, Yazd University, Yazd, Iran

2 Associate Professor, Department of Industrial Engineering, Yazd University, Yazd, Iran

3 Professor, School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran

4 Professor, Department of Industrial Engineering, Yazd University, Yazd, Iran

Abstract

This study focuses on the development of a stochastic bi-objective hub location-routing model for a railway rapid transit network design problem. Due to the use of railway rapid transit systems in the hub-level sub-network (i.e., the network among the hub nodes) and the spoke-level sub-network (i.e., the network that connect spoke nodes to each other and to hub nodes), the decisions to make concern the location of hub nodes, spoke nodes, hub edges and spoke edges, and the determination of hub and spoke lines, the percentage of satisfied demands, and the way of routing the demands, simultaneously. Uncertainty is assumed for demands represented by a finite set of scenarios. The problem is formulated through a two-stage stochastic modeling framework. The aim is to maximize the total expected profit and to minimize the total expected service time. The performance of the model is evaluated through computational tests using the well-known AP dataset. The computational results confirm the importance of considering the stochastic model and the conflicting profit and time objectives for the given problem. Some managerial insights are also provided through the analysis of the resulting networks under various parameter settings and the investigation of the effect of these settings on the characteristics of the obtained solutions and the interactions among the different aspects of the studied complex decision problem

Keywords

Main Subjects


  • Ahmadi, T., Karimi, H., Davoudpour, H. and Hosseinijou, S. A., (2015). A robust decision-making approach for p-hub median location problems based on two-stage stochastic programming and mean-variance theory: a real case study, The International Journal of Advanced Manufacturing Technology, 77 (9): 1943-1953, doi: 10.1007/s00170-014-6569-x.
  • Gutiérrez-Jarpa, G., Obreque, C., Laporte, G. and Marianov, V., (2013). Rapid transit network design for optimal cost and origin–destination demand capture, Computers & Operations Research, 40 (12): 3000-3009, doi: https://doi.org/10.1016/j.cor.2013.06.013.
  • Gutiérrez-Jarpa, G., Laporte, G., Marianov, V. and Moccia, L., (2017). Multi-objective rapid transit network design with modal competition: The case of Concepción, Chile, Computers & Operations Research, 78: 27-43, doi: https://doi.org/10.1016/j.cor.2016.08.009.
  • Marín, Á. and García-Ródenas, R., (2009). Location of infrastructure in urban railway networks, Computers & Operations Research, 36 (5): 1461-1477, doi: https://doi.org/10.1016/j.cor.2008.02.008.
  • López-Ramos, F., Codina, E., Marín, Á. and Guarnaschelli, A., (2017). Integrated approach to network design and frequency setting problem in railway rapid transit systems, Computers & Operations Research, 80: 128-146, doi: https://doi.org/10.1016/j.cor.2016.12.006.
  • Shushan, C., Qinghuai, L. and Zhong, S., (2019). Design of Urban Rail Transit Network Constrained by Urban Road Network, Trips and Land-Use Characteristics, Sustainability, 11, doi: https://doi.org/10.3390/su11216128.
  • Canca, D., De-Los-Santos, A., Laporte, G. and Mesa, J. A., (2017). An adaptive neighborhood search metaheuristic for the integrated railway rapid transit network design and line planning problem, Computers & Operations Research, 78: 1-14, doi: https://doi.org/10.1016/j.cor.2016.08.008.
  • Canca, D., De-Los-Santos, A., Laporte, G. and Mesa, J. A., (2019). Integrated Railway Rapid Transit Network Design and Line Planning problem with maximum profit, Transportation Research Part E: Logistics and Transportation Review, 127: 1-30, doi: https://doi.org/10.1016/j.tre.2019.04.007.
  • Contreras, I. and O’Kelly, M., (2019). Hub Location Problems, In Location Science, edited by G. Laporte, S. Nickel, and F. Saldanha da Gama. Cham: Springer International Publishin, doi: 10.1007/978-3-030-32177-2_12.
  • Campbell, J. F., Ernst, A. T. and Krishnamoorthy, M., (2005). Hub Arc Location Problems: Part I—Introduction and Results, Management Science, 51 (10): 1540-1555, doi: 10.1287/mnsc.1050.0406.
  • Contreras, I., Tanash, M. and Vidyarthi, N., (2013). The cycle hub location problem, Technical Report CIRRELT 59.
  • Contreras, I., Fernández, and Marín, A., (2010). The Tree of Hubs Location Problem, European Journal of Operational Research, 202 (2): 390-400, doi: https://doi.org/10.1016/j.ejor.2009.05.044.
  • Labbé, M. and Yaman, H., 2008, Solving the hub location problem in a star–star network, Networks, 51 (1): 19-33, doi: https://doi.org/10.1002/net.20193.
  • Martins de Sá, E., Contreras, I., Cordeau, J.-F., de Camargo, R. S. and de Miranda, G., (2015). The Hub Line Location Problem, Transportation Science, 49 (3): 500-518, doi: 10.1287/trsc.2014.0576.
  • Martins de Sá, E., Contreras, I. and Cordeau, J.-F., (2015). Exact and heuristic algorithms for the design of hub networks with multiple lines, European Journal of Operational Research, 246 (1): 186-198, doi: https://doi.org/10.1016/j.ejor.2015.04.017.
  • Mahmutoğulları, A. İ. and Kara, B. Y., (2015). Hub Location Problem with Allowed Routing between Nonhub Nodes, Geographical Analysis, 47 (4): 410-430, doi: 10.1111/gean.12075.
  • Yaman, H., Kara, B. Y. and Tansel, B. Ç., (2007). The latest arrival hub location problem for cargo delivery systems with stopovers, Transportation Research Part B: Methodological, 41 (8): 906-919, doi: https://doi.org/10.1016/j.trb.2007.03.003.
  • Thomadsen, T. and Larsen, J., (2007). A hub location problem with fully interconnected backbone and access networks, Computers & Operations Research, 34 (8): 2520-2531, doi: https://doi.org/10.1016/j.cor.2005.09.018.
  • Kartal, Z., Hasgul, S. and Ernst, A. T., (2017). Single allocation p-hub median location and routing problem with simultaneous pick-up and delivery, Transportation Research Part E: Logistics and Transportation Review, 108: 141-159, doi: https://doi.org/10.1016/j.tre.2017.10.004.
  • Basirati, M., Akbari Jokar, M. R. and Hassannayebi, E., (2020). Bi-objective optimization approaches to many-to-many hub location routing with distance balancing and hard time window, Neural Computing and :Applications, 32 (17), 13267-13288, doi: 10.1007/s00521-019-04666-z.
  • Kemmar, O., Bouamrane, K. and Gelareh, S., (2021). Hub location problem in round-trip service applications, RAIRO-Oper. Res., 55: 2831-S2858. [Online]. Available: https://doi.org/10.1051/ro/2020125.
  • Tikani, H., Honarvar, M. and Mehrjerdi, Y. Z., (2018). Developing an integrated hub location and revenue management model considering multi-classes of customers in the airline industry, Computational and Applied Mathematics, 37 (3): 3334-3364, doi: 10.1007/s40314-017-0512-3.
  • Taherkhani, G. and Alumur, S. A., 2019, Profit maximizing hub location problems, Omega, 86: 1-15, doi: https://doi.org/10.1016/j.omega.2018.05.016.
  • Kaveh, F., Tavakkoli-Moghaddam, R., Triki, C., Rahimi, Y. and Jamili, A., (2021). A new bi-objective model of the urban public transportation hub network design under uncertainty, Annals of Operations Research, 296 (1): 131-162, doi: 10.1007/s10479-019-03430-9.
  • Oliveira, F. A., de Sá, E. M. and de Souza, S. R., (2022). Benders decomposition applied to profit maximizing hub location problem with incomplete hub network, Computers & Operations Research, 142, doi: https://doi.org/10.1016/j.cor.2022.105715.
  • Fallah-Tafti, M., Honarvar, M., Tavakkoli-Moghaddam, R. and Sadegheih, A., (2022). Mathematical modeling of a bi-objective hub location-routing problem for rapid transit networks, RAIRO-Oper. Res., 56 (5): 3733-3763. [Online]. Available: https://doi.org/10.1051/ro/2022170.
  • غفاری نسب، ن.، غضنفری، م. و تیموری، ا.، (۱۳۹۲). طراحی شبکه لجستیک هاب استوار با درنظر گرفتن تقاضاهای تصادفی برای شرکت‌های ارائه‌ دهنده خدمات لجستیکی، نشریه پژوهش‌های مهندسی صنایع در سیستم‌های تولید، 1 (2): ۱۰۷-۹۷. ]برخط[. در دسترس: https://ier.basu.ac.ir/article_681_4dbeb44595ef5e040966e14187201025.pdf.
  • Rahimi, Y., Torabi, S. A. and Tavakkoli-Moghaddam, R., (2019). A new robust-possibilistic reliable hub protection model with elastic demands and backup hubs under risk, Engineering Applications of Artificial Intelligence, 86: 68-82, doi: https://doi.org/10.1016/j.engappai.2019.08.019.
  • عیدی، ع. و برزگر, خ.، (۱۳۹۴). ارائه یک الگوریتم حل دقیق برای مسأله جایابی p هاب میانه با تخصیصی r-تایی، نشریه پژوهش‌های مهندسی صنایع در سیستم‌های تولید، 3 (5): ۷۱-۶۱. ]برخط[. در دسترس: https://ier.basu.ac.ir/article_1176_9765f80ebbc8d02cf4f0a5ff2aef4a67.pdf.
  • حسینی، س. م. ح.، حسنی، ع. ا. و اسدیان، م.، (۱۳۹۶). مدل‌سازی و حل مسأله مکان‌یابی هاب سلسله مراتبی چندوسیله‌ای با درنظر گرفتن محدودیت ظرفیت هاب‌ها، نشریه پژوهش‌های مهندسی صنایع در سیستم‌های تولید، 5 (10): ۱۵-۱، doi: 10.22084/ier.2017.12211.1560.
  • Verma, A., Kumari, A., Tahlyan, D. and Hosapujari, A. B., (2017). Development of hub and spoke model for improving operational efficiency of bus transit network of Bangalore city, Case Studies on Transport Policy, 5 (1): 71-79, doi: https://doi.org/10.1016/j.cstp.2016.12.003.
  • Huang, D., Liu, Z., Fu, X. and Blythe, P. T., (2018). Multimodal transit network design in a hub-and-spoke network framework, Transportmetrica A: Transport Science, 14 (8): 706-735, doi: 10.1080/23249935.2018.1428234.
  • Chen, K., Xin, X., Zhang, T. and Yang, Z., (2020). Multiport cooperative location model with a safe-corridors setting in West Africa, International Journal of Logistics Research and Applications, 23 (6): 580-601, doi: 10.1080/13675567.2019.1708873.
  • Gelareh, S. and Nickel, S., (2011). Hub location problems in transportation networks, Transportation Research Part E: Logistics and Transportation Review, 47 (6): 1092-1111, doi: https://doi.org/10.1016/j.tre.2011.04.009.
  • Fallah-Tafti, M., Honarvar, M., Tavakkoli-Moghaddam, R. and Sadegheih, A., (2022). Developing a capacitated hub location-routing model for the rapid transit network design under uncertainty, Iranian Journal of Operations Research, 13 (1), 103-122.
  • Ernst, A. T. and Krishnamoorthy, M., (1996). Efficient algorithms for the uncapacitated single allocation p-hub median problem, Location Science, 4 (3): 139-154, doi: https://doi.org/10.1016/S0966-8349(96)00011-3.

Birge, J. and FV, L., (2011). Introduction to stochastic programming. New York, Dordrecht, Heidelberg, London: Springer, doi: 10.1007/978-1-4614-0237-4_2.