Optimum Routing in the Urban Transportation Network by Integrating Genetic Meta-heuristic (GA) and Tabu Search (Ts) Algorithms

Q: How can I download an article?

To download an article from SID, first log in to the site, search for the article title, and click on the 'Download Article' option.

Q: How can I download an ISI article?

To download an ISI article on SID, enter the keyword or article title in the search bar, view the relevant results, click on the desired article, and select the 'Download Article' option.

Q: How can I access the SID database?

To access the SID database, visit SID.ir, create an account, and log in to access scientific resources.

Q: Is downloading articles from SID free?

Some articles on SID are available for free, while others require payment. Details are specified on the article's page.

SHAHMORADI A.; BEHZADI S.

مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

Journal Paper

Paper Information

Journal: JOURNAL OF GEOMATICS SCIENCE AND TECHNOLOGY Year:2020 | Volume:9 | Issue:3 Page(s): 145-158

Download Full-Text

Persian Verion

View:

673

Download:

Cites:

Information Journal Paper

Title

Optimum Routing in the Urban Transportation Network by Integrating Genetic Meta-heuristic (GA) and Tabu Search (Ts) Algorithms

Author(s)

SHAHMORADI A. | BEHZADI S. | Issue Writer Certificate

Keywords

Finding the Shortest PathQ1

Genetic AlgorithmQ2

Tabu Search AlgorithmQ2

Geometric pre-processingQ1

Search ExtentQ1

Abstract

Urban transportation is one of the most important issues of urban life especially in big cities. Urban development, and subsequently the increase of routes and communications, make the role of transportation science more pronounced. The shortest path problem in a network is one of the most basic network analysis issues. In fact, finding answers to this question is necessity for higher level analysis. In general, shortest path solution methods using optimization algorithms are divided into two categories: exact and approximate algorithms. In exact algorithms, achieving the optimal solution requires time, and consequently more cost. On the opposite side, there are some approximate algorithms that work in a short period of time. Meta-heuristic algorithms are among approximate algorithms that are capable of finding optimal or near-optimal solutions in a reasonable period of time. The method used in this study is to solve the shortest path problem with the combination of Genetic meta-heuristic (GA) and Tabu Search (TS) algorithms. GA is inspired by genetic science and Darwin's theory of evolution; it is based on survival of the highest or natural selection. A common use of Genetic Algorithms is to be used as an optimization function. In GA, the genetic evolution of living things of life is simulated. Inspired by the evolutionary process of nature, these algorithms solve problems. GA forms a set of population (solutions), then it achieves an optimal set by acting some possess on the correct set. To solve a problem by Genetic Algorithms, it is necessary the problem is converted to the specific form required by GA. On the other hand, TS algorithm is not population-based. It obtains an answer, then it tries to direct the answer to the optimal solution by applying a series of operators. This algorithm is highly similar to the Simulated Annealing algorithm. In this paper, for solving the shortest path problem, a series of Geometric pre-processing on the network is done to generate a search area around the source and destination nodes. In the proposed algorithm, the cost function is defined as a complex number, which the real part shows the sum of the weight of the real edges, and the imaginary part denotes the number of virtual edges. The innovation of this research is about applying Tabu Search Algorithm in mutations process of Genetic Algorithm. The proposed method overcomes the inappropriate response of the pure Genetic Algorithm in terms of the final weight of the path especially the large networks. In order to evaluate the efficiency of the proposed algorithm, the algorithm was implemented on a real directional network which is part of Tehran city road networks including 739 nodes and 1160 edges. The results show that in the proposed algorithm, the length of the path is as close as possible to the solution obtained from the definitive Dijkstra’ s algorithm. This algorithm predicts approximately the final path length of 5% more than Dijkstra’ s algorithm. But in terms of running speed, it is 5. 12 times faster than the Dijkstra’ s algorithm. In comparison with the pure Genetic Algorithm, the proposed algorithm is 9% shorter in average in terms of path length. And about the running time, the speed of the proposed algorithm is approximately equal to the pure Genetic Algorithm. Regarding to repeatability, the proposed algorithm also shows 25. 36% of repeatability.

Cites

No record.

References

No record.

Cite

APA: Copy

SHAHMORADI, A., & BEHZADI, S.. (2020). Optimum Routing in the Urban Transportation Network by Integrating Genetic Meta-heuristic (GA) and Tabu Search (Ts) Algorithms. JOURNAL OF GEOMATICS SCIENCE AND TECHNOLOGY, 9(3 ), 145-158. SID. https://sid.ir/paper/249450/en

Vancouver: Copy

SHAHMORADI A., BEHZADI S.. Optimum Routing in the Urban Transportation Network by Integrating Genetic Meta-heuristic (GA) and Tabu Search (Ts) Algorithms. JOURNAL OF GEOMATICS SCIENCE AND TECHNOLOGY[Internet]. 2020;9(3 ):145-158. Available from: https://sid.ir/paper/249450/en

IEEE: Copy

A. SHAHMORADI, and S. BEHZADI, “Optimum Routing in the Urban Transportation Network by Integrating Genetic Meta-heuristic (GA) and Tabu Search (Ts) Algorithms,” JOURNAL OF GEOMATICS SCIENCE AND TECHNOLOGY, vol. 9, no. 3 , pp. 145–158, 2020, [Online]. Available: https://sid.ir/paper/249450/en

Related Journal Papers