Problema generalizado del viajante de comercio

El problema generalizado del viajante de comercio es un problema de optimización combinatoria que es una generalización del conocido problema del viajero de comercio . Los datos iniciales del problema son un conjunto de vértices, una partición de este conjunto en los llamados conglomerados, así como una matriz de costos de transición de un vértice a otro. El problema es encontrar el camino cerrado más corto que visitaría un vértice en cada grupo (también hay una modificación cuando el camino debe visitar al menos un vértice en cada grupo).

Dependiendo de las propiedades de la matriz de costos, el problema puede ser simétrico si la matriz es simétrica, o asimétrico en caso contrario. Uno de los casos especiales considerados con más frecuencia de un problema simétrico es el problema euclidiano o planar, cuando cada vértice tiene sus propias coordenadas en el espacio, y el costo de moverse entre los vértices corresponde a la distancia euclidiana entre los puntos correspondientes en el espacio.

Al igual que el problema del viajante de comercio , el problema generalizado del viajante de comercio pertenece a la clase de problemas NP-difíciles . Para probarlo, basta con considerar un caso especial del problema, cuando cada grupo contiene exactamente un vértice, y el problema se reduce a un simple problema del viajante de comercio, que es NP-difícil.

Métodos de solución

Métodos exactos

Hay dos métodos efectivos para la solución exacta del problema generalizado del viajante de comercio: Brunch-and-Cut [1] , así como un método para reducir el problema generalizado al problema habitual del viajante de comercio, cuyos métodos de resolución están bien estudiados. [2] .

En 2002, se demostró [3] que el problema generalizado del viajante de comercio puede reducirse a un problema ordinario del viajante de comercio de la misma dimensión reemplazando la matriz de peso .

Métodos heurísticos

Métodos heurísticos simples

Los métodos heurísticos más simples para resolver el problema generalizado del viajante de comercio incluyen el algoritmo codicioso , que en cada paso selecciona el borde de menor costo del conjunto de bordes que no violan la corrección de la solución, así como el vecino más cercano más eficiente. método, que parte de un vértice arbitrario y en cada paso agrega a la solución, el vértice más cercano al último agregado. También hay otras heurísticas que son modificaciones de heurísticas bien conocidas para el problema ordinario del viajante de comercio.

En particular, a menudo se utilizan los siguientes tipos de búsqueda local :

2-opt , que se usa ampliamente en muchos problemas de optimización combinatoria, se reduce a eliminar dos aristas del recorrido e insertar dos nuevas aristas que no violan la corrección de la solución (en el caso de 2-opt, las aristas que se insertarán están determinados de forma única). Un recorrido se considera un mínimo local si en él no existen pares de aristas cuya sustitución suponga una mejora en la solución. Así, tanto el tamaño de la vecindad como la complejidad de la heurística son , donde es el número de agrupaciones. ${\ estilo de visualización O (m ^ {2})}$ $metro$
3-opt es similar a 2-opt, sin embargo, no se eliminan dos, sino tres bordes en cada uno. En el caso de 3 opciones, hay ocho formas no triviales de insertar nuevos bordes para restaurar la corrección del recorrido. Una de estas formas conserva la dirección de cada uno de los fragmentos del recorrido, lo cual es una propiedad importante para los problemas asimétricos. El tamaño del vecindario y la complejidad de la heurística son . ${\ estilo de visualización O (m ^ {3})}$
Existen modificaciones naturales de los algoritmos de 2 y 3 opciones, que además incluyen la búsqueda de vértices óptimos dentro de clústeres cambiantes.
"Inserción" es un caso especial de 3-opt. En cada iteración, el algoritmo elimina el vértice e intenta encontrar una posición más favorable para él. La complejidad del algoritmo es . Es muy utilizada una modificación que considera la inserción no solo de un vértice remoto, sino también de cualquier otro vértice del clúster correspondiente. ${\ estilo de visualización O (m ^ {2})}$
La optimización de clústeres es una búsqueda local específica para el problema generalizado del viajante de comercio. La esencia del algoritmo es encontrar el camino más corto a través de una secuencia dada de grupos. En otras palabras, la vecindad del algoritmo incluye todos los recorridos que difieren del original en nada más que la elección de los vértices dentro de cada uno de los grupos. El tamaño del vecindario investigado es:

$\prod_{i=1}^{m}|C_{i}|\,,$ donde está numerado el grupo . Aplicando la búsqueda del camino más corto en un gráfico especialmente construido, el algoritmo encuentra un mínimo local para , donde . Así, Cluster Optimization pertenece a la clase de búsquedas locales con una vecindad muy grande , es decir, explora una vecindad exponencial en tiempo polinomial. $C_{yo}$ $i$ $O(ms^{3})$ $s=\max _{i}|C_{i}|$

Metaheurísticas

El campo de los algoritmos genéticos, que han demostrado su eficacia para esta tarea, ha sido muy estudiado. El primer trabajo en esta área pertenece a Snyder y Duskin [4] , luego importantes resultados fueron obtenidos por Silbergoltz y Golden [5] , Gyuten y Karapetyan [6] .

Notas

↑ M. Fischetti, J. J. Salazar-González y P. Toth. Un algoritmo de rama y corte para el problema generalizado simétrico del viajante de comercio. Investigación de operaciones 45(3) (1997), 378-394.
↑ D. Ben-Arieh, G. Gutin, M. Penn, A. Yeo y A. Zverovitch. Transformaciones de ATSP generalizado en ATSP, Operations Research Letters 31 (2003), 357-365.
↑ 6. Arash Behzad, Mohammad Modarres (2002). Una nueva transformación eficiente del problema generalizado del viajante de comercio en el problema del viajero de comercio
↑ LV Snyder y MS Daskin. Un algoritmo genético de clave aleatoria para el problema generalizado del vendedor ambulante. Revista europea de investigación operativa 174 (2006), 38-53.
↑ J. Silberholz y B. Golden. El problema generalizado del viajante de comercio: un nuevo enfoque del algoritmo genético. Extendiendo los horizontes: Avances en computación, optimización y tecnologías de decisión, 2007, 165-181.
↑ G. Gutin y D. Karapetyan. Gregory Gutin y Daniel Karapetyan. Un algoritmo memético para el problema generalizado del viajante de comercio. Natural Computing 9(1), páginas 47-60, Springer 2010. (enlace no disponible)

Problemas NP-completos
Problema de maximización del apilamiento (packing)	Envasado en contenedores embalaje bidimensional embalaje lineal embalaje por peso embalaje por valor El problema de la mochila
teoría de grafos teoría de conjuntos	Problema de cobertura de vértices Haga clic en problema El problema de un conjunto independiente (conjunto) Establecer problema de cobertura Problema de Steiner El problema del viajante de comercio Problema generalizado del viajante de comercio
Problemas algorítmicos	Problema de satisfacibilidad para fórmulas booleanas (en forma normal conjuntiva)
Juegos de lógica y rompecabezas.	Etiquetas generalizadas (juego en N 2 -1) problema de solución más corta Problemas cuyas soluciones se aplican en Tetris Problema de sudoku generalizado Problema de llenado de cuadrados latinos La tarea de Kakuro
Clases de dificultad La investigación de operaciones Mejoramiento optimización combinatoria Matemáticas Aplicadas Teoría de Algoritmos Programación dinámica 21 Problema de Karp NP-completo