Построение оптимального маршрута с применением генетического алгоритма

0. 62 02.01.13 02:54 Сейчас в теме
Не так давно столкнулся с проблемой решения задачи коммивояжера. Суть задачи в нахождении кратчайшего пути для объезда N городов. Основная проблема заключалась в том, что задача коммивояжера относится к классу NP-полных задач и самый очевидный способ решения методом перебора всех вариантов уже на 30 точках занимает длительное время.

Перейти к публикации

Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. Smaylukk 841 02.01.13 14:09 Сейчас в теме
За реализацию ГА алгоритма поставил плюс, но было бы лучше, если бы он был реализован в коде обработке - для понимания сути ГА.
Второй вопрос - это использование. По сути для применения ГА, нужен массив точек с правильным расстоянием между ними, но вот как получить эти расстояния? По-скольку занимался этим вопросом в последнее время, то есть 2 решения:
  • Интегрировать в 1С оффлайн-сервис (например СитиГид) и написать для него функцию определения правильного расстояния.
  • Использовать онлайн-сервисы, но лицензия...
P.S. Сыылку на публикацию в посте просьба выделить как ссылку.
RomanUzmov; Новенький_2209; Kneo; +3 Ответить
2. MadHead 62 02.01.13 14:48 Сейчас в теме
(1) Smaylukk, Цель была опубликовать компоненту. В приложенной обработке расстояния берутся из яндекс карт, но -это лишь для иллюстрации работы. В общем откуда их брать при решении реальных задач уже дело того кто будет использовать компоненту. В принципе компоненту можно использовать и для построения маршрута по складу, где вес ребра будет зависеть не только от расстояния.

Ссылку на вашу публикацию сейчас выделю как ссылку.
3. eugen91 04.01.13 13:18 Сейчас в теме
Добрый день. Хотелось бы уточнить по поводу алгоритма, можно подробности того каким образом он "просчитывает" ?
5. MadHead 62 05.01.13 13:07 Сейчас в теме
(3) eugen91, Если вкратце, то он считает по классической схеме ГА о которой подробно написано в статье Генетический алгоритм

(4) cdb, после изучения теории я рассматривал 2 алгоритма генетический и муравьиный. Из прочтенного понял, что сейчас - это передовые методы решения задачи коммивояжера для большого числа точек. Для генетического нашел больше информации и решил его попробовать и в принципе не прогадал, алгоритм считает очень быстро даже для большого числа точек и выдает результат близкий к оптимальному. К стати где-то на вики читал, что многие сервера СУБД выбирают план запроса с применением генетического алгоритма
4. cdb 26 04.01.13 16:02 Сейчас в теме
1. Почему именно ГА? (есть и другие методы решения задачи коммивояжёра)
2. Кокой ГА использовался? (какой тип деления и т.п.)
6. pumbaE 641 05.01.13 15:25 Сейчас в теме
Так а где же районирование, кластеризация? Для одной ходки/машины/одного курьера и стандартных средств яндекса хватает.
7. MadHead 62 07.01.13 23:19 Сейчас в теме
(6) pumbaE, на сколько знаю, у Яндекса нет средств оптимизации маршрута. У гугла есть, но там ограничение по количеству точек, а точнее 10 точек для бесплатной версии и что-то около 25 для платной. Данная компонента и для 100 точек построит маршрут очень близкий к оптимальному минут за 10 на компе средней мощности. А потом его и порезать можно и будет на несколько машин. А деление по районам уж выходит за рамки задачи решаемой компонентой
8. vbuots 20 09.01.13 09:55 Сейчас в теме
По-моему, правильнее было бы посетить в обратной последовательности (см рис. в статье), судя по расстоянию, комивояджер затратит меньше времени на посещение больших точек, а самую дальнюю оставит на конец.
9. MadHead 62 09.01.13 10:52 Сейчас в теме
(8) vbuots, Так как было принято, что расстояние между точками не зависит от направления (я в описании об этом писал) то направление не играет роли. И все точки в рамках задачи коммивояжера замыкаются в кольцо
10. wolfsoft 2422 09.01.13 12:50 Сейчас в теме
Плюсанул. Мне пока не надо, но штука полезная, мало ли - пригодится :)
11. Murom 10.01.13 12:58 Сейчас в теме
Как раз сейчас занимаюсь похожей проблемой.
Спасибо автору, посмотрю что есть интересного.
12. Новенький_2209 10.01.13 22:48 Сейчас в теме
Автор молодец. Но хотелось бы действительно на реализацию алгоритма взглянуть! Если уж на самом 1С - тогда вообще шик!
13. MadHead 62 10.01.13 23:39 Сейчас в теме
(12) Новенький_2209, на выходных планирую переписать на 1с и выложить
14. MadHead 62 10.01.13 23:40 Сейчас в теме
(12) Новенький_2209, Но думаю раза в 4 будет дольше считать
15. Андроид 198 10.01.13 23:40 Сейчас в теме
Молодца. Плюс однозначно..
16. vladzem 11.01.13 08:24 Сейчас в теме
Могу я вас попросить выслать мне обработку опубликованную в данной теме а также версию с алгоритмом в 1с. В настоящий момент также занимаюсь реализацией задачи нахождения оптимального пути. Есть реализации алгоритма Дейкстры и Муравьиного алгоритма. Адрес электронной почты prog@sirobogatov.ru
17. MadHead 62 11.01.13 13:02 Сейчас в теме
(16) vladzem, На сколько я помню. Алгоритм Дейкстры - это по методу нахождения "ближайшего соседа"? Если да, то его можно выкинуть. А вот муравьиный вполне хорошо. Из того, что я читал они на одном уровне по результативности с генетическим при решении задачи коммивояжера.
18. vladzem 11.01.13 14:54 Сейчас в теме
Нет ближайший сосед - это "жадный алгоритм". Алгоритм Дейкстры - это поиск гамильтонова цикла на неотрицательном графе (читай оптимальный маршрут). Обработку пришлите пож очень нужно иметь несколько вариантов расчета чтобы видеть возможные отклонения.
19. artmicro 11.01.13 15:06 Сейчас в теме
Если важна скорость вывполнения, что логично, то лучше все же использовать среды более низких уровней чем 1С. Наверное на языке 1С это имеет смысл разве что для ознакомления с генетическим алгоритмом или любым другим. Но для использования, я бы для себя выбрал компоненту.
20. phsin 182 13.01.13 10:47 Сейчас в теме
Спасибо автору! Очень интересная разработка!

Предлагаю провести битву алгоритмов, ну или забеги на дистанции среди генетических алгоритмов :)
http://infostart.ru/public/168946/
21. MadHead 62 13.01.13 19:23 Сейчас в теме
(20) phsin, я не против - это вполне может натолкнуть на идеи по улучшению алгоритма. Только вот у меня в алгоритме нет никаких функций ограничения, кроме длинны маршрута. Хотя конечно планирую добавить, пока в рабочем варианте строится 1 большой маршрут и разбивается на кусочки для машин.
22. Angeros 06.02.13 09:17 Сейчас в теме
что-то не вижу полюса сама суть где-то во внешней компоненте зарыта, запуститься ли она в будущих релизах платформы и ОС не понятно... Даешь пример реализации на чистом 1с?!
23. NoN098 14 22.05.13 15:24 Сейчас в теме
В решении данной задачи, очень помогла статья, где расписано все, вплоть до алгоритма. Ссылка на pdf
djon10000; Andry.Boris; +2 Ответить
24. Algiz 24.10.13 11:33 Сейчас в теме
Спасибо, возьму в копилочку. Скоро буду рассматривать
25. bds22 19 28.10.14 12:17 Сейчас в теме
это совсем не работает
ничего не меняя в обработке,
добавил 5 адресов последовательно, добавляя их по одному в маршрут. 2 из них - соседние дома.
потом нажимаю "построить маршрут". программа при первом нажатии на "построить маршрут" показывает какое-то нереально малое расстояние, 2-3км.
при последующих нажатиях просто хаотично переставляет точки в маршрутах, причем соседние дома рядом оказываются не чаще, чем со случайными адресами.
одно радует - первая точка всегда остается первой (это наш склад)
26. yerasolo 31.10.17 17:35 Сейчас в теме
обработка не юзает длл, есть описание, как обратиться к длл
Оставьте свое сообщение
Вопросы с вознаграждением