Cómo resolver el problema del vendedor ambulante en ruby ​​(más de 50 ubicaciones)

Question

Estoy trabajando en una empresa de entregas. Actualmente resolvemos más de 50 rutas de ubicaciones por "mano".

He estado pensando en usar Google Maps API para resolver este problema, pero he leído que hay un límite de 24 puntos.

Actualmente estamos usando rails en nuestro servidor, así que estoy pensando en usar un script de ruby ​​que obtenga las coordenadas de las más de 50 ubicaciones y produzca una solución razonable.

¿Qué algoritmo usaría para abordar este problema?

¿Es Ruby un buen lenguaje de programación para resolver este tipo de problema?

¿Conoces algún script de ruby ​​existente?

Answer 1

Esto podría ser lo que buscas:

Advertencia:

este sitio se marca por Firefox como sitio de ataque - pero no parece ser. De hecho he usado antes sin ningún problema

[Comprobar el historial de revisiones de URL]

rubyquiz parece estar abajo (ha estado abajo por un poco) no obstante usted puede comprobar fuera de Wayback Machine y archive.org a ver que la página: http://web.archive.org/web/20100105132957/http://rubyquiz.com/quiz142.html

Answer 2

Una de las soluciones optimizadas es la Programación dinámica, pero sigue siendo muy costosa O (2 ** n), lo cual no es muy factible, a menos que use algunos clústeres y distribuya informática, ruby ​​o servidor único. para ti.

Le recomendaría que elabore criterios ambiciosos en lugar de usar DP o fuerza bruta, que serían más fáciles de implementar.

Una vez que finalice su programa, puede hacer algunas memoraciones y almacenar los resultados en algún lugar para búsquedas posteriores, que también pueden ahorrarle algunos ciclos.

en términos del código, deberá implementar vértices, bordes que tengan pesos.

es decir: clase de vértice que tienen bordes con pesos, recursivo. que una clase de gráfico que poblará los datos.

Answer 3

Aquí hay un par de trucos:
1: ubicaciones fijas únicas que están relativamente cerca en una gráfica, y convertir esos lugares en un solo nodo en el gráfico principal. Esto te permite ser codicioso sin mucho trabajo.
2: Use un algoritmo de aproximación.
2a: Mi favorito son los viajes bitónicos. Son bastante fáciles de hackear.
ver Boletín

Here's a py lib with a bitonic tour y here's another
Déjame buscar un rubí uno. Tengo problemas para encontrar algo más que el RGL, que tiene problemas de eficiencia ....

actualización
En su caso, el ataque de árbol de expansión mínimo debe ser eficaz. No puedo pensar en un caso en el que sus ciudades no cumplan con la desigualdad del triángulo. Esto significa que debería haber una especie de aproximación relativamente rápida y bastante decente. Particularmente si la distancia es euclidiana, que creo, de nuevo, debe ser.

Answer 4

Incluso con la solución de DP mencionada en otra respuesta, eso requerirá O (10^15) operaciones. Por lo tanto, tendrá que buscar soluciones aproximadas, que probablemente sean aceptables, dado que actualmente las hace a mano. Mira http://en.wikipedia.org/wiki/Travelling_salesman_problem#Heuristic_and_approximation_algorithms

Answer 5

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

Answer 6

Trabajé en el uso de algoritmos meta-heurestic como Ant Colony Optimazation para resolver problemas TSP para el problema Bays29 (29-city), y me dio cerca de soluciones óptimas en muy poco tiempo. Usted puede potencialmente usar el mismo.

lo he escrito en Java, sin embargo, voy a enlazar aquí de todos modos, porque yo estoy trabajando actualmente en un puerto al rubí: Java: https://github.com/mohammedri/ant_colony_java_TSP Ruby: https://github.com/mohammedri/aco-ruby (incompleta) Este es el conjunto de datos que resuelve para: https://github.com/jorik041/osmsharp/blob/master/Core/OsmSharp.Tools/Benchmark/TSPLIB/Problems/TSP/bays29.tsp

Tenga en cuenta que estoy usando la distancia euclidiana entre cada ciudad, es decir, la distancia en línea recta, no creo que sea ideal en una situación real considerando carreteras y un mapa de la ciudad, etc. pero puede ser un buen comienzo punto :)