Маршрут складского отбора: от списка ячеек к допустимому пути

Решение: какой физический обход выдать сотруднику

Рассматриваем фиксированный набор мест, из которых нужно отобрать товар и вернуться к упаковке. Размещение SKU и состав заказа уже определены. Мы не объединяем новые заказы, не меняем их приоритет и не проектируем склад.

Цель учебной модели — минимальная длина допустимого обхода. Геометрия проходов, направления движения и пригодность маршрута для человека и оборудования должны быть подтверждены отдельно. Расчёт не разрешает обходить физическую блокировку, менять организацию движения или проходить между стеллажами там, где такого пути нет.

Warehouse & Distribution Science рассматривает складской отбор как маршрут, ограниченный проходами, и отдельно отмечает различие между последовательностью мест и реальным путём. Bartholdi и Hackman: chapter 10.

Сначала карта связей, потом расстояния между ячейками

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

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

Google в примере TSP использует матрицу расстояний и отдельно задаёт начальную и конечную точку. Порядок индексов матрицы не является порядком исполнения. Google OR-Tools: distance matrix и depot. Для склада важно дополнительно сохранять путь, которым получено каждое расстояние.

Учебный граф с четырьмя узлами

Все числа вымышлены. D — точка начала и возврата у упаковки. A, B и C — три места обязательного отбора. Между ними в модели существуют следующие отдельные двусторонние разрешённые связи:

• D–A: 40 метров;
• D–B: 60 метров;
• D–C: 120 метров;
• A–B: 70 метров;
• A–C: 80 метров;
• B–C: 60 метров.

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

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

Ближайшее следующее место может дать лишний путь

Начнём с понятного правила: каждый раз выбирать ближайшее ещё не обслуженное место. Из D ближе A: 40 против 60 до B и 120 до C.

После A остаются B и C. До B 70, до C 80, поэтому выбирается B. Затем нужно посетить C за 60 и вернуться в D за 120.

Получается D→A→B→C→D длиной 40 + 70 + 60 + 120 = 290 метров. Все три места посещены, обязательный возврат включён. Это допустимый обход, но правило ближайшего шага не доказало минимальность всей поездки.

В документации OR-Tools построение первого решения также отделено от итогового поиска. Не следует объявлять любой результат жадного правила глобальным минимумом. Наша следующая проверка будет полной только благодаря малому размеру примера.

Проверьте все шесть порядков

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

1. A–B–C с началом и возвратом D: 290 метров.
2. A–C–B: 40 + 80 + 60 + 60 = 240.
3. B–A–C: 60 + 70 + 80 + 120 = 330.
4. B–C–A: 60 + 60 + 80 + 40 = 240.
5. C–A–B: 120 + 80 + 70 + 60 = 330.
6. C–B–A: 120 + 60 + 70 + 40 = 290.

Минимум равен 240; его достигают два противоположных обхода. Например, можно выдать D→A→C→B→D. Относительно ближайшего соседа путь короче на 50 метров.

Это доказательство для указанного маленького графа и набора условий. Оно не обещает тот же выигрыш на другом складе. Меньшее количество метров также не равно автоматически меньшей выплате сотруднику или более ранней отгрузке: могут изменяться ожидания и последующая обработка.

Закрытие связи меняет карту и матрицу

Теперь B–C закрыта. Её нужно исключить из допустимого графа. Нельзя оставить прежнее расстояние 60 между B и C в расчёте только потому, что оно сохранено в старой матрице.

От C до B теперь кратчайший путь проходит через A: C→A→B, 80 + 70 = 150. Через D было бы 120 + 60 = 180. Номер ячейки B остался прежним, но физический способ добраться до неё изменился.

Прежний список D→A→C→B→D после раскрытия переходов превращается в D→A→C→A→B→D. Его длина: 40 + 80 + 80 + 70 + 60 = 330 метров. Повтор A в физическом пути необходим для этого обхода и не является ошибкой списка требований.

Повторная полная проверка по новым кратчайшим расстояниям даёт для тех же шести порядков 380, 330, 330, 330, 330 и 380. Минимум нового графа — 330. Есть несколько подходящих обходов; названный путь не объявляется единственным.

Повторное прохождение не повторяет отбор

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

Предположим, сотрудник уже прошёл D→A→C, выполнил оба отбора и только тогда получил подтверждение закрытия B–C. Пройдено 120 метров, текущее место C; остаются B и возврат D.

Допустимое продолжение C→A→B→D занимает ещё 80 + 70 + 60 = 210 метров. Общий путь станет 330. Отбор в A повторять не нужно, а начинать новое задание как будто сотрудник и пустая тележка снова находятся в D нельзя.

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

Сохраните исполнимую версию задания

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

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

Односторонние проходы потребуют направленного графа: расстояние A→B может отличаться от B→A. Ограничение вместимости, обязательный порядок укладки или временные окна также меняют задачу. Не сохраняйте старое доказательство минимальности после добавления новых условий.

Приёмочный чек-лист

• Все шесть связей имеют подтверждённое направление и длину.
• Прямое расстояние на плане не заменяет путь по разрешённым связям.
• Ближайший сосед даёт 290, полный исходный минимум — 240.
• Возврат в D включён во все сравнения.
• Закрытая B–C удаляется и из графа, и из производных расстояний.
• Новый переход C→B раскрывается через A и имеет длину 150.
• Развёрнутый обход даёт 330, не содержит закрытого ребра.
• После выполненных A и C остаются 210 метров и только отбор B.
• Повторное посещение A не создаёт повторного взятия товара.

Для склада SABSUS и управления заказами подтвердите хранение этих данных и способ передачи маршрута. Граф проходов, поиск пути и автоматическое перепланирование не предполагаются готовыми возможностями конфигурации.

Частые вопросы

Достаточно отсортировать ячейки по коду?

Только если такой порядок действительно соответствует принятому процессу. Сам код не доказывает короткий или доступный путь.

Можно повторно пройти уже обслуженную ячейку?

В модели — да, по разрешённым связям. Повтор прохода не создаёт повторного требования отбора.

Почему прежний маршрут стал длиннее без новых товаров?

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

Источники

• Bartholdi, Hackman: Warehouse & Distribution Science 0.98.1, chapter 10.
• Google OR-Tools: Traveling Salesperson Problem.

Проверено 9 октября 2026 года. Граф и числовые обходы редакционные, не план реального склада.