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

Публикация № 1081085

Программирование - Практика программирования

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

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

Введение

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

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

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

 

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

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

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

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

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

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

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

 

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

48

Скачать файлы

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

См. также

Специальные предложения

Комментарии
Избранное Подписка Сортировка: Древо
1. Fragster 863 24.06.19 18:24 Сейчас в теме
В свое время решали эту задачу таким образом: склад проектировался и адреса ячеек устанавливались таким образом, что кратчайший (конечно, с небольшой погрешностью) путь сборки заказа всегда получался простой сортировкой адресов. Конечно, тут не было красивых карт и прочего, но на 20000 ячеек хватало :)
2. genayo 24.06.19 18:30 Сейчас в теме
Годно. Теперь нужно, чтоб алгоритм ещё и разводил наборщиков так, чтобы они не мешали друг другу.
informa1555; +1 Ответить
3. informa1555 1037 24.06.19 18:53 Сейчас в теме
(2) Спасибо. На начальном шаге их надо в максимально удаленные друг от друга места отправить, а вот потом - сложнее))
4. quaker94 24.06.19 19:14 Сейчас в теме
5. sm.artem 12 25.06.19 05:11 Сейчас в теме
Прям напомнило мою дипломную работу по оптимизации компоновок гибких производственных комплексов.
6. it@contlog.ru 25.06.19 06:28 Сейчас в теме
По моей оценке jump point search работает быстрее чем a* эта разница не ощутима на складе 10*10 но будет ощутимой на реальном.
Решение без конфигуратора не взлетело. Надо было выложить dt шку кроме как со скринов на странице не ясно чем заполнить бд чтобы проверить. Еще увидел работу с сетью, про это тоже интересно было-бы(dt). А так хороший старт!
7. informa1555 1037 25.06.19 06:46 Сейчас в теме
(6) почему не взлетело? Какая ошибка? По поводу чем заполнять бд - а там нет никаких данных в бд - все данные в форме обработки. Вы добавляете ряды со стеллажами, препятствия они добавляются в табличную часть обработки. Больше никаких данных.
9. it@contlog.ru 26.06.19 06:25 Сейчас в теме
(7) Это не список претензий, а скорее описание с чем столкнулся. Началось все с того что форма вылетала без ошибок - а оказывается это ошибка установки драйвера. ддл должена лежать в определенной папке о чем в описании ни слова зато сказано, что надо качать файл другой разработки, но на самом деле не надо все уже и так есть в цф.
Пришлось немного разкоментировать одни строки и закоментировать другие после чего драйвер увиделся.
Калибровка тоже не вкатила пока не комментировал проверку клика вне рабочего квадрата.
Все наладил но дальше надо было нарисовать свою карту с этим не ясно - поидее элементы должны автоматом привязываться к шагу выбраной сетки но этого не происходит препятствия клетки текст можно лепить где угодно.
Дальше что-то нажал и все зависло... не успел с этим разобраться.
10. informa1555 1037 26.06.19 07:45 Сейчас в теме
(9) Спасибо что сказали - убрал из макета компоненту. Калибровка должна работать. Может положение окна после калибровки поменялось?
8. Идальго 116 26.06.19 00:59 Сейчас в теме
Мне кажется, ещё прикольно будет сделать модельные-имитационные примеры (с визуазизацией), где попробовать посмотреть, на каких конфигурациях складов и нагрузках сборщики начнут мешать друг-другу (и на сколько сильно это скажется вообще) и использовать эти модели для проработки более эффективных моделей.
CheBurator; informa1555; +2 Ответить
11. informa1555 1037 26.06.19 07:47 Сейчас в теме
(8) Хорошая мысль! Если поведение каждого - идти к ближайшему то да, это можно сделать...
12. it@contlog.ru 28.06.19 04:19 Сейчас в теме
Что-то сбился с пути.
Прикрепленные файлы:
13. myxins1989 47 30.06.19 09:53 Сейчас в теме
(12) Это другой грузчик его прикурить попросил.
rovenko.n; informa1555; +2 Ответить
14. informa1555 1037 30.06.19 11:02 Сейчас в теме
(12) А путь при этом не увеличился если считать по ячейкам. Так что все нормально.
rovenko.n; +1 Ответить
15. CheBurator 3389 05.07.19 00:26 Сейчас в теме
полезно. очень напоминает встречавшуюся мне статью в одном из логистических журналов, видимо потому что описывается тот же алгоритм построения маршрута "по квадратикам" ;-)
однако такой динамический расчет в массовых промышленных решениях вряд ли применим (имхо, ?). потому что в общем случае непонятно при больших количествах заказов, большого количества сборщиков, большого количества ограничений по ролям, лимитам и прочего - сколько понадобится на текущий расчет в горячем режиме. проще получается заранее рассчитать и выдавать по порядку обхода. Как частное решение - вполне себе годно.
informa1555; +1 Ответить
16. informa1555 1037 05.07.19 06:24 Сейчас в теме
(15) Спасибо! А нисколько не понадобится. Там все 1 раз считается, записывается в таблицу и в момент когда надо определить следующую цель - простенький запрос к таблице расстояний. Это настолько быстро что я даже не заморачиваюсь всякими многопоточными расчетами заданий как это сделано в 1Сных WMS, а просто отрисовываю на экране в При открытии. Расчет всей таблицы - это долго, да. Но как я и говорю он 1 раз- нарисовал, рассчитал, записал в таблицу. Все.
Оставьте свое сообщение