Улучшаем маршруты обхода на складе силами веб-программиста и математики20.11.2022 14:31

Сразу к сути: есть склад, где все бизнес-процессы уже отлажены и в целом всех всё устраивает. Ничего, что даст рост в 30%, сделать уже невозможно, но хочется. Поставлена цель: оптимизировать маршрут, по которому идёт сборщик товаров, чтобы товар собирался быстрее. Результат 2–3% роста вполне устроит. Ограничения:

останавливать работу склада для экспериментов нельзя
денег — кроме зарплаты — не выделим
специалистов в этой области не имеется — свободен только веб-программист, да и тот без профильного образования
закончить нужно не то, чтобы ещё вчера, но через две недели точно.

Статью можно считать продолжением темы наглядного применения известных алгоритмов где-нибудь в промышленности. В этот раз в работу вступает алгоритм k-ближайших соседей.

Для прочтения знать сам алгоритм k-ближайших соседей не требуется — он очень простой и станет ясен ещё в ходе прочтения. Он чем-то похож на теорему Пифагора, только на стероидах.

Для нетерпеливых сразу обозначу основную идею: скорость сборки товара зависит от того, в каком порядке его собирать. Сборщики собирают товар по бумажным листам примерно такого вида:

Товар	Срок годности	Количество	Ячейка
Блины 20 см. №10	3 дня	4	03–02–07
Блины со сгущёнкой 25 см. №4	2 дня	4	02–02–01
Варенье земляничное, 400 г.	01.08.2023	1	01–01–05

Здесь строчки пока что отсортированы по ячейкам: от самой дальней к самой ближней. Ячейки имеют такой формат наименования: /номер_стеллажа/-/номер_полки/-/номер_ячейки/. Стеллажи 01 и 02 находятся у входа и следующие идут по нарастающей. Мы попробуем отсортировать строчки в более оптимальном порядке.

Программирования в статье нет — уклон сделан на последовательность действий, которые приспособят алгоритм к жизни. Любой базовый алгоритм, к сожалению, достаточно сырой, словно осенняя погода за окном, поэтому в первозданном виде в эксплуатацию не пойдёт.

Начнём пристрелку

Если сталкиваемся с поиском оптимального маршрута в первый раз, то с вероятностью 100% поисковик расскажет нам об алгоритме Дейкстры. Беглый осмотр алгоритма покажет, что он не умеет работать с отрицательными весами и имеет ещё несколько минусов. Этой информации ещё недостаточно, чтобы отвергнуть его или, наоборот, продолжить копать под него глубже. Таким образом мы сталкиваемся с первым выбором: ищем новый алгоритм, или дорабатываем этот? В статье про алгоритм Левенштейна мы пошли вторым путём, здесь для примера пойдём первым. Если есть подозрительные особенности алгоритма, важность которых вам не очевидна — это первый звоночек, чтобы вы пошли искать что-то другое. Не стоит считать, что это универсальное правило, но часто это именно так и может экономить время.

Лайфхак, чтобы при поисках решений начать мыслить шире

Гораздо полезней научиться переформулировать изначальную цель. Это может дать новые идеи для поисков, затронув смежные сферы. В данном случае можно перефразировать «поиск оптимального маршрута» в «поиск рекомендуемого маршрута». Это незначительное изменение не только изменит выдачу поисковой системы, но и сразу покажет нам интересные примеры. Я, например, наткнулся на то, как с помощью алгоритма поиска k-ближайших соседей выстроили систему рекомендаций в каком-то интернет-магазине (сообщения в стиле: «возможно, вам понравится этот товар»).

Как я уже писал, сборщики работают с помощью сборочных листов. Рабочий день у них идёт так:

Печатаем сборочный лист
Идём налегке к самой дальней ячейке из листа и от неё направляемся ко всем остальным, постепенно набирая товар в корзинку или тележку

Если бы склад был одноэтажным, а ещё узким и длинным, а ещё без разветвлений, а ещё и без перекрёстков, а ещё с рациональным размещением самих товаров, то текущий принцип работы наверняка можно было бы считать оптимальным. Почему? Потому что самый большой отрезок пути человеку нужно идти налегке, а наибольший груз накапливается уже ближе к зоне выгрузки товара.

Из этого описания уже вырисовываются первые критерии, которые осложняют ручной труд и которые мы учтём в алгоритме. Сейчас мы пока ещё рассмотрим упрощённую версию склада, чтобы не отвлекаться от процесса внедрения алгоритма в жизнь людей.

На каких критериях, влияющих на сборку, остановимся? Для примера попробуем эти:

«Этаж» полки на стеллаже, на котором находится эта ячейка
Расстояние до ячеек (кстати, как от места старта, так и между ними)
Масса переносимого товара
Количество «особенных» точек на пути между ячейками

«Особенными» точками считаются повороты и перекрёстки.

А как вообще выбирать эти и другие критерии? Идти на склад, смотреть своими глазами на его работу, а также включать логику. По-хорошему, это всё должен делать бизнес-аналитик, но, как вы помните, у нас его нет.

Первые два критерия сильно связаны с «географией» склада. Остановимся на них подробней. Как их представить в цифровом виде? Ничего нового придумывать не нужно — вы уже сами хорошо знаете эту двухмерную систему координат:

А вот упрощённый пример обозначения стеллажей на такой сетке:

В этом примере все стеллажи кроме одного имеют по три ячейки на полке. Все координаты ячеек отсчитываются от общей точки отсчёта. Для удобства, она размещена в левом нижнем углу, чтобы все значения были положительными числами — это удобней. Этаж учитывается с помощью добавления третьего измерения. Единицы измерения осей пока не нужны.

Для тех кому метрики интересней, чем сам алгоритм — прочитайте текст под спойлером.

Пройдёмся по каждой из них с картинками

Высота полки

С нижних полок собирать товар проще, поэтому их приоритет нужно сделать выше. Полки нумеруются с единицы от нижней к верхней. Первая и вторая полки анатомически одинаково удобны для изъятия товара и поэтому получат одинаковый приоритет. Полки, начиная с третьей, находятся слишком высоко, поэтому для работы с ними нужна стремянка или подъёмник. Подъёмнику особо без разницы куда тянуться — на третью полку, либо на пятую, поэтому все полки от третьей и выше тоже получат одинаковый рейтинг, но не такой, как у двух нижних.

Что это даст сборщику? Это даст возможность сперва собрать товар с одного уровня, а потом полностью с другого. Не нужно будет брать подъёмник для сборки первого товара и затем возвращать, чтобы потом снова взять его для сборки, например, пятого. То, какие ячейки собирать первыми — высокие или низкие — пока оставим открытым вопросом. Это легко можно поменять однократным измерением приоритета.

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

Расстояние до ячеек

Тут объяснять нечего, всё предельно просто:

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

На рисунке обозначено три маршрута: зелёный, бирюзовый и красный. Все три ведут из точки (0;4) в точку (13;7). Визуально заметно, что пройденное расстояние у всех трёх совпало, хотя количество поворотов у всех отличается.

На уровне БД для этого тоже лучше завести отдельную таблицу, так как её часто придётся join-ить с другими. Важно понимать, что единицей измерения расстояния не обязательно будут метры. Также как удава в известном мультике измеряли в попугаях, мы можем измерять расстояние, например, в ячейках или других условных единицах.

Количество особенных точек на пути

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

Нам нужно сделать так, чтобы между каждым товаром количество таких точек было минимальным. И тут есть проблема — наличие разных маршрутов. Ещё раз посмотрите на предыдущую картинку:

у зелёного маршрута есть четыре особенных точки: два поворота и два перекрёстка между ними
у бирюзового маршрута четыре точки: все из них перекрёстки
у красного маршрута вообще количество точек можно посчитать по-разному, так как часть стеллажей на него выходят торцом, а часть стоят вдоль. Некоторые промежутки между ними при этом совмещены как в точке (5;4), а вот точка (13;4) — нет.

То есть длина маршрута в метрах у всех такая же, а количество препятствий — нет.

Масса товара

Здесь вообще ничего сложного — информация не требует предварительного исследования и уже есть в WMS. Массу единицы товара умножаем количество и получаем сборочный вес.

Как выглядит алгоритм?

Если человек знает теорему Пифагора, то и с алгоритмом поиска k-ближайших соседей справится. Как я уже намекал, теорема Пифагора является его частным случаем. Сравните теорему:

a^2 = b^2 + c^2

И наш алгоритм для случая с тремя признаками:

a^2 = b^2 + c^2 + d^2

У теоремы Пифагора b — это длина первого катета, а c — длина второго. На рисунке ниже первый катет — это (x2-x1), а второй — это (y2-y1). Длина катета — это разность координат его конечной точки и начальной, убедитесь в этом из рисунка:

У алгоритма k-ближайших соседей из примера выше есть три параметра: b, c и d. Это тоже разность между значениями этих параметров. Если сравнивать нужно 10 характеристик, то и слагаемых в правой части тоже будет 10.

Вот, собственно, и весь алгоритм. Алгоритмы нередко бывают такими простыми, но часто их преподают странные чудаки на букву «м». Из-за этого не все учащиеся получают даже поверхностную картину. О том, как их применять — ещё меньше. В основном обучение ограничивается зубрёжкой каноничной формулировки и самой обобщённой математической формулы.

На уровне кода наш алгоритм — это функция, которая принимает на вход два товара из сборочного листа, а в ответ возвращает какое-то число. Это число показывает то, как эти товары «близки» между собой. «Близость» — это вовсе не то, о чём вы подумали. Да, речь не об их физической близости: 2 метра, 7 или 10. Близкими они являются по совокупности предложенных мной параметров. Чем меньше число, тем они ближе друг к другу, тем лучше их собирать вместе. Наверное.

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

	Блины 20 см. №10	Блины со сгущёнкой 25 см. №4	Варенье земляничное, 400 г.
Блины 20 см. №10	0
Блины со сгущёнкой 25 см. №4		0
Варенье земляничное, 400 г.			0

Кстати, а почему мы отталкиваемся от товаров, а не от признаков?

Отталкиваться от товаров в сборочном листе удобно из-за того, что их обычно немного. Их полный перебор не займёт много времени, даже если сложность возрастает квадратично. Это называется сложностью O (n2), когда при увеличении числа товаров в 10 раз объём работы увеличивается сразу в 100 раз, при увеличении в 5 раз — в 25 и т. д. Для небольших сборочных листов — самое оно. Признаков, правда, у нас тоже немного, поэтому обратный подход тоже имеет право на жизнь.

Покажу пример того, как нужно начинать расчёт и исправлять в нём первые ошибки/проблемы. Давайте вспомним метрики:

«Этаж» полки на стеллаже
Расстояние до ячейки
Масса товара
Количество «особенных» точек на пути

Сравним обычные блины (товар №1) из нашего сборочного листа с блинами со сгущёнкой (товар №2). У них третья и вторая полка (этаж) соответственно. Масса у первых, например, 40 г, а у вторых 80 г. Расстояние мы измеряем линейкой и получаем, допустим, 20 метров до первых и 28 метров до вторых. Количество особенных точек считаем на пальчиках и насчитываем 3 и 4. Черновой вид формулы у нас получается такой:

a^2 = (3-2)^2 + (80-40)^2 + (28-20)^2 + (4-3)^2

Думаю, теперь по алгоритму вопросов больше не осталось и как действовать программисту — ясно. Но внимательные и критически настроенные читатели сразу увидят в алгоритме недостаток: критерии неравноценны. Например, масса блинчиков вносит куда более существенный вклад, чем высота полки. А ещё в текущем виде формула зависит от единиц измерения. Если мы начнём измерять массу в килограммах, то результат кардинально изменится:

a^2 = (3-2)^2 + (0.08-0.04)^2 + (28-20)^2 + (4-3)^2

Это противоестественно, ведь ситуация с товаром не поменялась, а результат уже другой!

Решение для этих проблем уже придумали, причём оно одно для обеих: нормализация. Её идея заключается в том, что в формулу нужно подставлять не сами величины, а их преобразованные версии. Как их преобразовывать? Придумано несколько вариантов, я покажу один из них:

$x_0 = \frac{(x - \min(X))}{(\max(X)-\min(X))}$

После такого преобразования все критерии будут лежать в интервале от 0 до 1 и без всяких единиц измерения. Это очевидный момент, или всё же не очень?

С алгоритмом разобрались, а как это воплощать в жизнь?

Нужно «всего лишь» это:

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

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

А по второму пункту? Аналитики и здесь могут развернуть целое совещание, придумав самые разные показатели от простых до сложных. На мой взгляд, всё гораздо проще — это время. Помните первоначальную формулировку вопроса? Товар должны собирать быстрее.

Чуть-чуть скучного текста про то, как получить информацию по ячейкам

Список ячеек, как правило, в любой WMS уже есть. Там же — в идеале — присутствуют масса и размеры товара.

Что с остальными параметрами? Хотя это не работа программиста, лучше организовать её самому.

Сперва обращаемся к главному инженеру (или кто у вас там?) и в срочном порядке требуем актуальный план всех этажей склада с указанием размеров здания. Если человек сговорчивый — просим ещё, чтобы сам убрал с плана ненужные нам условные обозначения огнетушителей, эвакуационных выходов и всего такого.

Далее находим сравнительно низкооплачиваемого сотрудника, который пройдётся с планом здания по складу и нанесёт на него местоположение ячеек в метрах. Как вы помните, дополнительного финансирования нам выделять не стали, но истинный программист может придумать алгоритм, чтобы это обойти. Например, можно сходить в бухгалтерию и ласково попросить их написать приказ на «инвентаризацию стеллажей и осмотра их технического состояния». Когда бухгалтерия говорит: «Нам это нужно, это же инвентаризация!», им не отказывают. Конечно, точность такого плана будет хромать, но в качестве отправной точки — отличное начало. Из своей практики скажу, что здесь я столкнулся с проблемами, которых я никак не ждал:

не все люди умеют пользоваться рулеткой
не все люди могут научиться пользоваться рулеткой
обычная рулетка может стать причиной массовой драки среди сотрудников (видео 18+)

После проведения этого мероприятия у нас будет бумажный план, на котором напротив каждой ячейки написан её размер с неизвестной долей погрешности. Теперь это нужно оцифровать и, скорее всего, это будете делать вы и вручную. В каких-то случаях это будет очень большой объём работы, но мне повезло — склад имеет периодическую структуру и значительную часть данных удалось скопировать.

Как всё это хранить в БД? К сожалению, этот вопрос тоже будет опущен, так как тянет на ещё одну статью. Признаки ячеек можно попробовать хранить и в

Странно, но это всё

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

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

P. S. Я бы сам с удовольствием почитал другие примеры применения алгоритмов. Любопытно посмотреть, как бездонный кувшин народной смекалки орошает наши бескрайние поля трудовых будней.