Rail Transportation Network Design using Greedy Algorithm Based on Maximum Impact on Travel Time - Case Study: Railway of Iran

Document Type : Scientific - Research

Authors
Amirali Zarrinmehr 1
Reza Mohammad Hasany 2
1 Civil Engineering Group, Department of Engineering and Technology, University of Mazandaran, Babolsar, Iran
2 Faculty of Railway engineering, Iran University of Science and Technology, Tehran, Iran
10.22119/jte.2022.362463.2622
Abstract
The railway network design problem deals with how to allocate a limited budget for the development of the railway network infrastructure. Among the objectives used in this problem, we can mention the minimization of the total travel time in the network, the minimization of the development costs, or the maximization of the income. Considering that the two groups of decision-makers are influential in this problem, the general form of the network design problem will be a Bi-level problem that belongs to the category of NP-Hard problems, which cannot be solved using precise optimization methods in even small scales. In this article, an innovative approximate greedy algorithm is presented to solve the problem of rail network design. In this algorithm, the focus is on developing blocks of the rail network that have the greatest effect in reducing the average travel time in the network. The process of adding blocks in the network continues until the entire level of incoming demand can be transferred from the network. This algorithm was implemented with Java language and railway of Iran has been selected as a case study. The results show that with the development of the network up to the demand of 57 million tons, the average travel time will reach its lowest value; and for the higher demand values, the average travel time will increase.

Keywords

- Aashtiani, H. Z., and Magnanti, T. L. (1981) “Equilibria on a congested transportation network”, SIAM Journal on Algebraic Discrete Methods, Vol. 2, No. 3, pp 213-226.
 
- Afandi Zadeh, S., Ghafari, A., and Kalantari, N. (2011), "Demand Box Uncertainty Evaluation in Discrete and ContinuousTransportation Network Design with Genetic and Ant Colony Algorithms", Journal of Transportation Engineering, Vol. 2, No. 3, pp. 205-221(in Persian).
 
- Ahuja, R. K., Möhring, R. H., and Zaroliagis, C. D. (2009) “Robust and online large-scale optimization: models and techniques for transportation systems”, Springer.
 
- Amini, B., Esrafili, H. (2013), “Developing Travel Time-volume Functions for Two-way Two-lane Rural Highways in Iran”, Journal of Transportation Engineering, Vol. 4, No. 2, pp. 103-117(in Persian).
 
- Barahimi, A. H., Eydi, A., and Aghaie, A. (2021), ”Multi-modal urban transit network design considering reliability: multi-objective bi-level optimization”,  Reliability Engineering & System Safety, Vol. 216.
 
- Barros, L. A., Tanta, M., Martins, A. P., Afonso, J. L., and Pinto, J. (2020) “Opportunities and challenges of power electronics systems in future railway electrification”, Paper presented at the 2020 IEEE 14th International Conference on Compatibility, Power Electronics and Power Engineering.
 
- Boyce, D., Ralevic-Dekic, B., and Bar-Gera, H. (2004) “Convergence of traffic assignments: how much is enough?”, Journal of Transportation Engineering, Vol. 130, No. 1, pp 49-55.
 
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2022) “Introduction to algorithms”, MIT press.
 
- Cullinane, K., and Toy, N. (2000) “Identifying influential attributes in freight route/mode choice decisions: a content analysis”, Transportation Research Part E: Logistics and Transportation Review, Vol. 36, No. 1, pp 41-53.
 
- Fatemi, E. (2002) “Lane tracking, a new technique to reduce headway and increase travel capacity”, The Seven International of Railway Engineering.
 
- Hasany, R. M., and Shafahi, Y. (2018) “Modeling formulation and a new heuristic for the railroad blocking problem”, Applied Mathematical Modelling, Vol. 56, pp304-324.
 
- Hickish, B., Fletcher, D. I., and Harrison, R. F. (2022) “A methodology to optimise a rail network specification for maximum passenger satisfaction and reduced initial investment”, Journal of Rail Transport Planning & Management, Vol. 21.
 
- Hu, X., Zhou, S., Chen, T., and Ghiasi, M. (2021) “Optimal energy management of a DC power traction system in an urban electric railway network with dogleg method”, Energy Sources, Part A: Recovery, Utilization, and Environmental Effects, pp 1-23.
 
- Johansson, E., Camporeale, R., and Palmqvist, C.-W. (2020) ” Railway network design and regional labour markets in Sweden”, Research in Transportation Economics, Vol. 83.
 
- Kuby, M., Xu, Z., and Xie, X. (2001). Railway network design with multiple project stages and time sequencing”, Journal of Geographical Systems, Vol. 3, No. 1, pp 25-47.
 
- Iran Ministry of Roads & Urban Development, (2017), “Management report of the consulting project on the analysis of cargo transportation demand and capacity of the main axes of the country's railway network ”(in Persian).
 
- Lee, Y.-J., and Vuchic, V. R. (2005) “Transit network design with variable demand”, Journal of Transportation Engineering, Vol. 131, No. 1, pp 1-10.
 
- Lin, B., Liu, C., Wang, H., and Lin, R. (2017) “Modeling the railway network design problem: A novel approach to considering carbon emissions reduction”, Transportation Research Part D: Transport and Environment, Vol. 56, pp 95-109.
 
- Long, J., Gao, Z., Zhang, H., and Szeto, W. Y. (2010), “A turning restriction design problem in urban road networks”, European Journal of Operational Research, Vol. 206, No. 3, pp 569-578.
 
- Mathew, T. V., & Sharma, S. (2009) “Capacity expansion problem for large urban transportation networks”, Journal of Transportation Engineering, Vol. 135, No. 7, pp 406-415.
 
- Mesbah, M., Sarvi, M., and Currie, G. (2008), “New methodology for optimizing transit priority at the network level”, Transportation Research Record, Vol. 2089, No. 1, pp 93-100.
 
- Najy, W., and Diabat, A. (2020), “Benders decomposition for multiple-allocation hub-and-spoke network design with economies of scale and node congestion”, Transportation Research Part B: Methodological, Vol. 133, pp 62-84.
 
- Nie, Y. (2012), “A note on Bar-Gera's algorithm for the origin-based traffic assignment problem”, Transportation Science, Vol. 46, No. 1, pp 27-38.
- The official website of Railway of Iran, www.rai.ir.
 
- Poorzahedy, H., and Abulghasemi, F. (2005), Application of ant system to network design problem. Transportation, Vol. 32, No. 3, pp 251-273.
 
- Rosell, F., and Codina, E. (2020), “A model that assesses proposals for infrastructure improvement and capacity expansion on a mixed railway network”, Transportation Research Procedia, Vol. 47, pp 441-448.
 
- Seyedabrishami, E., Khanzad, I., Zarinmehr, A., and Mamdouhi, A. (2017), "A Heuristic Method for Public Transportation Network Design using Route - Generation Algorithm", Journal of Transportation Engineering, Vol. 8, No. 4, pp. 643-654(in Persian).
 
- Seyedvakili, S. A., Nasr Azadani, S. M., Zakeri, J. A., Shafahi, Y., and Karimi, M. (2018), “New model for the railway network design problem”, Journal of Transportation Engineering, Part A: Systems, Vol. 144, No. 11.
 
- Seyedvakili, S. A., Zakeri, J.-A., Azadani, S. N., and Shafahi, Y. (2020), “Long-term railway network planning using a multiperiod network design model”, Journal of Transportation Engineering, Part A: Systems, Vol. 146, No. 1.
 
- Sheffi, Y. (1985), “Urban transportation networks”: Prentice-Hall, Englewood Cliffs, New Jersey.
 
- Xin, X., Wang, X., Ma, L., Chen, K., and Ye, M. (2022), “Shipping network design–infrastructure investment joint optimization model: a case study of West Africa”, Maritime Policy & Management, Vol. 49, No. 5, pp 620-646.
 
- Xiong, Y., & Schneider, J. B. (1992). Transportation network design using a cumulative genetic algorithm and neural network. Transportation Research Record (1364).
 
- Yu, T., & Ma, J. (2016), “A review of the link traffic time estimation of urban traffic”, IEEE International Conference on Intelligent Transportation Engineering.
 
- Yaghini, M., Yamani, N., Tamaniee, M. (2011), “A Methodology for Assessing the Increasing Capacity Methods Using an Optimization Approach with a Case Study on Badrood- Ardakan Route”, Journal of Transportation Engineering, Vol. 3, No. 2, pp. 159-173(in Persian).
 
- Zarrinmehr, A. (2015), “Parallelization of Ant Colony Algorithm in Transportation Discrete Network Design”, Modares Civil Engineering journal, Vol. 15, No. 2, pp 37-50.
 
- Zarrinmehr, A., Aashtiani, H. Z., Nie, Y., and Azizian, H. (2019), “Complementarity Formulation and Solution Algorithm for Auto-Transit Assignment Problem”, Transportation Research Record, Vol. 2673, No. 4, pp 384-397.
 
- Zarrinmehr, A., and Moulouk Zadeh, H. (2022), “Transit Routes Network Design by Greedy Prioritization of the Routes in Grid Networks”, Journal of Transportation Research (in Persian).
 
- Zarrinmehr, A., Saffarzadeh, M., and Seyedabrishami, S. (2018), “A local search algorithm for finding optimal transit routes configuration with elastic demand”, International Transactions in Operational Research, Vol. 25, No. 5, pp 1491-1514.
 
- Zarrinmehr, A., Saffarzadeh, M., Seyedabrishami, S., and Nie, Y. M. (2016), “A path-based greedy algorithm for multi-objective transit routes design with elastic demand”, Public Transport, Vol. 8, No. 2, pp 261-293.
 
- Zarrinmehr, A., & Shafahi, Y. (2016), “Parallelization of the Branch-and-Bound Algorithm in Transportation Discrete Network Design”, Scientia Iranica, Vol. 23, No. 2, pp 407-419.
 
- Zhang, Y., Luo, X., Han, X., Lu, Y., Wei, J., & Yu, C. (2022), “Optimization of Urban Waste Transportation Route Based on Genetic Algorithm, Security and Communication Networks.
 
Quarterly Journal of Transportation Engineering
Volume 15, Issue 3 - Serial Number 60
Winter 2024
Pages 3767-3783

  • Receive Date 18 September 2022
  • Revise Date 12 October 2022
  • Accept Date 12 October 2022