توسعه شبکه حمل‌ونقل ریلی با استفاده از الگوریتم حریصانه مبتنی بر بیشترین تاثیر بر زمان سیر – مطالعه موردی: راه‌آهن ایران

نوع مقاله : علمی - پژوهشی

نویسندگان
1 استادیار، گروه مهندسی عمران، دانشکده فنی‌ومهندسی، دانشگاه مازندران، ایران
2 استادیار، دانشکده مهندسی راه‌آهن، دانشگاه علم و صنعت ایران، ایران
چکیده
مسئله طراحی شبکه راه‌آهن به نحوه تخصیص میزان محدودی بودجه برای توسعه زیرساخت شبکه ریلی می پردازد. از جمله هدف‌هایی که در این مسئله مورد استفاده قرار می‌گیرد می‌توان به کمینه سازی کل زمان سیر در شبکه، کمینه-سازی هزینه‌های توسعه، یا بیشینه سازی درآمد حاصله از انتقال بار اشاره کرد. با توجه به این که دو گروه تصمیم‌گیرنده در این مسئله تاثیر گذار هستند، شکل عمومی مساله طراحی شبکه یک مسئله دوسطحی خواهد بود که در رده مسائل NP-Hard قرار می‌گیرد که حل آن با استفاده از روش‌های دقیق بهینه سازی در مقیاس‌های حتی کوچک با دشواری روبروست. در این مقاله برای حل مسئله طراحی شبکه ریلی، یک الگوریتم تقریبی ابتکاری از نوع حریصانه ارایه می‌شود. در این الگوریتم تمرکز بر توسعه بلاک‌هایی از شبکه ریلی است که بیشترین اثر در کاهش متوسط زمان سیر در شبکه را دارد. روند اضافه کردن بلاک‌ها در شبکه آنقدر ادامه پیدا می‌کند که کل سطح تقاضای ورودی بتواند از شبکه انتقال پیداکند. این الگوریتم با زبان جاوا پیاده سازی شد و شبکه راه‌آهن ایران برای مطالعه موردی انتخاب شد. نتایج الگوریتم پیشنهادی تحلیل گردید. نتایج به دست آمده نشان می‌دهد که با توسعه شبکه تا سطح عبور تقاضای 57 میلیون تن، متوسط زمان سیر به کمترین مقدار خود می‌رسد و برای مقادیر تقاضای بیشتر، متوسط زمان سیر روند افزایشی خواهد داشت.

کلیدواژه‌ها


عنوان مقاله English

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

نویسندگان English

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
چکیده English

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.

کلیدواژه‌ها English

Network design
greedy algorithm
travel time
Railway of Iran
- 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.
 

  • تاریخ دریافت 27 شهریور 1401
  • تاریخ بازنگری 20 مهر 1401
  • تاریخ پذیرش 20 مهر 1401