The 20 reference contexts in paper E. Korobkov V., Е. Коробков В. (2016) “Процесс комплектования заказов на складе. Задача маршрутизации сборщиков заказов // Warehouse order-picking process. Order-picker routing problem” / spz:neicon:technomag:y:2015:i:4:p:270-310

  1. Start
    2030
    Prefix
    (dimensioning) складской системы; – распределение товаров по ячейкам хранения (storage assignment); – распределение по партиям (batching) и зонирование (zoning); – накопление заказов/сортировка (accumulation/sortation); – маршрутизация (routing) сборщиков заказов. Первые четыре подзадачи рассмотрены в первой статье цикла «Процесс комплектования заказов на складе»
    Exact
    [1]
    Suffix
    . Данная статья посвящена подзадаче маршрутизации сборщиков заказов. Структура статьи следующая. В п. 1 задача маршрутизации сборщиков заказов описывается как частный случай задачи коммивояжера.
    (check this in PDF content)

  2. Start
    2882
    Prefix
    В п. 4 представлены эвристические методы решения задачи маршрутизации сборщиков заказов. 1. Штейнеровская задача коммивояжера Задача маршрутизации сборщиков заказов (order-pickers routing problem) является частным случаем задачи коммивояжера (traveling salesman problem)
    Exact
    [2]
    Suffix
    . Задача коммивояжера получила свое название благодаря следующей ситуации. Коммивояжеру требуется посетить определенное число городов только один раз и вернуться обратно в родной город на место старта.
    (check this in PDF content)

  3. Start
    5423
    Prefix
    Однако, для планировок складов, аналогичных представленной на рис. 1 (в виде последовательно-параллельных графов, parallel-series graphs), существует алгоритм, позволяющий найти решение задачи за линейное время в зависимости от числа проходов и сборочных ячеек
    Exact
    [3]
    Suffix
    . 2. Оптимальный алгоритм Рэтлиффа-Розенталя решения задачи маршрутизации сборщиков заказов для одноблочных складов Рассмотрим заказ, содержащий m элементов (товаров), которые необходимо собрать на одноблочном (с двумя поперечными проходами, single-block) складе, конфигурация которого представлена на рис. 1. 2.1.
    (check this in PDF content)

  4. Start
    7469
    Prefix
    Для нахождения минимального маршрута обхода сборщиком заказов сборочных ячеек необходимо найти минимальный маршрутный подграф, то есть маршрутный подграф минимальной длины, при этом доказывается, что такой подграф не имеет вершин, соединенных друг с другом более чем двумя дугами
    Exact
    [3]
    Suffix
    . Для любого подграфа подграф является частичным маршрутным подграфом (ЧМП, partial tour subgraph, PTS) для L, если существует подграф ( определяет граф, получающийся удалением всех вершин и дуг графа L из графа G) такой, что является маршрутным подграфом G.
    (check this in PDF content)

  5. Start
    23449
    Prefix
    Таким образом, пятый параметр может принимать значения: a-bc, b-ac, c-ab. Например, нотация a-bc подразумевает, что вершина находится в одной компоненте связности, а вершины , — в другой. Доказывается, что существует 25 следующих эквивалентных классов
    Exact
    [4]
    Suffix
    : (0, 0, 0, 0), (0, 0, 0, 1), (Ч, Ч, Ч, 1), (Ч, Ч, Ч, 3), (Ч, 0, 0, 1), (0, Ч, 0, 1), (0, 0, Ч, 1), (Ч, Ч, 0, 1), (Ч, 0, Ч, 1), (0, Ч, Ч, 1), (Н, Н, 0, 1), (Н, 0, Н, 1), (0, Н, Н, 1), (Ч, Н, Н, 1), (Н, Ч, Н, 1), (Н, Н, Ч, 1), (Ч, Ч, 0, 2), (Ч, 0, Ч, 2), (0, Ч, Ч, 2), (Ч, Н, Н, 2), (Н, Ч, Н, 2), (Н, Н, Ч, 2), (Ч, Ч, Ч, 2, a-bc), (Ч, Ч, Ч, 2, b-ac), (Ч, Ч, Ч, 2, c-ab).
    (check this in PDF content)

  6. Start
    24078
    Prefix
    Заметим, что класс (0, 0, 0, 0) возможен, только если ни один из проходов в не содержит сборочных ячеек, а класс (0, 0, 0, 1) — только если ни один из проходов в не содержит сборочных ячеек. Согласно
    Exact
    [3–4]
    Suffix
    , после вычисления ЧМП , маршрутным подграфом минимальной длины маршрута сборщика заказов будет являться кратчайший среди следующих ЧМП: (0, 0, 0, 1), (Ч, 0, 0, 1), (0, Ч, 0, 1), (0, 0, Ч, 1), (Ч, Ч, 0, 1), (Ч, 0, Ч, 1), (0, Ч, Ч, 1), (Ч, Ч, Ч, 1).
    (check this in PDF content)

  7. Start
    33887
    Prefix
    Во-первых, маршрут, получаемый благодаря использованию данных методов, может представляться сборщику заказов нелогичным, или неоптимальным, что в свою очередь может привести к отклонениям от заданного маршрута
    Exact
    [5]
    Suffix
    . Авторами работ [6–7] данный феномен исследуется на реально существующих складах нидерландских компаний De Bijenkorf и Ankor. Во-вторых, точные методы зависят от таких параметров, как расположение базы, ее фиксированности, числа блоков и формы склада (прямоугольная или нет).
    (check this in PDF content)

  8. Start
    33907
    Prefix
    Во-первых, маршрут, получаемый благодаря использованию данных методов, может представляться сборщику заказов нелогичным, или неоптимальным, что в свою очередь может привести к отклонениям от заданного маршрута [5]. Авторами работ
    Exact
    [6–7]
    Suffix
    данный феномен исследуется на реально существующих складах нидерландских компаний De Bijenkorf и Ankor. Во-вторых, точные методы зависят от таких параметров, как расположение базы, ее фиксированности, числа блоков и формы склада (прямоугольная или нет).
    (check this in PDF content)

  9. Start
    36023
    Prefix
    Дальним блоком считается блок, наиболее удаленный от базы, которая располагается в ближней стороне склада, рядом с первым (слева) проходом. Заметим, что расположение базы также может оказывать влияние на среднее время сборки заказа. В работе
    Exact
    [8]
    Suffix
    рассматривается влияние расположения базы, а также размера заказа на среднее время сборочного процесса. Показывается, что разница между расположением базы по центру ближнего прохода и расположением вблизи первого прохода меньше 1%.
    (check this in PDF content)

  10. Start
    37752
    Prefix
    Для моделирования конфигурации склада, распределения типовых заказов и маршрутов, получаемых с использованием различных методов маршрутизации, используется программа «Interactive Warehouse»
    Exact
    [9]
    Suffix
    . 4.1. S-образный метод Наиболее простой эвристикой является S-образный (S-shaped) метод маршрутизации (еще одно встречающееся в литературе названием данного метода — метод пересечений, traversal).
    (check this in PDF content)

  11. Start
    38282
    Prefix
    Он основан на том, что любой проход, содержащий хотя бы одну сборочную ячейку должен быть пересечен полностью от ближнего (дальнего) поперечного прохода до дальнего (ближнего) поперечного прохода. Пример применения S-образной эвристики на типовом заказе представлен на рис. 13. Данной эвристике посвящены работы
    Exact
    [3–4, 6–8, 10–19]
    Suffix
    . Алгоритм S-образной эвристики состоит из следующих шагов [19]. 1) Определяем крайний левый (далее, КЛ) проход, содержащий как минимум одну сборочную ячейку, и наиболее удаленный от базы блок (далее, НУБ), содержащий как минимум одну сборочную ячейку. 2) Маршрут начинается из базы по направлению к ближнему концу КЛ прохода. 3) Пересекаем КЛ проход до ближнего поперечного прох
    (check this in PDF content)

  12. Start
    38357
    Prefix
    том, что любой проход, содержащий хотя бы одну сборочную ячейку должен быть пересечен полностью от ближнего (дальнего) поперечного прохода до дальнего (ближнего) поперечного прохода. Пример применения S-образной эвристики на типовом заказе представлен на рис. 13. Данной эвристике посвящены работы [3–4, 6–8, 10–19]. Алгоритм S-образной эвристики состоит из следующих шагов
    Exact
    [19]
    Suffix
    . 1) Определяем крайний левый (далее, КЛ) проход, содержащий как минимум одну сборочную ячейку, и наиболее удаленный от базы блок (далее, НУБ), содержащий как минимум одну сборочную ячейку. 2) Маршрут начинается из базы по направлению к ближнему концу КЛ прохода. 3) Пересекаем КЛ проход до ближнего поперечного прохода НУБ, попутно собирая товары из пересекаемых сборочных яч
    (check this in PDF content)

  13. Start
    41175
    Prefix
    использовании которого сборщик заказов заходит и выходит из сборочных проходов через один поперечный проход, пересекая сборочный проход целиком только в случае перехода из одного блока в другой, причем это возможно сделать только либо через КЛ ПНСЯ, либо через крайний правый (далее, КП) ПНСЯ. Данный эвристический метод маршрутизации рассматривается в работах
    Exact
    [8, 11, 13–14, 20–21]
    Suffix
    . Пример применения эвристики с возвратами на типовом заказе представлен на рис. 14. Рис. 14. Пример маршрута, полученного с использованием эвристики маршрутизации с возвратами Алгоритм эвристики с возвратами состоит из следующих шагов. 1) Определяем КЛ ПНСЯ и НУБ, содержащий как минимум одну сборочную ячейку. 2) Маршрут начинается из базы по направлению к ближнему концу КЛ ПНСЯ. 3) Пересе
    (check this in PDF content)

  14. Start
    43393
    Prefix
    Сборщик заказов пересекает проход целиком только для перехода из одного блока в другой, при этом это возможно сделать только через КЛ ПНСЯ, либо через КП ПНСЯ. Данный эвристический метод маршрутизации представлен в работах
    Exact
    [8, 11, 20–21]
    Suffix
    . Пример применения серединной эвристики на типовом заказе представлен на рис. 15. Алгоритм серединной эвристики состоит из следующих шагов. 1) Определяем КЛ ПНСЯ и НУБ, содержащий как минимум одну сборочную ячейку. 2) Маршрут начинается из базы по направлению к ближнему концу КЛ ПНСЯ. 3) Пересекаем КЛ ПНСЯ до ближнего поперечного прохода НУБ, попутно собирая товары из пересекае
    (check this in PDF content)

  15. Start
    47093
    Prefix
    Таким образом, наибольший интервал — это та часть подпрохода, которая остается непосещенной сборщиком заказов. Дальний поперечный проход блока может быть достигнут только через КЛ или КП ПНСЯ. Данный эвристический метод маршрутизации представлен в работах
    Exact
    [8, 14, 19–20, 22]
    Suffix
    . Пример применения эвристики с захождением на наибольший интервал на типовом заказе представлен на рис. 16. Рис. 16. Пример маршрута, полученного с использованием эвристики маршрутизации с захождением на наибольший интервал Алгоритм серединной эвристики состоит из следующих шагов. 1) Определяем КЛ ПНСЯ и НУБ, содержащий как минимум одну сборочную ячейку. 2) Маршрут начинается из
    (check this in PDF content)

  16. Start
    49954
    Prefix
    еще не был пройден, то возвращаемся на шаг 5, принимая во внимание, что ближний поперечный проход n-го блока является дальним поперечным проходом -го блока. 11) Возвращаемся на базу. 4.5. Последовательный метод Последовательный (или, метод «проход за проходом», aisle-by-aisle) эвристический метод маршрутизации во многоблочных складах представлен в работе
    Exact
    [23]
    Suffix
    . Сборочный маршрут, получающийся в результате использования данной эвристики, посещает каждый сборочный проход только один раз. Таким образом, вначале собираются все необходимые артикулы из первого прохода, затем — из второго и т.д.
    (check this in PDF content)

  17. Start
    50616
    Prefix
    Пример применения последовательной эвристики на типовом заказе представлен на рис. 17. Рис. 17. Пример маршрута, полученного с использованием последовательной эвристики маршрутизации Данный последовательный метод основывается на работах
    Exact
    [24–25]
    Suffix
    . Он позволяет, в частности, сузить ширину поперечных проходов, т.к. движение по ним будет осуществляться только в одну сторону. Алгоритм последовательной эвристики состоит из следующих шагов. 1) Определяем КЛ ПНСЯ и НУБ, содержащий как минимум одну сборочную ячейку. 2) Маршрут начинается из базы по направлению к ближнему концу КЛ ПНСЯ. 3) Пересекаем КЛ ПНСЯ до ближнег
    (check this in PDF content)

  18. Start
    52631
    Prefix
    Переходим на следующий проход, используя такой поперечный проход, для которого это расстояние минимально. Выполняем данный шаг, пока не останется ПНСЯ. 5) Возвращаемся на базу. 4.6. Составной метод Составной (composite) метод предложен в работе
    Exact
    [26]
    Suffix
    . Он сочетает в себе преимущества S-образной эвристики и эвристики с возвратами. Метод минимизирует преодолеваемое расстояние между наиболее удаленными сборочными ячейками двух смежных ПНСЯ и определяет наилучший способ преодоления прохода — пересечение или заход с возвратом.
    (check this in PDF content)

  19. Start
    54736
    Prefix
    Комбинированный метод Комбинированный (combined) метод схож с составным методом, однако решение, пересекать проход целиком или сделать заход с возвратом без изменения поперечного прохода принимается на основе динамического программирования
    Exact
    [4, 19]
    Suffix
    . Каждый ПНСЯ посещается только один раз. Пример применения комбинированной эвристики на типовом заказе представлен на рис. 19. Рис. 19. Пример маршрута, полученного с использованием комбинированной эвристики маршрутизации Введем следующие обозначения: k — число блоков; n — число сборочных проходов; — координата дальнего (от базы) конца j-го под-прохода i-го блока ( ;
    (check this in PDF content)

  20. Start
    60460
    Prefix
    В противном случае, увеличиваем i на единицу и возвращаемся к шагу 5. 4.8. Модифицированный комбинированный метод Комбинированный метод, рассмотренный в предыдущем разделе, возможно модифицировать следующим образом
    Exact
    [19]
    Suffix
    и получить модифицированный комбинированный метод (combined+). Рис. 21. Пример маршрута, полученного с использованием модифицированной комбинированной эвристики маршрутизации Во-первых, рассмотрим маршрут в ближайшем к базе блоке.
    (check this in PDF content)