algorithm - viajante - vendedor individual en amazon
Viajando vendedor con varios vendedores? (8)
¿Por qué no convierte su TSP múltiple en el TSP tradicional?
Este es un problema bien conocido (la transformación de múltiples vendedores TSP en TSP) y puede encontrar varios artículos sobre él.
Para la mayoría de las transformaciones, básicamente copia su depósito (donde los vendedores comienzan y terminan) en varios depósitos (en su caso 2), hace que los pesos de borde de una manera forzan a un TSP a regresar al depósito dos veces, y luego retire el depósito. Dos depósitos y conviértelos en uno.
Voila! Conseguí dos tours de costo mínimo que cubren los vértices exactamente una vez.
Tengo un problema que se ha reducido efectivamente a un problema de vendedor ambulante con varios vendedores. Tengo una lista de ciudades para visitar desde una ubicación inicial, y tengo que visitar todas las ciudades con un número limitado de vendedores.
Estoy tratando de llegar a una heurística y me preguntaba si alguien podría dar una mano. Por ejemplo, si tengo 20 ciudades con 2 vendedores, el enfoque que pensé tomar es un enfoque de 2 pasos. Primero, divida las 20 ciudades al azar en 10 ciudades para 2 vendedores cada una, y encontraré el recorrido para cada una como si fuera independiente para algunas iteraciones. Después, me gustaría intercambiar o asignar una ciudad a otro vendedor y encontrar el recorrido. Efectivamente, sería un TSP y luego un problema de makepan mínimo. El problema con esto es que sería demasiado lento y una buena generación de intercambios o asignaciones de ciudades en un vecindario es difícil.
¿Alguien puede dar un consejo sobre cómo podría mejorar lo anterior?
EDITAR:
Se conoce la ubicación geográfica de cada ciudad y los vendedores comienzan y terminan en los mismos lugares. El objetivo es minimizar el tiempo máximo de viaje, lo que hace que este tipo de problema sea mínimo. Entonces, por ejemplo, si el vendedor 1 tarda 10 horas y el vendedor 2 tarda 20 horas, el tiempo máximo de viaje sería de 20 horas.
Acabo de empezar a leer tu pregunta usando un algoritmo genético. solo use dos algoritmos genéticos al mismo tiempo, uno puede resolver cómo asignar ciudades a los vendedores y el otro puede resolver el TSP para cada vendedor que tenga.
Como se mencionó en la respuesta anterior, la solución de agrupación jerárquica funcionará muy bien para su problema. Sin embargo, en lugar de continuar disolviendo los clústeres hasta que tenga una sola ruta, deténgase cuando tenga n, donde n es el número de vendedores que tiene. Probablemente pueda mejorarlo agregando algunas paradas "falsas" para mejorar la probabilidad de que sus clusters terminen uniformemente separados del destino inicial si los clusters iniciales son demasiado dispares. No es óptimo, pero no va a obtener una solución óptima para un problema como este. Me gustaría crear una aplicación que visualice el problema y luego probar muchas variantes de la solución para saber si su heurística es lo suficientemente óptima.
En cualquier caso, no aleatorizaría los clústeres, lo que haría que la mayoría de los clústeres no sean óptimos.
Cuando empiezas a hablar de varios vendedores, empiezo a pensar en la optimización del enjambre de partículas. He encontrado mucho éxito con esto usando un algoritmo de búsqueda gravitacional. Aquí hay un documento (extenso) que encontré cubriendo el tema. http://eprints.utm.my/11060/1/AmirAtapourAbarghoueiMFSKSM2010.pdf
Eche un vistazo a esta pregunta (562904): si bien no es idéntica a la suya, debería haber algún buen alimento para el pensamiento y referencias para un estudio posterior.
Mi primer pensamiento al leer la descripción del problema sería utilizar un enfoque estándar para el problema del vendedor (buscar en Google uno apropiado ya que nunca tuve que escribir código para él); Luego toma el resultado y divídelo por la mitad. Entonces, su algoritmo podría ser decidir dónde está la "mitad": tal vez sea la mitad de las ciudades, o tal vez se base en la distancia, o tal vez alguna combinación. O busca el resultado para la distancia más grande entre dos ciudades y elige eso como la separación entre la última ciudad del vendedor # 1 y la primera ciudad del vendedor # 2. Por supuesto que no se limita a dos vendedores, se dividirían en x piezas; Pero en general, la idea es que su solución TSP de 1 vendedor estándar ya debería haber colocado las ciudades "cercanas" una al lado de la otra en el gráfico de viaje, para que no tenga que crear un algoritmo de agrupación separado ...
De todos modos, estoy seguro de que hay mejores soluciones, pero esto parece ser un buen primer acercamiento para mí.
No empezaría a escribir un algoritmo para un tema tan complicado (a menos que sea mi trabajo diario: escribir algoritmos de optimización). ¿Por qué no recurre a una solución genérica como http://www.optaplanner.org/ ? Debe definir su problema y el programa utiliza algoritmos que los principales desarrolladores tardaron años en crear y optimizar.
TSP es un problema difícil. Multi-TSP es probablemente mucho peor. No estoy seguro de que pueda encontrar buenas soluciones con métodos ad-hoc como este. ¿Has probado métodos meta-heurísticos? Primero intentaría usar el método Cross Entropy: no debería ser demasiado difícil usarlo para tu problema. De lo contrario, busque Algoritmos genéricos, Optimización de colonias de hormigas, Recocido simulado ...
Consulte "Un tutorial sobre el método de la entropía cruzada" de Boer et al. Explican cómo utilizar el método CE en el TSP. Una adaptación simple para su problema podría ser definir una matriz diferente para cada vendedor.
Es posible que desee asumir que solo desea encontrar la partición óptima de ciudades entre los vendedores (y delegar el recorrido más corto para cada vendedor en una implementación TSP clásica). En este caso, en la configuración de Entropía cruzada, considera una probabilidad de que cada ciudad Xi esté en el recorrido del vendedor A: P (Xi en A) = pi. Y trabajas, en el espacio de p = (p1, ... pn). (No estoy seguro de que funcionará muy bien, porque tendrá que resolver muchos problemas de TSP).