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

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 логистика

См. также

Поинтегрируем: сервисы интеграции – новый стандарт или просто коннектор?

Обмен между базами 1C Администрирование СУБД Механизмы платформы 1С Платформа 1С v8.3 Бесплатно (free)

В платформе 8.3.17 появился замечательный механизм «Сервисы интеграции». Многие считают, что это просто коннектор 1С:Шины. Так ли это?

11.03.2024    3574    dsdred    48    

66

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

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

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

24.01.2024    5033    YA_418728146    25    

62

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

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

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

11.12.2023    6161    dsdred    36    

110

1С-ная магия

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

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

06.10.2023    18197    SeiOkami    46    

116

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

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

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

14.09.2023    11767    human_new    27    

72

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

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

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

28.08.2023    8559    YA_418728146    6    

139

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

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

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

20.08.2023    6198    sebekerga    54    

93

Все скопируем и вставим! (Буфер обмена в 1С 8.3.24)

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

Рассмотрим новую возможность 8.3.24 и как её можно эффективно использовать

27.06.2023    15528    SeiOkami    31    

103
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. Fragster 1137 24.06.19 18:24 Сейчас в теме
В свое время решали эту задачу таким образом: склад проектировался и адреса ячеек устанавливались таким образом, что кратчайший (конечно, с небольшой погрешностью) путь сборки заказа всегда получался простой сортировкой адресов. Конечно, тут не было красивых карт и прочего, но на 20000 ячеек хватало :)
shard; acanta; +2 Ответить
2. genayo 24.06.19 18:30 Сейчас в теме
Годно. Теперь нужно, чтоб алгоритм ещё и разводил наборщиков так, чтобы они не мешали друг другу.
CheBurator; informa1555; +2 Ответить
3. informa1555 2605 24.06.19 18:53 Сейчас в теме
(2) Спасибо. На начальном шаге их надо в максимально удаленные друг от друга места отправить, а вот потом - сложнее))
4. quaker94 24.06.19 19:14 Сейчас в теме
5. sm.artem 14 25.06.19 05:11 Сейчас в теме
Прям напомнило мою дипломную работу по оптимизации компоновок гибких производственных комплексов.
6. it@contlog.ru 25.06.19 06:28 Сейчас в теме
По моей оценке jump point search работает быстрее чем a* эта разница не ощутима на складе 10*10 но будет ощутимой на реальном.
Решение без конфигуратора не взлетело. Надо было выложить dt шку кроме как со скринов на странице не ясно чем заполнить бд чтобы проверить. Еще увидел работу с сетью, про это тоже интересно было-бы(dt). А так хороший старт!
7. informa1555 2605 25.06.19 06:46 Сейчас в теме
(6) почему не взлетело? Какая ошибка? По поводу чем заполнять бд - а там нет никаких данных в бд - все данные в форме обработки. Вы добавляете ряды со стеллажами, препятствия они добавляются в табличную часть обработки. Больше никаких данных.
9. it@contlog.ru 26.06.19 06:25 Сейчас в теме
(7) Это не список претензий, а скорее описание с чем столкнулся. Началось все с того что форма вылетала без ошибок - а оказывается это ошибка установки драйвера. ддл должена лежать в определенной папке о чем в описании ни слова зато сказано, что надо качать файл другой разработки, но на самом деле не надо все уже и так есть в цф.
Пришлось немного разкоментировать одни строки и закоментировать другие после чего драйвер увиделся.
Калибровка тоже не вкатила пока не комментировал проверку клика вне рабочего квадрата.
Все наладил но дальше надо было нарисовать свою карту с этим не ясно - поидее элементы должны автоматом привязываться к шагу выбраной сетки но этого не происходит препятствия клетки текст можно лепить где угодно.
Дальше что-то нажал и все зависло... не успел с этим разобраться.
10. informa1555 2605 26.06.19 07:45 Сейчас в теме
(9) Спасибо что сказали - убрал из макета компоненту. Калибровка должна работать. Может положение окна после калибровки поменялось?
8. Идальго 226 26.06.19 00:59 Сейчас в теме
Мне кажется, ещё прикольно будет сделать модельные-имитационные примеры (с визуазизацией), где попробовать посмотреть, на каких конфигурациях складов и нагрузках сборщики начнут мешать друг-другу (и на сколько сильно это скажется вообще) и использовать эти модели для проработки более эффективных моделей.
CheBurator; informa1555; +2 Ответить
11. informa1555 2605 26.06.19 07:47 Сейчас в теме
(8) Хорошая мысль! Если поведение каждого - идти к ближайшему то да, это можно сделать...
12. it@contlog.ru 28.06.19 04:19 Сейчас в теме
Что-то сбился с пути.
Прикрепленные файлы:
13. mpeg1989 130 30.06.19 09:53 Сейчас в теме
(12) Это другой грузчик его прикурить попросил.
rovenko.n; informa1555; +2 Ответить
14. informa1555 2605 30.06.19 11:02 Сейчас в теме
(12) А путь при этом не увеличился если считать по ячейкам. Так что все нормально.
rovenko.n; +1 Ответить
15. CheBurator 3119 05.07.19 00:26 Сейчас в теме
полезно. очень напоминает встречавшуюся мне статью в одном из логистических журналов, видимо потому что описывается тот же алгоритм построения маршрута "по квадратикам" ;-)
однако такой динамический расчет в массовых промышленных решениях вряд ли применим (имхо, ?). потому что в общем случае непонятно при больших количествах заказов, большого количества сборщиков, большого количества ограничений по ролям, лимитам и прочего - сколько понадобится на текущий расчет в горячем режиме. проще получается заранее рассчитать и выдавать по порядку обхода. Как частное решение - вполне себе годно.
informa1555; +1 Ответить
16. informa1555 2605 05.07.19 06:24 Сейчас в теме
(15) Спасибо! А нисколько не понадобится. Там все 1 раз считается, записывается в таблицу и в момент когда надо определить следующую цель - простенький запрос к таблице расстояний. Это настолько быстро что я даже не заморачиваюсь всякими многопоточными расчетами заданий как это сделано в 1Сных WMS, а просто отрисовываю на экране в При открытии. Расчет всей таблицы - это долго, да. Но как я и говорю он 1 раз- нарисовал, рассчитал, записал в таблицу. Все.
18. CheBurator 3119 07.04.22 00:49 Сейчас в теме
(16) поясни, плиз,
1. Сборщику на исполнение выдается пул заданий, где 1подход к ячейке = 1задание, или если правильнее (мультипикинг/кластерный отбор) 1подход к ячейке = Nзаданий, вариант когда сборщику (штучная/коробочная сборка) в пуле выдается всего 1ячейка - ну очень частный случай. Итого - у сборщика пул "обойти 40 ячеек" (причем пул уже заранее может быт отсортирован по типу "сначала тяжелое, потом легкое" и эту сортировку нарушать нельзя.
2. Система (по твоему) алгоритму "на лету" - во время выдачи на ТСД - быстро считает (по заранее насчитанным тяжелым данным) оптимальный путь обхода для полученного пула заданий (с учетом уже предусовновленной сортировки)
3. Система показывает/ведет сборщика по рассчитанному маршруту.
.
так?
19. informa1555 2605 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 3119 07.04.22 11:50 Сейчас в теме
(19) в итоге обсуждения выяснилось, что для построения маршрута все равно в общем случае надо решать оптимизационную задачу, где матрица расстояний, насчитанная (описанная в данной публикации) - будет использоваться в оптимизационном алгоритме.
.
а динамический маршрут - как в публикации - это в частных случаях, когда в данный момент времени для выдачи сборщику - всего одна ячейка. Выдали ее - побежал сборщик к ячейке. взял. пока бежал - еще одна ячейка-задание свалилось.
.
т.е. такая схема работы вполне может быть применима в условиях "нехватки времени", когда даже 5 минут нельзя подождать, чтобы накопить несколько ячеек хотя бы 3-4 в маршрут чтобы сократить холостые пробеги....
17. Pim 180 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 2605 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 2605 11.11.22 17:15 Сейчас в теме
(23) Я ошибся, но Simple WMS устаревший проект, вместо него сейчас Simlple UI
25. AII14789 14.11.22 12:16 Сейчас в теме
Кто-нибудь прикручивал к этой разработке Жадный поиск? Поделитесь решением...
Оставьте свое сообщение