Título
Diseño de un algoritmo en 2 fases para un mtsp
Autor
VICTOR HUGO PACHECO VALENCIA
Colaborador
NODARI VAKHANIA MAISURADZE
Nivel de Acceso
Acceso Abierto
Resumen o descripción
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.
Editor
El autor
Fecha de publicación
15 de octubre de 2019
Tipo de publicación
Tesis de maestría
Recurso de información
Formato
Idioma
Español
Cobertura
MEX
Audiencia
Investigadores
Repositorio Orígen
Repositorio Institucional de Acceso Abierto de la Universidad Autónoma del Estado de Morelos
Descargas
0