Track: Operations Research

Abstract

There are a large number of variants for the traveling salesman problem, as well as the solution methods such as linear optimization, heuristics and metaheuristics that provide close or optimal solutions for the problem. When we deal with real instances, these solutions usually become invalid due to problems of accuracy and/or update of the digital maps, mainly when we want to create routes in a neighborhood due to dominant factors such as the sense of the streets, the closeness between the points, or the geospatial data of the map. Google Maps is the most accurate and accessible database in terms of spatial information. In this work we present a methodology to calculate precise routes for the Traveling Salesman Problem. We use the google maps APIs to obtain information, then preprocess the data in order to convert it into a valid graph, and finally the instance is solved by a proposed metaheuristic. The obtained solutions are compared between digital maps (INEGI, INE of Mexico) and the google maps API showing the advantage of use the APIs.