Когда передомной была поставлена данная задача, первым делом пошел в поиск, но — это особых результатов не дало. Видел парочку обработок, но они рассчитывали маршрут по очень примитивным методам и давали результат далекий от идеального либо расчитывали полным перебором, что занимало слишком длительное время. Начал рассмотривать алгоритмы решения безотносительно к 1с. Мой выбор пал на Генетический алгоритм.
Для ускорения рассчетов весь код алгоритма был вынесен в COM объект написанный на С#. Данный COM объект принимает на вход массив расстояний между точками, пока реализовано для симетричного графа, то есть расстояние от точки А до точки Б равно расстоянию от точки Б до точки А (недавно понял что в реальной жизни не всегда так) и возвращает строку с порядком точек. Для демонстрации работы набросал простенький пример. Шаблон работы с яндекс кртой взял из публикации //infostart.ru/public/167919/. Яндекс карта была использована лишь для иллюстрации работы COM объекта.
Для запуска обработки COM объект надо зарегистрировать в системе следующей командой:
regasm.exe ПутьККаталогу/genTspLib.dll /codebase
на всякий случай вложу в архив с обработкой утилиту regasm.exe, так как не на всех компах удалось ее найти.
Ссылки по теме:
Внимание! Обработка предназначена только для демонстрации возможностей интеграции картографических сервисов с 1С. Обработка распространяется как есть. Автор не несет ответственности за действия пользователей обработки, которые не будут удовлетворять лицензионные соглашения этих сервисов.
Related Posts
Получение логина и пароля техподдержки 1С из базы
Класс для вывода отчета в Excel
Счет-фактура для УПП
Библиотека классов для создания внешней компоненты 1С на C#- Акт об оказании услуг (со скидками) — внешняя печатная форма для Управление торговлей 11.1.10.86
Прайс-лист с артикулом в отдельной колонке
За реализацию ГА алгоритма поставил плюс, но было бы лучше, если бы он был реализован в коде обработке — для понимания сути ГА.
Второй вопрос — это использование. По сути для применения ГА, нужен массив точек с правильным расстоянием между ними, но вот как получить эти расстояния? По-скольку занимался этим вопросом в последнее время, то есть 2 решения:
P.S. Сыылку на публикацию в посте просьба выделить как ссылку.
(1) Smaylukk, Цель была опубликовать компоненту. В приложенной обработке расстояния берутся из яндекс карт, но -это лишь для иллюстрации работы. В общем откуда их брать при решении реальных задач уже дело того кто будет использовать компоненту. В принципе компоненту можно использовать и для построения маршрута по складу, где вес ребра будет зависеть не только от расстояния.
Ссылку на вашу публикацию сейчас выделю как ссылку.
Добрый день. Хотелось бы уточнить по поводу алгоритма, можно подробности того каким образом он «просчитывает» ?
1. Почему именно ГА? (есть и другие методы решения задачи коммивояжёра)
2. Кокой ГА использовался? (какой тип деления и т.п.)
(3) eugen91, Если вкратце, то он считает по классической схеме ГА о которой подробно написано в статье
(4) cdb, после изучения теории я рассматривал 2 алгоритма генетический и муравьиный. Из прочтенного понял, что сейчас — это передовые методы решения задачи коммивояжера для большого числа точек. Для генетического нашел больше информации и решил его попробовать и в принципе не прогадал, алгоритм считает очень быстро даже для большого числа точек и выдает результат близкий к оптимальному. К стати где-то на вики читал, что многие сервера СУБД выбирают план запроса с применением генетического алгоритма
Так а где же районирование, кластеризация? Для одной ходки/машины/одного курьера и стандартных средств яндекса хватает.
(6) pumbaE, на сколько знаю, у Яндекса нет средств оптимизации маршрута. У гугла есть, но там ограничение по количеству точек, а точнее 10 точек для бесплатной версии и что-то около 25 для платной. Данная компонента и для 100 точек построит маршрут очень близкий к оптимальному минут за 10 на компе средней мощности. А потом его и порезать можно и будет на несколько машин. А деление по районам уж выходит за рамки задачи решаемой компонентой
По-моему, правильнее было бы посетить в обратной последовательности (см рис. в статье), судя по расстоянию, комивояджер затратит меньше времени на посещение больших точек, а самую дальнюю оставит на конец.
(8) vbuots, Так как было принято, что расстояние между точками не зависит от направления (я в описании об этом писал) то направление не играет роли. И все точки в рамках задачи коммивояжера замыкаются в кольцо
Плюсанул. Мне пока не надо, но штука полезная, мало ли — пригодится 🙂
Как раз сейчас занимаюсь похожей проблемой.
Спасибо автору, посмотрю что есть интересного.
Автор молодец. Но хотелось бы действительно на реализацию алгоритма взглянуть! Если уж на самом 1С — тогда вообще шик!
(12) Новенький_2209, на выходных планирую переписать на 1с и выложить
(12) Новенький_2209, Но думаю раза в 4 будет дольше считать
Молодца. Плюс однозначно..
Могу я вас попросить выслать мне обработку опубликованную в данной теме а также версию с алгоритмом в 1с. В настоящий момент также занимаюсь реализацией задачи нахождения оптимального пути. Есть реализации алгоритма Дейкстры и Муравьиного алгоритма. Адрес электронной почты prog@sirobogatov.ru
(16) vladzem, На сколько я помню. Алгоритм Дейкстры — это по методу нахождения «ближайшего соседа»? Если да, то его можно выкинуть. А вот муравьиный вполне хорошо. Из того, что я читал они на одном уровне по результативности с генетическим при решении задачи коммивояжера.
Нет ближайший сосед — это «жадный алгоритм». Алгоритм Дейкстры — это поиск гамильтонова цикла на неотрицательном графе (читай оптимальный маршрут). Обработку пришлите пож очень нужно иметь несколько вариантов расчета чтобы видеть возможные отклонения.
Если важна скорость вывполнения, что логично, то лучше все же использовать среды более низких уровней чем 1С. Наверное на языке 1С это имеет смысл разве что для ознакомления с генетическим алгоритмом или любым другим. Но для использования, я бы для себя выбрал компоненту.
Спасибо автору! Очень интересная разработка!
Предлагаю провести битву алгоритмов, ну или забеги на дистанции среди генетических алгоритмов 🙂
(20) phsin, я не против — это вполне может натолкнуть на идеи по улучшению алгоритма. Только вот у меня в алгоритме нет никаких функций ограничения, кроме длинны маршрута. Хотя конечно планирую добавить, пока в рабочем варианте строится 1 большой маршрут и разбивается на кусочки для машин.
что-то не вижу полюса сама суть где-то во внешней компоненте зарыта, запуститься ли она в будущих релизах платформы и ОС не понятно… Даешь пример реализации на чистом 1с?!
В решении данной задачи, очень помогла статья, где расписано все, вплоть до алгоритма.
Спасибо, возьму в копилочку. Скоро буду рассматривать
это совсем не работает
ничего не меняя в обработке,
добавил 5 адресов последовательно, добавляя их по одному в маршрут. 2 из них — соседние дома.
потом нажимаю «построить маршрут». программа при первом нажатии на «построить маршрут» показывает какое-то нереально малое расстояние, 2-3км.
при последующих нажатиях просто хаотично переставляет точки в маршрутах, причем соседние дома рядом оказываются не чаще, чем со случайными адресами.
одно радует — первая точка всегда остается первой (это наш склад)
обработка не юзает длл, есть описание, как обратиться к длл