gifts2017

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

Опубликовал Михаил Горбов (MadHead) в раздел Программирование - Внешние компоненты

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

Когда передомной была поставлена данная задача, первым делом пошел в поиск, но - это особых результатов не дало. Видел парочку обработок, но они рассчитывали маршрут по очень примитивным методам и давали результат далекий от идеального либо расчитывали полным перебором, что занимало слишком длительное время. Начал рассмотривать алгоритмы решения безотносительно к 1с. Мой выбор пал на Генетический алгоритм.

Для ускорения рассчетов весь код алгоритма был вынесен в COM объект написанный на С#. Данный COM объект принимает на вход массив расстояний между точками, пока реализовано для симетричного графа, то есть расстояние от точки А до точки Б равно расстоянию от точки Б до точки А (недавно понял что в реальной жизни не всегда так) и возвращает строку с порядком точек. Для демонстрации работы набросал простенький пример. Шаблон работы с яндекс кртой взял из публикации http://infostart.ru/public/167919/. Яндекс карта была использована лишь для иллюстрации работы COM объекта. 

Для запуска обработки COM объект надо зарегистрировать в системе следующей командой:

regasm.exe ПутьККаталогу/genTspLib.dll /codebase

на всякий случай вложу в архив с обработкой утилиту regasm.exe, так как не на всех компах удалось ее найти. 

Ссылки по теме:

NP-полная задача 

Задача коммивояжера

Генетический алгоритм

 

Внимание! Обработка предназначена только для демонстрации возможностей интеграции картографических сервисов с 1С. Обработка распространяется как есть. Автор не несет ответственности за действия пользователей обработки, которые не будут удовлетворять лицензионные соглашения этих сервисов.

Скачать файлы

Наименование Файл Версия Размер
Демонстрационный пример работы 148
.rar 35,24Kb
02.01.13
148
.rar 35,24Kb Скачать

См. также

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

Ссылку на вашу публикацию сейчас выделю как ссылку.
3. Евгений Рачковский (eugen91) 04.01.13 13:18
Добрый день. Хотелось бы уточнить по поводу алгоритма, можно подробности того каким образом он "просчитывает" ?
4. Дмитрий Чекунов (cdb) 04.01.13 16:02
1. Почему именно ГА? (есть и другие методы решения задачи коммивояжёра)
2. Кокой ГА использовался? (какой тип деления и т.п.)
5. Михаил Горбов (MadHead) 05.01.13 13:07
(3) eugen91, Если вкратце, то он считает по классической схеме ГА о которой подробно написано в статье Генетический алгоритм

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

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