"Убер на складе": динамический расчет маршрутов с учетом реальных расстояний

24.06.19

Разработка - Механизмы платформы 1С

Представляю методику и инструмент для динамического расчета маршрутов отбора на высоконагруженных складах для максимального повышения эффективности склада, ускорения проходимости и, как следствие, экономии денег. Это методика и обработка для интеграции в WMS решения. Тестировалось на 1С 8.3.14.1565.

Скачать исходный код

Наименование Файл Версия Размер
Конфигурация с обработкой редактора склада и расчета таблицы расстояний
.cf 116,29Kb
18
.cf 116,29Kb 18 Скачать

Введение

Когда вы вызываете такси в одном из современных агрегаторов, ваше местоположение определяется и какой-то из находящихся рядом таксистов берет заказ. Ему не приходится ехать из таксопарка, он экономит ваше время и деньги. Этот принцип изменил бизнес перевозок. В складах с высокой проходимостью заказы обрабатываются построчно. Один заказ может собирать несколько человек. Даже одну строчку заказа может собирать несколько человек. Современные WMS поддерживают этот принцип.

Кто-то работает быстро, кто-то не очень. Постоянно появляются новые заказы, которые надо собирать, они падают в общий план. Т.е. ситуация постоянно меняется.  Это можно представить так: все строки заказов падают условно в одну таблицу. Из этой таблицы формируются задания на отбор «Пойти по такому то адресу, взять такую то номенклатуру, отнести в зону отбора». Исполнители получают эти задания и начинают выполнять. В WMS обычно есть план обхода, который базируется на порядке обхода. Порядок обхода, естественно, статический. Он не учитывает изменения ситуации. У меня не так.

Что предлагается?

 

Предлагается динамически назначать на отбор адреса ближайшего (по географическому принципу) свободного исполнителя.

Когда исполнитель работает с какой то ячейкой, его местоположение равно положению этой ячейки. Т.е. известно, где он, пока он не закончил с ней работать. А когда закончит, ему нужно просто идти на ближайшую от него ячейку, где есть актуальное задание. И так пока он не загрузит контейнер отбора. Как же определить, кто из исполнителей ближе всего к ячейке? Даже если есть электронная карта склада, то просто евклидово расстояние не пойдет, так как люди не умеют проходить сквозь стеллажи и прочие препятствия. Я решил эту проблему, и об этом подробно написано далее.

 Итак, допустим, я узнал реальные расстояния от каждого адреса к каждому адресу и заполнил таблицу этих расстояний (регистр сведений).

Тогда для определения следующей ячейки мне надо выполнить 2 действия (на самом деле это делается одним запросом по таблице заказов и таблице расстояний, но для наглядности я напишу как будто это просто таблицы):

  1. Заполнить в таблице заказов расстояние от текущей ячейки где я еще пока нахожусь до ячейки таблицы заказов. Используя ранее посчитанную таблицу расстояний
  2. Отсортировать таблицу по возрастанию и первая строчка будет искомая ближайшая ячейка

И когда вы закончили цикл на текущей ячейке, вам предлагается эта ближайшая ячейка в качестве следующей. Можно отказаться и пропустить, тогда она уйдет кому то другому. Этот принцип будет работать и с одним кладовщиком на сборке.  Вот так это выглядит в моем Simple WMS client:

Как посчитать реальные расстояния?

 

В многих WMS есть в справочнике ячеек есть такой числовой параметр, как «Порядок обхода» и логисты часто спрашивают меня «Дмитрий, а как его заполнять?». Все время начинаем придумывать некий виртуальный порядок обхода - зигзагом или еще как то… Все время понимал ущербность этого подхода и вот сейчас продвинулся в этом направлении.

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

Для расчета таблицы расстояний нам потребуется нарисовать карту склада. В конфигурации это делается в обработке "Карта склада" Можно взять готовою картинку и наложить на нее стеллажи. Я сделал редактор склада на основе разработки NativeDraw (//infostart.ru/public/378415/) . Да получился не самый удобный редактор но со своими функциями справляется. По сути это штука на один раз – один раз запустил, получил таблицу расстояний и все, больше она не нужна.

 

Внимание: для работы потребуется скачать библиотеку со вышеуказанной страницы автора и прописать путь к ней в форме обработки в процедуре NativeDraw_Инициализация().

Кроме того при первом запуске будет необходимо пройти калибровку, следуя подсказкам на экране: нужно будет нажать в левый верхний и правый нижний угол холста.

После того как на карте расположены объекты надо чтобы система рассчитала условные ячейки по которым кладовщик может ходить для этого надо нажать кнопку «Заполнить зоны перемещения» и система заполнит свободное пространство зелененькими квадратиками. Их размер можно выбрать таким как удобно. Например равным одному шагу или размеру паллеты.

В этом подходе не важна привязка к реальным размерам но важно соблюдать пропорции. Система будет считать пути в «квадратиках» и найдет путь с наименьшим числом «квадратиков» , а чему он равен не так уж важно.

Также система выбирает из поля по которому можно перемещаться у каждой ячейки стеллажа по одной ячейке. Они подсвечиваются бордовым. Это и будут стартовые и финишные ячейки. При рисовании стеллажей важно еще указать с какой стороне (на карте) у них загрузка чтобы система знала с какой ячейки стартовать. Это выбирается переключателем "Направление загрузки".

Теперь все  готово для того чтобы рассчитать таблицу расстояний. Кратчайший путь от ячейки к ячейке можно одним из множества математических алгоритмов. Это алгоритмы поиска пути на графах,  а ячейки можно также представить в виде графа, поэтому все они подходят.

Когда вы в игрушке вы отправляете орка валить лес он идет куда ему указали по алгоритму поиска пути. Самый простой(и самый неэффективный) – волновой, также есть Dijkstra, A*  и другие. Вот тут отличная разработка которая в мультиках покажет как работает каждый из этих алгоритмов : http://qiao.github.io/PathFinding.js/visual/ 

Я выбрал A* потому что его хвалят как эффективный. Вот тут он описан : https://ru.wikipedia.org/wiki/A* .

В обработке можно наглядно посмотреть как строятся пути от ячейки к ячейке. Просто так для того чтобы убедиться что это работает.

В редакторе можно рисовать не только ячейки но и всякие препятствия. Алгоритм их воспринимает как препятствия. Не удержался и проверил обход препятствия еще раз:

Ну и собственно, то ради чего это делалось – можно нажать кнопку «Вычислить путь по всем ячейкам и записать» и получите в регистре таблицу расстояний. Работает ооочень долго. Как вариант можно использовать вместо евклидовой метрики расстояния  «манхеттен» или «Чебышыва» - они без корней (в модуле обработки есть функция манхеттен) и должны работать быстрее. Но на самом деле это не важно – это делается один раз в жизни.

В итоге получается таблица расстояний по которой уже быстро в любой момент можно определить куда идти. В WMS может быть устроено по разному: может быть пул заданий на пикинг в виде объектов базы данных, которые ждут когда будет назначен либо не быть таких объектов а само задание просто высвечивается в виде надписи на экране ТСД. В любом случае имея полносвязанную таблицу реальных расстояний можно использовать этот принцип в любой системе.

WMS склад ТСД SimpleWMS логистика

См. также

Сервисы интеграции без Шины и интеграции

Механизмы платформы 1С Программист Стажер Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

Пример использования «Сервисов интеграции» без подключения к Шине и без обменов.

13.03.2024    3119    dsdred    16    

63

Как готовить и есть массивы

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

Все мы используем массивы в своем коде. Это один из первых объектов, который дают ученикам при прохождении обучения программированию. Но умеем ли мы ими пользоваться? В этой статье я хочу показать все методы массива, а также некоторые фишки в работе с массивами.

24.01.2024    7220    YA_418728146    25    

69

Планы обмена VS История данных

Перенос данных 1C Механизмы платформы 1С Системный администратор Программист Стажер Платформа 1С v8.3 Бесплатно (free)

Вы все еще регистрируете изменения только на Планах обмена и Регистрах сведений?

11.12.2023    7634    dsdred    36    

115

1С-ная магия

Механизмы платформы 1С Программист Бесплатно (free)

Язык программирования 1С содержит много нюансов и особенностей, которые могут приводить к неожиданным для разработчика результатам. Сталкиваясь с ними, программист начинает лучше понимать логику платформы, а значит, быстрее выявлять ошибки и видеть потенциальные узкие места своего кода там, где позже можно было бы ещё долго медитировать с отладчиком в поисках источника проблемы. Мы рассмотрим разные примеры поведения кода 1С. Разберём результаты выполнения и ответим на вопросы «Почему?», «Как же так?» и «Зачем нам это знать?». 

06.10.2023    19973    SeiOkami    46    

124

Дефрагментация и реиндексация после перехода на платформу 8.3.22

Механизмы платформы 1С Системный администратор Платформа 1С v8.3 Бесплатно (free)

Начиная с версии платформы 8.3.22 1С снимает стандартные блокировки БД на уровне страниц. Делаем рабочий скрипт, как раньше.

14.09.2023    13896    human_new    27    

77

Валидация JSON через XDTO (включая массивы)

WEB-интеграция Универсальные функции Механизмы платформы 1С Программист Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

При работе с интеграциями рано или поздно придется столкнуться с получением JSON файлов. И, конечно же, жизнь заставит проверять файлы перед тем, как записывать данные в БД.

28.08.2023    10245    YA_418728146    7    

147

Внешние компоненты Native API на языке Rust - Просто!

Механизмы платформы 1С Программист Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

Внешние компоненты для 1С можно разработывать очень просто, пользуясь всеми преимуществами языка Rust - от безопасности и кроссплатформенности до удобного менеджера библиотек.

20.08.2023    6952    sebekerga    54    

99
Комментарии
Подписаться на ответы Инфостарт бот Сортировка: Древо развёрнутое
Свернуть все
1. Fragster 1140 24.06.19 18:24 Сейчас в теме
В свое время решали эту задачу таким образом: склад проектировался и адреса ячеек устанавливались таким образом, что кратчайший (конечно, с небольшой погрешностью) путь сборки заказа всегда получался простой сортировкой адресов. Конечно, тут не было красивых карт и прочего, но на 20000 ячеек хватало :)
shard; acanta; +2 Ответить
2. genayo 24.06.19 18:30 Сейчас в теме
Годно. Теперь нужно, чтоб алгоритм ещё и разводил наборщиков так, чтобы они не мешали друг другу.
maksa2005; CheBurator; informa1555; +3 Ответить
3. informa1555 2656 24.06.19 18:53 Сейчас в теме
(2) Спасибо. На начальном шаге их надо в максимально удаленные друг от друга места отправить, а вот потом - сложнее))
4. quaker94 24.06.19 19:14 Сейчас в теме
5. sm.artem 15 25.06.19 05:11 Сейчас в теме
Прям напомнило мою дипломную работу по оптимизации компоновок гибких производственных комплексов.
6. it@contlog.ru 25.06.19 06:28 Сейчас в теме
По моей оценке jump point search работает быстрее чем a* эта разница не ощутима на складе 10*10 но будет ощутимой на реальном.
Решение без конфигуратора не взлетело. Надо было выложить dt шку кроме как со скринов на странице не ясно чем заполнить бд чтобы проверить. Еще увидел работу с сетью, про это тоже интересно было-бы(dt). А так хороший старт!
7. informa1555 2656 25.06.19 06:46 Сейчас в теме
(6) почему не взлетело? Какая ошибка? По поводу чем заполнять бд - а там нет никаких данных в бд - все данные в форме обработки. Вы добавляете ряды со стеллажами, препятствия они добавляются в табличную часть обработки. Больше никаких данных.
9. it@contlog.ru 26.06.19 06:25 Сейчас в теме
(7) Это не список претензий, а скорее описание с чем столкнулся. Началось все с того что форма вылетала без ошибок - а оказывается это ошибка установки драйвера. ддл должена лежать в определенной папке о чем в описании ни слова зато сказано, что надо качать файл другой разработки, но на самом деле не надо все уже и так есть в цф.
Пришлось немного разкоментировать одни строки и закоментировать другие после чего драйвер увиделся.
Калибровка тоже не вкатила пока не комментировал проверку клика вне рабочего квадрата.
Все наладил но дальше надо было нарисовать свою карту с этим не ясно - поидее элементы должны автоматом привязываться к шагу выбраной сетки но этого не происходит препятствия клетки текст можно лепить где угодно.
Дальше что-то нажал и все зависло... не успел с этим разобраться.
10. informa1555 2656 26.06.19 07:45 Сейчас в теме
(9) Спасибо что сказали - убрал из макета компоненту. Калибровка должна работать. Может положение окна после калибровки поменялось?
8. Идальго 229 26.06.19 00:59 Сейчас в теме
Мне кажется, ещё прикольно будет сделать модельные-имитационные примеры (с визуазизацией), где попробовать посмотреть, на каких конфигурациях складов и нагрузках сборщики начнут мешать друг-другу (и на сколько сильно это скажется вообще) и использовать эти модели для проработки более эффективных моделей.
CheBurator; informa1555; +2 Ответить
11. informa1555 2656 26.06.19 07:47 Сейчас в теме
(8) Хорошая мысль! Если поведение каждого - идти к ближайшему то да, это можно сделать...
12. it@contlog.ru 28.06.19 04:19 Сейчас в теме
Что-то сбился с пути.
Прикрепленные файлы:
13. mpeg1989 131 30.06.19 09:53 Сейчас в теме
(12) Это другой грузчик его прикурить попросил.
rovenko.n; informa1555; +2 Ответить
14. informa1555 2656 30.06.19 11:02 Сейчас в теме
(12) А путь при этом не увеличился если считать по ячейкам. Так что все нормально.
rovenko.n; +1 Ответить
15. CheBurator 3122 05.07.19 00:26 Сейчас в теме
полезно. очень напоминает встречавшуюся мне статью в одном из логистических журналов, видимо потому что описывается тот же алгоритм построения маршрута "по квадратикам" ;-)
однако такой динамический расчет в массовых промышленных решениях вряд ли применим (имхо, ?). потому что в общем случае непонятно при больших количествах заказов, большого количества сборщиков, большого количества ограничений по ролям, лимитам и прочего - сколько понадобится на текущий расчет в горячем режиме. проще получается заранее рассчитать и выдавать по порядку обхода. Как частное решение - вполне себе годно.
informa1555; +1 Ответить
16. informa1555 2656 05.07.19 06:24 Сейчас в теме
(15) Спасибо! А нисколько не понадобится. Там все 1 раз считается, записывается в таблицу и в момент когда надо определить следующую цель - простенький запрос к таблице расстояний. Это настолько быстро что я даже не заморачиваюсь всякими многопоточными расчетами заданий как это сделано в 1Сных WMS, а просто отрисовываю на экране в При открытии. Расчет всей таблицы - это долго, да. Но как я и говорю он 1 раз- нарисовал, рассчитал, записал в таблицу. Все.
18. CheBurator 3122 07.04.22 00:49 Сейчас в теме
(16) поясни, плиз,
1. Сборщику на исполнение выдается пул заданий, где 1подход к ячейке = 1задание, или если правильнее (мультипикинг/кластерный отбор) 1подход к ячейке = Nзаданий, вариант когда сборщику (штучная/коробочная сборка) в пуле выдается всего 1ячейка - ну очень частный случай. Итого - у сборщика пул "обойти 40 ячеек" (причем пул уже заранее может быт отсортирован по типу "сначала тяжелое, потом легкое" и эту сортировку нарушать нельзя.
2. Система (по твоему) алгоритму "на лету" - во время выдачи на ТСД - быстро считает (по заранее насчитанным тяжелым данным) оптимальный путь обхода для полученного пула заданий (с учетом уже предусовновленной сортировки)
3. Система показывает/ведет сборщика по рассчитанному маршруту.
.
так?
19. informa1555 2656 07.04.22 10:45 Сейчас в теме
(18) 1) рисуешь графическую схему со стеллажами 2) обработкой получаешь 1 раз на все случаи жизни таблицу расстояний между всеми адресами полносвязанную (как таблица умножения). Все, дальше уже по этой таблице считается на лету. Т.е. допустим в начале ты пикнул ячейку 1-1-1, ок значит ты стоишь в ней. У тебя еще надо посетить 3 ячейки 2-0-0-1, 5-0-3-1 и 4-2-0-2 - делаешь левое соединение по таблице расстояний с отбором по ячейке 1-1-1-1 и сортируешь по полученному расстоянию по возрастанию. Все. Это интегрируется в любую WMS
20. CheBurator 3122 07.04.22 11:50 Сейчас в теме
(19) в итоге обсуждения выяснилось, что для построения маршрута все равно в общем случае надо решать оптимизационную задачу, где матрица расстояний, насчитанная (описанная в данной публикации) - будет использоваться в оптимизационном алгоритме.
.
а динамический маршрут - как в публикации - это в частных случаях, когда в данный момент времени для выдачи сборщику - всего одна ячейка. Выдали ее - побежал сборщик к ячейке. взял. пока бежал - еще одна ячейка-задание свалилось.
.
т.е. такая схема работы вполне может быть применима в условиях "нехватки времени", когда даже 5 минут нельзя подождать, чтобы накопить несколько ячеек хотя бы 3-4 в маршрут чтобы сократить холостые пробеги....
17. Pim 182 27.01.20 21:55 Сейчас в теме
Калибровка "без напильника" так и не работает. По совету коллеги убрал строки:
Если НЕ ((LPARAM_X >= ВерхнийЛевый_X и LPARAM_X <= НижнийПравый_X) и (LPARAM_Y >= ВерхнийЛевый_Y и LPARAM_Y <= НижнийПравый_Y)) Тогда
Возврат;
КонецЕсли;
21. rom-x 152 11.11.22 12:00 Сейчас в теме
было бы хорошо увидеть сразу демо базу dt в формате все в одном, чтобы поставить и посмотреть как это работает, без предварительной настройки.
22. informa1555 2656 11.11.22 12:19 Сейчас в теме
(21) у меня есть публикация (вот эта https://infostart.ru/1c/articles/1081085/) там демобаза рисовалки склада в 1С. Оно основано на компоненте из той публикации на которую я ссылаюсь. Без напильника с этим вариантом - никак. На выходе - таблица более менее реальных расстояний для планировщика WMS или какого то мобильного решения - 1Сного или не -1Сного. С другой стороны у меня в платформе(симпле) появился уже более гуманный редактор склада который можно использовать для этого алгоритма, осталось только одно с другим соединить)))
23. rom-x 152 11.11.22 16:24 Сейчас в теме
(22) видимо ссылкой ошиблись, видимо имели ввиду эту https://infostart.ru/public/976636/, соединить было бы неплохо, спасибо.
24. informa1555 2656 11.11.22 17:15 Сейчас в теме
(23) Я ошибся, но Simple WMS устаревший проект, вместо него сейчас Simlple UI
25. AII14789 14.11.22 12:16 Сейчас в теме
Кто-нибудь прикручивал к этой разработке Жадный поиск? Поделитесь решением...
Оставьте свое сообщение