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

02.01.13

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

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

Скачать файл

ВНИМАНИЕ: Файлы из Базы знаний - это исходный код разработки. Это примеры решения задач, шаблоны, заготовки, "строительные материалы" для учетной системы. Файлы ориентированы на специалистов 1С, которые могут разобраться в коде и оптимизировать программу для запуска в базе данных. Гарантии работоспособности нет. Возврата нет. Технической поддержки нет.

Наименование По подписке [?] Купить один файл
Демонстрационный пример работы
.rar 35,24Kb
169
169 Скачать (1 SM) Купить за 1 850 руб.

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

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

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

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

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

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

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

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

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

 

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

См. также

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

Позволяет автоматизировать работу с картинками. С помощью компоненты можно измерять размер изображений, поворачивать их, наносить водяные знаки, конвертировать из одного формата в другой. Будет очень полезна для интернет-магазинов и всех, кому постоянно требуется работать с различными графическими форматами. Выполнена по технологии NativeAPI. Работает с форматами: jpg (jpeg), png, bmp, gif, tif

3600 руб.

02.09.2010    77970    73    280    

191

Разработка внешних компонент Программист Платформа 1С v8.3 1C:Бухгалтерия 1С:Управление нашей фирмой 1.6 1С:Бухгалтерия 3.0 Платные (руб)

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

3000 руб.

12.05.2020    29306    139    100    

92

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

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

1500 руб.

17.09.2018    37230    115    128    

116

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

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

2400 руб.

04.05.2018    47796    125    66    

68

Разработка внешних компонент Системный администратор Программист Стажер Бесплатно (free)

Библиотека для работы с базами SQLite из 1С на основе внешней компоненты. Для Linux и Windows, бесплатно и с открытым исходным кодом!

14.01.2025    2824    bayselonarrend    14    

48

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

В статье описывается приложение-конструктор внешних компонент (native API). Конструктор упрощает процесс разработки за счет удобного добавления всех нужных функций и процедур в графическом режиме, с указанием их параметров и типов параметров. На выходе приложение генерирует готовый код на С++ и Rust и позволяет сразу приступить к реализации, без настройки API компоненты вручную.

04.12.2024    5615    kovalevdmv    26    

77

Разработка внешних компонент Программист Платформа 1С v8.3 1C:Бухгалтерия 1С:Управление торговлей 11 Платные (руб)

Внешняя компонента для конвертации PDF файлов в картинки без использования дополнительных программ. Работает на сервере и в тонком клиенте.

2400 руб.

25.06.2024    1371    3    4    

3
Комментарии
Подписаться на ответы Инфостарт бот Сортировка: Древо развёрнутое
Свернуть все
1. Smaylukk 186 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. Андроид 218 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 183 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 Сейчас в теме
обработка не юзает длл, есть описание, как обратиться к длл
Оставьте свое сообщение