Введение

Когда вы вызываете такси в одном из современных агрегаторов, ваше местоположение определяется и какой-то из находящихся рядом таксистов берет заказ. Ему не приходится ехать из таксопарка, он экономит ваше время и деньги. Этот принцип изменил бизнес перевозок. В складах с высокой проходимостью заказы обрабатываются построчно. Один заказ может собирать несколько человек. Даже одну строчку заказа может собирать несколько человек. Современные 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 может быть устроено по разному: может быть пул заданий на пикинг в виде объектов базы данных, которые ждут когда будет назначен либо не быть таких объектов а само задание просто высвечивается в виде надписи на экране ТСД. В любом случае имея полносвязанную таблицу реальных расстояний можно использовать этот принцип в любой системе.