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

مسائل حمل و نقلی به سه سطح استراتژیک، تاکتیکی و کارکردی دسته بندی می شود که هریک سطح نفوذ، میزان بودجه مورد نیاز، تصمیم گیران و دوره زمانی متفاوتی دارند. مسئله طراحی و توسعه شبکه حمل و نقل ریلی یکی از مسائل مهم و کلیدی از سطح استراتژیک است. به طور خلاصه، طراحی شبکه به نحوه اختصاص دادن بودجه محدود به توسعه زیرساخت شبکه ریلی می پردازد، به گونه ای که هدف های خاصی همچون کمینه سازی کل زمان سفر در شبکه، کمینه سازی هزینه های توسعه یا نگهداری شبکه، بیشینه سازی درآمد حاصله از انتقال بار، یا بیشینه سازی جذب تقاضای سفر به سوی شیوه ریلی لحاظ شود. شکل عمومی مساله طراحی شبکه یک مسئله دوسطحی در رده مسائل np hard به شمار می رود که حل آن در مقیاس های کوچک با دشواری روبروست. در این مقاله بر ای حل مسئله طراحی شبکه یک الگوریتم حریصانه ارایه می شود که سعی دارد ضمن عبور سطح مشخصی از تقاضای بار از شبکه، هزینه های توسعه شبکه را در سطح کمینه نگه دارد. برای این منظور، الگوریتم از یک سطح تقاضای اولیه شروع کرده، پس از اعمال الگوریتم تخصیص ترافیک در هر تکرار، یکی از بلاک های به ظرفیت رسیده را انتخاب می کند و ظرفیت آن را به صورت جزئی افزایش می دهد.در یک رویکرد حریصانه، اولویت انتخاب در هر تکرار به بلاک دارای کمترین هزینه توسعه داده می شود. این روند تا جایی پیش می رود که کلسطح تقاضای ورودی بتواند از شبکه انتقال پید ا کند. مطالعه پیش رو این الگوریتم را به زبان جاوا پیاده سازی و نتایج حاصله را برای شبکه راهآهن ایرا ن به عنوان مطالعه موردی گزارش می کند. مطابق نتایج، با توجه به معیارهای سطح تقاضای عبوری و سطح توسعه (سرمایه گذاری ) درشبکه، می توان به جواب های به دست آمده به دید جواب های چندهدفی شبه پاریتو نگریست. این جواب ها با درصدهای متفاوت از اهمیت ایندو هدف مورد بررسی قرارگرفته و نتایج به دست آمده تحلیل می شوند.

introducing a network expansion greedy algorithm based on least cost expansions - case study: iran's railway network

transportation problems can be categorized into three strategic, tactical, and operational levels, each ofwhich has a different level of influence, required budget, decision making process, and time period. theproblem of developing the rail transportation network or rail network design is one of the key issues at thestrategic level of planning. in short, rail network design deals with the solution of allocating a limited budgetto a feasible subset of projects, in such a way that certain planning objectives are met, including 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. two stakeholders areinvolved in the problem of rail network design. on one side, the operators make the macro decisions to meetthe 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. to account for both sides of this problem, a bi-level structured problem should be taken into account. the general form of the network design problem, as a bi-level problem, falls in the category of np-hard problems, which are difficult to solve in even small scales. to solve this problem, the solution algorithms are classified into two generalcategories: exact and approximate. the exact solution algorithms strive to provide the best global solutionamong the possible solutions. regarding the combinatorial explosion of the problem, they are considered as 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 should be presented to solve the problem. greedy algorithms are classified in the category of approximate algorithms.this article proposes a greedy algorithm to solve the problem of network design trying to minimize the expansion costs of the rail network. in each iteration, the proposed algorithm performs a traffic assignment over the rail network and thereby obtains a list of rail blocks that have reached their capacity. among these block, in a greedy approach, the algorithm gives the priority of expansion to the block that has the least cost of expansion and marginally increases the capacity of that block. the process of traffic assignment, blockselection and marginal expansion continues until the entire level of input freight demand can be transferredthrough the rail network. this algorithm is implemented in java programming language and the railwaynetwork of iran is applied as a case study. considering the track of two criteria in the solutions obtained inthe process of the algorithm, namely the throughput of the system and the expansion costs, we also presentand analyze pseudo-pareto. the results are presented for two demand levels of 70 and 110 million tons of freight transportation per year. analyzing the solutions shows that the more emphasis is put on the expansion cost criterion, the 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. we also observe that the proposed greedy algorithm entails a light computational burden and, for iran’s railway network with more than 434 rail stations, achieves the track of its solutions in less than 1 hour.