Planejador de roteiros turísticos: uma aplicação do problema do Caixeiro viajante na cidade do Recife

Abstract

A mobile application (proof of concept) has been developed providing route recommendations for tourists visiting Recife by walking. The tourist selects the points of interest (POI) he wants to visit and the application recommends a route. The tourist can choose the points of interest from a list of points and view them on a map. The application also provides detailed information on points of interest to aid in the choice. Three algorithms were implemented to recommend the route. The algorithms were compared in terms of execution time, impact on the total length of the route generated, memory and CPU usage. The Brute Force algorithm presented a skillful execution time in up to 8 chosen points. Nearest Neighbor moved away more and more of the optimal solution as the number of points increased,while its combination with 2-OPT resulted in an optimization of up to 50 minutes in the route duration.