LISTA DE PROBLEMAS

  (Redirigido del problema del vendedor itinerante )

Saltar a navegaciónSaltar a búsqueda

Solución de un problema de vendedor ambulante: la línea negra muestra el bucle más corto posible que conecta cada punto rojo.

El problema del vendedor ambulante (también llamado el problema del vendedor ambulante ^[1] o TSP ) hace la siguiente pregunta: "Dada una lista de ciudades y las distancias entre cada par de ciudades, ¿cuál es la ruta más corta posible que visita cada ciudad y regresa a la ciudad de origen? Es un problema NP-difícil en la optimización combinatoria , importante en la investigación de operaciones y la informática teórica .

El problema del comprador viajero y el problema de ruta del vehículo son generalizaciones de TSP.

En la teoría de la complejidad computacional , la versión de decisión del TSP (donde, dada una longitud L , la tarea es decidir si el gráfico tiene algún recorrido más corto que L ) pertenece a la clase de problemas NP-completos . Por lo tanto, es posible que el peor tiempo de ejecución para cualquier algoritmo para el TSP aumente de manera superpolinómica (pero no más que exponencialmente ) con el número de ciudades.

El problema se formuló por primera vez en 1930 y es uno de los problemas de optimización más estudiados. Se utiliza como punto de referencia para muchos métodos de optimización. Aunque el problema es computacionalmente difícil, se conocen muchas heurísticas y algoritmos exactos , por lo que algunas instancias con decenas de miles de ciudades se pueden resolver por completo e incluso los problemas con millones de ciudades se pueden aproximar en una pequeña fracción del 1%. ^[2]

El TSP tiene varias aplicaciones incluso en su formulación más pura, como la planificación , la logística y la fabricación de microchips . Ligeramente modificado, aparece como un subproblema en muchas áreas, como la secuenciación del ADN . En estas aplicaciones, el concepto de ciudad representa, por ejemplo, clientes, puntos de soldadura o fragmentos de ADN, y el concepto de distancia representa los tiempos de viaje o el costo, o una medida de similitudentre fragmentos de ADN. El TSP también aparece en astronomía, ya que los astrónomos que observan muchas fuentes querrán minimizar el tiempo dedicado a mover el telescopio entre las fuentes. En muchas aplicaciones, pueden imponerse restricciones adicionales, como recursos limitados o ventanas de tiempo.

Historia [ editar ]

Los orígenes del problema del vendedor ambulante no están claros. Un manual para vendedores ambulantes de 1832 menciona el problema e incluye ejemplos de recorridos por Alemania y Suiza , pero no contiene ningún tratamiento matemático. ^[3]

William Rowan Hamilton

El problema del vendedor ambulante fue formulado matemáticamente en 1800 por el matemático irlandés WR Hamilton y por el matemático británico Thomas Kirkman . El juego Icosian de Hamilton fue un rompecabezas recreativo basado en la búsqueda de un ciclo hamiltoniano . ^[4] La forma general del TSP parece haber sido estudiada por primera vez por matemáticos durante la década de 1930 en Viena y en Harvard, en particular por Karl Menger , quien define el problema, considera el algoritmo de fuerza bruta obvio y observa la falta de optimización. del heurístico vecino más cercano:

Denotamos por problema de mensajería (ya que en la práctica esta pregunta debe ser resuelta por cada cartero, de todos modos también por muchos viajeros) la tarea de encontrar, para finitos puntos cuyas distancias por pares se conocen, la ruta más corta que conecta los puntos. Por supuesto, este problema se puede resolver mediante muchos ensayos. Se desconocen las reglas que empujarían el número de pruebas por debajo del número de permutaciones de los puntos dados. La regla de que primero se debe ir desde el punto de partida al punto más cercano, luego al punto más cercano a este, etc., en general, no produce la ruta más corta.

^[5]

Fue considerado matemáticamente por primera vez en la década de 1930 por Merrill M. Flood, que buscaba resolver un problema de ruta del autobús escolar. ^[6] Hassler Whitney de la Universidad de Princeton introdujo el nombre del problema del vendedor ambulante poco después. ^[7]

En las décadas de 1950 y 1960, el problema se hizo cada vez más popular en los círculos científicos de Europa y los EE. UU. Después de que la Corporación RAND en Santa Mónica ofreciera premios por los pasos para resolver el problema. ^[6] Contribuciones notables fueron hechas por George Dantzig , Delbert Ray Fulkerson y Selmer M. Johnson de la Corporación RAND, quienes expresaron el problema como un programa lineal entero y desarrollaron el plano de corteMétodo para su solución. Escribieron lo que se considera el documento seminal sobre el tema en el que con estos nuevos métodos resolvieron una instancia con 49 ciudades a la óptima mediante la construcción de un recorrido y demostrando que ningún otro recorrido podría ser más corto. Dantzig, Fulkerson y Johnson, sin embargo, especularon que, dada una solución casi óptima, podríamos ser capaces de encontrar la óptima o probarla agregando un pequeño número de desigualdades adicionales (recortes). Utilizaron esta idea para resolver su problema inicial de 49 ciudades utilizando un modelo de cadena. Descubrieron que solo necesitaban 26 recortes para llegar a una solución para su problema de 49 ciudades. Si bien este documento no dio un enfoque algorítmico a los problemas de TSP, las ideas que se encuentran dentro de él fueron indispensables para crear métodos de solución exactos para el TSP,^[6] Además de los métodos de plano de corte, Dantzig, Fulkerson y Johnson utilizaronalgoritmos de ramificación y unión quizás por primera vez. ^[6]

En las siguientes décadas, el problema fue estudiado por muchos investigadores de matemáticas , ciencias de la computación , química , física y otras ciencias. Sin embargo, en la década de 1960 se creó un nuevo enfoque, que en lugar de buscar soluciones óptimas, se produciría una solución cuya longitud esté probadamente limitada por un múltiplo de la longitud óptima, y ​​al hacerlo crear límites más bajos para el problema; Estos pueden ser utilizados con enfoques ramificados y vinculados. Un método para hacer esto fue crear un árbol de expansión mínima del gráfico y luego duplicar todos sus bordes, lo que produce el límite de que la longitud de un recorrido óptimo es como máximo el doble del peso de un árbol de expansión mínima. ^[6]

Christofides hizo un gran avance en este enfoque de dar un enfoque para el cual conocemos el peor de los casos. Algoritmo de Christofides dado en 1976, en el peor de los casos es 1,5 veces más largo que la solución óptima. Como el algoritmo era tan simple y rápido, muchos esperaban que daría paso a un método de solución casi óptimo. Este sigue siendo el método con el mejor de los peores escenarios. Sin embargo, para un caso especial bastante general del problema, fue superado por un pequeño margen en 2011. ^[8]

Richard M. Karp demostró en 1972 que el problema del ciclo hamiltoniano era NP completo , lo que implica la dureza NP de TSP. Esto proporcionó una explicación matemática para la aparente dificultad computacional de encontrar recorridos óptimos.

Se hicieron grandes progresos a fines de los años setenta y ochenta, cuando Grötschel, Padberg, Rinaldi y otros lograron resolver con exactitud instancias con hasta 2.392 ciudades, utilizando planos de corte y ramificación y atado .

En la década de 1990, Applegate , Bixby , Chvátal y Cook desarrollaron el programa Concorde que se ha utilizado en muchas soluciones de grabación recientes. Gerhard Reinelt publicó el TSPLIB en 1991, una colección de casos de referencia de diversa dificultad, que ha sido utilizado por muchos grupos de investigación para comparar resultados. En 2006, Cook y otros calcularon un recorrido óptimo a través de una instancia de 85,900 ciudades dada por un problema de diseño de microchip, actualmente la instancia TSPLIB resuelta más grande. Para muchas otras instancias con millones de ciudades, se pueden encontrar soluciones que están garantizadas dentro del 2-3% de un recorrido óptimo. ^[9]

Descripción [ editar ]

Como un problema gráfico [ editar ]

TSP simétrico con cuatro ciudades

TSP se puede modelar como un gráfico ponderado no dirigido , de modo que las ciudades son los vértices del gráfico , las rutas son los bordes del gráfico y la distancia de una ruta es el peso del borde. Es un problema de minimización que comienza y termina en un vértice específico después de haber visitado el vértice exactamente una vez. A menudo, el modelo es un gráfico completo ( es decir, cada par de vértices está conectado por un borde). Si no existe una ruta entre dos ciudades, agregar un borde arbitrariamente largo completará el gráfico sin afectar el recorrido óptimo.

Asimétrico y simétrico [ editar ]

En el TSP simétrico , la distancia entre dos ciudades es la misma en cada dirección opuesta, formando un gráfico no dirigido . Esta simetría reduce a la mitad el número de posibles soluciones. En el TSP asimétrico , las rutas pueden no existir en ambas direcciones o las distancias pueden ser diferentes, formando un gráfico dirigido . Las colisiones de tráfico , las calles de un solo sentido y las tarifas aéreas para ciudades con diferentes tarifas de salida y llegada son ejemplos de cómo esta simetría podría romperse.

Problemas relacionados [ editar ]

• Una formulación equivalente en términos de teoría de grafos es: dado un gráfico ponderado completo (donde los vértices representarían las ciudades, los bordes representarían los caminos y los pesos serían el costo o la distancia de ese camino), encuentre un ciclo hamiltoniano con El menor peso.
• El requisito de regresar a la ciudad inicial no cambia la complejidad computacional del problema, vea el problema de la ruta de Hamilton .
• Otro problema relacionado es el problema del vendedor ambulante de cuello de botella (TSP de cuello de botella): encuentre un ciclo hamiltoniano en un gráfico ponderado con el peso mínimo del borde más pesado . Por ejemplo, evitar calles estrechas con grandes autobuses. ^[10] El problema es de considerable importancia práctica, aparte de las áreas evidentes de transporte y logística. Un ejemplo clásico es en la fabricación de circuitos impresos : programación de una ruta del taladromáquina para perforar agujeros en una PCB. En las aplicaciones de mecanizado o perforación robóticas, las "ciudades" son partes de la máquina o agujeros (de diferentes tamaños) para perforar, y el "costo de viaje" incluye tiempo para reorganizar el robot (problema de secuencia de trabajo de una sola máquina). ^[11]
• El problema generalizado del vendedor ambulante , también conocido como el "problema político itinerante", se refiere a los "estados" que tienen (una o más) "ciudades" y el vendedor tiene que visitar exactamente una "ciudad" de cada "estado". Se encuentra una aplicación al ordenar una solución al problema del material de corte para minimizar los cambios de cuchilla. Otro tiene que ver con la perforación en la fabricación de semiconductores , véase, por ejemplo, la Patente de Estados Unidos 7.054.798 . Noon y Bean demostraron que el problema generalizado del vendedor ambulante puede transformarse en un problema estándar del vendedor ambulante con el mismo número de ciudades, pero una matriz de distancia modificada .
• El problema de ordenamiento secuencial trata el problema de visitar un conjunto de ciudades donde existen relaciones de precedencia entre las ciudades.
• Una pregunta de entrevista común en Google es cómo enrutar datos entre nodos de procesamiento de datos; las rutas varían según el tiempo para transferir los datos, pero los nodos también difieren según su capacidad informática y almacenamiento, lo que agrava el problema de dónde enviar los datos.
• El problema del comprador viajero trata con un comprador al que se le encarga comprar un conjunto de productos. Puede comprar estos productos en varias ciudades, pero a diferentes precios y no todas las ciudades ofrecen los mismos productos. El objetivo es encontrar una ruta entre un subconjunto de las ciudades, que minimice el costo total (costo de viaje + costo de compra) y que permita la compra de todos los productos requeridos.

Formulaciones de programación lineal entera [ editar ]

El TSP puede formularse como un programa lineal entero . ^{[12] [13] [14]} Se conocen varias formulaciones. Dos formulaciones notables son la formulación Miller-Tucker-Zemlin (MTZ) y la formulación Dantzig-Fulkerson-Johnson (DFJ). La formulación DFJ es más fuerte, aunque la formulación MTZ sigue siendo útil en ciertos entornos. ^[15] [16]

Formulación de Miller-Tucker-Zemlin [ editar ]

Rotula las ciudades con los números 1, ..., ny define:

{\ displaystyle x_ {ij} = {\ begin {cases} 1 & {\ text {el camino va desde la ciudad}} i {\ text {to city}} j \\ 0 & {\ text {else}} \ end {cases }}}

Para i = 1, ..., n , let$${\ displaystyle u_ {i}} ser una variable ficticia y finalmente tomar $${\ displaystyle c_ {ij}}ser la distancia de la ciudad i a la ciudad j . Entonces TSP puede escribirse como el siguiente problema de programación lineal de enteros:

{\ displaystyle {\ begin {alineado} \ min & \ sum _ {i = 1} ^ {n} \ sum _ {j \ neq i, j = 1} ^ {n} c_ {ij} x_ {ij} \ dos puntos && \\ & x_ {ij} \ in \ {0,1 \} && i, j = 1, \ ldots, n; \\ & u_ {i} \ in \ mathbf {Z} && i = 2, \ ldots, n; \\ & \ sum _ {i = 1, i \ neq j} ^ {n} x_ {ij} = 1 && j = 1, \ ldots, n; \\ & \ sum _ {j = 1, j \ neq i} ^ {n} x_ {ij} = 1 && i = 1, \ ldots, n; \\ & u_ {i} -u_ {j} + nx_ {ij} \ leq n-1 && 2 \ leq i \ neq j \ leq n; \ \ & 0 \ leq u_ {i} \ leq n-1 && 2 \ leq i \ leq n. \ End {alineado}}}

El primer conjunto de igualdades requiere que se llegue a cada ciudad desde exactamente otra ciudad, y el segundo conjunto de igualdades requiere que desde cada ciudad haya una salida hacia exactamente otra ciudad. Las últimas restricciones obligan a que solo haya un recorrido único que cubra todas las ciudades, y no dos o más recorridos desarticulados que colectivamente cubran todas las ciudades. Para demostrar esto, se muestra a continuación (1) que cada solución factible contiene solo una secuencia cerrada de ciudades, y (2) que para cada recorrido que cubre todas las ciudades, hay valores para las variables ficticias$${\ displaystyle u_ {i}} que satisfacen las limitaciones.

Para demostrar que cada solución factible contiene solo una secuencia cerrada de ciudades, es suficiente mostrar que cada subtour en una solución factible pasa por la ciudad 1 (señalando que las igualdades aseguran que solo pueda haber una gira de este tipo). Porque si sumamos todas las desigualdades correspondientes a$${\ displaystyle x_ {ij} = 1}para cualquier subtour de k pasos que no pasen por la ciudad 1, obtenemos:

$${\ displaystyle nk \ leq (n-1) k,}

Lo cual es una contradicción.

Ahora se debe demostrar que para cada recorrido que cubre todas las ciudades, hay valores para las variables ficticias $${\ displaystyle u_ {i}} que satisfacen las limitaciones.

Sin pérdida de generalidad, defina el recorrido como originario (y finalizado) en la ciudad 1. Elija $${\ displaystyle u_ {i} = t}si se visita la ciudad i en el paso t ( i , t = 1, 2, ..., n). Luego

$${\ displaystyle u_ {i} -u_ {j} \ leq n-1,}

ya que $${\ displaystyle u_ {i}}puede ser no mayor que n y$${\ displaystyle u_ {j}}puede ser no menos de 1; por lo tanto, las restricciones se cumplen siempre$${\ displaystyle x_ {ij} = 0.} por $${\ displaystyle x_ {ij} = 1}, tenemos:

$${\ displaystyle u_ {i} -u_ {j} + nx_ {ij} = (t) - (t + 1) + n = n-1,}

satisfaciendo la restricción.

Formulación de Dantzig-Fulkerson-Johnson [ editar ]

Rotula las ciudades con los números 1, ..., ny define:

{\ displaystyle x_ {ij} = {\ begin {cases} 1 & {\ text {el camino va desde la ciudad}} i {\ text {to city}} j \\ 0 & {\ text {else}} \ end {cases }}}

Tomar $${\ displaystyle c_ {ij}}ser la distancia de la ciudad i a la ciudad j . Entonces TSP puede escribirse como el siguiente problema de programación lineal de enteros:

{\ displaystyle {\ begin {alineado} \ min & \ sum _ {i = 1} ^ {n} \ sum _ {j \ neq i, j = 1} ^ {n} c_ {ij} x_ {ij} \ dos puntos && \\ & 0 \ leq x_ {ij} \ leq 1 && i, j = 1, \ ldots, n; \\ & \ sum _ {i = 1, i \ neq j} ^ {n} x_ {ij} = 1 && j = 1, \ ldots, n; \\ & \ sum _ {j = 1, j \ neq i} ^ {n} x_ {ij} = 1 && i = 1, \ ldots, n; \\ & \ sum _ {i \ in Q} {\ sum _ {j \ in Q} {x_ {ij}}} \ leq | Q | -1 && \ forall Q \ subsetneq \ {1, \ ldots, n \}, | Q | \ geq 2 \\\ end {alineado}}}

La última restricción de la formulación de DFJ asegura que no haya sub-recorridos entre los vértices que no comienzan, por lo que la solución devuelta es un recorrido único y no la unión de recorridos más pequeños. Debido a que esto conduce a un número exponencial de posibles restricciones, en la práctica se resuelve con la generación de columnas retrasadas .