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

نوع مقاله : پژوهشی اصیل (کامل)

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

در این مقاله برای حل مسئله طراحی شبکه یک الگوریتم حریصانه ارایه می شود که سعی در کاهش هرچه بیشتر هزینه های توسعه شبکه دارد. الگوریتم با این هدف طراحی شده است که اولویت توسعه شبکه را به بلاک های با کمترین هزینه توسعه می دهد و این روند تا جایی پیش می رود که کل سطح تقاضای ورودی بتواند از شبکه انتقال پیداکند. این الگوریتم با زبان جاوا پیاده سازی شد و شبکه راه آهن ایران به عنوان مطالعه موردی استفاده شد. با توجه به ماهیت دو هدفی در مسئله، تقاضای عبوری و توسعه در شبکه، جواب های "شبه پاریتو" با درصد های متفاوت از اهمیت این دو هدف مورد بحث و بررسی قرار گرفت و نتایج الگوریتم پیشنهادی تحلیل گردید.

کلیدواژه‌ها

موضوعات

عنوان مقاله English

The Greedy Algorithm for Development of The Network Based on the Lowest Developing Cost: The Case Study of Iran

نویسندگان English

A. Zarrinmehr 1
R. Mohammad Hasany 2
1 Assistant Professor, School of Civil Engineering, University of Mazandaran
2 Assistant Professor, School of Railway Engineering, Iran University of Science and Technology
چکیده English

Transportation issues are categorized into three strategic, tactical, and operational levels, each of which has a different level of influence, required budget, decision makers, and time period. The issue of developing the rail transportation network is one of the key issues at the strategic level. In short, network design deals with the solution of allocating a limited budget to a feasible subset of the set of projects, in such a way that specific goals: such as minimizing the total travel time in the network, the developing costs of the network, maximizing revenue from freight transportation, or maximizing the attraction of freight demand to the rail mode should be taken into account. In this issue, two stakeholders are considered. On one side, the operators make the macro decisions to meet the criteria; such as maximization of benefit, maximization of travel coverage, minimization of development costs, minimization of casualties and minimization of total travel time. On the other side users who try to maximize their benefits such as finding the shortest route through the network.

The general form of the network design problem is a two-level problem in the category of NP-hard problems, which is difficult to solve in even small scales. To solve this problem, the solution algorithms are classified into two general categories: exact and approximate. The exact solution algorithm give the best global solution among the possible solutions, they are so-called intractable in terms of memory usage and solution time with the increase in the size of the problem. Therefore, the second category of so-called approximate algorithms was presented to solve network design problem. Greedy algorithms are classified in the category of approximate algorithms. In the greedy algorithm, reaching the goal in each step is independent of the previous step. That is, at each step to reach the solution, regardless of what choices was made in the previous stages.

In this article, the greedy algorithm is presented to solve the problem of network design trying to reduce network development costs. The proposed algorithm is designed to develop the blocks with priority of the lowest cost, and this process continues until the entire level of incoming demand can be transferred through the network. This algorithm is implemented with Java language and the railway of Iran is used as a case study. Considering the nature of two objectives in the problem, freight demand passing through and development cost in the network, "pseudo-pareto" solutions with different percentages of the importance of two mentioned objectives are discussed. The analysis has shown that with the increasing importance of the development cost, fewer blocks are developed and as a result, less demand is passed through the network. Also, with the increasing importance of freight demand, the algorithm leads to solutions that have caused extensive development in the network. The proposed greedy algorithm has a light computational load, and it achieves its solutions in less than 1 hour. Also, the algorithm is implemented for two demand levels of 70 million tons per year and 110 million tons per year and the results are analyzed.

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

Network design
greedy algorithm
multi-objective optimization
Railway of Iran
1. Hasany RM, Shafahi Y. Modeling formulation and a new heuristic for the railroad blocking problem. Applied Mathematical Modelling. 2018;56:304-24.
2. Seyedvakili SA, Zakeri J-A, Azadani SN, Shafahi Y. Long-term railway network planning using a multiperiod network design model. J Transp Eng Part A: Syst. 2020;146(1):04019054.
3. Profillidis V. Railway Planning, Management and Engineering: Taylor & Francis Limited; 2022.
4. Tamannaei M, Zarei H, Rasti-Barzoki M. A game theoretic approach to sustainable freight transportation: Competition between road and intermodal road–rail systems with government intervention. Transportation Research Part B: Methodological. 2021;153:272-95.
5. Assembly IC. Law on the development of public transportation and fuel consumption management (in Persian). 2006.
6. Zarrinmehr A, Saffarzadeh M, Seyedabrishami S. A local search algorithm for finding optimal transit routes configuration with elastic demand. International Transactions in Operational Research. 2018;25(5):1491-514.
7. Zarrinmehr A, Saffarzadeh M, Seyedabrishami S, Nie YM. A path-based greedy algorithm for multi-objective transit routes design with elastic demand. Public Transport. 2016;8(2):261-93.
8. Zarrinmehr A. Parallelization of Ant Colony Algorithm in Transportation Discrete Network Design. Modares Civil Engineering journal. 2015;15(2):37-50.
9. Mesbah M, Sarvi M, Currie G. New methodology for optimizing transit priority at the network level. Transportation Research Record. 2008;2089(1):93-100.
10. Long J, Gao Z, Zhang H, Szeto WY. A turning restriction design problem in urban road networks. European Journal of Operational Research. 2010;206(3):569-78.
11. Lee Y-J, Vuchic VR. Transit network design with variable demand. Journal of Transportation Engineering. 2005;131(1):1-10.
12. Xiong Y, Schneider JB. Transportation network design using a cumulative genetic algorithm and neural network. Transportation Research Record. 1992(1364).
13. Laporte G, Mesa JA, Perea F. A game theoretic framework for the robust railway transit network design problem. Transportation Research Part B: Methodological. 2010;44(4):447-59.
14. Miralinaghi M, Lou Y, Keskin BB, Zarrinmehr A, Shabanpour R. Refueling station location problem with traffic deviation considering route choice and demand uncertainty. International Journal of Hydrogen Energy. 2017;42(5):3335-51.
15. Cullinane K, Toy N. Identifying influential attributes in freight route/mode choice decisions: a content analysis. Transportation Research Part E: Logistics and Transportation Review. 2000;36(1):41-53.
16. Shafipour Borojni M. Examining the requirements of privatization in the construction of the infrastructure of the country's rail network (in Persian). Isfahan University of Technology: Isfahan University of Technology; 2017.
17. Rosell F, Codina E. A model that assesses proposals for infrastructure improvement and capacity expansion on a mixed railway network. Transportation Research Procedia. 2020;47:441-8.
18. Fatemi E. Lane tracking, a new technique to reduce headway and increase travel capacity. The Seven International of Railway Engineering2002.
19. Barros LA, Tanta M, Martins AP, Afonso JL, Pinto J, editors. Opportunities and challenges of power electronics systems in future railway electrification. 2020 IEEE 14th International Conference on Compatibility, Power Electronics and Power Engineering (CPE-POWERENG); 2020: IEEE.
20. Wardrop A, Pudney P. Development of strategic infrastructure and train operations modelling: Railway Technical Society of Australasia; 2000.
21. Poorzahedy H, Abulghasemi F. Application of ant system to network design problem. Transportation. 2005;32(3):251-73.
22. Mathew TV, Sharma S. Capacity expansion problem for large urban transportation networks. Journal of Transportation Engineering. 2009;135(7):406-15.
23. Zarrinmehr A, Shafahi Y. Parallelization of the Branch-and-Bound Algorithm in Transportation Discrete Network Design. Scientia Iranica. 2016;23(2):407-19.
24. Sheffi Y. Urban transportation networks: Prentice-Hall, Englewood Cliffs, NJ; 1985.
25. Boyce D, Ralevic-Dekic B, Bar-Gera H. Convergence of traffic assignments: how much is enough? Journal of Transportation Engineering. 2004;130(1):49-55.
26. Aashtiani HZ, Magnanti TL. Equilibria on a congested transportation network. SIAM Journal on Algebraic Discrete Methods. 1981;2(3):213-26.
27. Zarrinmehr A, Aashtiani HZ, Nie Y, Azizian H. Complementarity Formulation and Solution Algorithm for Auto-Transit Assignment Problem. Transportation Research Record. 2019;2673(4):384-97.
28. Nie Y. A note on Bar-Gera's algorithm for the origin-based traffic assignment problem. Transportation Science. 2012;46(1):27-38.
29. Yu T, Ma J, editors. A review of the link traffic time estimation of urban traffic. 2016 IEEE International Conference on Intelligent Transportation Engineering (ICITE); 2016: IEEE.
30. Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to algorithms: MIT press; 2022.
31. Zarrinmehr A, Moulouk Zadeh H. Transit Routes Network Design by Greedy Prioritization of the Routes in Grid Networks (in Persian). Journal of Transportation Research. 2022:-.
32. 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). IUT Transportation Research Institute, 2017.
33. The official website of Railway of Iran [Available from: www.rai.ir.
34. Seyedvakili SA, Nasr Azadani SM, Zakeri JA, Shafahi Y, Karimi M. New model for the railway network design problem. Journal of Transportation Engineering, Part A: Systems. 2018;144(11):04018070.
35. Makui AT, Ata Allah. Decision Making Techniques and Models (in Persian): Iran University of Science and Technology; 2021.
36. Hwang T, Ouyang Y. Assignment of freight shipment demand in congested rail networks. Transportation Research Record. 2014;2448(1):37-44.
مهندسی عمران مدرس
دوره 23، شماره 3
مرداد و شهریور 1402
صفحه 41-56