Volume 23, Issue 3 (2023)
MCEJ 2023, 23(3): 41-56 |
Back to browse issues page
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Zarrinmehr A, Mohammad Hasany R. The Greedy Algorithm for Development of The Network Based on the Lowest Developing Cost: The Case Study of Iran. MCEJ 2023; 23 (3) :41-56
URL: http://mcej.modares.ac.ir/article-16-63521-en.html
URL: http://mcej.modares.ac.ir/article-16-63521-en.html
1- Assistant Professor, School of Civil Engineering, University of Mazandaran
2- Assistant Professor, School of Railway Engineering, Iran University of Science and Technology , rmhasany@iust.ac.ir
2- Assistant Professor, School of Railway Engineering, Iran University of Science and Technology , rmhasany@iust.ac.ir
Abstract: (649 Views)
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.
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.
Article Type: Original Research |
Subject:
Transportation Management
Received: 2022/08/13 | Accepted: 2022/12/18 | Published: 2023/08/1
Received: 2022/08/13 | Accepted: 2022/12/18 | Published: 2023/08/1
Send email to the article author
| Rights and permissions | |
 |
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. |