Комментарии 19
Пройдите уже пару вводных курсов по машинному обучению, и вам перестанет казаться, что между теоремой Пифагора и k ближайших соседей много общего :)
У меня непрофильный вопрос. А зачем в описанных условиях это потребовалось программисту без профильного образования?
Попробую ответить за автора. Может чтобы немного подрасти, почувствовать свои возможности, развить их и идти дальше?
@Zhuikoffуже верно ответил - для меня это главная причина. Есть и другая - кто-то же должен это делать? У предприятия есть потребность, а из свободных людей только я.
Чем это не задача коммивояжера(traveling salesman problem)?
Задача коммивояжера подходит, конечно же!
Однако в статье не описать всех нюансов - многое опущено. Если кратко: поиск k-ближайших соседей позволяет эффективней объединить некоторые товары в группы. На волновой сборке (та, которая в два этапа) это экономит число спуско-подъёмных операций раз в 40.
Проблема в том, что для предложенного алгоритма не очевидны критерии оптимальности. Можно было бы на небольших примерах, сравнить его с честным комбинаторным решением дающим глобальный оптимум.
Они потому и не приведены, так как решение не является оптимальным, а лишь возможным. Там был рост всего в ~2%. Вам, например, это сразу бросилось в глаза и, вероятно, очевидно даже на интуитивном уровне.
Я потому и написал, что алгоритм выдал скромные результаты и перекочевал из сборочных листов. Когда появились ресурсы, они стали генерироваться иначе.
Так и не понял, по какому именно маршруту идут сборщики после вашей обработки их листа. Просто после каждого предмета жадно идут к ближайшему (с точки зрения вашей "близости") невзятому продукту и берут его?
Строчки в сборочном листе выстраиваются так, что сумма "близости" для всего листа максимальная. Допустим, есть четыре товара с такими показателями:
Первый и второй имеют "близость" 10.
Первый и третий: 9.
Первый и четвёртый: 8.
Второй и третий: 7.
Второй и четвёртый: 6.
Третий и четвёртый: 5.
При таких показателях наибольшая сумма может быть 25. Например, она будет у такой последовательности сборки:
Товар №3, потом товар №1, потом товар №2, потом №4.
25 здесь получается как сумма: 9+10+6.
При всех возможных комбинациях такая сумма может быть у нескольких маршрутов (3->2->1->4, либо 4->1->2->3, например). Какой выбирается из них - это ещё один "алгоритм".
Верно! При сборке нахрапом - я уверен - это не будет работать вообще. Впрочем, я ещё не работал на складах с хаотичной сборкой. На одном складе сборка шла раздельно по "зонам": дорогостоящие препараты собирали одни (важные) люди, сильнодействующие препараты - другие (надёжные) и т. п. Так сотрудники равномерно распределялись по всему помещению.
На другом использовался ещё более хитрый алгоритм, но, на самом деле, он хорошо работал только в теории, а на практике лишь при стечении обстоятельств.
Так что да - как ни крути, только одним алгоритмом на крупном складе не обойтись. Нужно и листы разделять, и строчки сортировать, и приоритеты в динамике менять, и вот это вот всё.
Симплекс-метод?
Не, не слышали...
Да, верно. На тот момент для меня 99,9% всего это было чем-то новым: "Линейное программирование? Что это такое? В моём вузе такого не бывает!"
Даже вменяемая статья на хабре появилась спустя год. Собственно, так всегда: сначала возникает потребность, а уже потом человек начинает разбираться в теме. Реализация своих велосипедов как раз происходит между ними.
Навскидку вопросы по алгоритму:
1. Проходы между полками имеют одинаковую ширину или есть "магистрали/улицы/переулки".
2. Брать товары можно с любой стороны полки, или обязательно заходить "спереди".
3. Есть ли разница в движении между точками (1,7)-(3,7) и (3,7)-(3,5) на вашей схеме (первая цифра - координата по горизонтали). Разница на практике и в вашем алгоритме.
4. В любом ли проходе между полками может развернуться погрузчик? То есть - нужно ли учитывать необходимость доп. телодвижений, когда нужно достать груз с двух полок, расположенных напротив друг друга через проход? Различаются ли скорости движения "вперёд" и "назад" у погрузчика? Могут ли два погрузчика разъехаться в одном проезде?
5. В любой ли проход может пройти человек со стремянкой? Учитывается ли в алгоритме необходимость идти в другой конец склада за стремянкой (если идёт сначала сбор в дальнем конце)?
6. Ограничены ли дополнительные ресурсы (стремянка, погрузчик) по количеству?
7. Как влияют друг на друга рабочие, собирающие заказ в одном переулке/на одном стеллаже/на одной полке?
В реальном складе, конечно же, ширина разная. Кстати, ячейки тоже.
Ячейки с разных сторон одного стеллажа - это у нас разные ячейки. Поэтому подойти можно только с одной стороны.
Сложный вопрос, тем более, если обобщить. Думаю, разница с практикой больше, чем в половине случаев.
Нужно учитывать, но не учитывается. Причём, не только в рамках статьи. Я это и в реальности тогда не смог учесть - вся техника как будто в идеальных условиях и никогда не сталкивается с проблемами. Вся техника, к слову, была поделена на два вида: стремянка и погрузчик.
Как и в п. 1, и в п. 4 - не в любой. Некоторые проходы заставлены сезонным товаром, поэтому не пролезть. Но, на удивление, это учитывалось. Проходы между стеллажами в системе заведены как виртуальные ячейки, поэтому на них и товар вполне официально числится, и размеры в системе есть, но есть признак, что по ней можно пройти, когда пустая.
5.1. Необходимость в стремянке и погрузчике позже стал учитывать отдельным вычислением, в этот алгоритм не вписалось.Да, техники ограничена и в дефиците. Сборочному листу назначается конкретный экземпляр.
Как? Конечно же, мешают друг другу. Иногда дерутся. Чтобы избежать заторов разбиваю сборку по зонам, чтобы люди и техника максимально разбрелись по складу и их плотность на кв. м. была минимальной
Не совсем по теме, но может кому то пригодится "Сравниваем open-source решения VRP задачи"
Улучшаем маршруты обхода на складе силами веб-программиста и математики