Solución al problema del agente viajero utilizando el API de Google Maps y sistema Android

Abstract

The deterministic algorithms are a family of algorithms whose goal is precisely to give approximate solutions to general NP type problems, without the need to go through the entire search space. The classic heuristics perform a limited exploration on the search space and normally the solutions produced are good in a short time. Its implementation is simple and easily adaptable to real world problems. There are two types of heuristics: constructive and improvement or search, the algorithm implemented is located in the second type, because it belongs to the family of algorithms whose goal is precisely to give approximate solutions to general NP type problems. The Traveler agent consists of: given a finite set of cities and travel costs between all the pairs of cities, find the cheapest way to visit all the cities exactly once and return to the starting point. To solve this problem, we rely on the Google Maps Api's, to represent the routes to follow and the estimated time of arrival.

El algoritmo es la secuencia de instrucciones mediante la cual podemos resolver un problema o cuestión. Los algoritmos cuasi-óptimos son una familia de algoritmos cuya meta es dar soluciones aproximadas a problemas generales de tipo NP, sin necesidad de recorrer todo el espacio de búsqueda. Las heurísticas clásicas realizan una exploración limitada sobre el espacio de búsqueda y normalmente las soluciones producidas son buenas en poco tiempo. Su implementación es sencilla y son fácilmente adaptables a problemas del mundo real. Existen dos tipos de heurísticas: constructivas y de mejoramiento o de búsqueda, el algoritmo de Kruskal implementado en el presente trabajo se ubica en las segundas, ya que pertenece a la familia de algoritmos cuya meta es precisamente dar soluciones aproximadas a problemas generales de tipo NP. El problema del agente viajero consiste en: dado un conjunto finito de puntos y el costo de viaje entre todos los pares de puntos, encontrar la forma más barata de visitar todos los puntos exactamente una vez, y volver al punto de partida. Para resolver este problema se apoya en el algoritmo de Kruskal y en las librerías de Google Maps, para representar las rutas a seguir y el tiempo estimado de llegada. Para solucionar este problema, lo principal es tener todos los puntos a visitar, a continuación, con el algoritmo de Kruskal resuelve y crea un árbol n-ario, el cual se va a recorrer. El resultado de este recorrido traza una ruta que se representa en google Maps con el recorrido de todos los puntos visitando cada uno de ellos y regresando al origen en el menor tiempo posible con el apoyo de Google Maps.