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

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.