Algoritmo: planificación de viaje

Question

Necesito planificar un viaje que conecte n ubicaciones en el mar con un origen y un destino especificados con las siguientes limitaciones.
El viaje tiene que tocar todas las ubicaciones.
Si hay una reserva de A a B entonces A tiene que ser tocado antes de que B
El gasto de tiempo en cada lugar varía (depende de las reservas a ese lugar)
Cada lugar tiene una ventana de trabajo. Si el buque llega antes de la ventana de trabajo, tiene que esperar.
Nota: Los algoritmos de "árbol de expansión mínimo" pueden no ser como el tiempo requerido en cada puerto depende de la ruta anterior (debido a la ventana de trabajo)
¿Hay algún algoritmo disponible para esto?

Answer 1

Ant colony optimization parece ser la mejor solución conocida a este. Tenga en cuenta que este es un NP problem, en realidad incluso un problema NP-completo. Esto significa que es "fácil" verificar que una solución sea correcta, pero es "difícil" encontrarla. La única forma de encontrar la solución "óptima" sería probar todas las soluciones posibles, comparar los resultados y tomar el mejor. Por supuesto, eso no es aceptable si quiere resolverlo dentro de un marco de tiempo razonable.

Los algoritmos de ACO encontrarán una buena solución, cerca del óptimo. Lo digo de cerca, ya que AFAIK no puede garantizar encontrar siempre el mejor. Mejores soluciones pueden existir. Sin embargo, a menudo no es necesario encontrar realmente la mejor solución posible, una solución que es simplemente "muy buena" hará el truco y aquí ACO es exactamente lo que estás buscando. Puede encontrar la solución en intervalos de tiempo razonables y la solución será segura.

En su caso, necesita modificarlo un poco. Por lo general, solo tratará de encontrar la ruta más corta, solo teniendo en cuenta la ruta. En su caso, debe tener en cuenta su ventana de trabajo, las reservas y el tiempo invertido en una ubicación. Pero estas son solo modificaciones de "cómo viajan las hormigas", el algoritmo básico sigue siendo el mismo y seguirá funcionando igual.

Answer 2

Ver Traveling salesman problem

Answer 3

Este es un problema de vendedor ambulante con una modificación que agrega la restricción de la ventana de trabajo ... lo que significa que la solución a este problema será aún más difícil de encontrar que el problema del vendedor ambulante estándar.

Tengo varios enfoques que funcionan decentemente para dar soluciones aproximadas.

1. Genetic Algorithms
2. Tabu Search
3. Randomized Algorithm (Ej, paseo aleatorio)

No sé si se aplica a su problema, la parte superior de mi cabeza Yo digo que no lo hace , pero dynamic programming puede ocasionalmente usarse en problemas insolubles.

Answer 4

Hay mucho trabajo en este problema. Va por diferentes nombres

1. problema vendedor ambulante (enrutamiento del vehículo) con ventanas de tiempo y restricciones de precedencia.
2. Problema de recogida y entrega.

Hay una gran cantidad de investigaciones sobre este problema, muchas de ellas en la Investigación de Operaciones Journals. Este problema es, en general, NP-Hard, por lo que una solución general exacta al problema como usted describió, el problema no es práctico, pero puede haber soluciones buenas, exactas o aproximadas a su problema específico. El mejor algoritmo será una función de tus datos.

• ¿Qué tan grande es su conjunto de datos. Si la "n" es relativamente pequeña (30-100), es probable que exista una solución exacta con math programming.
• Qué tan ajustadas son las ventanas de tiempo y las restricciones de precedencia. Si el número de ubicaciones posibles para visitar en cualquier ventana de tiempo es pequeño, entonces es posible una solución como la programación dinámica.
• Si no puede encontrar un caso especial, entonces probablemente quiera combinar un algoritmo de construcción heurística con un postprocesador de búsqueda local. Una alternativa sencilla es la llamada GRASP heurística, donde
• toma una heurística de construcción existente,
• randomize es por lo que múltiples carreras le dará múltiples soluciones,
• ejecutar la versión aleatorizado varias veces
• toma la mejor solución que resulta