Моделирование процесса оптимального размещения товаров на складе самообслуживания на основе эволюционных алгоритмов поиска

Аннотация

А.В. Кузнецова, В.А. Мохов, Е.В. Туровская

Дата поступления статьи: 19.02.2014

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

Ключевые слова: Ключевые слова (5–10 слов, через запятую, в именительном падеже, со строчной буквы)

05.13.01 - Системный анализ, управление и обработка информации (по отраслям)

05.13.18 - Математическое моделирование, численные методы и комплексы программ

За последние 20 лет функциональные возможности программного обеспечения для торговой деятельности значительно расширились. Появилось новое поколение систем, построенных на основе оптимизации методов организации производственного цикла с использованием экономико-математических методов, автоматизированного сбора и интегрированной обработки оперативной информации, а также комплексной автоматизации специфических производственных функций, связанных с процессами учёта, контроля и эффективного размещения товаров [1, 2].
Задача автоматизации функций персонала отдела «Склад самообслуживания» компании «ИКЕА-Дон» относится к классу целочисленных задач многокритериальной оптимизации и предусматривает выбор наилучших мест хранения (ячеек) для вновь поступивших товаров; товаров, на которые распространяются акции (скидки, ликвидация); товаров, пользующихся повышенным спросом у покупателей. Определение нового порядка размещения должно предусматривать не только поддержание соотношений уровня продаж, типа, размера и цветовой гаммы, но и минимальное число перемещений уже размещённых товаров.
Авторами предлагается новый способ автоматического формирования карты размещения на основе одной из разновидностей эволюционных вычислений, позволяющих отказаться от сложных методов поиска и за приемлемые сроки отыскать решения, близкие к оптимальным [3 - 5].
В роли хромосом начальной популяций выступают далеко не эффективные размещения, гены которых представляют собой множество имеющихся мест хранения (структура «Ячейка»), в которых размещены не повторяющиеся товары (структура «Товар»). Кроме того, в составе популяции присутствует хромосома, соответствующая текущему размещению. Структура «Товар» (табл. 1) включает физические, количественные и качественные характеристики, структура «Ячейка» содержит её тип и габаритные размеры (табл. 2).

Таблица 1.
Структура «Товар»

Таблица 2.
Структура «Ячейка»

Указанные характеристики комплексно учитываются оценочной функцией пригодности (fitness-функцией).
Из базовой хромосомы, соответствующей текущему размещению товаров, генерируется исходный материал для работы эволюционного алгоритма. Для сужения пространства поиска перед началом работы поискового алгоритма набор генов каждой неэффективной хромосомы генерируется с учётом исключения повторов одного и того же товара в различных ячейках [6, 7]. Длина и соотношение «свободные/занятые ячейки» во всех хромосомах начальной популяции являются постоянными величинами и при последующем изменении популяции не меняются. Также не подлежат изменению и характеристики товаров и ячеек. Размер популяции – суть константная величина, является одним из важных характеристик поискового алгоритма.
Предлагаемый оператор скрещивания обеспечивает исследование окрестностей текущего размещения товаров и сохраняет принцип «исключения повторов» генов [8, 9]. Скрещивание основывается на маске, накладываемой на базовую хромосому путём выработки Nm случайных чисел – номеров ячеек. Ячейки с выбранными номерами можно представить единицами, остальные – нулями (маска). Для каждой отмеченной ячейки во второй хромосоме отыскивается пара: ячейка, с тем же номером и ячейка, содержащая тот же самый товар. Между ними производится обмен. Число единиц в маске является предметом настройки алгоритма поиска [10]. На рис. 1 иллюстрируется процесс обмена генами для маски 1000010000.

Рис. 1. – Обмен генами по маске базовой хромосомы

В алгоритме предусмотрены три способа мутации хромосом. Первый предусматривает перемещение товара из ячейки n₁ в ячейку n₂. Величина n₁ и n₂ случайные. Причём n₂ – ячейка привилегированного диапазона (близость к местам движения основного потока покупателей), n₁ – ячейка, принадлежащая всему диапазону ячеек [1, XY*I]. Второй способ предусматривает схожее перемещение, причём n₁ – ячейка, из непривилегированного диапазона. При мутации третьего типа происходит случайное заполнение всех пустых на текущий момент ячеек привилегированного диапазона товарами из ячеек непривилегированного диапазона. Выбор сочетаний мутаций и их частот также относятся к важнейшим характеристикам поискового алгоритма и подлежат настройке в процессе моделирования.
Поиск решения будет осуществляться в два этапа. На первом этапе алгоритм fitness-функции_1 предусматривает проверку соответствия совокупности физических характеристик товаров глобальным ограничениям:

1. товары из схожих номенклатурных групп должны размещаться в определенных зонах;
2. габариты торговых мест должны соответствовать габаритам максимального количества единиц товара (двухнедельному товарному запасу);
3. весогабаритные характеристики товара должны соответствовать уровню (высоте) размещения;
4. размещение крупногабаритных товаров должно производиться ближе к расчетному узлу или выходу из магазина.

В случае если товар удовлетворяет указанным ограничениям, оценочная функция получает положительное приращение Δ+, если же хотя бы одно из ограничений не удовлетворяется, результат оценочной функции получает отрицательное приращение Δ-. Таким образом, максимально возможное число, возвращаемое fitness-функцией_1, равно 4´N_Т´Δ+, где N_Т – количество всех товаров на складе.
Результатом работы первого этапа алгоритма эволюционного поиска является подмножество хромосом с максимально возможным значением оценки. Это подмножество является исходной популяцией для второго этапа.
На втором этапе производится разделение исходной популяции на N_Gr отдельных популяций, соответствующих числу номенклатурных групп товаров, т.е. каждая хромосома разделяется на N_Gr участков, каждый из которых содержит только товары из своей зоны. На сегодняшний день в «ИКЕА-Дон» их пять: 1) жилые комнаты; 2) офисная фурнитура; 3) кухня/столовая; 4) спальня; 5) детская. Внутри каждой популяции производится учёт остальных ограничений, который сопряжён с преимущественной обработкой качественных характеристик товара. Эти показатели оказывают решающее воздействие на значение, возвращаемое fitness-функцией_2, и должны стремиться к максимуму в соответствии со следующими ограничениями:

1. размещение товаров частого спроса должно иметь привилегии;
2. размещение товаров сезонного спроса должно иметь привилегии;
3. размещение товаров импульсного спроса должно иметь привилегии;
4. размещение товаров в соответствии с акциями, проводимыми в магазине, должно иметь привилегии (т.е. игнорировать ряд физических ограничений);
5. запрет на соседство товаров с одинаковыми упаковками.

В качестве значения, возвращаемого fitness-функцией_2, использованы величины соответствующих ограничениям коэффициентов: учёта частоты спроса k_F; учёта сезонного спроса k_SZ; учёта импульсного спроса k_IM; учёта расстояния между товарами с аналогичными упаковками k_PC; участия в акциях k_A.
Значение коэффициентов k_F,k_SZ,k_IM,k_A вычисляется на основе евклидового расстояния между векторами идеального и реального размещения товаров. Вектор идеального размещения по каждому критерию формируется на основе упорядочения ячеек зоны привилегированности и упорядочения множества соответствующих характеристик товаров по степени убывания. Вектор реального размещения по каждому критерию формируется на основе текущего размещения товаров в упорядоченных ячёйках. При этом

Коэффициент учёта расстояния между товарами с аналогичными упаковками k_PC вычисляется как

где N_{P0_2} – число пар товаров с одинаковыми упаковками, расстояние между которыми не превышает двух ячеек. Для определения расстояния между ячейками c_i и c_j используется ортогональная метрика:

где Δx_ij и Δy_ij – расстояния между ячейками i и j соответственно по осям X и Y; единица измерения расстояния – ячейка. В этом случае k_PC принимает значения от 0 (наихудший вариант) до 2 (удовлетворительный вариант). При N<sub>P0_2= 0 размещение товаров с одинаковыми упаковками полностью удовлетворяет последнему ограничению.
Указанные коэффициенты могут вычисляться на различных «горизонтах планирования» Т, соответствующих различным промежуткам времени – неделя, месяц, квартал, полугодие, в течение которого вычисляются характеристики EWS, EWS1.
Таким образом, вторая функция пригодности (fitness-функция_2) возвращает комплекс величин, характеризующих качество хромосомы с учётом размещения отдельных товаров на наиболее значимых (с точки зрения покупательских потоков) местах в заданном горизонте планирования Т.
Окончательное правило, в соответствии с которым будет производиться выбор искомого решения из множества хороших решений, заключается в том, что суммарное расстояние при выполнении операций перемещения товаров относительно текущего состояния склада должно быть минимальным, а коэффициент близости kL к товарам своей товарной группы не должен превышать 1:


Эволюционный алгоритм поиска первого уровня (этап 1) состоит из следующей последовательности шагов.
ШАГ 0. Формирование базовой хромосомы из БД системы складского учёта.
Chrombase = SELECT(Data Base System).
ШАГ 1. Создание начальной популяции {РN1} на основе базовой хромосомы, где N1 – варьируемая величина, зависящая от длины хромосомы.
{PN1} = func(Chrombase).
ШАГ 2. Отбор родительской особи для скрещивания:
Chromparent = select1({РN1}),
где select1( ) – функция отбора особи из рабочей популяции в кандидаты для скрещивания.
ШАГ 3. Формирование маски скрещивания
Mask = random_funck(Chrombase).
ШАГ 4. Формирование дочерней особи путём скрещивания базовой и родительской особей:
Chromchild = crossing(Mask, Chromparent),
где crossing( )– функция скрещивания.
ШАГ 5. Мутация дочерней хромосомы: одна мутация типа на Nm циклов скрещивания, Nm ≈ 100-200 циклов; случайный выбор типа мутации.
Chromchild* = mutate_func(Chromchild).
ШАГ 6. Отбор элитной особи:
Chromelite = select3(fitness(Chromchild, Chromparent)),
где select3( ) – функция отбора особи для возврата в рабочую популяцию: max( ) при fitness(Chromchild) ≠ fitness(Chrombase) или random( ) в противном случае.
ШАГ 7. Изменение рабочей популяции {Р’N1}:
{Р’N1}: {РN1}–{Chromparent }+{ Chromelite},
где {Р’N1} – изменённая популяция.
ШАГ 8. Оценка новой рабочей популяции {Р’N1}:
fitness({Р’N1}).
ШАГ 9. Если цель max(fitness({Р’N1})) достигнута ИЛИ число заданных циклов скрещивания выполнено, то завершение алгоритма, иначе переход к ШАГУ 2.
Эволюционный алгоритм поиска второго уровня (этап 2) аналогичен представленному выше и отличается лишь способом формирования исходной популяции на нулевом шаге.
Представленная схема использовалась для моделирования процесса поиска оптимального решения при:</sub>

• поступлении новых товаров;
• удалении отдельных товаров из ассортимента;
• проведении мероприятий, связанных с объявлением акций на отдельные группы товаров;
• плановой профилактике состояния склада.

Были определены диапазоны изменения параметров эволюционного алгоритма при различной степени наполняемости склада и его различных конфигураций.
Отличительными особенностями предложенной эволюционной модели являются следующие.

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

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

Литература:

1. Туровская, Е.В. Задача размещения товаров для ООО «Икеа-Дом» [Текст] / Е.В. Туровская, Ф.А. Туровский // Студенческая научная весна - 2013 : материалы регион. науч.-техн. конф. (конкурса науч.-техн. работ) студентов, аспирантов и молодых ученых вузов Рост. обл., 25-26 апр. 2013 г. / Юж.-Рос. гос. техн. ун-т (НПИ) – Новочеркасск : ЮРГТУ, 2013. – С. 84-85
2. Туровская, Е.В. Системный анализ процесса размещения товара на складе самообслуживания [Текст] / Е.В. Туровская, Ф.А. Туровский // Компьютерные технологии в науке, производстве, социальных и экономических процессах : материалы 14-й Междунар. науч.-практич. конф., г. Новочеркасск, 12 дек. 2013 г. / Юж.Рос. политехн. ун-т (НПИ) – Новочеркасск: ЮРГПУ (НПИ), 2013. – С. 71-74
3. Koza J. R. Genetic Programming [Текст] / J. R. Koza. – Cambridge: The MIT Press, 1998. – 609 c. – ISBN 0-262-11170-5
4.  Mitchell M. An Introduction to Genetic Algorithms [Текст] / M. Mitchell. – Cambridge: MIT Press, 1999 – 158 c. – ISBN 0-262-13316-4 (HB), 0-262-63185-7 (PB)
5. Гладков, Л.А. Генетические алгоритмы [Текст] / Л.А. Гладков, В.В. Курейчик, В.М. Курейчик – М.: Физматлит, 2006. – 320 с.
6. Michalewicz Z. Genetic algorithms + Data Structures = Evolution Programs [Текст] / Z. Michalewicz. – New York: Springer-Verlag, 1996. – 387 c. – ISBN 3540606769
7. Мохов, В.А. Интегрированный алгоритм когнитивной оценки и выбора оптимального варианта онтологической модели [Электронный ресурс] / В.А. Мохов, Н.Н. Сильнягин // «Инженерный вестник Дона», 2011, № 4. – Режим доступа: http://www.ivdon.ru/magazine/archive/n4y2011/600 (доступ свободный) – Загл. с экрана. – Яз. Рус.
8. Кузнецова, А.В. Оптимизация учебных планов на основе генетических алгоритмов [Текст] / А.В. Кузнецова, И.В. Георгица, Ю.С. Григорьева // Математические методы в технике и технологиях – ММТТ-23. : сб. тр. XXIII Междунар. науч. конф. : в 12 т. / Смоленск : Изд-во Смоленск. фил гос. техн. ин-та (техн.ун-та), 2010. – Т. 12, секц. 11. – С. 136-138.
9. Кузнецова, А.В. Создание учебных планов третьего поколения на основе эволюционных алгоритмов поиска [Текст] / А.В. Кузнецова, Ю.С. Чусова // Инфокоммуникационные технологии в науке, производстве и образовании (Инфоком-4): материалы IV Междунар. науч-техн. конф., 28-30 июля 2010 г. / Ставрополь: Изд-во Сев.-Кав. гос. техн. ун-та, 2010. – С. 64-67
10.   Мохов, В.А. Мультиагентное моделирование сетевой атаки типа DDoS [Электронный ресурс] / В.А. Мохов, И.В. Георгица, С.А. Гончаров // «Инженерный вестник Дона», 2013, № 3. – Режим доступа: http://ivdon.ru/magazine/archive/n3y2013/1852 (доступ свободный) – Загл. с экрана. – Яз. Рус.