¿Has utilizado un algoritmo de vendedor ambulante para resolver un problema?

Question

Estudié TSP en la universidad en el contexto de NP Completeness. Nunca he tenido una situación en la que se aplique a un problema práctico. Un poco de investigación muestra que se ha utilizado para elegir el camino más barato para mover un taladro, que está haciendo agujeros en las placas de circuito. Eso es casi todo lo que pude encontrar.

¿Lo estás usando? ¿Qué otras aplicaciones prácticas tiene la TSA?

Answer 1

Como con otros en este hilo, construí una solución para un problema completo de NP en la universidad (era un proyecto paralelo para un amigo): un programa de programación. En el momento en que acepté trabajar en su problema, no sabía qué era NP completo. Más tarde me di cuenta de que había encontrado algunas heurísticas bastante buenas para resolver el problema, pero, por supuesto, el verdadero truco era saber cuándo decirle al usuario que no había solución y que habían sobrecargado el problema.

Fue una excelente manera de reunir mis eventuales clases teóricas y el mundo real.

Nuevamente, heurística y "lo suficientemente cerca" generalmente son buenos para usos del mundo real donde se prefieren soluciones casi óptimas debido al costo de encontrar e implementar la solución ideal.

Answer 2

Una vez se me asignó la tarea de escribir un programa para llenar un área rectangular de manera bastante uniforme con un '' garabato '' - una línea curva que no se auto-intersecta. Mi primer intento fue generar puntos aleatorios dentro del rectángulo e intentar encontrar un recorrido por ellos (no necesariamente el más corto absoluto). Lamentablemente, este enfoque no funcionó muy bien y lo abandoné.

Al final resolví el problema:

??

Mi método exitoso no estaba relacionado con el TSP, pero para los curiosos lo resumiré:

Comience con un solo segmento de línea. Ahora bucle: si una línea es "demasiado larga", divídala en dos. Mueva cada punto un poco al azar, pero haga que los puntos se repelen entre sí. Termine el ciclo cuando se puede hacer poco progreso. Hay detalles, pero espero que entiendas la idea.

Por supuesto, esto produce una trayectoria angular (que habría sido aceptable) pero es fácil convertir las esquinas en arcos suaves.

Y sí, conservé el código.

Answer 3

Nunca lo he usado personalmente, pero otra aplicación además de perforar placas de circuito es si quieres ir a diferentes lugares, por ejemplo, para vender aspiradoras. Podría usar una solución del problema para decidir la forma más barata de visitar todos los lugares exactamente una vez.

Answer 4

Saber cuándo un problema es NP-hard es útil para excluir soluciones que impliquen resolver ese problema. Cada vez que veas que TSP (o cualquier otro problema NP-duro) se vuelve loco por problemas de tamaño no trivial que sabes estás yendo por el camino equivocado. No solo lo sabes, sino que sabes por qué y puedes decirle con confianza a tu jefe / compañero de equipo / a cualquier persona.

Dicho esto, http://en.wikipedia.org/wiki/CONCORDE revela que :

  

Concorde se ha aplicado a problemas   de mapeo genético, [1] función proteica   predicción, [2] ruta del vehículo, [3]   conversión de imágenes de mapa de bits a   dibujos lineales continuos, [4]   programar movimientos de barcos para sísmica   encuestas [5] y en el estudio de   propiedades de escala de combinatoria   problemas de optimización. [6]

Answer 5

Sí, lo uso en la aplicación Geocaching para la planificación de rutas.

Actualmente usa una distancia en línea recta entre los puntos, pero debería usar correctamente (cuando me acerque a él) caminos para calcular las distancias entre los puntos.

http://code.google.com/p/gpsturbo/

Answer 6

La mayoría de las veces no desea utilizar un algoritmo que resuelva el problema NP-Complete / Hard. Solo desea un algoritmo que sea "suficientemente bueno". Generalmente se basan en heurísticas y ofrecen aproximaciones razonables.

Tuve un problema que fue una instancia de Independent-Set (NP-Complete), pero encontré un algoritmo codicioso que dio muy buenos resultados en la gran mayoría de los casos, y tuve un tiempo de ejecución eficiente.

Answer 7

Muchos tipos de pedidos optimizados, como la recolección de vehículos compartidos, la entrega de paquetes de UPS, etc., siempre que los requisitos de recorrido del nodo se puedan expresar en una dimensión de esfuerzo, como el tiempo o la distancia.

Answer 8

TSP es el hello world de los problemas completos de NP. En su forma canónica pura, no lo encontrarás en la naturaleza a menudo ( demos como esta no incluida ), pero un gran subconjunto de problemas completos de NP están relacionados o incluso se basan en TSP, como:

• Enrutamiento del vehículo (incluye el enrutamiento del camión de suministros)
• Aerolínea / Rutas de vuelo
• Enrutamiento del tren
• Enrutamiento de la máquina de arado de pistas de esquí

Cada uno de estos tiene restricciones adicionales específicas de dominio, que los hacen más difíciles de resolver. Entonces TSP es una buena introducción a los problemas completos de NP, para entender su naturaleza.

Answer 9

Pocos problemas en la vida real coinciden con lo que aprendes en la clase de matemáticas. Los problemas se simplifican y abstraen para que pueda ver las matemáticas y no distraerse con los detalles. El mejor ejemplo de la vida real de los TSP grandes, como usted mencionó, en realidad no involucra a ningún vendedor ambulante: se trata de programar máquinas que tienen trabajos que realizar con cristalografía de rayos X donde tienes que orientar una muestra de un cristal en varios ángulos diferentes.

Answer 10

Esta compañía se basó en un algoritmo TSP mejorado.

http://www.pointserve.com/

Dirigen a los instaladores y reparadores de TV por cable a Nueva York, entre otros problemas.

Answer 11

Debido a que los humanos generalmente pueden resolver problemas de TSP a la par o mejor que la mayoría de los algoritmos para mapas con 20-60 nodos, no es muy común que una computadora resuelva el problema. Cuando el costo es lo suficientemente alto, hacer que la computadora obtenga una mejora del 1-2% sobre un humano puede valer el costo de realizar el cálculo. Si la ruta no cambia, entonces se puede justificar pasar algún tiempo optimizándola. Esto es común en el diseño de circuitos integrados.

Los sitios web de viajes de aerolíneas utilizan una versión especializada del problema de TSP cuando le muestran una lista de aerolíneas y los precios de cada ruta. La diferencia es en lugar de distancia, optimizan el costo y, ciertamente, ¡no es necesario visitar cada ciudad una vez! Digamos que quieres volar de LGA a LAX. Hay alrededor de 1/2 docena de rutas directas, y un número infinito de otras rutas. Puede sugerir LGA- > ORD- > LAX o LGA- > DWF- > LAX. Los seres humanos, que pueden cotizar manualmente las rutas, a veces pueden encontrar tarifas más bajas que las que buscan los sitios de viajes. Por lo general, las personas no quieren más de dos conexiones, pero no hay un límite superior para la cantidad de conexiones para un vuelo determinado.

Lo he usado para resolver rutas para mi Juego de iPhone de vendedor ambulante . Lo interesante es que las personas son muy buenas para resolver la ruta más corta, pero no para resolver la ruta más larga. Las rutas más largas y más cortas tienen la misma complejidad, pero las personas parecen capacitadas para poder encontrar rutas más cortas, a menudo más rápidas y mejores de lo que una computadora puede hacer.

Answer 12

En mi primer trabajo creamos una aplicación de programación de atención domiciliaria.
Resolvimos el problema de TSP con algunas restricciones de tiempo no lineales y con una función adicional de costo no lineal.
Utilizamos un solucionador no óptimo para resolver el problema.

Answer 13

¿No estaría Google Maps (y cualquier otro software de enrutamiento basado en mapas) utilizando algún tipo de vendedor ambulante para resolver las instrucciones de manejo?

Answer 14

No he usado TSP hasta donde sé, pero he trabajado en varios robots autónomos para atravesar un laberinto. Entonces me pregunto si TSP podría aplicarse a la resolución de laberintos.