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

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

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

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

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

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

Знаете ли вы о каком-либо существующем скрипте ruby?


ruby ruby-on-rails google-maps algorithm traveling-salesman
person jfanals    schedule 23.11.2010    source источник
comment
…вы, конечно же, понимаете, что это одна из самых сложных проблем, верно? Без действительно отличного ответа? Есть еще разумные решения, но просто убедитесь, что вы знаете, что они действительно не будут великолепными.   -  person Matchu    schedule 24.11.2010
comment
Ага... Я не ищу оптимального решения... подойдет разумное :)   -  person jfanals    schedule 24.11.2010
comment
Я добавил тег коммивояжер. Пробовали ли вы просматривать другие вопросы в этом теге?   -  person Andrew Grimm    schedule 24.11.2010
comment
Спасибо за добавление тега ... Я без особого успеха искал коммивояжера в stackoverflow ... Я ищу практическое решение для более чем 50 местоположений, которые можно выполнить (в ruby) на одном сервере ... КСТАТИ. путешествие пишется с двойным LL: путешествие   -  person jfanals    schedule 24.11.2010
comment
Андрей, извините за исправление орфографии... Я только что узнал, что это может быть написано в обоих направлениях;)   -  person jfanals    schedule 24.11.2010
comment
@ischnura: Это одна из тех вещей, которые противопоставляют американский английский английскому языку Содружества. На самом деле я сначала пытался ввести две ls!   -  person Andrew Grimm    schedule 24.11.2010
comment
Уточняю: 50 локаций на сколько пользователей/водителей/продавцов? Нужно ли запускать его в режиме реального времени или его можно запланировать на ночь, чтобы утром были решения? - Справедливости ради - я просто спрашиваю это с точки зрения нагрузки на сервер.   -  person konung    schedule 24.11.2010
comment
Это старая история про коммивояжера и 50 дочерей фермера?   -  person the Tin Man    schedule 24.11.2010
comment
Когда Матчу говорит, что это сложная проблема, это не означает, что программирование сложное, это означает, что наиболее известный алгоритм требует очень много времени для работы независимо от используемого языка. Чтобы добавить некоторые цифры - 50 локаций займут в 49019536704020485392579302011699200000000 раз больше времени, чем 24 локации.   -  person John La Rooy    schedule 18.05.2011

Ответы (6)


arrow_upward
6
arrow_downward

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

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

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

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

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

person konung    schedule 24.11.2010
comment
Предложенный вами URL-адрес указывает на несколько решений, которые можно загрузить... Мне удалось настроить код одного из решений (от Джозефа Ситона) в соответствии со своими потребностями. Еще раз спасибо за указание на этот сайт :) Мне удалось получить разумное решение менее чем за 10 секунд... - person jfanals; 26.11.2010
comment
Добро пожаловать. кстати - я настоятельно рекомендую изучить и попытаться решить некоторые проблемы там - это поможет вам стать лучшим программистом на руби. Я стараюсь делать одну задачу в неделю, когда у меня есть время. - person konung; 01.12.2010

arrow_upward
4
arrow_downward

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

person moinudin    schedule 24.11.2010
comment
+1! В частности, обратите внимание на PTAS, на который есть ссылка из подраздела Euclidean TSP или описание в cs. Princeton.edu/~arora/pubs/tsp.ps (более простое описание доступно по адресу corelab.ntua.gr/courses/приблизительно-alg/material/Euclidean%20TSP.pdf). Это дает вам поливременной алгоритм аппроксимации O (1 + 1 / эпсилон) для любого эпсилон, который вам нравится (конечно, будьте осторожны, что показатель степени растет с 1 / эпсилон)! - person Yonatan N; 24.11.2010

arrow_upward
2
arrow_downward

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

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

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

person Jake Kurzer    schedule 24.11.2010

arrow_upward
1
arrow_downward

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

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

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

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

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

person DarthVader    schedule 23.11.2010
comment
Подход грубой силы считается нецелесообразным для более чем 20 баллов. Для 50 ему пришлось бы попробовать факториальные (50!) перестановки - примерно = 30414093201713378043612608166064768844377641568960512000000000000 на каждого продавца. - person konung; 24.11.2010

arrow_upward
1
arrow_downward

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

Хотя я написал его на 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

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

person mr3mo    schedule 02.02.2017

arrow_upward
0
arrow_downward

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

person Gigamegs    schedule 12.03.2011