Investigation of Novel Methods to Optimise Shelf Space Allocation
The Automated Scheduling, Optimisation and Planning Research group (ASAP : http://www.asap.cs.nott.ac.uk) at the University of Nottingham has been carrying out highly successful research into the development and application of meta-heuristic techniques and hybridisations to scheduling and optimisation problems (particularly space allocation and timetabling) for the last 8 years. It has been at the forefront of research in the area during this period and is internationally recognised within the scheduling community for its work. The group has recently undergone significant expansion and now has 4 members of academic staff, 5 research assistants, 13 PhD students and a secretary. The investigators have many years of research experience.
Dr Kendall has carried out successful
research in the field of stock cutting for the past three years. His PhD thesis
considers a concept called the no fit polygon and applies it to nesting
problems. This idea is used in conjunction with a range of meta-heuristic and
evolutionary approaches (such as simulated annealing, tabu search, genetic
algorithms and ant algorithms) to search for good quality solutions. He has
published the results of his work in scientific journals and presented his work
at high quality, international conferences [BUR98a], [BUR99a] , [BUR99b] ,
[BUR99c] , [BUR99d]. This work is being further developed by an EPSRC CNA (CASE
for new Academics) grant he has just been awarded (the PhD student started in
October 2000). As part of this award the PhD student must work for at least
three months each year at the sponsoring company (Esprit Automation Ltd.,
Sandiacre, Nottingham). During this period of secondment the student will
assist the company to incorporate some of the latest research techniques into a
nesting software package they are currently re-developing. Since his PhD Dr
Kendall has further broadened his research interests and has published papers
which investigate how computers can learn to play chess [KEN01a], how
evolutionary strategies can be used to predict macro-economic factors
([KEN01b], [KEN01c], KEN01d]) and how collective behaviour can emerge from
seemingly simple organisms [WAR01].
In addition to the CNA grant, Dr Kendall has
recently been awarded a TCS (Teaching Company Scheme) award. This is, again, in
conjunction with Esprit Automation Ltd. and allows the company access to the
research being undertaken by the ASAP group. This scheme will run for three
years and the associate will re-engineer their current product to a product
that, hopefully, will be the leader in the field. Obviously, there will be
close links between the TCS and the CNA. Dr Kendall is also a co-investigator
on a recently awarded EPSRC award (“An Investigation of Hyper-heuristic
Methods” : GR/N36837/01) being led by Prof. Burke, a BBSRC award, and an EPSRC
network (“An Interdisciplinary Scheduling Network” : GR/R12268/01)
Dr. Kendall is a member of the program
committee of the 4th Metaheuristics International Conference (MIC
2001) : 16th – 20th July 2001, Porto, Portugal. He is
also a member of the Technical Committee of the Congress of Evolutionary
Computation (CEC-2001), COEX Center, Seoul, Korea, May 27-29, 2001 and is
co-organising a workshop at the Genetic and Evolutionary Computation Conference
(GECCO 2001), San Francisco, California, USA, July 7-11, 2001. He edits the
EURO (European Association of Operational Research) funded WATT (Working Group
of Automated Timetabling) Digest and has acted as a referee for the following
journals; The Journal of Scheduling, The Computer Journal, International
Journal of Applied Intelligence and Management Science.
Professor Edmund Burke holds a Chair in Computer
Science at the University of Nottingham. He leads the Automated, Scheduling,
Optimisation and Planning (ASAP) group within the school of Computer Science
and Information Technology. He has been awarded 13 major grants over the last 9
years. He is an Associate Editor on the IEEE Transactions on Evolutionary
Computation, Editor-in-chief of the Journal of Scheduling (published by Wiley)
and an area editor (for combinatorial optimisation) of the Journal of
Heuristics. Professor Burke is also chairman of the steering committee of the
international series of conferences on the Practice and Theory of Automated
Timetabling (PATAT) and co-editor of the conference proceedings and Selected
Paper volumes (published by Springer). Professor Burke is co-ordinator and
chairman of the committee of the EURO Working Group on Automated Timetabling
funded by EURO. He has published over 65 refereed papers during his career and
has acted on the programme/refereeing committees of over 20 international
conferences.
Professor Burke will act in an advisory
capacity for the proposed research project, contributing his expertise (both
technical and administrative) to the project. He also has experience in
managing research projects, which will be of assistance to the principal
investigator. Recent relevant publications include [BUR99f], [BUR00f],
[BUR00g].
Dr Peter Cowling is a Reader in Computer Science and a member of the ASAP group at the
University of Nottingham. He has been principal investigator or co-investigator
on 8 externally funded grants, investigating novel methods of decision support
for scheduling of people and production. He is an associate editor of the
Journal of Scheduling and has been on the programme/refereeing committee of 8
international computer science conferences over the past two years. He has 12
international scientific journal papers and has contributed to numerous
international scientific conferences. While at A.I. Systems, he was responsible
for managing project teams which developed the market leading SteelPlanner
range of steel scheduling decision support systems.
Dr Cowling will act in an advisory capacity
for the proposed research, contributing expertise in modelling and optimisation
of real world industrial systems, and solutions using meta- and
hyper-heuristics. Recent relevant publications include [COW00a], [COW00b],
[COW95].
Dr Sanja Petrovic is a lecturer in Computer Science and a
member of the ASAP group at Nottingham.
Before this she worked as a Senior Researcher at the Mihajlo Pupin
Institute in Belgrade, Yugoslavia. Her main area of research includes the
development of artificial intelligence techniques for operational research
problems. She is a member of Yugoslav Operational Research Society and Yugoslav
Society of Soft Computing and Intelligent System. She is also a member of the Congress of Evolutionary
Computation (CEC 2001) program committee and the Genetic and Evolutionary
Computation Conference (GECCO 2001) program committee. She was a member of the Programme committee for the 3rd
international conference on the Practice and Theory of Automated Timetabling
(PATAT 2000). She will be a guest co-editor for a feature issue of the European
Journal of Operational Research (EJOR) on "Timetabling and
Rostering". She has 8 papers published in distinguished scientific
journals and over 20 papers in conference proceedings.
Dr Petrovic has experience in case based
reasoning and multi-criteria optimisation. This experience will be used to good
effect in this project. Publications relevant to this proposal include
[BUR01a], [BUR01b], [BUR00a], [PET98], [RAD97], [PET95].
The retailing sector in the UK is an extremely
competitive arena. We only need to consider some high profile companies to show
that this is the case. A particular example is provided by the recent decline
of Marks and Spencer, who were the leading high street retailer. A further
example is given by C&A’s recent decision to close all of its high street
outlets. Yet another example is the decline of J Sainbury from its position as
the leading food retailer in the UK in the 1990’s (in 1996 Tesco opened up a 2%
lead over their rivals and continue to maintain an advantage). The recent
merger of Asda and Wal-Mart which is expected to bring increased pressure on
other retailers due to the buying power of Wal-Mart. This level of
competitiveness is unlikely to decline. On the contrary, the high street is
likely to become even more competitive.
Retailers are keen to do everything possible to make their systems more efficient, whilst maximising their profit. Two key areas where this can be realised is in the initial store layout (what categories of goods to sell and how much space is allocated to each category) and how the individual products are placed on the shelves. A shelf layout is known as a planogram. Investigating the use of novel techniques to automatically produce high quality planograms, in reasonable timescales, will be the focus of this research. Our industrial collaborators have told us that this research is particularly welcome because producing planograms is largely a manual process. There is software assistance available (e.g. one of the products developed by one of our collaborators) but it involves significant human interaction and is mainly a drag and drop procedure (i.e. drag a product line and drop it on a shelf). A recent publication [YAN99] surveyed the area and demonstrated the lack of academic work conducted in this domain. Only 12 references were cited. 5 of these dated back to the 70’s, 4 were drawn from the 80’s and only 3 were from the 90’s. It seems timely that this area should receive rigorous research attention, given the recent advances in AI search techniques. In fact, [YAN99] states
“The concern of simplicity and practicability of these commercial
approaches will certainly have a negative effect on their solution performance.
However, high-speed computers of low cost are nowadays available to overcome,
in some degree, the problem of complex computations. The optimization
approaches are therefore applicable to be used in space management systems for
improving the performance of shelf space allocation.”
At present, commercial systems use relatively simple
heuristic rules to allow retailers to plan their shelf space allocation
[ZUF86], a view also echoed recently [YAN01]. We would like to give the
industry the opportunity to incorporate the latest research developments into
their plangram procedures so that better quality solutions can be found. We
would also aim to do this using less resources than present (in terms of both
CPU time and man hours).
Buttle [BUT84] states that
the purpose of shelf space allocation is to improve the financial performance
of the store. Drèze [DRE94] also reported that product location had a large
impact on sales and that the number of facings of a product had less of an
impact, as long as a certain threshold is maintained. Interestingly, this is in
direct contradiction to a conversation we have had with one of our
collaborators. This proposal will address this issue and build the results into
the planogram model. Space elasticity is another area that has received
consideration in the past (see [CUR73] and DOY77]). Space elasticity can be
defined as “the ratio of relative change in unit sales to relative change in
shelf space” [YAN01]. This is another area we will investigate. Anderson and
Amato [AND74] proposed a model that determines the optimal brand selection. Whilst
most supermarkets indicate which brands they are to stock (and thus produce a
planogram for), this is an area which is worthy of research to ascertain if the
process can be further automated by allowing the software to choose which
products to display rather than having this as a manual process. Some of the
models that have been previously suggested ignore real world implications (for
example, by working with real numbers when integers values are required)
([COR81], [COR83], [ZUF86]). This research will ensure that any solution
methods we develop can be applied to real world problems, taking into account
any constraints that those problems present. The most recent work [YAN01] uses
a model based on a knapsack problem and presents a heuristic to solve instances
of shelf space allocation problems.
Planograms are a subset of
the wider domain of space allocation which incorporates more well known
research areas such as bin packing and knapsack problems [BAA88] [YAN01]. Some
of the techniques we intend to investigate have already been successfully
applied to problems within this wider domain. Bland [BLA99] has applied ant
colony optimisation [DOR96] to space planning.
In trying to produce an optimised planogram there are
many factors which must be taken into account. Some examples are:
·
The product lines defined by the store management must
all be displayed on the shelves.
·
The product lines must be allocated to shelves in such
a way that they can physically be placed onto those shelves (e.g. the
tin/jar/carton must not be taller than the shelf to which it is allocated).
·
If the product is placed on the shelves in its
packaging (e.g. the cellophane wrapper is removed and the cardboard box is
placed on the shelf), then the planogram must allow for two cartons to be
placed on the shelf. If only one carton were allowed the product could sell out
and no more sales could be made until a new carton was provided for the
customers. If two cartons are catered for, when there is less than one carton
left a new carton can be supplied, thus not interrupting sales.
·
For similar reasons, if products are completely
removed from their packaging before being placed on the shelf then provision
must be made to allow for 1½ packages to be accommodated on the shelf. This
allows for the shelf to be replenished from stock without having to return half
empty packages to the stock room.
·
The position of the product on the shelf could be an
important factor. It is thought by some in the industry that products at eye
level sell better than products at, say, floor level. However, sweets could be
placed at a lower level so that they are at the eye level of a small child.
Similarly, products at the start of an aisle sell better than products in the
centre of an aisle on the basis that if a customer wants a particular product
they will pick up the first one they see.
·
Suppliers may be able to influence the retailer as to
the amount of shelf space allocated to their brands and the position of the
brands on the shelf.
·
In some cases, it may be better to place a particular
brand in a ‘block’ (using several shelves) rather than using a single shelf to
display the brand.
We plan to investigate and further develop recent advances in heuristic optimisation techniques to produce good quality shelf layouts (also called planograms). Specifically, the objectives are to
1. Investigate modelling issues in formulating a shelf layout and develop appropriate models. The models will be capable of being optimised by exact techniques (e.g. linear programming, graph theory etc.) and AI techniques (e.g. genetic algorithms, ant algorithms, evolutionary strategies, multi-objective approaches etc.)
2. Investigate and develop operational research and artificial intelligence techniques to optimise the model developed in 1. The range of techniques we will consider will include initialisation strategies (so that we start searching from reasonable solutions), decomposition (to break the larger problem into sub-problems which may be easier to solve), case based reasoning (both as an initialisation strategy and as a method in its own right) and hybridisation (to combine two (or more) different algorithms).
3. Implement a prototype system for the next generation of planograms. These will produce planograms of higher quality than is currently available, using less time and labour than current methods.
4. Evaluate and assess the model on a range of real problems from the retail sector.
1. Develop
appropriate models
Several models have already been developed for shelf
space allocation. The model presented by Buttle [BUT84] defines five aspects
which contribute to profit (fixture location, product category location, item
location within categories, on-shelf display and POS promotional support). As
mentioned above, the model of Drèze [DRE94] concentrates more on product
location, rather than the number of facings presented to the customers. This
contradicts a conversation with one of our collaborators and it will be an
interesting line to investigate in formulating the models. Anderson and Amato
[AND74] propose a model that determines the optimal brand selection. This is
not something the supermarkets currently consider (they know which brands they
will sell and choose from that range), but we will investigate, with our
collaborators, if this is an area that they would like built into the model.
Some of the previously developed models provide a simplified abstraction of the
real world COR81], [COR83], [ZUF86]. Recent work by Yang and Chen [YAN01] uses
a knapsack model and a heuristic to solve the problem.
Our research will develop
the work cited above to produce a model that is robust and meets real world
objectives and constraints. A key aspect of this work is to build a general
model that represents the wide range of problem types which we are trying to
solve. The investigators on this project have experience in not only defining
mathematical models for a variety of applications but, more importantly, in
applying these models to real world problems (for examples, see [BUR99f] and
[COW00a]). We will develop a model which is suitable for optimisation using
exact techniques such as, but not limited to, integer programming, mixed
integer non linear programming and graph theory. In addition the developed
models will also be suitable for optimisation by the latest AI techniques.
These include, but are not limited to, ant algorithms [DOR96], tabu search
[GLO98], simulated annealing [KIR83], genetic algorithms [GOL89] evolutionary
strategies [FOG00], multi-objective approaches and case based reasoning
[KOL93].
2. Optimise the model
In recent years there has been a lot of interest in
solving the type of complex combinatorial optimisation problems that planograms
represent. The ASAP group at Nottingham has been a world leader in this field
and we aim to build on our expertise in office space allocation and other
optimisation problems to produce high quality shelf layouts.
In one sense planograms can be defined as a bin packing problem (i.e. fit the products on the shelves maximising some function). The recent research carried out by the principal investigator, as part of his PhD thesis, considers these type of problems (see [BUR98a], [BUR99a], [BUR99b], [BUR99c], [BUR99d]) by using various search techniques (tabu search, simulated annealing, ant algorithms and genetic algorithms). This research will develop these techniques and apply them to planograms. Bin packing is just one example of space allocation. This wider domain is an area that ASAP has worked in for many years [BUR00f] and we are ideally placed to conduct the proposed research project.
As well as investigating the search techniques listed above, we have evidence that hybridisation provides more than the sum of their individual parts [BUR99f], [BUR00f]. The so called memetic algorithm, for example, combines a population based approach (such as a genetic algorithm) with a local search technique (such as hill climbing). In previous research [BUR00g] on timetabling, this has proven to be extremely effective.
It is also recognised that
planograms are often based on previous planograms. Dog food, for example, might
be used as a basis for cat food, or even washing powder. Larger planograms,
such as the toiletry aisle might be used as a basis for the biscuits aisle.
This re-use of previous planograms suggests that case based reasoning (CBR)
would lend itself well to planogram optimisation, either as a direct approach
or as a method of initialisation. The investigators in this proposal already
have experience in CBR [BUR00a], [PET98] and this problem seems ideally suited
to being tackled by using this method.
In previous research
projects we have found that a good initialisation strategy can ultimately lead
to a better quality final solution as well as reducing the search time [BUR98b].
We will investigate the use of initialisation strategies within this proposal.
In particular, we will consider case based initialisation.
Another method we have found
to be very effective for other problem domains is decomposition. This has worked
particularly well on timetabling problems [BUR99f] and [CAR83] where it was not
only more efficient but also produced better quality solutions. It would seem
likely that shelf layout would be particularly suited to being decomposed into
smaller problems, due to the nature of the problem (e.g. you want all of one
particular product line in one place, so it can be solved as a sub-problem).
Indeed, at first sight, it would seem to have a better chance of working in
this problem domain than timetabling.
When optimising a shelf
layout we will be trying to optimise many competing objectives (selection of
brands, space allocated to each product, placement of each product, shelf life,
number of facings etc.) and it would seem appropriate to use a multi-objective
method to optimise the model developed above. ASAP have already developed these
techniques for other problems [BUR01a], [BUR01b], [RAD97] and we will
investigate the applicability to this problem.
In summary, we plan to
investigate the optimisation of the model developed above using a range of
techniques and approaches. These include heuristic, meta-heuristic,
hybridisation, initialisation strategies, cased based reasoning, decomposition
and multi-objective approaches.
3. Implement a
prototype system
A main aim of this research is to work with real world
problems. With this in mind we want to have regular contact with our
collaborators and with other industrial partners. We will develop a prototype
system that can be used to demonstrate our approaches so that the industry can
see what is possible using these new techniques and also so that we can gain
feedback. It should be emphasised that this research will not produce a piece
of commercial software, although ASAP has a good record of producing commercial software as can be
evidenced by its Optime package (which schedules university examinations and is
used in a number of institutions). Rather, we intend to produce a prototype
system which demonstrates the effectiveness of the new techniques.
4. Evaluate the
system/approaches on real world data
As mentioned above, an overriding aim of this project
is that it will tackle real world problems faced by industry and not just
simplified problems. Therefore, we will acquire real world data and conduct our
testing and evaluation on that data and validate the results with our partners.
The proposed research will be conducted in a series of
work packages. The work packages and deliverables are outlined in the following
table.
|
Work Package |
Deliverables
|
|
WP1 Analyse the way in which planograms can be represented, taking
into account the various factors which are peculiar to the retail industry
(for example, balancing the aesthetic requirements of the retailer with the
product placement requirements of the supplier). The PhD student will be
tasked with researching the literature and with developing models that meet
the objectives for planograms. The model will be reviewed and refined in
conjunction with our collaborators : 8 months |
·
A formal description and mathematical models
of shelf packing problems with regard to planograms ·
A technical report describing and discussing
the modelling issues. ·
Publication in professional journal. |
|
WP2 The construction of a set of test cases from both the
literature and industry. It is envisaged that the majority of test cases will
come from industry due to the lack of data available from existing
literature. This data will be primarily supplied from our collaborators : 6 months |
·
A set of training cases which will be used throughout
the project. ·
We aim to publish this data (commercial
confidentially allowing) so that it is available for the scientific
community. |
|
WP3 Thorough
and critical investigation of a range of techniques to optimise the model
from WP1 using the data compiled in WP2. The techniques we will investigate
will be heuristic, meta-heuristic, hybridisation, initialisation strategies,
cased based reasoning, decomposition and multi-objective approaches : 18
months |
·
Publication in Journals and UK and
International Conferences |
|
WP4 Detailed
evaluation, using the test suite from WP2 and algorithms developed from WP3 :
12 months |
·
Publication in Journals and UK and
International Conferences and Journals |
|
WP5 Demonstration
of our approaches to our collaborators : 6 months |
·
A successful outcome of the project could
lead to commitment from retailers that this work should be progressed
further. |
This is a three year project. Dr Kendall will be
responsible for the scientific and technical direction and for the
administration of the project. Professor Burke will act in an advisory role, in
particular giving the project the benefit of his experience and expertise in
managing externally funded projects. Dr. Cowling will contribute his knowledge
and experience of tackling real-world problems using heuristics,
meta-heuristics and decision support systems. He will also draw on his
experience from working at A.I Systems in Belguim. Dr. Petrovic will contribute
in the area of multi-objective optimisation and case-based reasoning as these
are particular areas of expertise for her.
Retail Vision will provide
consultancy and access to the industry, which would be difficult to do without
their support. Space Software Solutions will provide training as well as one of
the leading software packages in this area. Tesco will bring their knowledge
and expertise to this project and we will make full use of the consultancy they
have offered.
The main beneficiaries of the project will be:
1. The academic research
community: The proposed research explores an area which has lacked rigorous
academic input in the past. This research will not only provide a solid
foundation for future research into planograms but it will also apply current
operational research and artificial intelligence techniques to this area. We also envisage developing these areas so
that techniques applied to planograms will have wider applicability (in the
same way that initialisation and decomposition techniques, applied to
timetabling will be used here). As this is a new area of research, it is
envisaged that new, possibly hybrid, heuristics will arise from this work.
2. Collaborators: The three
partners supporting this proposal will benefit from this work by being made
aware of what is possible using the latest OR and AI techniques. By accessing
the papers produced from this work as well as day to day contact with the
researchers they will gain valuable insight into what is possible using the
latest ideas from the research community.
3. UK supermarkets are seen
as a major beneficiary of this research, as shown by the letter of support from
Tesco, but many areas of UK business can benefit, for example, warehouses, DIY
superstores and book stores.
4. Education programmes: The recruited PhD student will gain considerable knowledge of operational research and artificial intelligence techniques and their application to real world problems. Collaboration with the partners supporting this proposal, and other UK retailers will add to the student’s educational experience. In addition, the work carried out in this proposal will be included in the teaching of various undergraduate/postgraduate modules at the University of Nottingham. For example, the researchers named in this proposal are current module leaders for two AI modules (Dr. Kendall), an optimisation module (Dr. Cowling) and a scheduling module (Dr. Petrovic). All of these modules can draw from the work carried out under this proposal.
Successful outcomes of the proposed research project
will be disseminated via scientific journals and refereed conference
proceedings. Our aim is to publish in a number of international operational
research and artificial intelligence journals (e.g. Artificial Intelligence,
Operations Research, Journal of the Operational Research Society, International
Transactions on Operational Research, European Journal of Operational Research,
Journal of Heuristics). The results will also be presented and published in the
proceedings of international and UK conferences including EURO (European
Conference on Operational Research), IFORS Conferences, GECCO (Genetic and
Evolutionary Computation Conference), CEC (Congress on Evolutionary
Computation), European Conference on Artificial Intelligence etc. In addition,
a web site will be maintained that will plot the progress of the research.
Throughout the period of
research we will constantly seek advice and guidance from the industry to
ensure that the research is addressing the relevant problems. This will be
achieved by regular meetings with our collaborators, by visiting our
collaborators to demonstrate our results and by establishing new contacts with
industry as we disseminate this work through publication and the web site which
we will integrate with the recently updated ASAP web site.
Tesco is one of the
UK’s largest food retailers and also offers a range of other services such as
non-food goods, personal finance products and on-line shopping. They employ
over 163,000 people. As well as operating in the UK they have also expanded
into Europe. They sell a total of 60,000 lines, of which 25,000 are Tesco
own-brand products. We are very happy to have one of the UK’s leading retailers
supporting this proposal as it demonstrates the timeliness and high level of
commercial interest of this research.
Retail Vision was established in 1996 and provides
consultancy services to both retailers and suppliers. They specialise in
planograms and retail space allocation.
Space Software Solutions Limited provide a range of software to the retail
industry which allows them to plan their space usage, produce planograms and
perform range analysis on each of their planograms.