Diseño de un algoritmo en 2 fases para un mtsp

Resumen El Problema de los Vendedores Viajeros, MTSP, consiste en construir o encontrar una secuencia de clientes por visitar para cada vendedor, partiendo y concluyendo todos ellos su recorrido en el dep osito; de tal forma que todos los clientes sean visitados una vez y la suma de las distancias que los vendedores deben recorrer sea m nima. El dise~no del algoritmo para resolver el MTSP est a formado por 2 fases: i) obtener k particiones del conjunto de los clientes V ; y, ii) para cada partici on obtenida en la fase 1, construir un recorrido. La fase 1 se considera la m as importante, ya que la calidad de las soluciones depende mucho de las particiones que esta genera. En ella se observa que la distribuci on de los v ertices en las diferentes particiones es mejor, si el dep osito se encuentra en el centro con respecto a los dem as v ertices. La fase 2 obtiene recorridos con un margen de error entre 6% y 22 %, sobre los mejores resultados conocidos reportados en la biblioteca TSPLIB para el problema TSP, con una complejidad temporal O(n3). Los resultados para 22 instancias disponibles en la biblioteca TSPLIB, son los siguientes: i) El 45% de los costos de las soluciones, es menor que los mejores costos conocidos para el MTSP Bounded ; y, ii) El 59.09% de los costos de las soluciones obtenidas por el algoritmo 2 fases, tiene una diferencia menor al 5% con respecto a los mejores costos conocidos, reportados en la literatura para el MTSP Bounded.

Abstract The Multiple Traveling Salesman Problem, MTSP, consists in construct or nding a sequence of clients to visit for each salesman, starting and ending all of them in the depot; so that all clients are visited once and the sum of the distances that salesman must travel be the minimum. The design of the algorithm to solve the MTSP consists of 2 phases: i) obtain k partitions of the set of clients V; and, ii) for each partition obtained in phase 1, construct a tour. Phase 1 is considered the most important since the quality of the solutions depends a lot on the partitions it generates. It shows that the distribution of the vertices in the di erent partitions is better if the depot is in the center with respect to the other vertices. Phase 2 obtains tours with a margin of error between 6% and 22 %, on the best-known solutions reported in the TSPLIB library for the TSP problems, with time complexity O(n3). The results for 22 instances available in the TSPLIB library are the following: i) 45% of the costs of the solutions is less than the cost of the best-known solutions for the MTSP Bounded; and, ii) 59.09% of the costs of the solutions obtained by the 2-phase algorithm, have a di erence of less than 5% compared to the cost of the best-known solutions, reported in the literature for the MTSP Bounded.