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

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С. Обработка распространяется как есть. Автор не несет ответственности за действия пользователей обработки, которые не будут удовлетворять лицензионные соглашения этих сервисов.

+62 –

См. также

GGraphics - внешняя компонента для работы с картинками jpg (jpeg), png, bmp, gif, tif

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

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

3600 руб.

02.09.2010 77838 73 257

191

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

Разработка внешних компонент Программист Платформа 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 29178 139 100

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

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

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

1500 руб.

17.09.2018 37174 115 128

116

Imagius

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

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

2400 руб.

25.06.2024 1337 3 4

SQLite в 1С

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

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

14.01.2025 2742 bayselonarrend 14

Конструктор внешних компонент 1C (native API)

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

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

04.12.2024 5515 kovalevdmv 26

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

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

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

19.02.2024 6680 starik-2005 38

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

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

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

26.01.2024 7921 starik-2005 40

Комментарии

Подписаться на ответы Инфостарт бот

Свернуть все

1. Smaylukk 186 02.01.13 14:09 Сейчас в теме

За реализацию ГА алгоритма поставил плюс, но было бы лучше, если бы он был реализован в коде обработке - для понимания сути ГА.
Второй вопрос - это использование. По сути для применения ГА, нужен массив точек с правильным расстоянием между ними, но вот как получить эти расстояния? По-скольку занимался этим вопросом в последнее время, то есть 2 решения:

Интегрировать в 1С оффлайн-сервис (например СитиГид) и написать для него функцию определения правильного расстояния.
Использовать онлайн-сервисы, но лицензия...

P.S. Сыылку на публикацию в посте просьба выделить как ссылку.

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

24. Algiz 24.10.13 11:33 Сейчас в теме

Спасибо, возьму в копилочку. Скоро буду рассматривать

25. bds22 20 28.10.14 12:17 Сейчас в теме

это совсем не работает
ничего не меняя в обработке,
добавил 5 адресов последовательно, добавляя их по одному в маршрут. 2 из них - соседние дома.
потом нажимаю "построить маршрут". программа при первом нажатии на "построить маршрут" показывает какое-то нереально малое расстояние, 2-3км.
при последующих нажатиях просто хаотично переставляет точки в маршрутах, причем соседние дома рядом оказываются не чаще, чем со случайными адресами.
одно радует - первая точка всегда остается первой (это наш склад)