An Android Application for Google Map Navigation System, Solving the Travelling Salesman Problem, Optimization throught Genetic Algorithm

Abstract

A salesman plans a trip through which he wants to visit his clients and come back to the starting point. During the trip, same client should not be visited more than once and the route should be shorter and less costly. The mathematical modeling of this problem has to do with the theory of graphs and combinatorics. Graph vertexes symbolize places to visit, and edges that connect the nodes are the paths (the distance of which is known from the beginning) that lead to those places. The complexity of the exact algorithm for solving this problem increases with the number of places to visit. For this reason genetic algorithm is offered as the optimal solution of TSP problem. The whole system is implemented as client-server system using RESTFul web services, Google-services and Android OS. Genetic Algorithm is used to determine the optimum route on Google map and solves the Travelling Salesman problem.