A NEW APPROACH BASED ON GENETIC ALGORITHM  FOR FINDING THE OPTIMAL ROAD IN MULTI-SOURCE,  MULTI-DESTINATION OF GOOGLE MAPS

Hoàng Phước Lộc; Nguyễn Phong; Lê Thanh Hiếu

A NEW APPROACH BASED ON GENETIC ALGORITHM FOR FINDING THE OPTIMAL ROAD IN MULTI-SOURCE, MULTI-DESTINATION OF GOOGLE MAPS

About this article

Received: 30/09/19 Revised: 14/10/19 Published: 25/10/19

Authors

1. Hoang Phuoc Loc , Quang Tri Teacher Training College
2. Nguyen Phong, Quang Tri Teacher Training College
3. Le Thanh Hieu, Hue University of Education

Abstract

Searching path problem in two points of graph is solved by some algorithms such as Dijkstra, Hueristic, Floyd, etc. This problem is belong to single source, single destination problem. However, in our real life, we need to solve more complexity problems, which are how to find the optimal path through multi-source selection, multi-destination for some works such as postman, roundsman or travel man, etc. are interesting research problems. The Dijkstra and Floyd algorithms can not solve the finding path problem in multi-source and multi-destination. This research proposes an optimal algorithm based on genetic algorithm approach to solve finding path problem through multi-point, which belong to class of multi-source, multi-destination problem. And also proposes an application for optimizing travel cost based on Google Maps database. The experiment results pointed out that the proposed method is more optimal in time and travel cost in comparison with some real applications such as the Google Maps and Địa điểm applications, and also Dijkstra algorithm. We hope that, this study brings the application grounds to solve travel problems in the real life effectively.

Keywords

Shortest path, Graph, Google Maps, Genetic algorithm, Multiple sources multiple destinations

Full Text:

PDF (Tiếng Việt)

References

[1]. R. Avash and J. Ashi, "Genetic Algorithm based Logistics Route Planning," International Journal of Innovation, Management and Technology, vol. 1, pp. 4, 2009.

[2]. K. Faisal and A. Nabil, "An Efficient Multiple Sources Single-Destination MSSD) Heuristic Algorithm Using Nodes Exclusions," International Journal of Soft Computing · January 2015, vol. 10, pp. 6, 2015.

[3]. Z. Liang and W. Wenjia, "A New Path Search Algorithm for Providing Paths among Multiple Origins and One Single Destination"International Journal of Computer Science and Application (IJCSA), vol. 3, pp. 5, 2014.

[4]. S. Yagvalkya, C. S. Subhash, and B. Manisha, "Comparison of Dijkstra’s Shortest Path Algorithm with Genetic Algorithm for Static and Dynamic Routing Network," International Journal of Electronics and Computer Science Engineering, vol. 1, pp. 10, 2016.

[5]. K. Rakesh and K. Mahesh, "Exploring Genetic Algorithm for Shortest Path Optimization in Data Networks," Global Journal of Computer Science and Technology, vol. 10, p. 5, 2010.

[6]. V. Hars, B. Shreejith, H. Wanjun, R. Miguel, S. Arularasi, T. Limin, M. Paolo, T. Marco, and F. Andrea, "Finding a Simple Path with Multiple Must-include Nodes," 2009.

[7]. G. Bilal and S. J. L., "Genetic Algorithm Finding the Shortest Path in Networks," presented at the Fifth International Conference on Genetic and Evolutionary Computing, San Diego, California, USA, 2011.

[8]. V. Anusuya and R. Kavitha, "Genetic Algorithm for Finding Shortest Path in a Network," Intern. J. Fuzzy Mathematical Archive, vol. 2, pp. 6, 2013.

[9]. C. Anu and K. P. Neeraj, "Genetic algorithm for shortest path in packet switching networks," Journal of Theoretical and Applied Information Technology, vol. 29, pp. 11, 2011.

[10]. Y. H. Ahmed and M. R. Hassan, "A Genetic Algorithm To Solve The Minimum-Cost Paths Tree Problem," International Journal of Computer Networks & Communications (IJCNC), vol. 7, pp. 11, 2015.

[11]. A. Sachith, G. Baladasan, and K. Saluka, "A Genetic Algorithm Approach to Solve the Shortest Path Problem for Road Maps," in International Conference on Information and Automation, Colombo, Sri Lanka, 2005.

[12]. A. Umit, R. K. Ismail, G. Cevdet, Y. Beyza, and M. O. Ilhami, "An Idea for Finding the Shortest Driving Time Using Genetic Algorithm Based Routing Approach on Mobile Devices," International Journal of Mathematics and Computers In Simulation, vol. 6, pp. 8, 2012.

[13]. B. Saeed and A. A. Alia, "Developing a Genetic Algorithm for Solving Shortest Path Problem," presented at the International conference on Urpan planing and transportation, Heraklion, Crete Island, Greece, 2008.

[14]. A. Nouara and C. Mohamed, "Mobile Robots Path Planning using Genetic Algorithms," in The Seventh International Conference on Autonomic and Autonomous Systems, 2011.

[15]. B. Eşref and B. Selami, "A Hybrid Genetic Algorithm for Mobile Robot Shortest Path Problem," International Journal of Intelligent Systems and Applications in Engineering, vol. 1, pp. 8, 2016.

[16]. S. Aravindh and G. Michael, "Hybrid Of Ant Colony Optimization And Genetic Algorithm For Shortest Path In Wireless Mesh Networks," Journal of Global Research in Computer Science, vol. 3, pp. 4, 2012.

Refbacks

There are currently no refbacks.



Remember me