Решение задачи коммивояжера в рубине (более 50 локаций)

Question

Я работаю в компании доставки. В настоящее время мы решаем более 50 маршрутов локаций «вручную».

Я думал об использовании Google Maps API для решения этой проблемы, но я прочитал, что существует ограничение в 24 балла.

В настоящее время мы используем рельсы на нашем сервере, поэтому я думаю об использовании сценария ruby, который бы получил координаты 50+ мест и вывел разумное решение.

Какой алгоритм вы бы использовали для решения этой проблемы?

Является ли Ruby хорошим языком программирования для решения подобных проблем?

Вам известен какой-нибудь существующий скрипт ruby?

Answer 1

Это может быть то, что вы ищете:

Предупреждение:

этот сайт помечен firefox как сайт атаки - но я не вижу,На самом деле я использовал его раньше без проблем

[Проверить историю изменений для URL]

rubyquiz, кажется, не работает (был выключен некоторое время), однако вы все равно можете проверить машину WayBack иarchive.org, чтобы увидеть эту страницу: http://web.archive.org/web/20100105132957/http://rubyquiz.com/quiz142.html

Answer 2

Даже с решением DP, упомянутым в другом ответе, это потребует O (10 ^ 15) операций. Таким образом, вам придется искать приблизительные решения, которые, вероятно, являются приемлемыми, учитывая, что вы в настоящее время делаете их вручную. Посмотрите на http://en.wikipedia.org/wiki/Travelling_salesman_problem#Heuristic_and_approximation_algorithms

Answer 3

Вот несколько хитростей:
1: Объедините местоположения, которые находятся относительно близко в одном графике, и превратите эти местоположения в один узел в вашем основном графике. Это позволяет вам быть жадным без особого труда.
2: Используйте алгоритм приближения.
2а: Мои любимые туры. Их довольно легко взломать.
См. Обновление

Вот эта библиотека с битоническим туром и вот еще
Позволь мне поискать рубиновый. У меня проблемы с поиском не только RGL , в котором есть проблемы с эффективностью ....

Обновление
В вашем случае минимальная атака связующего дерева должна быть эффективной. Я не могу вспомнить случай, когда ваши города не соответствовали бы неравенству треугольника. Это означает, что должно быть относительно быстрое, довольно приличное приближение. Особенно, если расстояние евклидово, что, я думаю, опять же должно быть.

Answer 4

Я работал над использованием метаэвристических алгоритмов, таких как Ant Colony Optimaizing, для решения задач TSP для проблемы Bays29 (29-city), и это дало мне близкие к оптимальным решения за очень короткое время.Вы можете потенциально использовать то же самое.

Хотя я написал это на Java, я все равно буду связывать его здесь, потому что в настоящее время я работаю над портом на ruby: Java: https://github.com/mohammedri/ant_colony_java_TSP Ruby: https://github.com/mohammedri/aco-ruby (не завершено)Это набор данных, для которого он решает: https://github.com/jorik041/osmsharp/blob/master/Core/OsmSharp.Tools/Benchmark/TSPLIB/Problems/TSP/bays29.tsp

Имейте в виду, что я использую евклидово расстояние между каждым городом, то есть расстояние по прямой линии, я не думаю, что это идеально в реальной жизни, учитывая дорогии карта города и т. д., но это может быть хорошей отправной точкой:)

Answer 5

Одним из оптимизированных решений является использование динамического программирования, но все еще очень дорого O (2 ** n), что не очень выполнимо, если вы не используете кластеризацию и распределение вычислений, рубин или один сервер не будут очень полезныВы.

Я бы порекомендовал вам придумать жадные критерии вместо того, чтобы использовать DP или грубую силу, которую было бы проще реализовать.

Как только ваша программа завершится, вы можете сделать некоторые заметки и сохранить результаты где-нибудь для последующих поисков, что также может сэкономить вам несколько циклов.

с точки зрения кода, вам потребуетсяреализовать вершины, ребра с весами.

т.е.: класс вершин с ребрами с весами, рекурсивный.чем класс графа, который будет заполнять данные.

Answer 6

Если вы хотите, чтобы стоимость решения, полученного с помощью алгоритма, была в пределах 3/2 от оптимальной, тогда вам нужен алгоритм Christofides. ACO и GA не имеют гарантированной стоимости.