¿Cuál es el nombre de esta variante logística de TSP?

Tengo un problema logístico que puede verse como una variante de $\text{TSP}$. Es tan natural, estoy seguro de que se ha estudiado en la investigación de operaciones o algo similar. Aquí hay una forma de ver el problema.

Tengo almacenes en el plano cartesiano. Hay un camino desde un almacén a cualquier otro almacén y la métrica de distancia utilizada es la distancia euclidiana. Además, hay elementos diferentes. Cada elemento puede estar presente en cualquier número de almacenes. Tenemos un colector y se nos da un punto de partida por ello, por ejemplo el origen . El colector recibe una orden, por lo que una lista de artículos. Aquí, podemos suponer que la lista solo contiene elementos distintos y solo uno de cada uno. Debemos determinar el recorrido más corto a partir de visita a varios almacenes para que podamos recoger cada artículo del pedido.$P$$n$$1 \leq i \leq n$$s$$(0,0)$$s$

Aquí hay una visualización de una instancia generada aleatoriamente con . Los almacenes se representan con círculos. Los rojos contienen el elemento , los azules el elemento y los verdes el elemento . Dados algunos puntos de partida el pedido ( ), debemos elegir un almacén rojo, uno azul y uno verde para que se pueda completar el pedido. Por accidente, no hay almacenes multicolores en este ejemplo, por lo que todos contienen exactamente un artículo. Esta instancia particular es un caso de set-TSP .$P = 35$$1$$2$$3$$s$$1,2,3$

Puedo demostrar que el problema es de hecho -hard. Considere una instancia donde cada artículo se encuentra en un almacén diferente . El orden es tal que contiene cada artículo. Ahora debemos visitar cada almacén y encontrar el recorrido más corto al hacerlo. Esto es equivalente a resolver una instancia de .$\mathcal{NP}$$i$$P_i$$P_i$$\text{TSP}$

Siendo tan obviamente útil al menos en el contexto de logística, enrutamiento y planificación, estoy seguro de que esto se ha estudiado antes. Tengo dos preguntas:

1. ¿Cuál es el nombre del problema?
2. ¿Qué tan bien se puede esperar aproximar el problema (suponiendo )?$\mathcal{P} \neq \mathcal{NP}$

Estoy bastante contento con el nombre y / o referencia (s) al problema. Quizás la respuesta al segundo punto se sigue fácilmente o puedo averiguarlo yo mismo.

El problema está en si el número de elementos es constante.$\mathrm{P}$

Sea el número de elementos (independiente de ). Para cada pedido de artículos, use el rastreo para probar todas las rutas permitidas: primero pasa por algún almacén para el primer artículo (prueba todos los almacenes), luego uno para el segundo artículo y así sucesivamente.$K$$n$

Hay ordenamientos los artículos. Sea el número de almacenes para el artículo . El número de rutas es . Por lo tanto, el tiempo de ejecución del algoritmo anterior es , que es polinomio para fijo .$O(K!)$$W_i$$i$$\prod_{i=1}^K W_i \leq \prod_{i=1}^K n = n^K$$O(K! n^K)$$K$

Si el número de elementos puede ser lineal en , el problema es al menos tan difícil de aproximar como : puede tomar una instancia de , hacer un elemento para cada vértice como observó y luego agregar vértices adicionales muy lejos de todos los demás vértices para inflar (y, por lo tanto, permitir suficientes elementos para que cada vértice de la instancia de tenga un elemento diferente), sin destruir la dureza de la accesibilidad de . Tenga en cuenta que si sus puntos están en el plano euclidiano, esto realmente no lo ayudará, ya que hay un para planar .$n$$TSP$$TSP$$n$$TSP$$TSP$$PTAS$$TSP$

Entre otros, este problema puede verse como una instancia del Problema del Comprador Viajero. $\text{TPP}$ es una generalización de $\text{TSP}$ y fue propuesto por primera vez por T. Ramesh, problema del comprador viajero, 1981. El problema es el siguiente:

Nos dan un set $M = \{ 1, ..., m \}$ de mercados y un conjunto de $N = \{ 1, ..., n \}$de productos. También nos dan$c_{ij}$, el costo de viajar desde la ciudad $i$ a la ciudad $j$y no negativo $d_{ij}$, el costo de un producto $i$ en el mercado $j$. El comprador comienza desde su ciudad de origen (por ejemplo, ciudad$1$) y viaja a un subconjunto de $m$ ciudades y compra cada una de las $n$productos de las ciudades que visita y regresa a su ciudad natal. El objetivo es encontrar un recorrido para el comprador que minimice la suma del viaje y los costos de compra.

Entonces, en términos de la pregunta original, los almacenes son mercados. Cada artículo disponible en un mercado tiene el mismo precio. Si el artículo$i$ no está disponible en un mercado $j$, su precio $d_{ij}$ se establece en un valor alto.

Además de contener $\text{TSP}$, $\text{TPP}$ contiene premios coleccionables $\text{TSP}$, problema de ubicación de la instalación no capacitada, problema del árbol Steiner grupal y el problema de la cobertura del conjunto como sus casos especiales inmediatos. Para la dureza, siguiendo los resultados de dureza actuales para la cubierta establecida, se deduce que no hay PTAS para$\text{TPP}$ incluso con costos de viaje métricos cuya relación de rendimiento es mejor que $(1-o(1))\ln n$ a no ser que $\mathcal{P} = \mathcal{NP}$. Para una discusión y formulación adicional como IP, ver por ejemplo R. Ravi y FS Salman, Algoritmos de aproximación para el problema del comprador viajero y sus variantes en el diseño de redes, 1999 . La entrada de Wikipedia para TPP también ofrece enlaces a algunos enfoques heurísticos.

Lo que describiste suena más como un problema de planificación en IA. Parece lo que podría modelarse con un lenguaje de planificación, como STRIPS , ADL, PDDL, etc. Una vez modelado, el plan puede resolverse mediante uno de los muchos algoritmos / heurísticos de planificación, que generalmente son algoritmos de búsqueda de espacio de estados. Los enlaces de Wiki deberían ayudarlo a comenzar. Un capítulo de planificación en cualquier libro de texto de IA también puede ayudar. Un ejemplo de planificador PDDL es el software GraphPlanner .

Por supuesto, algunas instancias bastante degeneradas de este problema pueden ser equivalentes a TSP, este problema no es, en general, el mismo que TSP, ni es Set TSP. Tanto en TSP como en Set TSP, el conjunto de ciudades (almacenes) a visitar está predefinido. Aquí, realmente no nos importa qué almacenes se visitan, sino que solo nos preocupamos por cumplir un pedido de la manera más económica y eficiente posible. Podría tener órdenes que no se pueden cumplir. Un planificador volverá con un plan vacío o parcial en tal caso, un informe de no satisfacción. En general, se sabe que el problema de la capacidad de saturación del plan es completo para PSPACE. En TSP o Set TSP, siempre existe un recorrido óptimo, aunque puede que no sea único.