Resumen

Aquí se estudia el problema del vendedor viajero múltiple (MTSP), una extensión del conocido problema del vendedor viajero (TSP). En el MTSP, partiendo de un depósito, varios vendedores deben visitar todas las ciudades, de modo que cada ciudad debe ser visitada una sola vez por un solo vendedor. Es NP-difícil y más complejo que el TSP habitual. Por lo tanto, sólo se pueden obtener soluciones óptimas exactas para casos de problemas de pequeño tamaño. Para problemas de gran tamaño, es esencial aplicar algoritmos heurísticos, y entre ellos, el algoritmo genético se ha identificado para hacer frente con éxito a este tipo de problemas de optimización complejos. Así, proponemos un algoritmo genético híbrido (HGA) que utiliza el cruce constructivo secuencial, un enfoque de búsqueda local junto con una técnica de inmigración para encontrar una solución de alta calidad al MTSP. A continuación, comparamos el HGA propuesto con algunos de los algoritmos más avanzados resolviendo instancias simétricas del TSPLIB de varios tamaños y con distintos números de vendedores. Nuestra investigación experimental demuestra que el HGA es uno de los mejores algoritmos.

• Materias:Matemáticas Análisis Matemático Álgebra Ingeniería Matemática aplicada Lógica matemática
• Subjects:mathematics Mathematical Analysis Algebra Engineering Applied Mathematics Mathematical logic
• Palabras claves:hga, mtsp, problema del vendedor, problemas de optimización tan complejos, soluciones óptimas exactas, algoritmo genético híbrido, enfoque de búsqueda local, cruce constructivo secuencial, instancias del problema de tamaño, problema de tamaño más pequeño
• Keywords:hga, mtsp, salesman problem, such complex optimization problems, exact optimal solutions, hybrid genetic algorithm, local search approach, sequential constructive crossover, sized problem instances, smaller sized problem