Publication
FrAPP - Framework for Automated Product Placement
Nico Herbig
Mastersthesis, Deutsches Forschungszentrum für Künstliche Intelligenz, 2014.
Abstract
The main objective of this thesis is to find optimal solutions for the shelf space allo- cation problem in retailing: how much space should be assigned to the individual products and where should they be placed in order to maximize the category profit? Therefore, a mathematical optimization model was formalized and an efficient algorithm for solving this model was determined. The implemented system called FrAPP, Framework for Automated Product Placement, offers an interface for selecting boards and products and allows to specify further criteria such as minimum facing amounts and stacking limits. Furthermore, to fulfill merchandising specifications, users can manually place products and let FrAPP optimize the empty space around them. It is also possible to enter discounts achieved by purchasing a specific amount of products from the producer or wholesaler merchant, which will then be considered in the computation. The out- put solution is placed directly into a 3D model of a supermarket through which the user can navigate. FrAPP also offers the possibility to export a planogram of the found solution as a web page for easy accessibility. For formalizing the optimization model a function capturing the demand in a given placement is needed. To make the model practical, the demand function aims to only use available data and at the same time reflect reality as closely as possible. It contains known parameters as the facing area, the space elasticity and location values, however, trends and the so called cross space location elasticity are also introduced. Here, the trends reflect the expected sales or losses due to factors outside of the store such as advertisement. The cross space location elasticity is an improvement to the well known cross space elasticity and combines the effects of space and location of one product on the demand of a substitute product. In order to express the fact that some products are more popular than others even if placed equally, the so called worst allocation demand is used. That is, the demand a product would achieve if it had one single facing on the lowest board. This worst allocation demand can be computed from the previous sales and placements and even incorporates regional differences in popularity. The evaluation function of the optimization model is the overall profit achieved by the placement. All valid solutions must fulfill the following requirements: first, given upper and lower bounds on the facing amounts and stacking limits have to be satisfied. Secondly, decreases in demand due to disappearing facings as well as stock-outs are prohibited as they would result in financial penalties. Finally, all instances of a product must be connected to achieve a minimum level of sorting and therefore avoid irritating solutions. As the search space is too large for simple brute force algorithms, FrAPP uses a simulated annealing based hyper-heuristic as an optimization algorithm. This hyper-heuristic approach uses a set of heuristics to generate neighbors instead of one single neighboring function and can therefore adapt to different problem vii instances easily. The heuristics were created such that they fulfill the above requirements with high probability. To improve customer satisfaction, the found solutions are sorted by brand or type while keeping the quality of the placement intact. Apart from a single threaded version three different parallelization modes were implemented. An evaluation with data provided by a German retailer showed that all algorithms are able to find the optimal solution within a small amount of time. However, some algorithms outperform the others depending on the allowed computation time.