Heuristic Approach for Automated Shelf Space Allocation
Dario Landa-Silva

ASAP Research Group
School of Computer Science
University of Nottingham, UK
Fathima Marikar

School of Computer Science
University of Nottingham, UK
Khoi Le
ASAP Research Group
School of Computer Science
University of Nottingham, UK
ABSTRACT
Shelf space allocation is the problem of efficiently arranging
retail products on shelves in order to maximise profit,
improve stock control, improve customer satisfaction, etc.
Most work reported in the literature on this problem has
focused on the case of large retailers such as big supermarkets.
The interest here is to tackle this problem in the context
of small retail shops where different issues arise when
compared to large retailers. This paper proposes a heuristic
approach to automate shelf space allocation in small retail
shops. Several initialisation heuristics and local search
moves are incorporated into the proposed method which
generates high quality practical arrangements represented
graphically as simple planograms.
Categories and Subject Descriptors
I.2.8 [Artificial Intelligence]: Problem solving, control
methods and search, Heuristic methods
Keywords
Allocation Heuristic, Shelf Space Allocation, Planograms
1. INTRODUCTION
In this paper, we are interested in the computer generation
of planograms which are the graphic representations of
the arrangement of products on shelves in retail shops. We
propose a heuristic approach for the automated allocation
of shelf space. This approach has been developed in cooperation
with a retailer who provided in-depth knowledge
of the problem and requirements for a computer solution.
We incorporate the heuristic approach into a prototype decision
support system to aid managers of small retail shops
Please send all correspondence to the following email address:
dario.landasilva@nottingham.ac.uk
This work was carried out when Fathima Marikar was still
at the University of Nottingham.
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
SAC'09 March 8-12, 2009, Honolulu, Hawaii, U.S.A.
Copyright 2009 ACM 978-1-60558-166-8/09/03 ...$5.00.
to make better use of the limited shelf space. The heuristic
approach provides an efficient arrangement of products
into shelves and the graphical interface provides a graphical
illustration of the proposed arrangement in the form of a
simple planogram.
The goal of our research is to develop an algorithm to
create an efficient arrangement of products on shelves or to
improve upon an existing arrangement. The main objective
considered here is to improve sales profit. For a realistic approach
to understanding and solving the subject problem,
we gathered real data and information from a small supermarket
in the UN headquarters in Vienna, Austria. Previous
work has focused on large retail shops such as big supermarkets
(e.g. [7, 11, 10, 8]). The heuristic method described in
this paper consists of four phases: 1) the preparatory phase
checks that enough shelf space in available for all products
to be displayed, 2) the allocation phase constructs an initial
arrangement, 3) the adjustment phase makes iterative
changes to the arrangement in order to improve the overall
profit, 4) the termination phase computes the quality
of the final arrangement and generates the corresponding
planogram.
Section 2 describes the shelf space allocation problem and
gives an account of previous related research. Section 3 gives
a formulation of the shelf space allocation problem in the
small retail shop considered here. Section 4 describes in
detail the four-phase heuristic algorithm proposed to tackle
the subject problem. Section 5 presents and discusses our
experiments and results while Section 6 concludes the paper.
2. SHELF SPACE ALLOCATION
Retailers require a competitive edge if they want to stay
ahead of their competition. One way of doing this is to capture
a larger market share and in the process, increase sales.
One way of increasing sales is to improve retail operations
and making an efficient use of the often limited shelf space
in shops is an important strategy. Although shelf space allocation
accounts for a small part on the whole set of management
strategies for retailers, it is a comparatively easy
way of earning more profits.
The management of shelf space in any retail outlet, big or
small, plays a significant role in the shop's profitability [10,
8]. Shelf space is a vital yet limited resource and must be efficiently
used and carefully managed in order to achieve the
main objectives of maximising profits, reducing costs and
increasing customer satisfaction. In their simplest form, the
product selection problem refers to choosing which products
are to be displayed in the limited shelf space available while
922
the shelf space allocation problem refers to designing the actual
arrangement of the chosen products on shelves and how
many units of each product will be displayed [7].
There are many issues to consider when stocking shelves
in retailing (see [4, 7, 3, 10] for more details). For example,
items in clear view to the customer are the ones that
are most likely to be seen and therefore bought. More importantly,
a product must always be available on the shelf,
otherwise loss of sales will occur. Products should be located
depending on the target audience (e.g. toys and sweets
should generally be placed on lower shelves so they are accessible
to children). The larger the space given to a certain
product, the easier it will be seen by customers. In many
cases, there are standards imposed by the product manufacturers
themselves (e.g. demanding that their product is
located in certain shelves). Well-managed shelf space takes
into consideration many of these issues and helps to achieve
the objectives mentioned above in relation to profits, costs
and customer satisfaction.
2.1 Previous Work
Several formulations have been proposed in the literature
for the shelf space allocation problem. Previous research
has focused on large supermarkets and therefore it is not
fully applicable to small retail shops as the one considered
in this paper. This is because not all data usually available
for large retailers (e.g. sales, demand, marketing) is
available for smaller ones. Examples of models for the shelf
space allocation problem include those proposed in [4, 1,
7, 5, 3, 11, 6, 2, 10, 9, 8]. Cairns proposed an interactive
approach to produce a graphical model taking into account
factors such as space elasticity with the main objective of
maximising profits [4]. Space elasticity is a common concept
in shelf space management and it basically refers to
the ratio of change in unit sales of a product, in relation to
the change in shelf space allocated to the product (see [6]).
Anderson and Amato investigated the role of consumer preference
for specific product brands on the potential product
demand and hence the impact on deciding the optimum allocation
of shelf space [1]. Later, Hansen and Heinsbroek
proposed an improved model which considered the cost effect
[7]. In the model by Corstjens and Doyle the objective
was to optimise profits considering three main issues: the
cost effect, the demand effect and the cross elasticity effect
[5]. Cross elasticity refers to the effect that sales of
certain products can have on sales of other products. The
model by Buttle incorporates five factors: fixture location,
product category location, item location within categories,
off-shelf display and promotional support [3]. Buttle suggests
that all these aspects must be taken into consideration
in order to increase profits. Zufryden followed in the footsteps
of Corjstens and Doyle and produced a dynamic model
including many demand-related marketing variables but not
cross-elasticity among other simplifications [11]. Dreze et
al. suggested that while location plays a significant role in
the arrangement of products, the number of facings of each
product was far less important (i.e. after a certain number,
an additional facing does not make any difference to the
product sales) [6]. A facing represents one unit of the product
face straight out towards the customer. Borin et al. suggested
that product assortment (selecting which products to
display) and stockouts (products missing from shelves) are
crucial issues that must be considered in shelf space management
in addition to the demand effects [2]. The elaborate
model by Yang and Chen incorporates many of the concepts
from previous models and new ones, e.g. space elasticity,
cross elasticity, marketing variables (price, promotion, advertisement,
etc.), demand effect, display costs, inventory
levels, etc. [10]. More recent studies tried to simplify the
complex nature of previous models without compromising
the ease of application. For example, Yang proposed a simple
linear model based on the knapsack problem and only
considering the profitability of products [9] and showed that
the problem is NP-hard. Lim et al. proposed an extended
model considering the effect of product groupings, i.e. placing
products of the same category together or apart, and
the effect of non-linear profit functions [8].
It is clear that the optimisation of shelf space allocation
is very important and several models have been proposed.
Most of the work carried out so far concentrates on large
retailers and takes into consideration various marketing and
consumer behaviour variables, which are not completely relevant
or not available in the case of small retail shops. Small
retailers are more likely to benefit from a model that is focused
on their specific needs and takes into account constraints,
requirements and rules that are specific to small
shops. The simplified (yet NP-hard) models proposed more
recently by Yang [9] and Lim et al. [8] seem more applicable
to small retail shops. The formulation used in this paper is
a modification of the one by Yang [9].
3. PROBLEM SPECIFICATION
The small shop considered in this study organises shelves
into blocks, where each block consists of a set of shelves and
each shelf can be divided into parts. A shelf is considered
a horizontal unit of space, i.e. a shelf can be top-level, eyelevel
or bottom-level. Each shelf is then split horizontally
into left, middle and right parts of the shelf. Different priority
is assigned to shelves and to parts within the shelf. Based
on the examination of sales history, the eye-level shelves and
centre shelf parts are assumed to have the highest profitability.
For each product, the following is known: the minimum
and maximum number of facings required, the length of one
facing, the total number of units available, the profit per unit
and the profit category code. The height of each product
unit is ignored because the practice in the shop is to stack
two units of products one above the other and the height of
all shelves is enough to allow this for all products. The shop
management does not require a product selection stage to
decide which products should be displayed on shelves. The
shop does not generally place facings of the same product
on different shelves. However, they stated that if doing so
improves profitability then they would be willing to try that
kind of arrangement. The shop management groups products
by general categories (for example, tea, coffee, cereals)
but more sophisticated product grouping methods are not
used during allocation. The reason for this is that the shop
is small and products are found easily by customers because
shelves are close enough to each other.
The problem formulation is as follows:
n : number of products to allocate
m : number of shelves
p : number of parts in each shelf (in our case p = 3)
ai : length of facing of product i
923
Tjk : length of part k in shelf j
Li : minimum number of facings required for product i
Ui : maximum number of facings required for product i
xijk : number of facings of product i on part k of shelf j
yijk = 1 if facings of product i are assigned to part k of shelf
j, 0 otherwise
i : profit per unit of product i
j : priority coefficient of shelf j
k : priority coefficient of shelf part k
ijk = ijk : profitability of product i if placed on part
k of shelf j
i = 1 . . . n, j = 1 . . . m, k = 1 . . . p
The objective is to maximise the total profit given by:
Z =
n
i=1
m
j=1
p
k=1
ijkxijk (1)
Subject to the following constraints:
n
i=1
aixijk  Tjk for j = 1 . . . m, k = 1 . . . p (2)
m
j=1
p
k=1
yijk = 1 for i = 1 . . . n (3)
Li 
m
j=1
p
k=1
xijk  Ui for i = 1 . . . n (4)
yijk  xijk  Uiyijk and xijk  Z+
(5)
The following assumptions are made in the formulation:
1. There is enough shelf space available for the minimum
number of products allocated, so that a selection algorithm
is not required.
2. Product and shelf height and depth are ignored (only
number of facings are considered).
3. Products are allocated adjacently (not stacked on top
of each other).
4. All facings of a product must be placed on a single
shelf (facings of a product cannot be placed on different
shelves).
Note that the model above is an adaptation of Yang's
model [9] to allow priorities for shelves and shelf parts to reflect
current practice in the UN shop (and other small retail
shops) where long shelves tend to be divided into smaller
parts for better management. Allowing the shop manager
to divide a shelf into parts and assigning a priority based on
their observations about shelf profitability results in a more
accurate overall profit estimation. A potential difficulty of
dividing a shelf into parts arises when a product cannot fit
into the remaining space in a shelf part. In this case the
product might be assigned to another shelf part leaving unused
space in the first shelf part. This could result on the
fragmentation of space in the shelf parts which is less likely
to occur if the whole shelf is treated as a unit.
4. PROPOSED HEURISTIC APPROACH
4.1 Yang's Heuristic Method
Yang proposed a three-phase heuristic to tackle the shelf
space allocation problem in large retails shops [9]. We first
outline Yang's method below and in the next subsection we
explain our proposed adaptation.
1. Preparatory phase. Checks that solving the current
problem is feasible, i.e. that there is enough shelf space
to allocate the minimum required number of facings for
all products. If this is the case, a set of priority indexes
based on the notion of `profit weight' is created. The
`profit weight' is calculated by dividing the profitability
of product i with respect to each shelf k (Pik) by
the length of the product's facing (ai). Products with
larger `profit weight' are given a higher priority index.
The algorithm continues to the next phase if solving
the problem is feasible, otherwise it stops.
2. Allocation phase. Uses two sub-phases to construct
an initial arrangement by assigning shelf space to each
product following the ordered priority indexes established
in the preparatory phase. This allocation phase
tries to allocate a number of facings of each product
within the given lower (Li) and upper (Ui) bounds.
As noted by Yang, assigning shelf space following the
priority indexes does not guarantee that a feasible arrangement
can be constructed, the whole algorithm
might fail in this phase.
3. Adjustment phase. If a feasible initial solution is created
in the allocation phase, changes are made to improve
the arrangement by swapping the location of
products and/or adjusting the number of facings. Yang
proposed three adjustment methods. The first adjustment
method swaps one facing between two products
allocated to the same shelf. The second adjustment
method swaps one facing between two products
allocated to different shelves. The third adjustment
method (extension of second method) seeks additional
space in a shelf to allocate more facings of a product
before swapping facings between two products in different
shelves.
4. Termination phase. Calculates the total profit of the
final arrangement.
4.2 Adaptations Made in Our Approach
We now give an overview of our method highlighting the
differences with Yang's approach. After that, the next subsection
gives full details of these different elements in our
method.
1. Preparatory phase. Checks that solving the current
problem is feasible but we do not create the list of
priority indexes proposed by Yang.
2. Allocation phase. Creates an initial solution by one
of three optional methods based on different criteria:
product profit, product size and random choice. Alternatively,
the user can provide an existing arrangement
and apply phases 3 and 4 only. Yang used only one
initialisation method based on product weight as described
above.
924
3. Adjustment phase. Consists of five heuristic moves designed
to improve upon the current solution. These
heuristics swap products between shelves based on different
criteria. Only one of these heuristics is inspired
by Yang's work.
4. Termination phase. As in Yang's method, this phase
calculates the total profit for the final arrangement but
we also implemented a graphical user interface for the
shop manager to visualise the proposed arrangement
in the form of a simple planogram.
4.3 Initialisation in the Allocation Phase
We implemented three optional initialisation methods in
the allocation phase. The three methods place one product
at a time on a given shelf part until all products are allocated.
The methods differ in the order in which the products
are sorted.
Arrangement Profit. This is a modified version of the
initialisation algorithm proposed by Yang and it consists of
three steps:
1. Prioritise. Products and shelves are sorted such that
the most profitable products are assigned to the most
profitable shelf parts. Products are sorted in descending
order of their profit weight (i/ai) which represents
the profit of a product relative to its size. All (p × m)
shelf parts are sorted in descending order of their priority
coefficients (j and k).
2. Allocate Minimum. Using the sorted lists from step 1,
select the first product and first shelf part and allocate
the minimum required number of facings of the product
(Li) to that shelf part. Repeat this process for the
next product and next shelf part. After the last shelf
part in the last shelf is reached, continue with the first
shelf part in the priority list until all products have
been allocated. This step ensures that Li facings of
each product are placed in the shelves and remaining
space is likely to exist in all shelf parts.
3. Allocate More. Using the arrangement from step 2
and the product priority list from step 1, increment
the number of facings of each product by one ensuring
that the upper bound on the number of facings (Ui)
and the length of the shelf part (Tjk) are not exceeded.
Continue incrementing the number of facings by one
until no more facings can be allocated.
Note that the initial solution method based on profit implemented
by Yang [9] requires the profit of a product i with
respect to each shelf k. However, the product profitability
values (i) obtained from the UN shop are independent of
the shelf allocation. Also, the priority coefficients obtained
for shelves (j) and shelf parts (k) are independent of the
product allocated.
Arrangement Size. This method is similar to the arrangement
by profit but the criteria for ordering products is the
facing length.
1. Prioritise. Products and shelves are sorted such that
the most profitable shelf parts are assigned as many
products as possible. Products are sorted in ascending
order of their facing length (ai). All (p × m) shelf
parts are sorted in descending order of their priority
coefficients (j and k).
2. Allocate Minimum. Idem Arrangement Profit step 2.
3. Allocate Rest. Idem Arrangement Profit step 3.
Arrangement Random Choice. This method serves as
a benchmark to assess the usefulness of the product priority
list used in the above two methods. All (p × m) shelf parts
are sorted in descending order of their priority coefficients
(j and k) but products are not sorted.
1. Allocate Minimum. Randomly select a product and
allocate the minimum required number of facings (Li)
of the product to the first shelf part in the priority list.
Continue with another randomly selected product and
the next shelf part in the priority list. After the last
shelf part in the last shelf is reached, continue with
the first shelf part in the priority list until all products
have been allocated.
2. Allocate Rest. Idem Arrangement Profit step 3.
User-defined Arrangement. We introduced this option
to allow users to improve upon their existing arrangement.
The arrangement is designed and supplied by the user in the
form of a text file which should include a list of all products
with the following details: shelf code, shelf part code, product
code and currently allocated number of facings. In this
study we considered the actual arrangement of products in
the UN shop.
4.4 Heuristic Moves in the Adjustment Phase
The moves proposed by Yang [9] can result in facings of
the same product being placed on different shelves which is
not allowed in our case. We introduce the AdjustInter move
to carry out swaps between four products located on two
different shelves. This move makes possible to examine different
neighbourhoods to possibly improve the overall solution.
The RemoveLeastProfitable move is also introduced to
escape from local optima. This move was initially designed
to fully remove the least profitable product from every shelf
part. However, after some preliminary testing, we observed
this was too much and it would greatly reduce the overall
profit if many shelf parts. We now describe the five heuristic
moves used in the adjustment phase of our approach. Four
of these heuristic moves aim to improve profit by changing
the location or the number of facings of products in shelves.
The fifth move disturbs the current arrangement by releasing
shelf space and the aim is to diversify the search.
Swap
This move swaps all facings between two products i1 and
i2 located on different shelf parts j1k1 and j2k2 respectively.
The aim is to improve the overall profit by moving high
profitable products to more profitable shelves. The following
must be satisfied: Tj1k1 + a11 xi1j1k1 - ai2 xi2j2k2 > 0
and Tj2k2 - a11 xi1j1k1 + ai2 xi2j2k2 > 0.
AdjustIn
This move was proposed by Yang [9] and it adjusts by 1
the number of facings of two different products i1 and i2 on
the same shelf part jk. The move makes xi1jk = xijk + 1
925
and xi2jk = xi2jk - 1. The aim is to improve the overall
profit by adjusting facings so that high profitable products
have more facings displayed. The following must be satisfied:
Tjk - ai1 + ai2 > 0, xi1jk < Ui1 and xi2jk > Li2 .
MultiShift
This move was proposed by Lim et al. [8] and is an extension
of the AdjustIn move that allows an adjustment of
multiple facings between two different products i1 and i1)
on the same shelf part jk. The move adjust facings of both
products by randomly choosing values 1 and 2 so that
xi1jk = xi1jk +1 and xi2jk = xi2jk -2. Like AdjustIn, the
aim of MultiShift is to improve the overall profit in the arrangement
by adjusting facings so that high profitable products
have more facings displayed. The following must be
satisfied: Tjk - 1ai1 + 2ai2 > 0, xi1jk + 1  Ui1 and
xi2jk - 2  Li2 .
AdjustInter
We propose this move to make possible swaps between
four different products located on two different shelf parts.
The aim is to improve the overall profit by adjusting facings
between the first pair of products in the hope that a profit
improving move can be made later with the second pair of
products. For products i1 and i2 on shelf j1k1 and products
i3 and i4 on shelf j2k2, there are two possibilities:
1. Interchange i1 (on shelf j1k1) and i3 (on shelf j2k2)
If xi1j1k1 = Li1 and xi3j2k2 = Li3 , and there is enough
space on each shelf part to swap i1 and i3, make the swap,
save the new arrangement and calculate the resulting profit.
Otherwise, if possible, implement the following sub-moves
regardless of an increase or decrease in profit. For each of
these sub-moves, check if each adjustment described below
can be made. If so, make the adjustment, and check if there
is enough space on shelf j1k1 and shelf j2k2 to swap i1 and
i3. If there is enough space, make the swap, save the new
arrangement and calculate the resulting profit.
If xi1j1k1 > Li1 then xi1j1k1 = xi1j1k1 - 1
If xi3j2k2 > Li3 then xi3j2k2 = xi3j2k2 - 1
If xi1j1k1 > Li1 and xi3j2k2 < Ui3 then xi1j1k1 = xi1j1k1 - 1
and xi3j2k2 = Xi3j2k2 + 1
If xi1j1k1 < Ui1 and xi3j2k2 > Li3 then xi1j1k1 = xi1j1k1 + 1
and xi3j2k2 = xi3j2k2 - 1
If xi1j1k1 < Ui1 and xi3j2k2 < Ui3 then xi1j1k1 = xi1j1k1 + 1
and Xi3j2k2 = xi3j2k2 + 1
If xi1j1k1 > Li1 and xi3j2k2 > Li3 then xi1j1k1 = xi1j1k1 - 1
and xi3j2k2 = xi3j2k2 - 1
2. Interchange i2 (on shelf j1k1) and i4 (on shelf j2k2)
If xi2a = Li2 and xi4b = Li4 , and there is enough space on
each shelf part to swap i2 and i4, make the swap, save the
new arrangement and calculate the resulting profit. Otherwise,
if possible, implement the following sub-moves only if it
results in an increase in profit. For each of these sub-moves,
check if each adjustment described below can be made. If
so, make the adjustment, and check if there is enough space
on shelf j1k1 and shelf j2k2 to swap i2 and i4. If there is
enough space, make the swap, save the new arrangement
and calculate the resulting profit.
If xi2j1k1 > Li2 then xi2j1k1 = xi2j1k1 - 1
If xi4j2k2 > Li4 then xi4j2k2 = xi4j2k2 - 1
If xi2j1k1 > Li1 and xi4j2k2 < Ui4 then xi2j1k1 = xi2j1k1 - 1
and xi4j2k2 = xi4j2k2 + 1
If xi2j1k1 < Ui2 and xi4j2k2 > Li4 then xi2j1k1 = xi2j1k1 + 1
and xi4j2k2 = xi4j2k2 - 1
If xi2j1k1 < Ui2 and xi4j2k2 < Ui4 then xi2j1k1 = xi2j1k1 + 1
and xi4j2k2 = xi4j2k2 + 1
RemoveLeastProfitable
We propose this move which is intended to prevent the
algorithm getting stuck in a local optimum. For one out of
ten randomly chosen shelf parts, find the product i1 which
has more than the minimum required facings xijk > Li and
also contributes with the least profit ijk and reduce the
number of its facings by one xijk = xijk - 1. The aim is to
disturb the solution so that the other moves can ultimately
lead to a much better overall profit. Reducing the number
of facings for the least profitable products leaves more space
to allocate additional facings of higher profitable products
and thus increase the overall profit.
5. EXPERIMENTS AND RESULTS
5.1 Experimental Setting
The experiments were carried out using data kindly provided
by the management of the UN shop. Two problem
instances were made available to us, a small one with 135
products and 15 shelf parts and a large one with 907 products
and 114 shelf parts. The characteristics of each problem
instance are outlined below.
Small Problem. Includes 135 products and 15 shelf
parts (5 shelves). The total shelf space available is 33 meters.
The minimum number of facings required for each
product is 1. The maximum number of facings required for
each product ranges from 2 to 11. The average width of a
product facing is 0.11 meters.
Large problem. Includes 907 products and 114 shelf
parts (38 shelves). The total shelf space available is 248
meters. The minimum number of facings required for each
product is 1. The maximum number of facings required for
each product ranges from 2 to 13. The average width of a
product facing is 0.13 meters.
5.2 Allocation Phase
Only the Arrangement Random Choice heuristic produces
different arrangements in each run. Therefore, this heuristic
was executed 20 times and the average profit was computed.
The profits achieved by each of the initialisation
heuristics on the small and large problems are shown in Table
1 together with the profit for the current arrangement.
The results for the large problem are expected. It is clear
that an arrangement sorted by profit offers the highest overall
profit. The arrangement sorted by size produces just a
slightly higher profit than the random and current arrangements.
The current and random arrangements produce very
similar profits. This suggests that the UN shop management
has not taken much care in creating their arrangement. It
seems that products are placed in a random fashion rather
than being organised by some logical heuristic. We would
expect similar results on the small problem. However, it appears
that on a small scale, the supermarket has allocated
their products fairly efficiently. Note that the three initialisation
heuristics produce an arrangement very quickly even
for the large problem.
926
Current Profit Size Random
Small Problem 78.646 (N/A) 77.119 (0.07) 71.360 (0.06) 71.806 (0.07)
Large Problem 2463.053 (N/A) 2959.334 (3.55) 2574.381 (3.33) 2513.546 (4.07)
Table 1: Profit of the arrangements generated by the initialisation heuristics and profit of the current
arrangement. The computation time (in seconds) for the three initialisation heuristics is shown in brackets.
5.3 Adjustment Phase
Each adjustment heuristic was executed alone for 30 seconds,
this was repeated 20 times for each of the four initial
arrangements generated above. The aim of this experiment
was to assess the effectiveness of each adjustment heuristic
on improving the overall profit of the initial solution. The
summarised results are shown in Table 2. Using these results,
we assigned priorities to each adjustment heuristic in
the local search when selecting the next move to explore.
We assigned probability equal to 0.35 to each of the two
best moves (MultiShift and AdjustInter) and probability of
0.15 to each of the two other moves (AdjustIn and Swap).
Then, the overall Adjustment Phase incorporating the five
adjustment heuristics was executed 15 times for each of the
initial arrangements and each of the two problems. Each run
took 1000 seconds for the small problem and 8000 seconds
for the large problem. This execution time was set based
in our preliminary experiments in which we observed that
usually after around 600 seconds for the small problem and
7000 seconds for the large problem no further improvement
was achieved. In each iteration of this Adjustment Phase,
one of the Swap, AdjustIn, MultiShift or AdjustInter heuristics
is selected with the probability as mentioned above. The
RemoveLeastProfitable move was applied whenever after one
tenth of the overall execution time (100 seconds for the small
problem and 800 seconds for the large problem) no improvement
in the current arrangement was observed.
The results of these experiments are shown in Table 3
for both problems. We can see that for the small problem,
the profit increase achieved by the Adjustment Phase
is fairly similar regardless of the initialisation heuristic used
and also quite large (around 50% improvement over the initial
profit) in all cases. This gives an indication that the
adjustment phase is capable of making substantial improvements
over the initial arrangements including the manual
current arrangement. For the large problem, we can see
that profits have almost doubled from the initial arrangements.
It should be noted that since adjustment heuristic
moves are not restricted to product category, the resulting
arrangement contains products from different categories interspersed.
While it is important for the customer to be
able to find products according to categories, placing product
category restrictions in a small shop can greatly affect
the arrangement possibilities available. A small shop has
very limited shelf space available, fewer number of products
and therefore, there are only a few products within each
category. We argue, with some support from the UN shop
manager, that in a small shop, product category restriction
is not crucial since most products are likely to be visible.
On the other hand, we should remember that customer satisfaction
plays a big role in profits, so the arrangement must
be also such that it is convenient for the customer. Further
assessment of the proposed arrangements by the shop
manager is planned.
5.4 Generated Planograms
Once the final arrangement of products on shelves is created
and evaluated, the termination phase also generates the
graphical visualisation of the proposed solution in the form
of a simple planogram. This is the tool that managers of
retail shops consider important to aid them in deciding the
best way to utilise the available shelf space. An example
of the planograms generated with our system is shown in
Figure 1.
Figure 1: Example of planogram generated with the
proposed system for the large problem.
6. CONCLUSIONS
The optimisation of shelf space allocation is a difficult
problem and a very important area of research. Recent
work has concentrated on the case of large retail shops like
big supermarkets. The aim of this paper was to produce
an efficient optimisation model for the case of small retail
shops. Real data taken from a small retailer and communications
with the shop manager helped us to gather the
relevant information to approach this problem. We have
designed a heuristic method inspired by the work of previous
researchers but adapted to the specific needs of small
retail shops. The proposed heuristic creates an initial arrangement
and then uses adjustment moves in order to iteratively
improve the profit of the current solution. We tested
the method on two problem instances, one small problem
involving 135 products on 15 shelves and one large problem
involving 907 products on 114 shelves. Our results show
that the method is capable of generating much improved arrangements
in terms of the overall profit. We also created a
tool to visualise the proposed arrangements in the form of
simple planograms.
This initial investigation illustrates that a simple and lowcost
shelf space allocation decision support system focused
927
Small Problem Large Problem
Current Profit Size Random Current Profit Size Random
Swap 7.168 5.167 5.874 6.535 83.651 57.086 83.806 72.477
AdjustIn 11.768 23.086 25.164 23.472 133.850 434.227 432.833 396.897
MultiShift 17.574 28.250 30.734 29.227 202.434 394.433 396.424 442.737
AdjustInter 20.986 20.621 27.262 27.446 243.619 94.790 221.183 105.923
Table 2: Average increase in profit achieved by the adjustment heuristics on each problem.
Small Problem Large Problem
Profit Increase Overall Profit Profit Increase Overall Profit
Mean Std Dev Initial Final Mean Std Dev Initial Final
Current 29.064 0.7789 78.646 107.710 2386.334 51.198 2463.053 4849.387
Profit 30.93 0.9372 77.119 108.049 1869.772 27.562 2959.334 4829.106
Size 37.194 0.8388 71.360 108.554 2391.472 23.961 2574.381 4965.853
Random 36.253 0.5154 71.806 108.059 2191.735 36.024 2513.546 4705.281
Table 3: Summary of results achieved by the heuristic method on the small and large problems.
on small retailers will not only be appealing but also encourage
shop managers to use these tools to their advantage.
There are a number of issues that demand further
investigation. For example, modify the RemoveLeastProfitable
move to overcome the local optimum more effectively.
Currently, this move removes one product from within ten
shelves. Even for the large problem with 114 shelves, this
means that only 11 (out of the 907) products are removed.
Perhaps removing more products could result in more space
being available and better adjustments made later. Another
issue is the objective function which at present, is based on
the perceived profitability as measured by the shop manager.
Perhaps, further evaluation on the proposed arrangements
in the real world could also suggest other criteria that should
be considered when evaluating the quality of the generated
arrangements. Also, much further experimentation should
be carried out on more instances and more scenarios. We
intend to continue with this research and collect or generate
data that reflects the real world problem faced by small
retail shops.
7. ACKNOWLEDGMENTS
We thank the management of the UN shop in Vienna for
kindly providing the data and information for the work presented
in this paper. We are also grateful to the anonymous
referees for their comments and feedback.
8. REFERENCES
[1] E. Anderson and H. Amato. A mathematical model
for simultaneously determining the optimal brand
collection and display area allocation. Operations
Research, 22(1):13­21, 1974.
[2] N. Borin, P. Farris, and J. Freeland. A model for
determining retail product category assortment and
shelf space allocation. Decision sciences,
25(3):359­384, 1994.
[3] F. Buttle. Retail space allocation. International
Journal of Physics Distribution and Material
Management, 14(4):3­23, 1984.
[4] J. Cairns. Allocate space for maximum profits.
Journal of Retailing, 39(2):41­55, 1963.
[5] M. Corstjens and P. Doyle. A model for optimizing
retail space allocations. Management Science,
27(7):822­833, 1981.
[6] X. Dreze, S. Hoch, and M. Purk. Shelf management
and space elasticity. Journal of Retailing,
70(4):301­326, 1994.
[7] P. Hansen and H. Heinsbroek. Product selection and
space allocation in supermarkets. European journal of
operational research, 3(6):474­484, 1979.
[8] A. Lim, B. Rodrigues, and X. Zhang. Metaheuristics
with local search techniques for retail shelf-space
optimization. Management science, 50(1):117­131,
2005.
[9] M. Yang. An efficient algorithm to allocate shelf
space. European journal of operational research,
131:107­118, 2001.
[10] M. Yang and W. Chen. A study on shelf space
allocation and management. International journal of
production economics, 60-61:309­317, 1999.
[11] F. Zufryden. A dynamic programming approach for
production selection and supermarket shelf-space
allocation. Journal of the operational research society,
37(4):413­422, 1986.
928