algorithm - traveling - travelling salesman problem c++

Vendedor ambulante con nodos repetidos y pesos dinámicos. (6)

¿Desea una solución casi óptima o desea la solución óptima?

Para la solución óptima, todavía hay una buena fuerza bruta. Debido al requisito 1 que involucra la repetición de nodos, deberá asegurarse de buscar primero en la amplitud, no primero en el departamento. De lo contrario, puede terminar en un bucle infinito. Puede eliminar lentamente todas las rutas que excedan su mínimo actual hasta que se agoten todas las rutas y se descubra la ruta mínima.

Dada una lista de ciudades y el costo de volar entre cada ciudad, estoy tratando de encontrar el itinerario más barato que visite todas estas ciudades. Actualmente estoy usando una solución MATLAB para encontrar la ruta más barata, pero ahora me gustaría modificar el algoritmo para permitir lo siguiente:

nodos repetidos: se deben permitir los nodos repetidos, ya que viajar a través de las ciudades centrales puede resultar en una ruta más barata
Pesos de borde dinámicos : los vuelos de ida y vuelta tienen un costo diferente (generalmente más bajo) a dos vuelos de ida equivalentes

Por ahora, estoy ignorando el tema de las fechas de vuelo y asumiendo que es posible viajar de cualquier ciudad a cualquier otra ciudad.

¿Alguien tiene alguna idea de cómo resolver este problema? Mi primera idea fue utilizar un método de optimización evolutivo como GA o ACO para resolver el punto 2, y simplemente ajustar las ponderaciones de los bordes al evaluar la función objetivo en función de si el itinerario contiene vuelos de ida y vuelta, pero quizás alguien más tenga una mejor idea.

(Nota: estoy usando MATLAB, pero no estoy buscando específicamente soluciones codificadas, más solo ideas de alto nivel sobre qué algoritmos pueden usarse).

Editar: después de pensar en esto un poco más, permitir "repetir nodos" parece ser una limitación demasiado flexible. Podríamos restringir aún más el problema para que, aunque los nodos se pueden visitar repetidamente, cada borde dirigido solo se pueda visitar una vez como máximo. Parece razonable ignorar cualquier itinerario que incluya el mismo vuelo en la misma dirección más de una vez.

En primer lugar, ¿cuál es el número aproximado de ciudades en su conjunto de problemas? (¿Hasta 100? ¿Más de 100?) Tengo bastante experiencia con GA (no ACO), y como dice el epitafio, tiene un poco de aspecto de juego. Para algunos comentarios, podría detenerse en una solución brutalmente ineficiente. Entonces, lo que he hecho en el pasado es usar GA como la primera opción, comparar la respuesta con algún límite inferior, y si eso parece estar "fuera de lugar", ejecute un segundo algoritmo (generalmente menos eficiente).

Por supuesto, utilicé muchos términos que no eran estándar, así que asegurémonos de estar de acuerdo con lo que serían en este contexto:

límite inferior - por supuesto, en este caso, MST sería un límite inferior.
"Modo desactivado": si la desigualdad del triángulo se mantiene, un límite superior es UB = 2 * MST. Una buena "salida" en este contexto sería 2 * UB.
Segundo algoritmo: en este caso, tanto un enfoque basado en programación lineal como Christofides serían buenas elecciones.

No lo he probado yo mismo; sin embargo, he read que la implementación del Recocido Simulado para resolver el TSP (o sus variantes) puede producir excelentes resultados. El punto clave aquí es que el Recocido Simulado es muy fácil de implementar y requiere ajustes mínimos, mientras que los algoritmos de aproximación pueden tardar mucho más en implementarse y probablemente son más propensos a errores. Skiena también tiene una page dedicada a solucionadores de TSP específicos.

Resolver el TSP es un problema NP-difícil para sus restricciones de eliminación de subciclos, si elimina alguno de ellos (para sus ciudades centrales) simplemente hace que el problema sea más fácil.

Pero tenga cuidado: TSP tiene similitudes con el problema de asociación en el sentido de que podría obtener itinerarios no válidos como:

Ciudades: Nueva York, Boston, Dallas, Toronto

Camino:

Boston - Nueva York Nueva York - Boston

Dallas - Toronto Toronto - Dallas

lo que está claramente mal, ya que no cruzamos todas las ciudades.

Las restricciones de eliminación del subciclo sirven solo para este propósito. Incluir una ''ciudad central'' suena como si fuera necesario agregar pesos al punto y hacer un híbrido entre problemas de flujo y problemas de tsp. Suena bastante difícil, pero el primer intento puede ser: elimine las restricciones de los subciclos en relación con sus ciudades centrales (y deje todas las demás). Luego puede vincular los subciclos obtenidos para las ciudades centrales.

Buena suerte

Si desea que el costo de la solución producida por el algoritmo se encuentre dentro de 3/2 del óptimo, entonces desea el algoritmo Christofides. ACO y GA no tienen un costo garantizado.

Si limita el problema a viajes de ida y vuelta (es decir, el vendedor solo puede comprar boletos de viaje de ida y vuelta), entonces puede representarse mediante un gráfico no dirigido, y el problema se reduce a encontrar el árbol de expansión mínimo , que se puede hacer de manera eficiente.

En el caso general, no conozco una forma inteligente de usar algoritmos eficientes; GA o similar podría ser una buena manera de ir.