0. MadHead 62 02.01.13 02:54 Сейчас в теме

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

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

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

Комментарии
Избранное Подписка Сортировка: Древо
1. Smaylukk 795 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 629 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 2420 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. Андроид 193 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 178 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 14 28.10.14 12:17 Сейчас в теме
это совсем не работает
ничего не меняя в обработке,
добавил 5 адресов последовательно, добавляя их по одному в маршрут. 2 из них - соседние дома.
потом нажимаю "построить маршрут". программа при первом нажатии на "построить маршрут" показывает какое-то нереально малое расстояние, 2-3км.
при последующих нажатиях просто хаотично переставляет точки в маршрутах, причем соседние дома рядом оказываются не чаще, чем со случайными адресами.
одно радует - первая точка всегда остается первой (это наш склад)
26. yerasolo 31.10.17 17:35 Сейчас в теме
обработка не юзает длл, есть описание, как обратиться к длл
Оставьте свое сообщение
Новые вопросы с вознаграждением
Автор темы объявил вознаграждение за найденный ответ, его получит тот, кто первый поможет автору.

Вакансии

Программист/Cтарший программист 1С
Москва
зарплата от 100 000 руб. до 250 000 руб.
Полный день

Программист 1С
Калининград
зарплата от 60 000 руб. до 80 000 руб.
Полный день

Руководитель проектов 1С
Санкт-Петербург
Полный день

Программист 1С
Новосибирск
зарплата от 80 000 руб. до 150 000 руб.
Полный день

Консультант-аналитик 1С
Москва
зарплата от 40 000 руб. до 120 000 руб.
Полный день