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

02.01.13

Разработка - Разработка внешних компонент

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

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

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

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

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

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

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

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

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

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

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

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

 

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

См. также

Медиадисплей. Рекламный информационный монитор для покупателя.

Разработка внешних компонент POS терминал Рабочее место Розничная торговля Платформа 1С v8.3 1С:Комплексная автоматизация 1.х 1С:Управление торговлей 10 1С:Розница 2 1С:Управление нашей фирмой 1.6 1С:ERP Управление предприятием 2 1С:Бухгалтерия 3.0 1С:Управление торговлей 11 1С:Комплексная автоматизация 2.х Розничная и сетевая торговля (FMCG) Рестораны, кафе и фаст-фуд Реклама, PR и маркетинг Управленческий учет Платные (руб)

Монитор покупателя может отображать текущую покупку на кассовом месте, показывать видеорекламу, баннеры, во время простоя разворачивать рекламу на весь экран. Можно использовать в качестве графического меню-борда в кафе и видеовывески. Управление выводом на телевизор через hdmi-приставку на базе Windows или Android. В качестве устройства отображения можно использовать Android-планшеты, фоторамки с Android, монитор любого Windows-компьютера, доступного по сети. Настраивается ЛЮБОЙ ДИЗАЙН экрана!

16800 руб.

30.05.2017    52105    34    69    

43

Внешняя компонента для сканирования (замена TWAIN-компоненты БСП) (Native Win 32/64)

Разработка внешних компонент Платформа 1С v8.3 Конфигурации 1cv8 Платные (руб)

Внешняя компонента позволяет работать c TWAIN-совместимым оборудованием (сканерами, камерами) . Полностью совместима со стандартной TWAIN-компонентой из БСП и может применяться как ее замена без изменения вызовов, при этом может работать с 64-разрядной платформой, а так же имеет расширенную функциональность, например, сохранение результата непосредственно в PDF без использования сторонних утилит. Прекрасно работает на сервере, тонком клиенте и веб-клиенте (проверена работа в браузерах Google Chrome, Mozilla Firefox и Microsoft Internet Explorer).

2400 руб.

12.05.2020    26244    131    99    

83

Внешняя компонента для подключения 1С к телефонии Asterisk

Разработка внешних компонент Телефония, SIP Платформа 1С v8.3 Конфигурации 1cv8 Россия Платные (руб)

Внешняя компонента выполнена по технологии Native API для 1С 8.х, обеспечивает доступ к программным АТС Asterisk (FreePBX, Elastix) через AMI интерфейс. Через него можно управлять многими функциями Asterisk (определение номеров, перевод звонков, набор телефона и т. д.)

2400 руб.

04.05.2018    44977    117    64    

60

Внешняя компонента печати PDF (Native Win 32/64)

Разработка внешних компонент Платформа 1С v8.3 Конфигурации 1cv8 Платные (руб)

Внешняя компонента позволяет печатать PDF файлы непосредственно из 1С, не используя при этом сторонних программ. Прекрасно работает на сервере, тонком клиенте и веб-клиенте. Основана на проекте PDFium из состава проекта Chromium/Chrome

1500 руб.

17.09.2018    35081    104    123    

111

Мастер создания внешних компонент 1С (технология COM) для DELPHI 6/7/8/2005/2006/2007/2008/2010/XE/XE2/XE3

Разработка внешних компонент Платформа 1С v8.3 Платные (руб)

Средство для сверхбыстрой разработки внешних компонент 1С:Предприятия 7.7 и 8 по технологии COM на всех версиях DELPHI, начиная с 6.

2000 руб.

28.03.2013    54000    35    14    

68

QR-код с логотипом компании (обычная и управляемая форма)

Разработка внешних компонент Платформа 1С v8.3 Управляемые формы Конфигурации 1cv8 Платные (руб)

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

2400 руб.

22.06.2016    30840    4    4    

8

Внешняя компонента 1С и С++. Продолжаем разговор.

Разработка внешних компонент Платформа 1С v8.3 Бесплатно (free)

А давайте запилим 8.3.26 до релиза, или оповещение с сервера...

19.02.2024    4039    starik-2005    28    

52

Внешние компоненты 1С и язык C++

Разработка внешних компонент Механизмы платформы 1С Платформа 1С v8.3 Бесплатно (free)

Некоторые практические аспекты создания внешних компонент на языке С++ для платформы 1С 8.3++.

26.01.2024    4781    starik-2005    32    

39
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. Smaylukk 185 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 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 2421 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. Андроид 215 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 181 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 15 22.05.13 15:24 Сейчас в теме
В решении данной задачи, очень помогла статья, где расписано все, вплоть до алгоритма. Ссылка на pdf
djon10000; Andry.Boris; +2 Ответить
24. Algiz 24.10.13 11:33 Сейчас в теме
Спасибо, возьму в копилочку. Скоро буду рассматривать
25. bds22 20 28.10.14 12:17 Сейчас в теме
это совсем не работает
ничего не меняя в обработке,
добавил 5 адресов последовательно, добавляя их по одному в маршрут. 2 из них - соседние дома.
потом нажимаю "построить маршрут". программа при первом нажатии на "построить маршрут" показывает какое-то нереально малое расстояние, 2-3км.
при последующих нажатиях просто хаотично переставляет точки в маршрутах, причем соседние дома рядом оказываются не чаще, чем со случайными адресами.
одно радует - первая точка всегда остается первой (это наш склад)
26. yerasolo 31.10.17 17:35 Сейчас в теме
обработка не юзает длл, есть описание, как обратиться к длл
Оставьте свое сообщение