Problema con la grúa apiladora

En optimización combinatoria , el problema de la grúa apiladora es un problema de optimización estrechamente relacionado con el problema del viajante . Su entrada consiste en una colección de pares ordenados de puntos en un espacio métrico , y el objetivo es conectar estos puntos en un ciclo de longitud total mínima que incluya todos los pares, orientados de forma consistente entre sí. Modela problemas de programación de la recogida y entrega de cargas individuales, mediante una grúa apiladora , una grúa de construcción o (en transporte terrestre ) un camión, en una forma simplificada sin restricciones en el tiempo de estas entregas. ^{[ 1 ]} Fue introducido por Frederickson, Hecht y Kim (1978) , con una formulación equivalente en términos de grafos mixtos con aristas dirigidas que modelan los pares de entrada y aristas no dirigidas que modelan sus distancias. Frederickson et al. atribuyen su formulación a una comunicación personal de Daniel J. Rosenkrantz. ^{[ 2 ]}

El problema de la grúa apiladora puede verse como una generalización del problema del viajante en espacios métricos: cualquier instancia del problema del viajante puede transformarse en una instancia del problema de la grúa apiladora, teniendo un par${\displaystyle (p,p)}$para cada punto en la instancia del viajante. En la otra dirección, el problema de la grúa apiladora puede considerarse un caso especial del problema del viajante asimétrico, donde los puntos del problema del viajante asimétrico son los pares de una instancia de la grúa apiladora y la distancia de un par a otro se toma como la distancia desde el punto de entrega del primer par, pasando por su punto de recogida, hasta el punto de entrega del segundo par. Debido a que generaliza el problema del viajante, hereda la misma complejidad computacional : es NP-difícil y al menos igual de difícil de aproximar. ^{[ 2 ]}

Un algoritmo de aproximación basado en el algoritmo de Christofides para el problema del viajante de comercio puede aproximar la solución del problema de la grúa apiladora con una razón de aproximación de 9/5. ^{[ 2 ]}

El problema de diseñar el reverso de un patrón de bordado para minimizar la cantidad total de hilo utilizado está estrechamente relacionado con el problema de la grúa apiladora, pero permite que cada uno de sus pares de puntos (los extremos de las puntadas visibles en el anverso del patrón) se recorra en cualquier dirección, en lugar de requerir que el recorrido pase por todos los pares en una dirección consistente. Es NP-difícil mediante la misma transformación del problema del viajante de comercio y se puede aproximar con una razón de aproximación de 2. ^{[ 3 ]} Otra variación del problema de la grúa apiladora, llamada problema del transporte a demanda , pide la ruta mínima para que un vehículo realice una serie de recogidas y entregas, permitiéndole transportar un número k > 1 de cargas en cualquier punto de su ruta. ^{[ 4 ]}