SID.ir New Version

Paper Information

Journal:   JOURNAL OF GEOMATICS SCIENCE AND TECHNOLOGY   2017 , Volume 6 , Number 4 ; Page(s) 231 To 239.

Paper:

Finding Shortest Path In A Network By Using Cuckoo Optimization Algorithm And Gis

Author(s):

*

Abstract:
Nowadays with the rapid rate of urban development and increasing volume of vehicles and traffic restrictions, routing in urban networks is not only necessary but essential. Management of such massive volume of data makes the need to for GIS with capabilities to conduct spatial data analysis inevitable. People often, when deciding to start a journey from one location to another, consider not only which route and means of transportation will save them time, but also which are the most inexpensive and cost effective. Hence, they outline the issue as a question in their mind, and based on the criteria, seek to find the optimal solution. The same behavior occurs in a different routing system. Finding the most optimal, efficient and shortest route is one of the key pillars in route finding for which finding the right solutions could lead to answering other questions on the issue. In fact, for a more in depth level of analysis, the answer to this question is essential; Finding the shortest path possible from a starting point or origin, to an ending point or destination. Metaheuristic algorithms are estimating algorithms, that are able to find optimal or almost optimal solutions in a reasonable time. The showcased methodology in this research for solving the optimal route is recommended for the first time and is the Cuckoo Optimization Algorithm. The reason for choosing this algorithm, is the fact that it is a new method that provides appropriate solutions for different problems than other meta-heuristic algorithms. Route finding which is by nature a discrete problem, is managed by changes in binary version of this algorithm. In setting up the first population, a controlled approach was used to prevent the creation of random populations, that only a few of them could create routes. In this method, population variables that are basically the same network points and situations of each cuckoo are not randomly selected. These variables are selected in a controlled system. Meaning, selection of each next node is from those that are connected to it. While implementation of the algorithm, cuckoo’s locations are converted to binary numbers, if a node exists in the route it will become 1 and if not 0. A Sigmoid Function is used in the migration phase of the Cuckoo. In this phase the new location of Cuckoo stands between the range of zero and one, and other locations are converted to zero and one. To test the recommended algorithm, three network are used; hypothetical, local and real networks. The result of running this algorithm in 2 hypothetical and local networks with 20 and 31 nodes was the same result of a deterministic algorithm. However, in a network, that was part of a real network and composed of 617 nodes and 995 arcs, it could indicate the optimal route slightly better than that of deterministic algorithm. The results showed that the algorithm is capable of routing in the network and with some changes on the structure of the network can be used on networks with large data.

Keyword(s): FINDING SHORTEST ROUTE IN NETWORK, GEOGRAPHICAL INFORMATION SYSTEM (GIS), CUCKOO OPTIMIZATION ALGORITHM, BINARY ENCODING, CONTROLLED POPULATION

International related papers:

Most related Highly related Moderately related Least related

References:
• Not Registered.
•
•

Citations:
• Not Registered.

+ Click to Cite.
APA: Copy

SARGOLZAEI, A., & VAFAEINEJAD, A. (2017). FINDING SHORTEST PATH IN A NETWORK BY USING CUCKOO OPTIMIZATION ALGORITHM AND GIS. JOURNAL OF GEOMATICS SCIENCE AND TECHNOLOGY, 6(4 ), 231-239. https://www.sid.ir/en/journal/ViewPaper.aspx?id=572525

Vancouver: Copy

SARGOLZAEI A., VAFAEINEJAD A.R.. FINDING SHORTEST PATH IN A NETWORK BY USING CUCKOO OPTIMIZATION ALGORITHM AND GIS. JOURNAL OF GEOMATICS SCIENCE AND TECHNOLOGY. 2017 [cited 2022May29];6(4 ):231-239. Available from: https://www.sid.ir/en/journal/ViewPaper.aspx?id=572525

IEEE: Copy

SARGOLZAEI, A., VAFAEINEJAD, A., 2017. FINDING SHORTEST PATH IN A NETWORK BY USING CUCKOO OPTIMIZATION ALGORITHM AND GIS. JOURNAL OF GEOMATICS SCIENCE AND TECHNOLOGY, [online] 6(4 ), pp.231-239. Available: https://www.sid.ir/en/journal/ViewPaper.aspx?id=572525.

Persian Abstract

Latest on Blog
Enter SID Blog