Risolvere il problema del commesso viaggiatore in Ruby (50 + posizioni)

Question

Sto lavorando in una società di consegna. Al momento Risolviamo 50 + posizioni percorsi da "mano".

Ho riflettuto su come utilizzare API di Google Maps per risolvere questo problema, ma ho letto che c'è un limite di 24 punti.

Al momento stiamo usando le rotaie nel nostro server così sto pensando di usare uno script Ruby che otterrebbe le coordinate dei luoghi e 50 + uscita una soluzione ragionevole.

Che algoritmo usereste per affrontare questo problema?

rubino un buon linguaggio di programmazione per risolvere questo tipo di problema?

Sai di qualsiasi script Ruby esistente?

Answer 1

Questo potrebbe essere quello che stai cercando:

Attenzione:

questo sito viene segnalato da Firefox come sito di attacco - ma non sembra essere. In realtà ho usato prima senza un problema

[Verificare la storia delle revisioni di URL]

rubyquiz sembra essere verso il basso (è stato premuto per un po ') ma è ancora possibile controllare la macchina WayBack e archive.org per vedere la pagina: http://web.archive.org/web/20100105132957 /http://rubyquiz.com/quiz142.html

Answer 2

Anche con la soluzione DP citato in un'altra risposta, che sta andando a richiedere O (10 ^ 15) operazioni. Così si sta andando a guardare a soluzioni approssimate, che sono probabilmente accettabile, considerando che attualmente fa a mano. Guardate http://en.wikipedia.org/wiki/Travelling_salesman_problem#Heuristic_and_approximation_algorithms

Answer 3

Qui ci sono un paio di trucchi:
località nodulo che sono relativamente vicini in un grafico, e trasformano quelle posizioni in un unico nodo nel grafico principale: 1. Questo ti permette di essere avidi, senza troppo lavoro.
2:. Utilizzare un algoritmo di approssimazione
2 bis: Il mio preferito è giri bitoniche. Sono abbastanza facile da hackerare l'alto.
Vedere Aggiornamento

Ecco un lib PY con un tour bitonico e ecco un altro
Lasciami andare a cercare uno rubino. Sto avendo difficoltà ritrovamento più che il RGL , che ha problemi di efficienza ....

Aggiorna
Nel tuo caso, la copertura minimo attacco albero dovrebbe essere efficace. Non riesco a pensare ad un caso in cui le tue città non avrebbe incontrato la disuguaglianza triangolare. Ciò significa che ci dovrebbe essere una relativamente sorta di tipo di quasi veloce approssimazione piuttosto decente. In particolare, se la distanza è euclidea, che mi sembra, ancora una volta, deve essere.

Answer 4

Una delle soluzione ottimizzata sta usando Programmazione Dinamica, ma ancora molto costoso O (2 ** n), che non è molto fattibile, a meno di utilizzare un po 'di clustering e la distribuzione di calcolo, rubino o singolo server non saranno molto utili per te.

I raccomanderebbe a venire con un criterio di avidi invece di utilizzare DP o la forza bruta che sarebbe più facile da implementare.

Una volta che il fine del programma si può fare qualche Memoizzazione, e memorizzare i risultati in qualche luogo per le ricerche successive, che possono così risparmiare qualche cicli.

in termini di codice, che sarà necessario implementare i vertici, spigoli che hanno pesi.

Per esempio: classe vertice che hanno bordi con pesi, ricorsivo. di una classe grafico che popoleranno i dati.

Answer 5

Ho lavorato su utilizzando algoritmi meta-heurestic quali Ant Colony optimazation per risolvere i problemi TSP per il (29-città) problema Bays29, e mi ha dato vicino al soluzioni ottimali in tempi molto brevi. È potenzialmente possibile utilizzare lo stesso.

L'ho scritto in Java, però, voglio creare un collegamento qui in ogni modo, perché Attualmente sto lavorando su una porta a Ruby: Java: https://github.com/mohammedri/ant_colony_java_TSP Rubino: https://github.com/mohammedri/aco-ruby (incompleto) Questo è il set di dati risolve per: https://github.com/jorik041/osmsharp/blob/master/Core/OsmSharp.Tools/Benchmark/TSPLIB/Problems/TSP/bays29.tsp

Tenete a mente che sto usando la distanza euclidea tra ogni città cioè la distanza in linea retta, non credo che sia l'ideale in una situazione di vita reale in considerazione strade e una piantina della città, ecc, ma può essere un buon punto di partenza :)

Answer 6

Se si desidera che il costo della soluzione prodotta dai algoritmo è nel 3/2 della ottimali poi si desidera l'algoritmo Christofides. ACO e GA non hanno un costo garantito.