Автоматический расчет планограммы товаров на основе принципа блочной выкладки

При активном развитии розничной сети на определенном этапе появляется понимание того, что без качественной выкладки товаров в магазинах по определенным правилам дальнейший рост продаж и прибыли невозможен. Эти правила представляют собой результаты эмпирических наблюдений за тем, каким образом то или иное расположение товаров влияет на их продажи, и научные исследования в области мерчендайзинга. Определенное время возможно выдерживать соблюдение правил в ручном режиме, но с увеличением количества магазинов, их дифференциацией на различные форматы, постоянным изменением ассортимента это становится практически невозможным. После этого перед розничной сетью появляется дилемма – либо отказываться или обобщать правила выкладки (например, делать единые планограммы на определенные кластеры магазинов, характеризующимися похожими характеристиками), либо рассматривать возможность автоматизации процесса создания планограмм. Недостатком первого подхода является то, что индивидуальные характеристики магазинов при этом теряются, что снижает эффективность планограмм, поэтому далее будет рассматриваться подход с автоматизацией. Недостатком существующих систем, позволяющих получить автоматизированные планограммы, является их очень высокая стоимость (на российском рынке доступна исключительно розничным сетям федерального значения) и, в рассмотренных, их реализация на основе некоторой мастер-планограммы (то есть планограммы, созданной вручную, и автоматически корректируемой для учета индивидуальных особенностей магазина). В связи с этими недостатками, было принято решение разработать полностью автоматизированную систему, в качестве входных данных использующих только правила выкладки и оборудование в магазинах.

Постановка задачи

Исследованиями ряда авторов [1, 2] установлено, что качественная выкладка товаров является одним из самых важных методов поддержания и увеличения продаж в розничных сетях. В ходе анализа данных источников был выявлен ряд подходов к формированию планограмм выкладки товаров, основанных на определенных принципах, одним из наиболее распространенных методов является блочная выкладка. Блочная выкладка товаров в планограмме представляет собой группировку товаров в некоторые прямоугольные блоки, каждый из которых включает в себя товары только определенного типа. Классическим примером является группировка товаров внутри одного бренда, что можно отобразить графически (рис. 1).

Рис. 1. Пример блочной выкладки товаров

Входными данными при расчете планограммы (на примере блочной выкладки, основанной на брендах), являются:

• •    список товаров со ссылкой на бренд;

• •    показатели товаров (продажи, розничные цены и т. д.);

• •    список брендов;

• •    ширина и количество полок, на которых будут располагаться товары.

Также, в качестве входных параметров, которые влияют на то, какая в итоге будет получена планограмма, выступают:

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

• •    максимальная разница показателя двух брендов (выбранного в предыдущем пункте), при котором данные бренда можно объединить в единый вертикальный блок (но при этом каждый бренд все равно остается прямоугольником). Как правило, значение показателя нормируется, поэтому значение максимальной разницы можно выбирать от 0 до 1 (где 0 означает, что никакой бренд нельзя объединить с другим, а 1 – любой бренд можно объединить с любым).

Математическая модель

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

Перебор вариантов при расчете планограммы идет в двух разрезах:

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

• •    подбор планограммы для заданного количества товаров, настроек групп товаров и оборудования. В данной статье описывается алгоритм, при котором предполагается полный перебор вариантов, которые удовлетворяют заданным условиям, что гарантирует оптимальность найденного решения (но, следствием этого является то, что поиск решения реален лишь в определенном диапазоне шаблонов выкладки).

Подбор количества товаров в планограмме

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

При выборе методики подбора количества товаров в простой планограмме следует руковод- ствоваться двумя критериями:

• •    способность найти решение близкое к оптимальному;

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

Поскольку речь идет о машинной реализации перебора, одним из самых важных нюансов при оценке скорости нахождения решения является способность к параллельному выполнению процесса расчета. Рассматриваемый в статье метод расчета планограммы для заданного оборудования, количества полок и настроек является практически атомарной операцией и распараллеливанию практически не поддается, поэтому единственно возможный путь к ускорению – параллельный запуск расчетов простых планограмм, но с отличающимися в чем-либо исходными данными (например, с отклонениями в заданной ширине или в количестве товаров). В частности, методика, в которой одна итерация подбора зависит от результата расчета предыдущей, вполне может оказаться хуже другой, реализация которой поддается параллельному расчету, даже если в первом случае просчитывается N вариантов, а во втором, например, N ·10.

Предлагаемый алгоритм перебора (в виде блок-схемы изображен на рис. 2):

Обозначения:

Q – количество наименований товаров;

W – суммарная ширина полок (ширина полок, умноженная на их количество);

S – заданная ширина полок;

x i – количество товара, i = 1, Q ;

m i – минимальное количество товара, i = 1, Q ;

z i – требуемая доля товара, согласно значениям соответствующего показателя, i = 1, Q ;

w i – ширина единицы товара, i = 1, Q ;

f ( x 1 , …, x Q ) = f ( x ) – ширина товаров, которую заняли товары, выставленные согласно настроенным правилам, в количестве { x 1 , …, x Q }. Если расчет производился на несколько полок, то возвращаемое значение соответствует максимальной ширине занятой товарами, на одной из них;

s i ( x 1 , …, x Q , a ) = s i ( x , a ) – ширина товаров, которую заняли товары, выставлены согласно выставленным правилам, в количестве { x 1 , …, x i –1 , x i + a , x i +1 , x Q };

s i ( x , a ) = ^f ( x 1 , . , x i - 1 , x i + a , x i + 1 , . , x q ) ;

d ( x 1 , …, x Q ) = d ( x ) – квадрат суммы отклонений количества товаров { x 1 , …, x Q } от требуемой доли;

d (x1, ^, xQ ) = £ i=1

(   x i   f

Q z i - Z x i V i = 1    7

;

g i ( x 1 , …, x Q , a ) = g i ( x , a ) – квадрат суммы отклонений количества товаров { x 1 , …, x i–1 , x i + a , x i+1 , x Q };

g i ( x , a ) = d ( x ! , .. , x i - ! , x i + a , x i _{+ 1}, .. , x q ) ;

i ( x , a ) – индекс товара, для которого выполняются следующие условия:

g i ( x , a ) = min g i ( x , a ) ;

i=1, Q si (x, a) < 5.

Если условия не выполнены для всех товаров, то возвращаем 0. Если условия выполняются для нескольких товаров, то возвращаем индекс у того, для которого s- (x, a) min s (x, a).

i = 1, Q

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

Рис. 2. Алгоритм поиска оптимальной простой планограммы

Преимущества алгорита:

• •    а лгори тм от ли чн о п од де р живает параллельные вычисления в момент р ас чета u = i ( x , 1), по ск оль к у п ри э том в озмож н о од н ов ре ме н н о ра сс чи тыв а ть в а ри а н ты д ля в с е х i ;

• •    от н осительн а я п р ос тота р е а ли за ц и и .

Недостаток алгоритма:

• •    исходное значение x для перебора достаточно далеко от оптимального, п оэ тому п ри б ли ж е н и е к нем у може т з а н ять п род ол жи те льн о е в ре мя.

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

Р ас с мотри м н ес кол ьк о в спомогат ель ны х за да ч (алгоритмы их решения в данной статье приводится не будут):

• а)    п о ис к с пи с к а н аборов по дмножеств, покрывающих требуемое мно ж ес тво, при э том мно жес тва в наборе не п е ре с ек аю тся

Дано:

множество R ;

совокупность D н ек оторы х п од мн ож е с тв R :

V s е Ds е R , при этом U D = R .

Необ ход и мо на й ти м н ож ес тв о A совокупностей D :

A = { 5 1 5 е D : U 5 = R } , при э том V a , b е A , a * b : a n b = 0 .

• б)    п о ис к с писк а наб оров по дмножеств, покрывающих требуемое мно ж ес тво, при э том множества в наборе не п е ре секаются, а количество подмножеств в каждом набо ре н е превышает заданное число

Дано:

множество R ;

совокупность D н ек оторы х п од мн ож е с тв R :

V s е D s е R , при этом U D = R .

• x , x е N .

Необходимо найти множество A совокупностей D :

A = { 5 1 5 e D : U 5 = R } , при этом V a , b e A , a * b : a n b = 0 , IA I <  x .

• в)    поиск списка набора натуральных чисел, сумма и количество которых в каждом из наборов равна заданным натуральным числам

Дано:

• x , x e N ;

• У , У e N .

Необходимо найти множество A совокупностей D натуральных чисел:

A =^D ={ di}: |D| = x,

fd. = У. i = 1            ,

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

Дано:

множество групп G ;

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

множество расчетных значений W , каждое из которых принадлежит соответствующей по индексу группе;

• h ( g ) – функция, возвращающая значение из множества W , соответствующие элементу множества G , g e G ;

максимальное расстояние между расчетными значениями групп, при которых допускается их слияние – w ^max;

количество полок N ;

• f ( s , n ) – функция, которая показывает, сколько будет занимать объект s на количестве полок n , 5 e 5 , n <  N .

Для решения задача введем еще несколько обозначений:

T – произвольное множество элементов G , в котором максимальное отклонение в соответствующем каждому элементу значению из множества W не превышает w ^max:

T = { FIF e G } , при этом, V a , b e TI h ( a ) - h ( b ) | < w max .

Для каждого T найдем такую комбинацию входящих в него множеств, при котором общая ширина будет наименьшей. Для этого, сначала, используем вспомогательную задачу «б». В качестве входных данных, выступаем множество T и количество полок N . В результате ее решения получим множество наборов подмножеств элементов T . Далее, в каждого найденного набора, решим вспомогательную задачу «в», при этом, в качестве входных данных будет количество подмножеств в наборе и количество полок ( x и y соответственно). После нахождения решения вспомогательной задачи «в» каждому из подмножеств в наборе будет поставлено в соответствие некоторое натуральное число (физический смысл которого – количество полок, которое отдано данному подмножеству).

Рассмотрим на простом примере. Пусть T состоит из 3 элементов (I, II и III) и количество полок равно 3. Множество его возможных комбинаций (их пять):

{{I, II, III}}, {{I; II}, {III}}, {{I, III}, {II}}, {{II, III}, {I}}, {{I}, {II}, {III}}. Их физический смысл следующий:

• 1)    все три элемента располагаются слева направо;

• 2)    элементы I, II располагаются слева направо, а под ними находится элемент III;

• 3)    элементы I, III располагаются слева направо, а под ними находится элемент II;

• 4)    элементы II, III располагаются слева направо, а под ними находится элемент I;

• 5)    элемент I расположен над элементом II, а элемент II – над элементом III.

Теперь, для каждой из комбинаций, найдем количество полок, приходящееся на каждое подмножество. Рассмотрим на примере комбинации II:

• 1)    {I; II} – 1 полка, {III} – 2 полки;

• 2)    {I; II} – 2 полки, {III} – 1 полка.

Для того чтобы найти расстояние, которое займет комбинация при заданном распределении полок, надо сначала найти сумму расстояний, занимаемых каждым множеством в подмножестве, а затем найти из максимальное значение. Рассмотрим на нашем примере (для распределения полок 1). Сначала находим, сколько занимает элемент I и элемент II на одной полке, а элемент III – на двух полках (используя функцию f ( s , n )). Обозначим их x I , x II и x III . Затем найдем максимум из x I + x II и x III . Найденное значение и будет означать, сколько займет множество T для заданной комбинации. Рассчитав данные значения для всех возможных комбинаций, мы найдем из них ту, при которой T занимает наименьшее расстояние. Обозначим в качестве T^* некоторый объект, который содержит в себе множество T , ту комбинацию, которая обеспечивает ему наименьшее расстояние и это наименьшее расстояние (обозначим его T w ).

Q – совокупность всех возможных множеств T :

Q = { T };

Z – совокупность наборов T^* , таких, что соответствующие им T не пересекаются, а их сумма является покрытием G . Поиск Z , как видно из формулировки, сводится к вспомогательной задаче «a», при этом в качестве входного множества R выступает множество G , а в качестве входного множества D выступает множество Q .

Для того чтобы найти окончательное решение задачи поиска оптимальной планограммы, нужно найти такой элемент Z , при котором сумма T_w входящих в него элементов T^* минимальна. Расстояние, занимаемое элементом Z , является суммой расстояних, занимаемых входящими в него элементами T^* (физический смысл этого в том, что все T^* располагаются слева направо), поэтому для каждого элемента Z находим их сумму и выбираем тот, который обеспечивает наименьшее.

Заключение

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