the retail shelf space allocation problem: new optimization methods applied to a supermarket chain

Faculdade de Engenharia da Universidade do Porto PORTO FEUP FACULDADE DE ENGENHARIA UNIVERSIDADE DO PORTO DEPARTAMENTO DE ENGENHARIA E GESTÃO INDUSTRIAL U. The Retail Shelf Space Allocation Problem: New Optimization Methods Applied to a Supermarket Chain Maria Teresa Peixoto Braga Bianchi de Aguiar Submitted to Faculdade de Engenharia da Universidade do Porto in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Industrial Engineering and Management, supervised by Maria Antónia Carravilla, Associate Professor of the Faculdade de Engenharia da Universidade do Porto, and José Fernando Oliveira, Full Professor of the Faculdade de Engenharia da Universidade do Porto Department of Industrial Engineering and Management Faculdade de Engenharia da Universidade do Porto 2015 This research was partially supported by the PhD grant SFRH/BD/74387/2010 awarded by the Portuguese Foundation for Science and Technology Teoria e Prática “Toda a teoria deve ser feita para poder ser posta em prática, e toda a prática deve obedecer a uma teoria. Só os espíritos superficiais desligam a teoria da prática, não olhando a que a teoria não é senão uma teoria da prática, e a prática não é senão a prática de uma teoria. Quem não sabe nada dum assunto, e consegue alguma coisa nele por sorte ou acaso, chama «teórico» a quem sabe mais, e, por igual acaso, consegue menos. Quem sabe, mas não sabe aplicar - isto é, quem afinal não sabe, porque não saber aplicar é uma maneira de não saber -, tem rancor a quem aplica por instinto, isto é, sem saber que realmente sabe. Mas, em ambos os casos, para o homem são de espírito e equilibrado de inteligência, há uma separação abusiva. Na vida superior a teoria e a prática completam-se. Foram feitas uma para a outra. ” Fernando Pessoa, in ´Palavras iniciais da Revista de Comércio e Contabilidade’ Abstract While shopping, customer choices are influenced by in-store factors, in particular during unplanned purchases and product stockouts. The arrangement of products on the shelves becomes crucial in this context and a key factor to retailers’ competitiveness. Recently, the shortage of shelf space and the increasing number of products available have greatly magnified the importance of how merchandise is displayed. The Shelf Space Allocation Problem (SSAP) has long been considered by marketing professionals and the scientific community, with the first published studies tracing back to the seventies. However, academic work is far from being applied in practice: most of the optimization models have practical limitations, either because of their simplicity and lack of key-practical features or due to the large number of parameters difficult to estimate. As a result, there has been a misalignment between software applications, business practices, and research. Motivated by the space management problems arising in the Food Retail Industry, the objective of this thesis is to tackle the SSAP and bridge the existing gap between research and practice with the development of innovative quantitative tools that support the generation of automated and optimized shelf space allocation solutions in practice. A case study in a European Food Retailer provides the right motivation to understand the current challenges faced by retailers and constitutes the perfect environment to assess the practical value of our scientific contributions. The contributions of this thesis are aligned with two main directions. On one hand, we pushed the frontier of the shelf space literature with new mathematical models and stateof-the-art solution approaches that combine mathematical programming with heuristics. We investigated key practical features of the problem, with an emphasis in Merchandising Rules, and developed innovative approaches capable of delivering high quality solutions, suitable to business practice, in reasonable computational time. On the other hand, we developed a comprehensive decision support system for the automatic generation of shelf space solutions (planograms) that is nowadays being used on a daily basis in the case study company, proving the validity of our achievements. Despite the straight link with the case study, all the mathematical models and algorithms that emerged from this thesis are extensible to other food or non-food retailers sharing similar challenges. We believe that this thesis is an important contribution both by bringing additional realism into academia and by proving the value of advanced analytics in practice. Moreover, it will ultimately contribute to the “next generation” of shelf space planning systems. v Resumo Durante o processo de compra, as escolhas dos consumidores são influenciadas por fatores associados à disposição dos produtos nas lojas, especialmente durante as compras não planeadas e nas situações de rutura de produtos. Neste contexto, a disposição dos produtos nas prateleiras torna-se crucial e um fator-chave para a competitividade dos retalhistas. Recentemente, a escassez de espaço e o aumento do número de produtos disponíveis criou uma maior ênfase na forma como a mercadoria é exibida. O Problema da Alocação dos Produtos nas Prateleiras (SSAP) tem sido alvo de estudo por profissionais de marketing e pela comunidade científica desde os anos setenta. No entanto, a maioria dos modelos e abordagens de otimização têm limitações que inibem a sua aplicação prática, seja por causa da sua simplicidade e falta de características-chave ou devido ao elevado número de parâmetros difíceis de estimar. Consequentemente, existe um desalinhamento entre as aplicações de software existentes, as práticas do negócio, e a investigação desenvolvida. Motivados pelos problemas de gestão de espaço na Indústria Alimentar, o objetivo desta dissertação é abordar o SSAP com vista a um melhor alinhamento entre a prática e a teoria, através do desenvolvimento de ferramentas quantitativas inovadoras que suportem a geração de soluções de alocação de espaço na prática. Um caso de estudo num retalhista europeu constitui o ambiente ideal para compreensão dos desafios atuais e para avaliação do valor prático das contribuições científicas. As contribuições desta dissertação estão alinhadas com duas direções principais. Por um lado, foram desenvolvidos novos modelos matemáticos e novos métodos de solução que constituem avanços científicos no SSAP. Estas abordagens integram novas características práticas do problema, com ênfase nas Regras de Merchandising, e oferecem soluções de alta qualidade, adequadas para a prática, e com bom desempenho computacional. Por outro lado, foi desenvolvido um sistema de apoio à decisão para a geração automática de soluções de alocação de espaço (denominados planogramas), que está atualmente implementado e em utilização no caso de estudo. Apesar desta estreita ligação com um retalhista, todos os modelos matemáticos e todos os métodos de solução desenvolvidos são extensíveis a outras indústrias com características semelhantes. Acreditamos que esta tese é uma contribuição importante quer por trazer métodos inovadores e realismo adicional à investigação científica quer por provar o valor de abordagens quantitativas na prática. Além disso, acreditamos ter contribuido para a próxima geração de sistemas de planeamento e gestão de espaço no retalho. vii Acknowledgments It is with sincere gratitude and appreciation that I thank all that have assisted me during this amazing journey. I am most grateful to Sonae MC, the European Food Retailer that collaborated in this project, for their support and many contributions. I address special thanks to João Amaral who trusted in me for this huge project, Jorge Liz for believing in the project since the very first second, Joel Pacheco for being the perfect liaison in some critical phases and also Frederico Santos, Sérgio Lapela, Miguel Camanho, Vasco Rei, Hélder Matos and all the micro-space team. At last, but not the least, I would like to acknowledge Constantino Gomes, Pedro Soares and Susana Borges for their patience and kindness when explaining me the deepest details of space management and afterwards when testing the first GAP prototypes. I acknowledge my supervisors, Maria Antónia Carravilla and José Fernando Oliveira, for their endless support, contagious enthusiasm and for all the trust in my capabilities (much more than mine for sure). They were truly friends in so many moments and I have learned so much more than Operations Research (OR) with them. They gave to me all kinds of opportunities to grow and become a better researcher, better professional and better person. I also appreciate their dedication to teaching and emphasize again the deep admiration that I have for them since the very first OR class. The members of Iolab have contributed immensely to my personal and professional time during the PhD. Our group has been a source of very strong friendships as well as good advices and collaborations. I am especially thankful to Elsa Silva. We built a very strong friendship out of the project and I cannot thank her enough for all the support and for all the help she has given me. This project would not have been the same without her. I would also like to acknowledge Pedro Amorim, Victor Camargo, Gonçalo Figueira, Miguel Gomes, Pedro Rocha, Sam Heshmatti and the women power, Diana Lopez, Sara Martins, Maria João Pires, and Beatriz Oliveira. There are also many other past and present members from Iolab, and from FEUP in general, that I have had the pleasure to meet during this time. Above all, thank you all for making my days so much better. I am also grateful to José Pedro Rodrigues for participating with me in the different extra curricular activities that I was involved. Finally, I acknowledge Bernardo Almada-Lobo for the words of advice in many situations. During this time I had the pleasure to visit ICMC at the University of São Paulo and the UCLA Anderson School of Management. I am very grateful to Franklina Toledo for the ix 2Chapter 1. Motivation and Overview development of large-scale data processing technologies, with limited or no use of mathematical optimization and disregarding the space effects on consumer demand. On the other hand, state-of-the-art optimization methods have practical limitations, either because of their simplicity and lack of key features, or due to their complexity and expensive estimation requirements for parameters. A closer cooperation between retail research and practice is needed and will ultimately lead to the “next generation” of shelf space planning systems, with automated and optimized shelf space allocation solutions (Bai [2005]). This thesis is the result of problem-driven research motivated by the space management problems arising in the food retail industry. In collaboration with a European Food Retailer, the objective is to tackle the SSAP and bridge this gap between retail research and practice with the development of quantitative tools that support the generation of automated and optimized shelf space allocation solutions in practice. The case study not only provides the motivation to understand the current challenges and flaws on the current literature approaches, but also constitutes the perfect environment to assess the practical value of our scientific contributions. Despite this straight link with the case study, all the mathematical models and algorithms emerging from this thesis are expected to be extensible to other food or non-food retailers sharing similar challenges. This introductory chapter presents an overview of shelf space planning and defines the objectives of this thesis. The remainder of the chapter is organized as follows. In Section 1.2, shelf space planning is framed within retail operations. Section 1.3 introduces the SSAP in detail focusing on current practices, consumer demand effects and relevant decisions and constraints. The case study of the European Food Retailer that collaborated in this thesis, Sonae MC, is introduced in Section 1.4. Section 1.5 presents the research objectives and methodology, and section 1.6 contains a synopsis of the remaining chapters of this thesis. 1.2. Shelf Space Planning within Retail Operations Getting the right goods to the right places at the right time in the most efficient way requires the coordination and cooperation of thousands of individual decisions in supply chain planning and customer management. Hübner et al. [2013] and Hübner and Kuhn [2012] present comprehensive operations planning frameworks that identify and integrate all relevant retail planning aspects. The objective is to enable practitioners and researchers to classify decisions and realize the interdependencies between them. In this section, shelf space planning is framed within both the supply chain planning and master category frameworks. 1.2.1 Demand and Supply Chain Planning The primary objective of retail is to bridge the gap between the point of production and the point of sale, which stresses the supply chain role in this industry. Both distribution and in-store operations are costly and importantly as the first has a direct impact on the latter. Furthermore, the low value nature of grocery products leads to a higher share of distribution costs compared to manufacturing companies. 1.2. Shelf Space Planning within Retail Operations 3 Hübner et al. [2013] present a retail oriented, consumer-backed demand and supply chain planning matrix based on the supply chain planning framework from Fleischmann et al. [2008] for manufacturing industries. This framework, depicted in Figure 1.1, follows the concept of hierarchical planning and distinguishes the planning problems horizontally along the flow of goods and vertically along the time horizon. The flow of goods is divided into four domains: Procurement, Warehousing, Distribution and Sales; and the time horizon is classified into long-, midand short-term. Long-term planning take strategic decisions concerning the configuration and layout of the entire network; Mid-term master planning deals with the coordination and planning of the operations and promotions for the next 6-12 months and short-term execution planning specifies the activities for the next few days or weeks. The disaggregation of data and results follows the decreasing planning horizon down the hierarchy. Figure 1.1 – Retail demand and supply chain planning framework (Hübner et al. [2013]) The planning modules are linked by vertical and horizontal information flows that identify the interdependencies between the activities. These activities usually belong to different organizational hierarchies and responsibilities which cause some obstacles in their cooperation. Additionally, this framework is embedded between consumer interactions on the sales side and supplier interactions on the procurement side, which affects the entire planning process and requires an integrative approach. Shelf space planning fits within the master category planning module, which frames all the mid-term sales planning tasks of category management. It also has major interactions with other planning activities. The layout and infrastructure of stores are long-term decisions from strategic outlet planning that highly constrain the space available for shelf place planning. Nowadays, retailers have to balance the conflict of an increasing number of products to display versus the limited amount of store space available (Bai [2005]). Despite being a sales-oriented decision, shelf space planning impacts and is impacted by supply chain decisions. Backstage is limited and scarce and shelf space should hold enough inventory until restocking to ensure product availability and avoid the occurrence of stockouts. Therefore, distribution decisions such as shipping frequencies, lead times and 4Chapter 1. Motivation and Overview order sizes have to be properly coordinated with shelf space allocation. At last, all these decisions affect in-store planning, with a high impact on shelf-replenishment operations and personnel planning. 1.2.2 Master Category Planning Master category planning covers the sales planning tasks of category management, divided into four major hierarchical activities: category sales planning, assortment planning, shelf space planning and in-store logistics planning, as proposed by Hübner and Kuhn [2012] (Figure 1.2). Figure 1.2 – Interdependencies between retail problems (Hübner and Kuhn [2012]) Category sales planning start by identifying the set of categories to have in each store type, their role and depth, price position, space share and mid-term demand forecasting. Moreover, it sets the guidelines for subordinated planning problems, to ensure that the categories’ role is always present. From that moment on, categories are planned individually in a shorter planning horizon. Assortment planning involves deciding the products to carry in the stores. Optimizing assortment planning requires the consideration of the consumer demand for the products, including both substitution and complementary demand (substitution demand from non-existing products and complementary demand from related products) (Kök et al. [2009]). On the other hand, shelf space planning assigns and locates the space to the individual products of the assortment, under capacity and restocking constraints. Both assortment and shelf space planning activities are usually accomplished for clusters of stores with similar demand and space patterns. At the end of master category planning, in-store planning includes store personnel planning and store logistics planning. Similarly to the rest of the supply chain, the above decisions differ in their planning horizon, decision owners and IT areas. Ultimately, they also diverge in terms of research domains. The interdependency between the activities is evident. Large assortments drive lower 1.3. The Shelf Space Allocation Problem 5 inventory levels of individual products, which reduce their visibility on the shelves, increase the risk of stockouts and impose frequent replenishment operations, leading to high restocking costs. However, Hübner and Kuhn [2012] alert that those problems are not yet sufficiently integrated. On the one hand, assortment decisions disregard space elasticity effects and to a large extent shelf space constraints too. On the other hand, shelf space allocation assume lost sales and no consumer substitution for non-available products. Furthermore, the shelf inventory is not carefully handled to obtain synergies in replenishment activities. 1.3. The Shelf Space Allocation Problem According to a survey to US retailers (Keltz and Sterneckert [2009]), the main drivers for space planning initiatives rely on the improvement of overall profitability (and overall sales), reduction of the stock levels, improvement of product availability and in delivering a differentiated consumer shopping experience. However, the same survey concludes that the benefits realized are not meeting the expectations. This chapter presents an overview of the shelf space allocation problem and its current challenges. 1.3.1 Current Practices As mentioned above, shelf space planning follows assortment planning and is done separately for each category, in a mid-term planning horizon. It is often called micro-space planning because of its precedence by store space planning (known as macro-space planning, a long-term decision). The increasing number of stores turns impractical individual plans and often lead to store clustering based on demand and space patterns. However, current trends towards customer centricity state that “One plan does not fit all” and defend store-specific space planning. Retailers use planograms to plan the products placement on the shelves. A planogram is an illustration of a category specific part of a store, showing exactly where each product should physically be displayed and how many faces that product should hold. An example of a planogram and its corresponding implementation in a store is present in Figure 1.3. Figure 1.3 – Example of a planogram and its implementation in a supermarket 6Chapter 1. Motivation and Overview Products are usually placed on shelves following merchandising rules which specify associations of products in families that are placed together on the shelves (such as color, brand, type and flavor). These rules try to reproduce the way customers search for the products while shopping and have also in mind the identity of the retailer and its strategy for each category. The complexity of the merchandising rules vary from retailer to retailer but can include more than one level of family types, family sequences, special display locations, among other requirements. In some situations, those rules are defined together with category captains, which are key suppliers with deeper knowledge about each category (for more information about category captains, please consult Kurtulus and Toktay [2009]), or using techniques such as market basket analysis. In Figure 1.4 one can see a planogram where products are organized and highlighted by brand. Note that products are placed in rectangular shapes, one shape for each brand. Figure 1.4 – Planogram with products organized and highlighted by brand Generating planograms is a highly time consuming activity - the industry standard for manually creating a single planogram is three hours (JDA [2009]). Therefore, adequate Information Technology (IT) systems are essential. Despite this, 30% of the retailers did not use any kind of IT support in 2009, and only 36% had up-to-date technology, as seen in Figure 1.5. This reality is changing as retailers are realizing the benefits of space planning. Current commercial IT solutions are similar in their purpose and scope and focus on simplicity, allowing for realistic views of the shelves, the ability to quickly handle products and providing different data and powerful analysis reporting. Those systems already incorporate tools for the automatic generation of planograms based on simple heuristics such as proportional-to-market share or proportional-to-profit share and require a significant tunning effort for additional requirements. Among the space planning solutions currently on the market the top three vendors are: Spaceman suite (AC Nielsen) and Space planning (JDA), with over 2000 users each, and Apollo professional (MEMRB/IRI), with over 800 users (Hübner and Kuhn [2012]). Nevertheless, today’s commercial IT solutions for space planning have been essentially used for visual and handling purposes, and the planograms are still generated with significant human interaction. As a matter of fact, many authors argue that no “real” optimization takes places due to the limited or non existing use of mathematical optimization and consumer demand effects (Irion et al. [2011], Hansen et al. [2010], Hübner and Kuhn [2012], 1.3. The Shelf Space Allocation Problem 7 Drèze et al. [1994], Desmet and Renaudin [1998]). As a result, automatically generated planograms are most likely to receive significant manual adjustments by the end users. No IT support 30% Planned major upgrade 13% Started major upgrade 21% Up-to-date technology 36% Figure 1.5 – Status of retailers IT usage for shelf space planning (Hübner and Kuhn [2012]) 1.3.2 Consumer Demand Effects Most shoppers enter the store with only a general idea of what to purchase, becoming susceptible to in-store marketing. Additionally, reduced assortments and stockouts force consumers to search for substitution products, highlighting the role of space management. The low level of involvement that customers have with in-store decisions, often made quickly and with only a minimal search, reinforces the importance of in-store marketing. Experimental studies have consistently proven the positive effect of space on the demand of the products. These studies point to three main elasticities: space elasticity measures the increasing responsiveness of sales as more space is allocated to a product, experiencing declined marginal returns at some point - see Fgure 1.6 (Curhan [1972], Chandon et al. [2009]); location elasticity highlights key display locations that bring a better exposure, such as the eyeor hand-level (Drèze et al. [1994]); lastly, cross elasticity measures the interdependency between adjacent products and is assumed to be positive for complementary products and negative for substitute products (Corstjens and Doyle [1981]). Additionally, the way products are arranged on the shelves can also have an important role on gaining the consumers’ attention. Thus, carefully organizing them in families can increase interest, while disorganized or excessive complexity (i.e. variations in the basic visual content) damages the buying experience (Pieters et al. [2010]). We call to this effect design complexity. 1.3.3 Problem Definition Shelf Space Allocation is the scientific name for the problem of distributing the scarce shelf space of a retail store among a set of products of a category. The definition of the problem may vary depending on the retail segment, company’s strategy, relation with vendors, store layout, among others. This section will define the problem as generic as possible, considering food retail environments. 8Chapter 1. Motivation and Overview Figure 1.6 – Sales rate in function of shelf space for a single product (Abbott and Palekar [2008]) To start with, there is the need to review some concepts related to shelf space allocation, some of them already mentioned before. A Stock-Keeping Unit (SKU) is a unique identifier for each distinct product that can be purchased. Each SKU belongs to a supplier, is part of a brand, and contains a set of other attributes, such as colour, size and packaging, that distinguishes it from all other products. We call to these attributes family types. A family is a set of products sharing the same value for a given attribute. The highest organizational structure of products are categories. Usually in a planogram all SKUs belong to the same category. A retailer usually displays a limited part of the inventory of a SKU on the shelves, leaving the rest in the backroom. The visible stock of each product can be characterized by the number of facings wide, high and deep, as depicted in Figure 1.7. The number of facings wide is most commonly known as the facings of the product. The way each product is placed on the shelves defines its orientation: front, back, top or side. The days-supply value of a product measures the number of demand days covered by its shelf stock until the need for replenishment. 2 Facings High 2 Facings Wide 3 Facings Deep Figure 1.7 – Facings wide, high and deep of a product (front view on the left and side view on the right) 1.3. The Shelf Space Allocation Problem 9 Fixtures are located in segments that are placed end-to-end (i.e. horizontally stacked against each other) to form the aisles of the stores. Each segment has its own shelf placement. Shelves can be aligned with the shelves of the other segments, forming continuous long shelves from the beginning to the end of the aisle or they can be placed differently, forming misalignments that need to be taken into consideration while placing the products. Whenever a planogram has misalignments between the shelves we refer to it as irregular planogram, as opposed to regular planogram. Figure 1.8 presents an irregular planogram with 3 segments. Figure 1.8 – Example of an irregular planogram Shelf space planning may involve other fixtures than shelves, such as chests, pallets and pegboards. Chests are enclosed spaces for storing non-organized products and pegboards are bars with steel rods sticking out to hold peggable products like shewing gums. Nevertheless, these fixtures are out of the scope of this thesis. Objectives The aim of the SSAP is usually to obtain the maximum profit or sales out of the available space, considering consumer demand in function of the space allocated to the products. Section 1.3.2 presented a brief overview of the most commonly considered consumer demand effects: space-, locationand cross-elasticities. Some authors also include a cost reduction approach, with a higher emphasis in inventory management. However, Bai [2005] points out that if the products’ demand is dependent on the space, a cost-minimization objective may not be appropriate as it may reduce the number of product facings which is against the intent of the problem. Decisions The most common SSAP decisions are the number of facings (wide) for the products and their placement on the shelves. The problem is usually seen in a 2D fashion because the items placed behind each facing cannot be seen directly and hence do not have an impact on 10 Chapter 1. Motivation and Overview consumer demand (inventory requirements can be considered by determining the number of items behind each facing). The fixtures location is frequently given as input to the model because retailers are not likely to change the layout of the shelves during products reallocation. However, it is also possible to consider the shelf location as a decision. Several approaches also integrate other non-space decisions that have an impact on consumer demand, including assortment, replenishment, promotions and advertising. Constraints There are several potential constraints for the SSAP, ranging from hard to soft, depending on the need to entirely satisfy these requirements. A list of the most commonly considered constrains is presented below, organized from the hardest to the softest. •Integrality Constraints - the space allocated to a product on each shelf should be an integral number of times the size of that product; •Physical Constraints - The total shelf space available cannot be exceeded. Physical constraints can be one or two dimensional, whether they consider height constraints. Nevertheless, these are often ignored when the vertical location of the shelves can be readjusted at the end. •Control Constraints - Many retailers set lower and upper bounds to the number of facings to ensure that a minimum and a maximum exposure is given to the products. Other bounds can result from special contracts with important suppliers, with the power to influence the location and shelf space of their products. These contracts usually set minimum space shares for brands. Retailers may also try to maintain a minimum and maximum number of days-supply for each product, in order to control stockouts, inventory costs and replenishment costs. •Family Constraints - Merchandising rules identify families of products that should be placed together on the shelves, preferably in rectangular shapes. These rules may also specify predefined family sequences and shapes orientation. Most part of the complexity in the SSAP comes from the inclusion of the space effects on the demand function, which are hard to estimate and non-linear by nature. The literature presents a great variety of models which incorporate different estimates of (some of) those effects. These models also differ in the level of detail of the decisions, ranging from facings calculation to almost complete planogram descriptions. As a consequence, there is no definitive shelf space allocation model. Moreover, models that can be adapted to reality are particularly difficult to find either because of their simplicity and lack of key practical features, or due to their complexity and expensive estimation requirements for parameters. One important practical limitation is that most models disregard that product allocation must follow merchandising rules which specify associations of products on the shelves. Finding the best products allocation from the set of all possible arrangements of products is clearly a combinatorial problem. From a simplistic point of view, it consists in 1.4. Case Study Presentation 11 placing a set of small items (products) into a set of large objects (fixtures). Therefore, it can be related to the literature of Cutting and Packing Problems. More specifically, the SSAP can be considered a extension of a placement type of problem, according to the Wäscher’s improved typology of Cutting and Packing Problems Wäscher et al. [2007]. In this paper, Placement Problems are described in the following way: “ (...) a weakly heterogeneous assortment of small items has to be assigned to a given limited set of large objects. The value or the total size (as an auxiliary objective) of the accommodated small items has to be maximized (...) ” The simplest form of the Placement Problem, with one large object, is already NPhard. The SSAP further extends Placement Problems by integrating the effect of space variables on the products’ demand. Several practical constraints are additionally added to the problem. 1.4. Case Study Presentation This thesis had the collaboration of Sonae MC with whom we carried out a project aiming at developing a tool for the automatic generation of planograms, where we integrated and validated the main outcomes of this thesis. Sonae MC operates a food retail business in Portugal and is one of the biggest Portuguese companies (ranked the 4th in 2014, with 3.33 billion annual sales). Its brand Continente is the country food retail market leader, with a network of 478 stores (and additionally 162 stores under franchising) covering the entire country, with three major formats: convenience stores (Continente Bom dia), supermarkets (Continente Modelo), and hypermarkets (Continente). Sonae MC has a centralized operations management activity, responsible for planning all the operations for the stores nationwide. The space planning department is engaged with managing the space available at the stores, an activity that comprises two main levels: a macro-space planning level that defines, on a long-term basis, the layout of the stores; and a micro- (or shelf-) space planning level that defines, for each category, the products’ placement on the shelves. Shelf space plans are updated with an average rate of 2 to 3 times a year for more than 300 categories. This activity fully occupies 23 space managers that generate an average of 60,000 planograms each year. Similarly to other retailers, shelf space is managed on a cluster based approach. Space managers start by creating generic shelf space plans that fit the average sales of each cluster of stores. Once validated with category managers to check its consistency with the category strategy, these generic plans are then replicated for all the stores of the clusters, by adjusting the product facings to each store, while keeping the same allocation rules. Figure 1.9 summarizes this shelf space planning process. Sonae MC uses a space planning software from one of the top three vendors, the JDA Software Group, Inc. Although automatic tools for planogram generation are available in JDA software, these tools do not accommodate all the intrinsic complexity of 18 Chapter 2. From a Literature Review to a Classification Framework for Shelf Space Allocation Problems by nature. The literature presents a great variety of models which incorporate different estimates of some of those effects. Models also differ in the level of detail of the decisions, ranging from rough space estimations to almost complete shelf space descriptions. Moreover, shelf space problems may also differ from company to company, depending on strategies, managerial style, categories of products, retailer-supplier relationships, among others. Additionally, the SSAP is usually addressed together with other related retail problems that integrate other sales’ elasticities, further increasing the complexity of the demand functions. As a consequence, there is no unique shelf space allocation model and no instance benchmarks set are available. In this paper, a literature review of the shelf space allocation models is made. The SSAP has long ago been addressed by marketing professionals and researchers, with the first studies tracing back to the 1970s. This stream of research has been growing ever since without any work systematizing published research. The only exception comes from Hübner and Kuhn [2012] in 2011 that presented an overview of the state-of-the-art research and software applications in retail category management, which includes shelf space management. Nevertheless, the vast scope of the paper did not allow a deep analysis of shelf space allocation problems. Figure 2.1 shows the increasing number of publications between 1970 and 2015, with a total of 43 papers. We highlight the decade of 2000, when the number of published works sharply increased to the double, and also the projection for the current decade that anticipates a sustained growth. The European Journal of Operational Research has been the major journal for the presentation of new developments in this field (with 9 published articles). Other journals such as the Journal of Retailing (6 articles) and the Journal of Operational Research Society (5 articles) have also presented significant contributions. These publications focused both on experimentally measuring the effects of shelf space allocation on the products’ demand and on building decision models and optimization algorithms. 34 7 16 26 0 5 10 15 20 25 30 1970 1980 1990 2000 2010 NUMBER OF PUBLICATIONS (TOTAL OF 43) YEAR OF PUBLICATION (IN DECADES) Figure 2.1 – The evolution of the publication activity on Shelf Space Allocation (the last decade is projected based on the data available for the period 2010-2015) Despite the recent progresses that this research area has been experiencing, Bai [2005] and Hübner and Kuhn [2012] state a misalignment in shelf space management between 2.2. Shelf Space Allocation Problem 19 existing commercial software applications and research agenda. Software vendors focus mainly on the development of applications with large-scale data processing technologies, with limited or no use of mathematical optimization and disregarding the space effects on consumer demand. As a consequence, these applications require significant human interaction and are essentially used for visual and handling purposes. State-of-the-art optimization methods, on the other hand, have practical limitations, either because of their simplicity and lack of key features, or due to their complexity and expensive parameter estimation requirements. Therefore, many challenges still exist and the SSAP is still an open problem. With this literature review we intent to stimulate further research and boost more practical approaches to the problem. For that purpose, the remainder of the review is organized as follows. In Section 2.2 we present the problem and identify the basic features that models must capture to support decision making. Section 2.3 reviews the existing literature of the SSAP focusing on mathematical models with an emphasis in 3 main building blocks: decisions, demand and cost functions, and problem constraints. We also analyze the integration of the problem with other interdependent decisions and identify the main areas of application. Section 2.4 introduces a classification framework that systematizes the different types of approaches. Based on this framework, section 2.5 draws the final conclusions and disagnoses existing gaps in order to identify promising future research lines. 2.2. Shelf Space Allocation Problem Space management comprises two hierarchical levels. A store (macro) level, deciding the space for product categories, and a product category (micro) level, which allocates individual products within each category. The SSAP is usually connected with the micro level and considers the allocation of a category of products onto the shelves to which it has been previously assigned. The traditional space planning tool is a planogram, representing an illustration of a specific part of a store, showing exactly where each product should physically be displayed and how much space that product should have. Figure 2.2 presents an example of a planogram where we can see the number of different decisions that must be taken to create a full planogram. The shelf stock of each product can be characterized by the number of facings wide, high and deep. The number of facings wide is most commonly known as the product’s facings (as often the remaining decisions are not tackled) and is the key space decision. The location of each product is defined by the shelf allocated to the product and its placement within the shelf. Other decisions include the products’ orientation that specify the way products are displayed on shelves: front, back, top or sideway. Product Ain Figure 2.2 has 2 facings wide, 3 facings high and 4 facings deep. It is located in the first shelf of the planogram in the first position (0 cm measured from the lower-left corner). The aim of the SSAP is to maximize the outcome obtained from the available retail space. The problem focuses on demand and in the center of the problem there is the objective of maximizing the profit obtained with consumer demand, which in turn depends on the space allocated to the products. This problem has also a cost side and besides the 20 Chapter 2. From a Literature Review to a Classification Framework for Shelf Space Allocation Problems 3 Facings High 2 Facings Wide 4 Facings Deep A A Figure 2.2 – Example of a planogram (front view on the left and side view on the right) product costs, it sometimes considers operation costs originated by replenishment, holding and ordering activities. There are several potential constraints for the SSAP, ranging from hard to soft, depending on the need to entirely satisfy these requirements. Besides the integrality and capacity constraints, typical of placement problems, Control constraints for lower and upper bounds may also be set for the products. Lower bounds are defined when the retailer wants to maintain a minimum number of facings of all products or because of new products which need a chance to make an impact. Upper bounds are set for products at a later stage of the life cycle, or for sales’ champions, when the retailer wants to leave space for refreshing the product assortment of the stores. Availability constraints also limit products’ sales by a production or availability limit. On top of the previous requirements, many companies also define merchandising rules that identify families of products that should be placed together on the shelves, preferably in rectangular shapes. For example, the products of the planogram in Figure 2.2 are grouped into 3 rectangular-shaped families. These are called product grouping constraints. Merchandising rules may also specify other company-specific requirements such as family sequences, shapes’ orientation (either columns or lines), special locations for special products, among others. Merchandising rules try to reproduce the way customers search for the products while shopping and are obtained with the help of category captains (key suppliers with deeper knowledge about each category - Kurtulus and Toktay [2009]) and techniques such as market basket analysis. Shelf space allocation has a close interaction with other related retail problems, such as assortment planning, inventory management and shelf replenishment operations. When planning stores’ assortment, retailers have to carefully consider the effect of carrying large assortments due to the space limitations. Increasing the assortment reduces the visibility of the products on the shelves and drive lower inventory levels, which leverages the risk of stockouts and imposes frequent replenishment operations. On the other hand, not carrying some products in the assortment may generate lost-demand from loyal costumers. Therefore, a careful alignment is needed between space, assortment and inventory levels. Moreover, retailers only display a limited amount of the inventory on the shelves, storing the 2.2. Shelf Space Allocation Problem 21 remaining products in the backroom. Hence, the alignment between shelf replenishment operations and shelf space allocation is also vital to avoid stockouts and design efficient shelf space plans. Nonetheless, most part of the complexity in the SSAP comes from the inclusion of the space effects on the demand function. We will now review the key space effects that were studied in the literature and that are usually present in the demand functions. 2.2.1 Space Effects on Consumer Demand Marketing studies have proven the positive influence of shelf space in stimulating consumer demand and identified three main types of product elasticities that should be incorporated into the demand functions to represent the consumers’ behavior: space elasticity, location elasticity and cross elasticity. Space Elasticity was originally defined by Curhan [1972] as “the ratio of relative change in unit sales to relative change in shelf space”. Experiments have concluded that products’ demand increases as more space is allocated to them. However, the increasing rate slows down until a steady point, resembling an “S” shape. An average increasing rate of 20% was reported by Curhan [1972] and 9% by Corstjens and Doyle [1981]. These values are only an indication, as the space elasticity strongly differs with the products category and shelves features. Location Elasticity measures the impact of the vertical and horizontal location on the demand of the products. Studies show a higher impact of products located on the topand middleshelf positions (at eye and hand level) and at the beginning of the aisles, with the vertical effects dominating the horizontal ones (Chandon et al. [2009]). Drèze et al. [1994] reported an average of 39% and 15% sales’ increase from the worst to the best vertical and horizontal position, respectively. Cross Elasticity was introduced by Corstjens and Doyle [1981] to evaluate the interdependency between two different products. Ranging between [-1,1] cross elasticities are considered to be positive for complementary products and negative for substitution products. Drèze et al. [1994] experienced a boost of sales of above 5% in complementary merchandising. However, most retailers reveal the difficulty to attain a real estimation of such values, due to the complicated merchandizing relationships between products and the quantity of data required. Additionally, the way products are arranged on the shelves can also have an important role on gaining the consumers’ attention, which we call here the Design Complexity effect. Pieters et al. [2010] show that carefully organizing a display in families increases the viewers’ attention but its excessive complexity (i.e. variations in the basic visual content) can indeed decrease their interest. As a result, products are organized in families in rectangular shapes (Geismar et al. [2014], Russell and Urban [2010]). The need to follow structured shapes is sometimes further stressed by assuming a direction for the shapes, either vertical or horizontal (forming straight columns or straight lines). To the best of our knowledge, the impact of this latter effect on demand has never been studied or included in any model. Due to the high testing costs, experiments have not been sufficiently extensive, with most of them dating from the 1960s and 1970s. In addition, some results are contradictory, 22 Chapter 2. From a Literature Review to a Classification Framework for Shelf Space Allocation Problems with few conclusions that can be generalized. As an example, while Chandon et al. [2009] reveal that the variation in the number of facings is the most significant in-store factor, Drèze et al. [1994] state that location has a larger impact, as long as a minimum inventory is maintained to avoid stockouts. 2.3. Shelf Space Allocation Review As aforementioned, the demand estimation is at the center of the problem and products are to be organized having in mind the effect of space in their demand. Nevertheless, (1) the types of decisions, (2) the space effects considered, (3) the way the demand and cost functions are estimated and (4) the problem constraints vary considerably from one approach to the other, which creates a high level of inconsistency in this field. This section reviews the literature of SSAP focusing on the existing mathematical formulations. The review mainly tackles the four topics just mentioned (1)-(4) plus an additional topic that analysis the instances used in the publications. Hereafter consider the following notation: Nproducts, indexed by i,j∈ N are to be placed on Kshelves, indexed by k∈ M. Products and shelves features are described below, the remaining parameters are introduced as required. aiwidth of product i, li(ui) lower bound (upper bound) on the number of facings of product i, piunitary profit of product i, ciunitary cost of product i, Wtotal capacity of the planogram, wkwidth of shelf k, hkvertical location of shelf k. 2.3.1 Space Decisions Space allocation models generally consider 3 different decisions: the space occupied by each product, often measured by the number of facings (Space), the allocation of products to the shelves (Allocation) and the location of the products on each shelf (Location). The following 3 variables are associated with these decisions: Withe space allocated to product i∈ N, either measured in facings or linear space, Yik =1 weather product i∈ N in allocated to shelf k∈ M or not, Xik the continuous horizontal location of product i∈ N in shelf k∈ M (measured from the most left point of the shelf). Table 2.1 shows the publications that consider each of the 3 decisions mentioned above. Note that the existing mathematical models focus specially on determining the space for the products. The reason behind this emphasis lies in the fact that most authors consider 2.3. Shelf Space Allocation Review 23 space elasticity as the most important effect, with a higher impact on demand than the remaining elasticities. The table also shows that only 4 publications consider location decisions. Nevertheless, if location decisions are disregarded, solutions do not translate into a complete description of a planogram. Table 2.1 – Shelf space decisions Decisions References Space n Facings Anderson and Amato [1974], Hansen and Heinsbroek [1979], Anderson [1979], Corstjens and Doyle [1981], Corstjens and Doyle [1983], Zufryden [1986], Bultez et al. [1989],Preston and Mercer [1990], Borin et al. [1994], Drèze et al. [1994], Brown and Lee [1996], Urban [1998], Yang and Chen [1999], Yang [2001], Urban [2002], Lim et al. [2004], Bai [2005], Hwang et al. [2005], Reyes and Frazier [2005], Maiti and Maiti [2006], Hariga et al. [2007], Reyes and Frazier [2007], Bai and Kendall [2008], van Nierop et al. [2008], Abbott and Palekar [2008], Hwang et al. [2009], Ranaseshan et al. [2009], Raut et al. [2009], Gajjar and Adil [2010], Hansen et al. [2010], Murray et al. [2010], Russell and Urban [2010], Irion et al. [2011], Lotfi et al. [2011], Gajjar and Adil [2011a], Gajjar and Adil [2011a], Lotfi and Torabi [2011], Hübner and Kuhn [2011], Irion et al. [2012], Geismar et al. [2014] Allocation Shelf k Drèze et al. [1994], Yang and Chen [1999], Yang [2001], Lim et al. [2004], Bai [2005], Hwang et al. [2005], Hariga et al. [2007], van Nierop et al. [2008], Hwang et al. [2009], Raut et al. [2009], Gajjar and Adil [2010], Hansen et al. [2010], Murray et al. [2010], Russell and Urban [2010], Gajjar and Adil [2011a], Gajjar and Adil [2011a], Lotfi and Torabi [2011], Geismar et al. [2014] Location Shelf k x van Nierop et al. [2008], Hwang et al. [2009], Hansen et al. [2010], Raut et al. [2009], Russell and Urban [2010] The variables defined before construct the problem in a 2D fashion. Such an approach is based on the fact that items placed behind each facing cannot be seen directly and hence do not have an impact on consumer demand. As a result, it is not also common to see other type of space-related decisions such as the number of facings high and deep, and products’ orientation. Moreover, products tend to have a preferred orientation, specified by the suppliers. Nonetheless, as these quantities impact inventory related decisions recent works (see Ranaseshan et al. [2009] and Murray et al. [2010]) are starting to consider 3D space-related decisions. Due to the large number of products within categories, some authors also argue that it is not practical to optimize shelf space plans having in mind all products. As a result, the decisions are sometimes aggregated and tackled at the brand level (or subcategory level). All the above decisions are product-related but planograms also have shelves whose location needs to be determined. The shelf-related decisions are usually given as input to the models because retailers are not likely to change the layout of the shelves during products reallocation. However, some authors consider the shelf height as a decision: Hwang et al. [2009] and Coskun [2012] are two examples. To the best of our knowledge, the determination of the number of shelves to place on planograms has never been tackled. Several approaches also integrate other non-space decisions that have an impact on 24 Chapter 2. From a Literature Review to a Classification Framework for Shelf Space Allocation Problems consumer demand, with an emphasis on assortment and inventory management. Other variables such as promotions, advertising and pricing also appear in some formulations but these decisions are most of the times considered as fixed (i.e. decided beforehand) and only affect the demand function. The investigation of these related problems is considered beyond the scope of this paper. 2.3.2 Demand and Cost Estimation The objective functions have usually three main components: the profit obtained with the sales of the products, which depend on the demand di, subtracted by purchasing costs ci and other estimated costs oi, as identified in equation 2.1. The complexity of the shelf space formulation relies on the demand and cost estimations which will be analyzed next. P=X i∈N (pi·di−ci·di−oi) (2.1) Demand Estimation The literature has a great variety of demand functions which incorporate different elasticities’ estimates, as well as different ways of aggregating these effects. Moreover, many proposed functions tend to focus on particular effects while disregarding the others. Table 2.2 presents the characteristics that each publication has considered for the demand estimates. We distinguish between the space related elasticities (space-, cross-, vertical locationand horizontal location-), other demand effects that were also taken into consideration, and two different types of aggregation: additive and multiplicative. The consideration of the space elasticity is common to all approaches and this effect is frequently aggregated with other elasticities using a multiplicative form. Cross and vertical location elasticities are also frequently considered but only five approaches aggregate both effects. The horizontal dimension is often disregarded. Despite the existence of many demand estimates, this field presents some key demandfunctions that are almost consensual and used across multiple publications. Next, we review the most important ones. One of the first and most important demand functions in shelf-space allocation literature was introduced by Corstjens and Doyle [1981], which influenced most future research. They formulated the problem in a non-linear multiplicative form and included spaceand crosselasticities. The demand of product iwas formulated as: di=αi·Wβi i·Y j∈N:j,i Wδi j j(2.2) where Wiis defined in terms of (linear) space allocated to product i,αiis a scaling constant identified as the base demand for the product (demand with one facing), βiis the space elasticity expressed as a power function and δi j is the cross-elasticity between products iand j. Note that δi j can be positive or negative depending upon whether iand j are complementary or substitute of each other, and that δi j, is not necessarily equal to δji. 2.3. Shelf Space Allocation Review 25 Table 2.2 – Consumer demand effects in demand estimation Reference SE CE LE Other EA V H A M Anderson and Amato [1974] L out-of-assortment substitution • Hansen and Heinsbroek [1979] P Anderson [1979] P Corstjens and Doyle [1981] P • • Corstjens and Doyle [1983] P • • Zufryden [1986] P Bultez et al. [1989] P • • Preston and Mercer [1990] P Borin et al. [1994] P •Stockout and out-of-assortment substitution • Drèze et al. [1994] P • • Brown and Lee [1996] P • • Urban [1998] P • • Yang and Chen [1999] P • • • Yang [2001] L • Lim et al. [2004] L • • Bai [2005] P Hwang et al. [2005] P • • Inventory level • Reyes and Frazier [2005] L • • Maiti and Maiti [2006] P •Inventory level and price elasticity • Hariga et al. [2007] P • • Inventory level • Reyes and Frazier [2007] P Price elasticity • Bai and Kendall [2008] P Inventory level and decay (freshness) • van Nierop et al. [2008] P • • • Abbott and Palekar [2008] L • • Hwang et al. [2009] P • • • • Ranaseshan et al. [2009] P • • Raut et al. [2009] L • • • Gajjar and Adil [2010] P Hansen et al. [2010] L • • • • Murray et al. [2010] P •Ownand cross-price elasticity • Russell and Urban [2010] P • • • Gajjar and Adil [2011a] L • Gajjar and Adil [2011b] P Irion et al. [2011] P • • Lotfi and Torabi [2011] P • • Lotfi et al. [2011] P Ownand cross-price elasticity • Hübner and Kuhn [2011] P •Out of assortment substitution • Irion et al. [2012] P • • Geismar et al. [2014] L • SE - Space Elasticity (L - Linear and P - Polynomial), CE - Cross Elasticity, LE - Location Elasticity (V - Vertical and H - Horizontal), EA - Effects Aggregation (A - Additive and M - Multiplicative) 26 Chapter 2. From a Literature Review to a Classification Framework for Shelf Space Allocation Problems This demand formulation uses polynomial terms to model the decreasing demand rate as the number of facings increases. These polynomial forms were widely used by other authors who extended this formulation in many different ways. Urban [1998] stated that the unit of measure of the products, Wi, could also be in terms of facings, as long as all parameters reflect the appropriate measure, and many following formulations used facings instead. Yang and Chen [1999] additionally integrated the location effect of a product, by using variables Wik instead, and considering different parameter values depending on the shelf k. They also included additional marketing variables. Hwang et al. [2005] assumed an average location effect in case the same product is displayed on different shelves at the same time. Corstjens and Doyle [1983] and Raut et al. [2009] included the time dimension and assumed that past demand influences current period demand, and Gajjar and Adil [2010] and Irion et al. [2012] presented piecewise linearization approaches for this formulation. Nevertheless, Bai [2005] argues that the polynomial form is intrinsic linear as it can be easily transformed to a linear function by a logarithmic transformation and the parameters can then be estimated by a simple linear regression. To the best of our knowledge there is not any paper with such approach though. At last, Borin et al. [1994] and Urban [1998] extended the original function by considering the demand coming from the consumers which are willing to purchase a replacing product if their preferred product is not included in the assortment or is temporarily stockout. For that porpuse, consider products l∈ N−which are not present on the shelves. The demand function becomes: di=αi·Wβi iY j∈N:j,i Wδi j j         1+X l∈N− (1−Θl)·f(αl,δli)        (2.3) where Θlis the resistance to compromise and fis a function that represents the distribution of demand amongst the displayed products. Due to the highly non-linear nature of the space elasticities, all the models that include these effects are complex and generally hard to solve. Yang and Chen [1999] proposed a simplified and yet practical alternative model in the form of a linear multi-knapsack problem that started a new trend in SSAP. The authors state that in practice it is difficult to obtain an estimation for the sales volume elasticity and make the assumption that the profit of any product is linear with regard to a range of facings, if it is kept in a controlled range defined by proper upper and lower bounds. Those bounds are to be determined by the management according to the policy of the store. They propose a formulation that maximizes the benefit of including items (additional facings) in a set of knapsacks (each shelf is a knapsack) while not exceeding the knapsack capacity. The resulting objective function is the following: P=X i∈N X k∈M pik ·Wik (2.4) where pik is the per-facing profit of product ion shelf k. By associating the shelf space allocation problem to a knapsack problem, the authors also proved that even a simplified version of the problem is NP-hard. Nevertheless, its simplicity was criticized by several 2.3. Shelf Space Allocation Review 27 authors because it contradicted previous experiments revealing an S-shaped curve for the effects of space elasticity. Other authors, such as Lim et al. [2004], further defended the linearity assumption stating that retailers prefer to operate on the linear portion of the Sshaped curve of marginal returns. This simplified version has been used by several authors to develop efficient heuristics and matheuristics for the problem. The discrete nature of the aforementioned models disregards the exact location of the products and assigns the same effect regardless of the product’s location on a particular shelf. Hansen et al. [2010] and Russell and Urban [2010] considered location decisions and proposed (quasi) horizontal effects on the demand function that we will review now. Hansen et al. [2010] extended the simplified version of Yang and Chen [1999] and presented a formulation where the variables were discretized to consider the horizontal location of the products on the shelves. The authors divided the shelf in multiple horizontal segments and defined the binary decision variables Wjkh f as the decision of allocating product ion shelf kstarting at horizontal segment hfor face-length f. The resulting objective function is as follows: P=X i∈N X k∈M Tk X h=1 ui X f=1 pikh f ·Wikh f +X i∈N X j∈N Vi j 2·ei j (2.5) where pikh f is the profit of product iassociated with Wjkh f . A non-linear profit function is considered, with a decreasing demand rate as the number of facings increase. However, the non-linearity is absorbed by parameter pikh f , as it depends on the number of facings assigned to each product. The second part of the objective function is a linearization of the cross-elasticity effect. The authors defined parameters ei j as the unitary incremental profit or loss due to cross-elasticity effects between products iand j, which is multiplied by min(bi,bj), where biand bjare the total lengths of products iand jon the shelf. The function is linearized by introducing variables Vi j =min(bi,bj). Russell and Urban [2010] introduced the first formulation with continuous horizontal locations for the products. They based their demand function on a previous work by Drèze et al. [1994] who noted that sales tend to be quadratic in the horizontal dimension and cubic in the vertical one. As for space elasticity, the authors chose to use a quadratic formulation, not only for consistency and tractability, but also because it reflects diminishing returns. The expected demand for each product iis then expressed by: di=β0i+β1i·Xi+β2i·X2 i+ X k hβ3i·(hk·Yik)+β4i·(hk·Yik)2+β5i·(hk·Yik)3+β6i·Wik +β7i·W2 iki(2.6) where β•iare appropriate coefficients for the specific implementation. Since Yik is a binary variable, the demand formulation is expressed as a quadratic function. 34 Chapter 2. From a Literature Review to a Classification Framework for Shelf Space Allocation Problems deeper analysis on inventory-related concerns with a focus on replenishment synergies. Both problems are highly interdependent as shelf replenishment operations have expensive handling costs and are limited to the shelf merchandisers available to immediately fill the shelves after stockout. The inclusion of the concept of target service level would be an interesting approach. Alignment of software applications with science – Besides the need for efficient algorithms able to cope with high number of products, the expensive estimation requirements for parameters is also a major barrier for a better alignment between science and software applications. Nevertheless, there are other ways of improving the use of shelf space theory in practice. One example is to study the creation of shelf space solutions taking into account the current planogram implemented in the stores in order to trade-offpotential profit and the costs of changes, namely, handling costs. Appendix 2.A Problem Instances Table This section presents the details of the data sets discussed in this review, in section 2.3.4. We identify the following information: instance type (randomly generated or real-world), solution method (heuristic or exact method), instance size and motivation. 2.A. Problem Instances Table 35 Table 2.4 – Problem Instances Reference Data Method Instances G R Size Motivation Anderson and Amato [1974]•H 4 brands Illustrative example Hansen and Heinsbroek [1979]•H 6443 products Based on a LOEB-IGA study Corstjens and Doyle [1981]•E 5 product categories Quality candy, ice cream and greeting cards with 140 stores Corstjens and Doyle [1983]•E 4 product groups Illustrative example Zufryden [1986]•E up to 40 products Bultez et al. [1989]•H 20 products Canned dog food (Belgium retailer) Drèze et al. [1994]•Eaverage size 115 products Analgesics, Bottled Juices, Canned Seafood, Canned Soup, (27 min. and 235 max.) Oral Care, Refrigerated Juices (US supermarket - 60 stores) Borin et al. [1994], • • H6 products (generated), Ketchup (local supermarket) Borin and Farris [1995] 18 products (field study) Brown and Lee [1996]•E one instance with 2 product categories Juice (US grocery stores) Urban [1998]•H up to 54 products Based on Borin et al. [1994] Yang [2001]•H up to 10 products, 4 shelves Urban [2002]•H 6 products Based on Borin et al. [1994] Lim et al. [2004]•H up to 100 products and 30 shelves Bai [2005]•H up to 100 products and 40 shelves Hwang et al. [2005]•H 4 products and 6 shelves Reyes and Frazier [2005]•E 6 products Maiti and Maiti [2006]•H up to 5 products Hariga et al. [2007]•E 4 products and 4 display areas Reyes and Frazier [2007]•E 4 products Random but based on real world data collected from a US grocery store Bai and Kendall [2008]•H up to 64 products Small instances based on Borin et al. [1994] and generated large instances. van Nierop et al. [2008]•H 81 products and 5 shelves Canned Soup from Drèze et al. [1994]. Hwang et al. [2009]•E/H 4 products Ranaseshan et al. [2009]•H 6, 10 and 14 products Generated from a category of size 300 of Baked Beans and Noodles. Data collected from a medium size national grocery retailer. Raut et al. [2009]•E/H 6 screens /6 products, 5 weeks Exhibitors movie allocation problem in a multiplex. Gajjar and Adil [2010], Gajjar and Adil [2011a], •H up to 200 products and 50 shelves Gajjar and Adil [2011b] E up to 10 products and 2 shelves Hansen et al. [2010]• • H up to 100 products and 10 shelves (generated) Health and beauty H 67 products and 7 shelves (case study) Murray et al. [2010]•E up to 100 products (3 orientations) and 10 shelves Russell and Urban [2010]•E 10 products, 5 families, 4 shelves Distilled-spirits H 103 products, 36 families, 25 shelves Irion et al. [2011]•E 9 categories Home improvement-product retailer Lotfi and Torabi [2011]•E up to 20 products H up to 80 products Lotfi et al. [2011]•E 4 products Hübner and Kuhn [2012]•E up to 250 products Irion et al. [2012]• • E up to 50 products Home improvement-product retailer Geismar et al. [2014]•H 200 and 500 products Motivated by a case study in a blockbuster store Data: G - Generated and R - Real, Method: H - Heuristic and E - Exact 36 Bibliography Bibliography H. Abbott and U. S. Palekar. Retail replenishment models with display-space elastic demand. European Journal of Operational Research, 186(2):586–607, 2008. E. E. Anderson. An Analysis of Retail Display Space: Theory and Methods. Journal of Business, 52(1), 1979. E. E. Anderson and H. N. Amato. A mathematical model for simultaneously determining the optimal brand-collection and display-area allocation. Operations Research, 22(1): 13–21, 1974. R. Bai. An Investigation of Novel Approaches For Optimising Retail Shelf Space Allocation. PhD Thesis. The University of Nottingham, 2005. R. Bai and G. Kendall. A model for fresh produce shelf-space allocation and inventory management with freshness-condition-dependent demand. INFORMS Journal on Computing, 20(1):78–85, 2008. N. Borin and P. Farris. A sensitivity analysis of retailer shelf management models. Journal of Retailing, 71(2):153 – 171, 1995. N. Borin, P. W. Farris, and J. R. Freeland. A Model for Determining Retail Product Category Assortment and Shelf Space Allocation. Decision Sciences, 25(3):359–384, 1994. M. G. Brown and J.-Y. Lee. Allocation of shelf space: A case study of refrigerated juice products in grocery stores. Agribusiness, 12(2):113–121, 1996. A. Bultez, P. Naert, E. Gijsbrechts, and P. Vanden Abeele. Asymmetric cannibalism in retail assortments. Journal of Retailing, 65(2):153–192, 1989. P. Chandon, J. W. Hutchinson, E. T. Bradlow, and S. H. Young. Does In-Store Marketing Work ? Effects of the Number and Position of Shelf Facings on Brand Attention. Journal of Marketing, 73(6):1 – 17, 2009. M. Corstjens and P. Doyle. A Model for Optimizing Retail Space Allocations. Management Science, 27(7):822–833, 1981. M. Corstjens and P. Doyle. A dynamic model for strategically allocating retail space. The Journal of the Operational Research Society, 34(10):943–951, 1983. M. E. Coskun. Shelf space allocation: A critical review and a model with price changes and adjustable shelf heights. Master’s thesis, Open Access Dissertations and Theses, 2012. R. C. Curhan. The Relationship Between Shelf Space and Unit Sales in Supermarkets. Journal of Maketing Research, 9(4):406–412, 1972. X. Drèze, S. J. Hoch, and M. E. Purk. Shelf management and space elasticity. Journal of Retailing, 70(4):301 – 326, 1994. Bibliography 37 H. Gajjar and G. Adil. A piecewise linearization for retail shelf space allocation problem and a local search heuristic. Annals of Operations Research, 179(1):149–167, 2010. H. Gajjar and G. Adil. Heuristics for retail shelf space allocation problem with linear profit function. International Journal of Retail &Distribution Management, 29(2):144–155, 2011a. H. K. Gajjar and G. K. Adil. A dynamic programming heuristic for retail shelf space allocation problem. Asia-Pacific Journal of Operational Research, 28(2):183–199, 2011b. H. N. Geismar, M. Dawande, B. Murthi, and C. Sriskandarajah. Maximizing revenue through two-dimensional shelf-space allocation. Production and Operations Management, 2014. Available online. J. M. Hansen, S. Raut, and S. Swami. Retail shelf allocation: A comparative analysis of heuristic and meta-heuristic approaches. Journal of Retailing, 86(1):94–105, 2010. P. Hansen and H. Heinsbroek. Product selection and space allocation in supermarkets. European Journal of Operational Research, 3(6):474–484, 1979. M. A. Hariga, A. Al-Ahmari, and A.-R. A. Mohamed. A joint optimisation model for inventory replenishment, product assortment, shelf space and display area allocation decisions. European Journal of Operational Research, 181(1):239 – 251, 2007. A. H. Hübner and H. Kuhn. Retail shelf space management model with space-elastic demand and consumer-driven substitution effects. Working paper available at SSRN, 2011. A. H. Hübner and H. Kuhn. Retail category management: State-of-the-art review of quantitative research and software applications in assortment and shelf space management. Omega, 40(2):199 – 209, 2012. H. Hwang, B. Choi, and M.-J. Lee. A model for shelf space allocation and inventory control considering location and inventory level effects on demand. International Journal of Production Economics, 97(2):185 – 195, 2005. H. Hwang, B. Choi, and G. Lee. A genetic algorithm approach to an integrated problem of shelf space design and item allocation. Computers Industrial Engineering, 56(3):809 – 820, 2009. J. Irion, J.-C. Lu, F. a. Al-Khayyal, and Y.-C. Tsao. A hierarchical decomposition approach to retail shelf space management and assortment decisions. Journal of the Operational Research Society, 62(10):1861–1870, 2011. J. Irion, J.-C. Lu, F. Al-Khayyal, and Y.-C. Tsao. A piecewise linearization framework for retail shelf space management models. European Journal of Operational Research, 222 (1):122 – 136, 2012. 38 Bibliography M. Kurtulus and L. B. Toktay. Category captainship practices in the retail industry. In Retail Supply Chain Management: Quantitative Models and Empirical Studies, pages 79–98. Springer, 2009. A. Lim, B. Rodrigues, and X. Zhang. Metaheuristics with Local Search Techniques for Retail Shelf-Space Optimization. Management Science, 50(1):117–131, 2004. M. Lotfi and S. Torabi. A fuzzy goal programming approach for mid-term assortment planning in supermarkets. European Journal of Operational Research, 213(2):430 – 441, 2011. M. Lotfi, M. Rabbani, and S. F. Ghaderi. A weighted goal programming approach for replenishment planning and space allocation in a supermarket. Journal of the Operational Research Society, 62(6):1128 – 1137, 2011. M. Maiti and M. Maiti. Multi-item shelf-space allocation of breakable items via genetic algorithm. Journal of Applied Mathematics and Computing, 20(1-2):327–343, 2006. C. C. Murray, D. Talukdar, and A. Gosavi. Joint optimization of product price, display orientation and shelf-space allocation in retail category management. Journal of Retailing, 86(2):125 – 136, 2010. Special Issue: Modeling Retail Phenomena. R. Pieters, M. Wedel, and R. Batra. The Stopping Power of Advertising: Measures and Effects of Visual Complexity. Journal of Marketing, 74(5):48–60, 2010. J. Preston and A. Mercer. The influence of product range in the space allocation procedure. European Journal of Operational Research, 47(3):339 – 347, 1990. B. Ranaseshan, N. R. Achuthan, and R. Collinson. A retail category management model integrating shelf space and inventory levels. Asia-Pacific Journal of Operational Research, 26(4):457–478, 2009. S. Raut, S. Swami, and M. P. Moholkar. Heuristic and meta-heuristic approaches for multiperiod shelf-space optimization: the case of motion picture retailing. Journal of the Operational Research Society, 60(10):1335–1348, 2009. P. Reyes and G. Frazier. Initial shelf space considerations at new grocery stores: An allocation problem with product switching and substitution. The International Entrepreneurship and Management Journal, 1(2):183–202, 2005. P. M. Reyes and G. V. Frazier. Goal programming model for grocery shelf space allocation. European Journal of Operational Research, 181(2):634 – 644, 2007. R. A. Russell and T. L. Urban. The location and allocation of products and product families on retail shelves. Annals of Operations Research, 179(1):131–147, 2010. T. L. Urban. An inventory-theoretic approach to product assortment and shelf-space allocation. Journal of Retailing, 74(1):15 – 35, 1998. Bibliography 39 T. L. Urban. The interdependence of inventory management and retail shelf management. International Journal of Physical Distribution &Logistics Management, 32(1):41–58, 2002. E. van Nierop, D. Fok, and P. H. Franses. Interaction between shelf layout and marketing effectiveness and its impact on optimizing shelf arrangements. Marketing Science, 27 (6):1065–1082, 2008. M.-H. Yang. An efficient algorithm to allocate shelf space. European Journal of Operational Research, 131(1):107–118, 2001. M.-H. Yang and W.-C. Chen. A study on shelf space allocation and management. International Journal of Production Economics, 61(510):309–317, 1999. F. S. Zufryden. A Dynamic Programming Approach for Product Selection and Supermarket Shelf-Space Allocation. Journal of the Operational Research Society, 37(4):413–422, 1986. Chapter 3 Allocating Products on Shelves under Merchandising Rules: Multi-level Product Families with Display Directions Teresa Bianchi-Aguiar∗·Elsa Silva∗·Luis Guimarães∗· Maria Antónia Carravilla∗·José F. Oliveira∗ Abstract Retailers’ individual products are categorized as part of product families. Merchandising rules specify how the products should be arranged on the shelves using product families, creating more structured displays capable of increasing the viewers’ attention. This paper presents a novel mixed integer programming formulation for the Shelf Space Allocation Problem considering two innovative features emerging from merchandising rules: hierarchical product families and display directions. The formulation uses single commodity flow constraints to model product sequencing and explores the product families’ hierarchy to reduce the combinatorial nature of the problem. Based on the formulation, a mathematical programming-based heuristic was also developed that uses product families to decompose the problem into a sequence of sub-problems. To improve performance, its original design was adapted following two directions: recovery from infeasible solutions and reduction of solution times. A new set of real case benchmark instances is also provided, which was used to assess the formulation and the matheuristic. This approach will allow retailers to efficiently create planograms capable of following merchandising rules and optimizing shelf space revenue. Keywords Retail ·Shelf space allocation ·Single commodity flow formulation ·MIPbased heuristics 3.1. Introduction While shopping, customer choices are highly influenced by in-store factors, in particular during frequent unplanned purchases and when the products they are searching for are not ∗INESC TEC and Faculty of Engineering, University of Porto, Rua Dr. Roberto Frias, s/n 4200-465 Porto, Portugal 41 42 Chapter 3. Allocating Products on Shelves under Merchandising Rules: Multi-level Product Families with Display Directions available. In this context, more than just displaying the merchandise, a clever product arrangement on the shelves can boost demand and ultimately the stores’ financial performance. With the increasing number of products available for the same scarce space, shelf space planning has become more and more challenging and an active field of research in retail operations management, under the name Shelf Space Allocation Problem (SSAP). The SSAP consists of distributing the scarce shelf space of a retail store among the different products to be displayed. Marketing studies have proven that space allocation has a positive impact on the visibility, consumer awareness and demand for the products (Drèze et al. [1994], Chandon et al. [2009], Curhan [1972], Desmet and Renaudin [1998]). As a result, for the past 40 years several models have tried to address the various objectives associated with product-to-shelf allocation, ranging from comprehensive to simplistic forms. In practice, the traditional space planning tool is a planogram, which is a blueprint of the shelves where retailers develop their merchandising plan, showing exactly the location where each product should physically be displayed and the number of facings that the product should hold. Planograms are usually created separately for each category, whose space is determined beforehand on a macro or upstream level. There are space planning software systems which can assist retailers in this activity. These systems provide realistic views of the shelves and allow retailers to quickly handle products through the planograms. Moreover, they have powerful analysis reports and automatic tools for product-to-shelf allocation. However, Hübner and Kuhn [2012] and Bai [2005] identified a misalignment in shelf space planning between commercial software applications and research: on one hand, software vendors focus mainly on the development of large-scale data processing technologies, with limited or no use of mathematical optimization and disregarding consumer demand effects. On the other hand, state-of-the-art optimization methods have practical limitations, either because of their simplicity and lack of key features, or due to their complexity and expensive estimation requirements for parameters. Retailers’ individual products are categorized as part of product families. One important practical limitation from the current literature is that it disregards that product allocation must follow merchandising rules which specify associations of products on the shelves. Merchandising rules try to reproduce the way customers search for the products while shopping and are obtained with the help of category captains (key suppliers with deeper knowledge about each category - Kurtulus and Toktay [2009]) and techniques such as market basket analysis. Those rules vary from retailer to retailer, and can include more than one level of product association. Another key practical feature of the problem is the way families are arranged on the shelves. Pieters et al. [2010] show that carefully organizing a display increases the viewers’ attention but its excessive complexity (i.e. variations in the basic visual content) can indeed decrease their interest. These concepts are applied in the Shelf Space Allocation Problem by imposing that both the products and the families are arranged in rectangular shapes (Geismar et al. [2014], Russell and Urban [2010]). The need to follow structured shapes is sometimes further stressed by assuming a direction for the shapes, either vertical or horizontal (forming columns or lines). To the best of our knowledge, the display direction 3.2. Literature overview 43 is for the first time tackled in this paper. This paper presents a novel and realistic mathematical model for the SSAP with multilevel product families. The model uses a linear profit function, as suggested by Yang and Chen [1999], and considers space and location decisions, similarly to Russell and Urban [2010]. Considering product families requires the definition of the exact location of the products on the shelves (not common in SSA literature) and thus products need to be sequenced. This additional requirement turns the models much more complex as sequencing decisions are known to pose hard analytical challenges mainly due to subtour elimination constraints. Following the research done in other combinatorial problems such as the asymmetric traveling salesman problem (Öncan et al. [2009]), we improved the modeling of product location using commodity-based constraints which are known to yield very tight models. This formulation is embedded in a matheuristic aiming at delivering quasi optimal solutions in short computational times. The matheuristic solves a sequence of sub-problems, exploring the hierarchy present in the product families. Using instances taken from a European grocery retailer, we demonstrate the applicability of the formulation, and report the improvements obtained with both the formulation and matheuristic over the existing literature. The contributions of this paper are as follows. A novel mathematical model has been developed for the Shelf Space Allocation Problem with location decisions based on the commodity flow formulation. This model additionally explores the existence of product families to reduce the combinatorial nature of the problem and introduces a new practical constraint imposed to product families: the display direction. On the algorithmic front, an innovative matheuristic is presented that was tailor-made to the formulation as it is based on the existence of multi-level product families. To improve the matheuristic performance, its original design was adapted following two directions: recovery from infeasible solutions through backtracking (improving feasibility) and reduction of solution times by adjusting the model’s detail (improving efficiency). Finally, a new set of real case benchmark instances is provided for the shelf space allocation problem with location decisions, allowing for future research in this area. The remainder of this paper is structured as follows. Section 3.2 begins with a literature review on the Shelf Space Allocation Problem defining the basis of this research. The problem is formally defined in section 3.3 with a focus on the definition of real world features. Section 3.4 is dedicated to describing the novel realistic mathematical formulation with single commodity flow constraints, and section 3.5 describes the solution approach that was tailor-made for the model. The computational results are presented and analyzed in section 3.6. The final section 3.7 pinpoints the conclusions and potential topics for future research. 3.2. Literature overview The shelf space allocation problem has long been addressed by marketing professionals and researchers, with the first studies tracing back to the 1970s. Marketing studies have proven the positive influence of shelf space on stimulating con- 50 Chapter 3. Allocating Products on Shelves under Merchandising Rules: Multi-level Product Families with Display Directions Constraints (3.7) and (3.8) force the tour to pass once through the source and sink node, while constraints (3.9) and (3.10) ensure that, if a downstream block is on the shelf, it should be immediately preceded and proceeded by exactly one node, either a block or the source/sink. Constraints (3.11) state that one block is only present on a shelf if the parent block is also present and finally constraints (3.12) make the connection with the allocation part of the problem. Constraints (3.13) and (3.14) guarantee that the variables are binary. Inspired by the good results in the Asymmetric Traveling Salesman Problem (Öncan et al. [2009]), we used single commodity flow constraints to guarantee that sequences are connected. The disconnected subtours are eliminated with additional decision variables representing a commodity flow through each network, which has to satisfy conservation constraints. The commodity is associated with the length of the corresponding upstream block on the shelf. Every time the commodity goes from one downstream block to another, the length assigned to the first block is added to the commodity flow. At the end, when the commodity enters the sink node, its value should be equal to the total length occupied by the upstream block. In the first block, the total length is equal to the width of the shelf, meaning that the entire space of the planogram is occupied. For this purpose, two sets of decision variables are added to the model: Fmnk the continuous flow from block mto block non shelf k∈ K,u∈ M,m,n∈ Vu∪{0}, Lik shelf length assigned to product i∈ N on shelf k∈ K. The single commodity flow constraints that enforce the existence of a path from the source to the sink node of each network associated with block u∈ M are the following: X m∈Vu F0mk =0,∀u∈ M,k∈ K (3.15) X m∈Vu Fm0k=X i∈Nu Lik,∀u∈ M,k∈ K (3.16) X n∈Vu∪{0}: m,n Fnmk +X i∈Nm Lik =X n∈Vu∪{0}: m,n Fmnk,∀u∈ M,m∈ Vu,k∈ K (3.17) Fmnk ≤wk·Tmnk,∀u∈ M,m,n∈ Vu∪ {0}:m,n,k∈ K (3.18) X i∈N Lik =wk,∀k∈ K (3.19) ai·Wik ≤Lik,∀i∈ N,k∈ K (3.20) Lik ≥0,∀i∈ N,k∈ K (3.21) Fmnk ≥0,∀u∈ M,m,n∈ Vu∪ {0},k∈ K (3.22) Constraints (3.15) force the commodity flow to leave the source of each network with no length, and constraints (3.16) ensure that in the end the total flow amount must be equal to the total length of the upstream block on the shelf (equal to zero if the block is not on the shelf). The flow balance constraints are expressed by (3.17), which ensure that the flow that enters each node plus its block’s length is equal to the flow that leaves the node. Constraints (3.18) guarantee that the flow only traverses active arcs, and in (3.19) the total width of each 3.4. Model Formulation 51 shelf should be occupied by the products. Constraints (3.20) ensure that enough space is reserved on each shelf for the facings of the products. Finally, the nonnegativity of the product’s length and commodity flows are ensured by (3.21)) and (3.22)). 3.4.3 Product Grouping Constraints For aesthetic reasons, both the families and the products should have rectangular shapes on the shelves, which means that each block should be placed on contiguous shelves and aligned, with a small deviation vallowed between shelves. This leads to a new set of decision variables and an extension of variable Xs i, from product to block range: Xs mthe horizontal location of the block m∈ V (left coordinate), Xe mthe horizontal location of the block m∈ V (right coordinate), FLmk =1 if k∈ K is the first shelf of block m∈ V, LLmk =1 if k∈ K is the last shelf of block m∈ V. The sequencing constraints (3.9)-(3.14) already impose the connectivity of the blocks within each shelf. The following constraints guarantee the rectangular shape and also define the horizontal location of the blocks: Xs m≥Xs u+X n∈Vu∪{0}: n,m Fnmk,∀u∈ M,m∈ Vu,k∈ K (3.23) Xs m≤Xs u+X n∈Vu∪{0}: n,m Fnmk +W·(1−Ymk),∀u∈ M,m∈ Vu,k∈ K (3.24) Xe m−Xs m≥X i∈Nm Lik,∀m∈ V,k∈ K (3.25) Xe m−Xs m−v≤X i∈Nm Lik +W·(1−Ymk),∀m∈ V,k∈ K (3.26) X k∈K FLmk =1,∀m∈ V (3.27) X k∈K LLmk =1,∀m∈ V (3.28) FLm,k+1+Ymk =Ym,k+1+LLmk,∀m∈ V,k∈ K :k,K(3.29) FLm0=Ym0,∀m∈ V (3.30) LLmK =YmK,∀m∈ V (3.31) Xs m,Xe m≥0,∀m∈ V (3.32) FLmk,LLmk ∈ {0,1},∀m∈ V,k∈ K (3.33) Constraint sets (3.23) and (3.24) establish the horizontal location of each block (left coordinate) according to the location of its parent block and the flow coming from the preceding block (that equals the length of the blocks since the beginning of the parent block). Constraints (3.25) and (3.26) define the right coordinate for each block and keep 52 Chapter 3. Allocating Products on Shelves under Merchandising Rules: Multi-level Product Families with Display Directions its location within vunits from one shelf to the others. Constraint sets (3.27) and (3.28) establish the top and bottom shelf where each block is located, while constraints (3.29)- (3.31) keep the block on adjacent shelves. Finally, if the blocks have predefined orientations, either horizontal or vertical, the following constraints guarantee the desired shapes: Ymk =Yuk,∀u∈ SV,m∈ Mu,k(3.34) X n∈Vu:n,m Ynk ≤M·(2−Ymk −Ym,k+1),∀u∈ SH,m∈ Mu,k∈ K :k,K(3.35) Constraints (3.34) ensure that the vertical blocks are present on the same shelves as their parent block, while constraint set (3.35) only allows a horizontal block to occupy more than one shelf if the first one is fully occupied by the block. Note that these two last requirements can be defined as soft constraints by introducing two new sets of variables that can relax the constraints, although there is a penalty on the objective function value. For the sake of simplicity, this model will hereafter be referred to as BAP – Block Allocation Problem. 3.5. Solution Approach When the instance size increases, the shelf space allocation problem with location decisions becomes intractable, which limits the straightforward use of standard mathematical programming approaches, in particular when dealing with real world instances. This fact motivated the development of an approximate method. We chose a mathematical programming based approach because the high number of constraints associated with family grouping would make it difficult to develop a constructive heuristic capable of generating high quality feasible solutions within reasonable time limits. Our solution approach decomposes the original problem into smaller sub-problems that can be more easily solved using exact methods. Following the idea that most of the computational burden comes from the integer variables, we used an approach based on the relax-and-fix (R&F) framework (Pochet and Wolsey [2006]). This framework decomposes the integer variables of large-scale MIP problems into subsets, and then sequentially solves relaxed MIP sub-problems containing each subset. As the number of integer variables in each sub-problem is significantly smaller than the original problem, the solution times to solve each one to optimality is lower. Consider the set Gcomposed of the integer variables Y,Tassociated with the blocks, and Wwith the products. At each iteration l, the integer variables are grouped into three subsets: GF lvariables whose values have been fixed in previous iterations to the values Y0,T0and W0,GI lvariables required to be integer in the current iteration, and finally GR lthe relaxed variables. The sub-problem to be solved, labeled subBAPl, corresponds to the original SSA model where equations (3.6), (3.13) and (3.14) are replaced by: Y=Y0,T=T0,W=W0∀(Y,T,W)∈ GF l(3.36) (Y,T)∈ {0,1},W∈N0,∀(Y,T,W)∈ GI l(3.37) 3.5. Solution Approach 53 (Y,T,W)≥0,∀(Y,T,W)∈ GR l(3.38) As the matheuristic progresses, the three subsets are updated as follows: part or all the integer variables are fixed (moved from GIto GF) and part or all the remaining relaxed variables are turned into integer variables (from GRto GI). The way subsets evolve defines both the quality of the solution and the computational burden of the R&Fheuristic. The heuristic finishes when a feasible integer solution is found for the entire problem or when a sub-problem is infeasible. In the SSAP, the family blocks and their hierarchical structure define a natural partition of the problem. The relation between the blocks within each upper block is indeed the most computational demanding feature of the problem due to the Tvariables (for sequencing purposes). In accordance, a block partition is used to define the subsets. The heuristic starts by solving sub-problems corresponding to the blocks from the first level and progressively moves down until it reaches the blocks in the last level. For that reason, this matheuristic will hereafter be called H-BAP – hierarchical resolution of BAP. For clarification purposes, figure 3.4 depicts three successive iterations of the heuristic (the first iteration corresponds to the initial one). 0 A B A.1 A.2 A.3 B.1 B.2 B.3 B.4 B.5 B.6 B.7 ... Iteration 1 0 A B A.1 A.2 A.3 B.1 B.2 B.3 B.4 B.5 B.6 B.7 ... Iteration 2 Fixed Variables Integer Variables Relaxed Variables 0 A B A.1 A.2 A.3 B.1 B.2 B.3 B.4 B.5 B.6 B.7 ... Iteration 3 Blocks belonging to the same upper blok are solved at the same iteration Figure 3.4 – Successive iterations of the MIP based heuristic 54 Chapter 3. Allocating Products on Shelves under Merchandising Rules: Multi-level Product Families with Display Directions The blocks in dark gray are those in which the value of the integer variables are fixed to the solution obtained in previous iterations (equations 3.36). The blocks in light gray are restricted to assume integer values (equations 3.37), and finally, the blocks in white are relaxed to fractional values (equations 3.38). From one iteration to the next, the subsets are updated so that at each time the variables in the integer set correspond to all blocks from the same upstream block. This evolution scheme was chosen to take into consideration the shape’s orientation, as it impacts all the blocks from the same parent. The pseudocode for the heuristic is presented below (Algorithm 1), where the function getNextIntegerS et returns the integer variables for each iteration. The algorithm is a straightforward implementation of what has been previously described. Note that line 11 guarantees that the subset GF(fixed variables) is updated correctly if the integer variables of two successive iterations overlap. The code is sufficiently generic to allow other evolution schemes for the subsets (function getNextIntegerS et). Algorithm 1: Pseudocode for the MIP based heuristic (H-BAP) 1begin 2l←1 3GI l:=Solve getNextIntegerS et 4GF l:=∅ 5GR l:=G\{GI l} 6while GR l<∅do 7Status :=Solve subBAPl 8if Status =Feasible then 9Y’ :=Y, T’ :=T, W’ :=W 10 GI l+1:=Solve getNextIntegerS et 11 GF l+1:=GF l∪(GI l\{GI l∩ GI l+1}) 12 GR l+1:=GR l\{GI l+1} 13 else 14 Return Infeasible 15 end 16 l←l+1 17 end 18 Status :=Solve subBAPl 19 Return Status 20 end 3.5.1 Improving Feasibility Finding a feasible solution while using a R&Fheuristic is not always guaranteed. Even though a top-down approach for the SSAP explores the problem structure, it risks creating top level assignments that constitute infeasible product allocations. As it goes further down, the heuristic might not reserve enough space to guarantee the minimum facings for all the products, especially when forcing integrality on the W variables. Therefore, to minimize the chances of infeasibility, we have created a new set of constraints that take into consideration product-related features at an earlier stage. For that 3.5. Solution Approach 55 purpose, consider a new parameter wmax mwith the width of the largest product from each block m(wmax m=max{ai|i∈ Nm}). As the family (and product) blocks have to form rectangular shapes, and all the products have to be allocated, the minimum width of a block is wmax m. In accordance, we introduce the new set of constraints (3.39): X i∈Nm Lik ≥wmax m∀m∈ M,k∈ K (3.39) Additionally, the heuristic was also changed to include a backtracking scheme. Whenever a sub-problem is infeasible, the heuristic shifts backward instead of forward, and solves a larger sub-problem by unfixing previous parts of the solution while maintaining the current integer variables. The heuristic starts by unfixing all the integer variables from the previous level, and while the problem remains infeasible it moves further backwards until reaching a maximum number of backward moves, or the set GFis empty. Notice that the backtracking scheme unfixes the variables by level instead of blocks. This gives the necessary freedom to change the blocks arrangement. This backtracking only requires changes in the way the sets are updated and the above formulation does not suffer any change. Algorithm 2presents the backtracking scheme that should replace line 14 in Algorithm 1for handling infeasible sub-problems. The new subset GF lcontains the variables that should be unfixed in the next iteration. This subset is updated using the function getUnFixS et. Once again, the code allows other backtracking schemes (by changing the function getUnFixS et). We will hereafter call to this extension Improving Feasiblity (HBAP-IF). Algorithm 2: Pseudocode for improving feasibility – replaces line 14 in Algorithm 1 1if GF l<∅then 2GF l+1:=Solve getUnFixS et 3GI l+1:=GI l∪ GF l+1 4GF l+1:=GF l\{GF l+1} 5else 6Return Infeasible 7end 3.5.2 Improving Efficiency As previously mentioned, most of the problem’s complexity comes from the family groups which impose hard constraints on the positioning of the products. One possible approach to improve the problem’s efficiency would be to reduce the level of detail by not considering the products until a later stage (by removing the single product blocks from the model’s formulation, it is possible to substantially reduce its size). The products could be handled afterwards in a downstream problem by using a knapsack model (multiple examples are provided in the literature) or a heuristic method. Such approach is only possible if all the family groups are handled in this upstream model. However, there are two drawbacks when the products are removed from the formula- 56 Chapter 3. Allocating Products on Shelves under Merchandising Rules: Multi-level Product Families with Display Directions tion: firstly, the final space assigned to each block may not be enough to guarantee the minimum number of facings for the corresponding products, and secondly, the blocks may be assigned to shelves where the products do not fit because of their height. To avoid potential downstream infeasibilities, we chose to disregard the products’ sequencing and exact positioning, and yet consider the products’ linear shelf space allocation to shelves. This change requires the use of the length (L) instead of the number of facings (W) both in the objective function and to ensure the products’ lower and upper bounds. Constraints (3.2)-(3.6), (3.12)) and (3.20) are replaced by: Maximize X i∈N X k∈K Z=pi·γk·Lik (3.40) subject to: X k∈K Lik ≤ui·wi,∀i∈ N (3.41) X k∈K Lik ≥li·wi,∀i∈ N (3.42) Lik =0,∀i∈N,k∈ K :bi≤hk(3.43) Lik ≥Yik ·wi,∀i∈ N,k∈ K (3.44) Additionally, the sequencing and family block variables and constraints do not apply to single product blocks, except Yvariables. For that purpose, consider a new set MU containing all the blocks from Mexcept the lowest ones (MU∈ {0,A,B}in the diagram from Figure 3.2). In constraints (3.7)-(3.10),(3.14),(3.15)-(3.18),(3.22),(3.23) and (3.24) the set Mis replaced by MU, and in constraints (3.25)-(3.33) the set Vis replaced by M. We will hereafter call to this extension Improving efficiency (H-BAP-IE). 3.6. Experimental Analysis and Computational Results This section presents the results of the computational study to validate and assess the performance of both the formulation and the solution approach. For this purpose, we provide a set of benchmark instances for the shelf space allocation problem that capture the different features of real world problems as described in Section 3.3. All the computational experiments were conducted on Intel @2.40GHz processing units limited to 4.0Gb of Random Access Memory using the Linux operating system. The IBM ILOG CPLEX 12.4 was used both as the mixed integer and linear programming solver. 3.6.1 Problem Instances A total of 54 problem instances were obtained from a European Grocery Retailer. The company defines very complex block diagrams that try to reproduce the way customers search for the products while shopping. Blocks can be defined by different criteria and the most common ones are brand, type, package size and flavor. To ensure that different realities are covered, the instances belong to 22 different categories, ranging from low to high sales products, light to heavy block diagrams, vertically to horizontally shaped blocks, among other features. Table 3.1 presents the key information about the instances: 3.6. Experimental Analysis and Computational Results 57 number of products (N), number of family blocks (M), number of shelves (K), number of hierarchical levels (L) and number of vertical (MV) and horizontal blocks (MH). The instances are grouped by category and organized by increasing number of products (for example, instances AZ_1, AZ_2 and AZ_3 belong to category AZ, whose average number of products is higher than category FL). As it is possible to see, the instances vary in size and are significantly bigger than the ones reported in the literature, with up to 240 products, 9 shelves and 5 hierarchy levels. One critical information for planogram design is the lower and upper bounds on the number of product facings. The lower bounds were set to one in all instances and the upper bounds were determined by setting a days supply baseline for the planogram (i.e. number of days that the shelf inventory should last), based on the revenue potential and the space available. Other information was taken into consideration, such as the maximum number of facings determined by the management, product shelf life, supplier contracts, among others. The exact calculus behind the upper bounds is beyond the scope of this paper. Another key parameter is shelf effectiveness. We used beta functions to model the way the management considers the shelves’ attractiveness to the consumers, always privileging eye-level shelves. The instances are available online in Bianchi-Aguiar et al. [2014]. It was not possible to test the instances found in the literature either because they were not available, or because they did not consider family groups. As aforementioned, family groups are of major importance in practice and are a key feature of our problem definition and the basis of our formulation. Table 3.1 – Problem Instances Name N M K L MV MH Name N M K L MV MH Name N M K L MV MH FL_1 16 16 6 4 5 10 CR_2 32 13 7 3 0 12 SM_3 49 10 6 3 7 2 AZ_3 10 11 5 3 8 2 CR_1 82 44 5 4 4 39 SM_1 171 47 6 4 36 10 AZ_2 25 12 5 3 9 2 PT_1 38 22 6 5 0 21 CA_2 77 34 6 5 2 31 AZ_1 32 27 5 3 0 26 AI_1 37 22 7 4 5 16 AG_2 19 19 7 5 0 18 LS_1 26 5 8 2 0 4 AI_3 41 27 9 5 4 22 AG_1 39 6 7 2 5 0 VG_3 7 4 7 2 0 3 AI_4 47 24 9 4 7 16 AG_4 85 32 5 4 10 21 VG_2 19 18 6 4 2 15 AI_2 47 17 7 3 3 13 AG_3 113 24 8 4 17 6 VG_4 28 15 6 3 2 12 VN_1 45 32 6 3 0 31 AB_1 28 14 8 3 0 13 VG_5 42 17 6 4 10 6 SP_1 49 15 7 4 6 8 AB_2 160 42 8 4 0 41 VG_1 60 29 8 4 0 28 OM_3 22 16 5 4 2 13 VV_2 84 3 5 2 2 0 CP_2 8 11 6 3 0 10 OM_1 54 41 5 4 6 34 VV_1 121 9 5 2 8 0 CP_1 24 18 5 3 5 12 OM_2 78 17 6 3 0 16 LO_2 15 4 5 2 0 3 CP_4 47 29 8 3 28 0 LC_1 46 21 6 4 4 16 LO_1 206 128 7 3 122 5 CP_3 51 27 6 5 21 5 LC_2 59 25 6 3 4 20 BH_1 108 25 7 3 0 24 CR_6 16 8 5 2 0 7 SM_6 19 7 6 3 4 2 BH_2 131 26 5 4 17 8 CR_5 19 10 5 3 0 9 SM_2 31 8 6 3 5 2 CH_1 190 99 6 4 15 83 CR_4 22 14 5 3 0 13 SM_4 34 11 6 3 8 2 BC_1 239 121 6 5 10 110 CR_3 25 11 5 3 0 10 SM_5 38 10 6 3 7 2 DE_1 240 45 8 4 40 4 N - Number of Products, M - Number of Family Blocks, K - Number of Shelves, L - Number of Hierarchical Levels, MV - Number of Vertical Blocks, MH - Number of Horizontal Blocks 58 Chapter 3. Allocating Products on Shelves under Merchandising Rules: Multi-level Product Families with Display Directions 3.6.2 Model Validation and Performance Evaluation The model analysis will firstly focus on the validation of the practical constraints by analyzing one of the instances in three different scenarios: (1) the first scenario does not consider family blocks. For that purpose, Mwas replaced in all instances by a single block containing all the products: M={1},N1=N; (2) the second scenario considers the family blocks without the shapes’ direction, i.e. SH={} and SV={}; (3) and the third scenario considers the blocks to their full extent. Secondly, the performance of the formulation will be assessed. Although there is no comparable formulation in the literature, we have adapted Russell and Urban [2010] formulation (RU), which is, to the best of our knowledge, the only formulation present in the literature that also considers continuous location decisions, and have compared the results achieved by the two formulations. Appendix 3.A presents all the details about this adapted formulation. Figure 3.5 presents the planogram obtained for one of the smallest instances, AZ_3, in each of the three scenarios. The results were obtained using the IBM ILOG CPLEX Optimization Studio to run the monolithic model BAP until optimality. AZ_3 contains 10 products organized into two levels of product families, the first one being horizontal and the second one vertical. Each planogram is firstly highlighted by the families of level 1, secondly by the families of level 2, and lastly by the products. By analyzing Scenario 1, it is possible to see that the products with the highest profits were on the highest shelves and reaching the maximum number of facings, while the lowest profit products were on the lowest shelves and with the minimum number of facings. This allocation is in accordance with the objective function and resulted in the highest objective function value among the three scenarios (71751.4, 71749.4 and 70535.7 respectively). However, the resulting planogram does not follow any implementation logic, which may make the search for the products in the stores difficult, specially when the size of the planogram increases. In Scenario 2, which already organizes the products by product families, the blocks with the highest average profit are also pushed to the top, although they might include products with low profit. The objective function is lower than the one of the first scenario, but the families bring a better understanding of the planogram. Finally, by including the shapes’ direction in Scenario 3, we obtain the lowest objective function value but with a clear identification of the allocation rules. Moreover, this new feature brings more realism, providing shelf space layouts similar to what is seen in practice. This analysis demonstrates that, even though the objective function decreases with the new features, benefits are obtained by organizing products into families. These benefits are hard to grasp in the model as they are linked to the customers’ response to the complexity of the planograms and to the way costumers search for the products while shopping. However, merchandising rules have been and are carefully studied by marketeers and the gains obtained by taking these rules into consideration are supposed to overcompensate the decreasing values in the objective function. Table 3.2 summarizes the results obtained for all the instances in the three scenarios and the two formulations (BAP and RU). The detailed information is presented in Table 3.4 from Appendix 3.B. For each instance, we provide information about the linear relaxation (Zlr), best integer solution found (Z), total execution time in seconds (T) and the deviation 3.6. Experimental Analysis and Computational Results 59 Scenario 2 (without blocks orientation) Scenario 3 Level 3 (Products) Level 2 Level 1 1 2 456 Horizontal Vertical 7 3 89 10 11 Vertical 12 13 1715 21 20 16 14 18 19 50.00 76 0.96 3 0.70 3 14.08 3 9.04 10 15.66 4 1.37 3 2.40 3 3.00 3 50.00 43 Profit Maximum Facings 2 3 56 74 10 98 11 12 20 17 15 16 1814 19 13 21 Scenario 1 (without blocks) Level 1 Vertical Impact 2 3 6 7 4 8 910 7 11 14 12 20 16 19 1817 21 15 13 Level 2 Level 3 2 310 98 11 16 1814 19 56 7412 20 17 15 13 21 Figure 3.5 – Solution Analysis of instance AZ_3 in the three scenarios 66 Chapter 3. Allocating Products on Shelves under Merchandising Rules: Multi-level Product Families with Display Directions sure that the length allocated to each product on each shelf is enough for the corresponding number of facings, and constraints (3.50) ensure that the total length allocated to each shelf does not exceed its capacity. Constraints (3.52) ensure that the products do not exceed the height of the shelves. To guarantee that there is no physical overlap between the products, the formulation includes: Lik ≤wk·Yik,∀i∈ N (3.54) Xs ik ≥0,∀i∈ N,k∈ K (3.55) Xs ik ≤wk−ai·Wik,∀i∈ N,k∈ K (3.56) Xs ik ≤Xs jk +Ljk −wk·Ti j −wk·(2−Yik −Yjk),∀i,j∈N:i,j,k∈ K (3.57) Ti j +Tji =1,∀i,j∈N:i<j,k∈ K (3.58) Ti j ∈ {0,1},∀i,j∈ N (3.59) Constraints (3.54) relate variables Land Y: a product can only have length within the shelves it was assigned to. The limits of the shelves are imposed by constraints (3.55) and (3.56). Constraints (3.57) define the product sequencing by ensuring that the left coordinate of product iis to the right of the right coordinate of product j, unless product iis to the left of product j, or both products are on different shelves. Constraints (3.58) guarantees that a product is either to the left or to the right of another product. The sequencing part of the formulation is one of the key differences for the formulation proposed in this paper, which takes advantage of the family blocks to reduce the combinatorial nature of Ti j. Finally, product families are kept in rectangular and continuous blocks through the following constraints: Ymk ≤X i∈Nm Yik,∀m∈ V,k∈ K (3.60) Ymk ≥Yik,∀m∈ V,i∈ Nm,k∈ K (3.61) Xs mk ≤Xs ik +wk·(1−Yik),∀m∈ V,i∈ Nm,k∈ K (3.62) Xe mk ≥Xe ik +Li j −wk·(1−Yik),∀m∈ V,i∈ Nm,k∈ K (3.63) Xe mk −Xs mk =X i∈Nm Lik,∀m∈ V,k∈ K (3.64) FLm≤K−(K−k)·Ymk,∀m∈ V,k∈ K (3.65) LLm≥k·Ymk,∀m∈ V,k∈ K (3.66) LLm−FLm=X k∈K Ymk −1,∀m∈ V (3.67) LLm≥FLm,∀m∈ V (3.68) Xs m,k+1−Xs mk ≤v+wk·(2−Ymk −Ym,k+1),∀m∈ V,k∈ K :k<K(3.69) Xs mk −Xs m,k+1≤v+wk·(2−Ymk −Ym,k+1),∀m∈ V,k∈ K :k<K(3.70) Xe m,k+1−Xe mk ≤v+wk·(2−Ymk −Ym,k+1),∀m∈ V,k∈ K :k<K(3.71) Xe mk −Xe m,k+1≤v+wk·(2−Ymk −Ym,k+1),∀m∈ V,k∈ K :k<K(3.72) 3.B. Result Tables 67 Xs mk,Xe mk ≤0,∀m∈ V,k∈ K (3.73) Ymk ∈ {0,1},∀m∈ V,k∈ K (3.74) FLm,LLm∈N0,∀m∈ V (3.75) Constraints (3.60) and (3.61) associate the families’ placement on the shelves with the products’ placement, while constraints (3.62)-(3.64) define the family blocks’ left and right coordinates in accordance with the products’ coordinates. The blocks’ vertical adjacency is ensured by constraints (3.65)-(3.68), and the horizontal adjacency by (3.69)-(3.72). Constraints (3.34) and (3.35) from section 3.4.3, pertaining to the novel display direction feature, were additionally added to the formulation. Appendix 3.B Result Tables This section presents the detailed results obtained for all the instances present in section 3.6.1. Table 3.4 contains the results using both the BAP and RU formulations in the three scenarios. For each instance, we provide information about the linear relaxation (Zlr), best integer solution found (Z), total execution time in seconds (T) and the deviation of the best integer solution found from the best upper bound available at the stopping criteria (GAP). Note that Zis defined in equation (3.1) and additionally includes a penalty P defined in (3.45) whenever a shape’s vertical direction is violated. This penalty explains the negative values in some instances. The results are further explained in section 3.6.2. Table 3.5 contains the results obtained using the H-BAP matheuristic and its extensions in the last two scenarios. For each instance, we provide information about the best integer solution found (Z), the total execution time in seconds (T) and the deviation of the best integer solution from the best upper bound available (taken from the previous section) (GAP). The results are explained in section 3.6. 68 Chapter 3. Allocating Products on Shelves under Merchandising Rules: Multi-level Product Families with Display Directions Table 3.4 – Model Validation and Performance Results Instance Name Scenario 1 Scenario 2 Scenario 3 Zlr Z T(s)GAP(%) Zlr Z T (s)GAP(%) Zlr Z T(s)GAP(%) BAP RU BAP RU BAP RU BAP RU BAP RU BAP RU BAP RU BAP RU BAP RU BAP RU BAP RU BAP RU FL_1 10183.5 10183.5 10089.1 10089.1 2290 259 0.0 0.0 10178.4 10181.9 9927.5 9927.5 31 79 0.0 0.0 10112.4 10181.9 9761.0 9761.0 18 30 0.0 0.0 AZ_3 71751.4 71751.4 71399.8 71399.8 13 5 0.0 0.0 71749.4 71751.2 70875.1 70875.1 1 7 0.0 0.0 70535.7 71750.8 64203.2 64203.2 2 3 0.0 0.0 AZ_2 52398.2 52398.2 52268.0 52340.0 T l Tl 0.2 0.0 52376.8 52390.1 51695.4 51695.4 1090 1431 0.0 0.0 52107.9 52375.9 51107.5 51040.4 Tl T l 0.2 0.7 AZ_1 4936.2 4936.2 4885.2 4919.4 Tl Tl 0.8 0.1 4934.3 4935.4 4819.5 4829.7 Tl T l 0.6 0.5 4934.3 4935.4 4746.4 4746.4 255 96 0.0 0.0 LS_1 7393.2 7393.2 6969.1 7302.3 Tl Tl 5.7 1.2 7393.2 7393.0 7166.7 7147.1 Tl Tl 2.1 2.5 7393.2 7392.8 7124.2 7124.2 T l Tl 0.3 0.2 VG_3 18904.2 18904.2 18718.2 18718.2 16 7 0.0 0.0 18902.1 18903.1 18062.3 18062.3 21 20 0.0 0.0 18901.9 18903.0 17431.5 17431.5 11 8 0.0 0.0 VG_2 141171.9 141171.9 134769.0 140226.8 T l 58 4.0 0.0 141150.8 141169.8 138756.0 138756.0 T l Tl 0.2 0.3 140699.9 141169.5 135736.8 135736.8 29 58 0.0 0.0 VG_4 18013.3 18013.3 17826.3 17853.0 T l Tl 0.4 0.2 18013.3 18012.8 17231.2 17091.9 Tl Tl 0.4 2.4 18006.0 18012.2 16040.5 16040.5 34 282 0.0 0.0 VG_5 70919.1 70919.1 ∗70729.2 Tl T l 0.2 70919.0 70912.7 69202.0 66490.9 Tl T l 1.7 5.7 69752.5 70893.6 68151.0 ∗Tl T l 2.1 VG_1 11325.8 11325.8 ∗ ∗ Tl T l 11323.1 11325.2 ∗ ∗ Tl T l 11323.1 11325.2 10421.8 ∗1119 Tl 0.0 CP_2 782.8 782.8 760.1 760.1 8 3 0.0 0.0 782.8 782.8 690.2 690.2 12 9 0.0 0.0 782.8 782.8 690.2 690.2 1 2 0.0 0.0 CP_1 472.5 472.5 471.8 471.8 Tl 1329 0.0 0.0 472.5 472.5 463.3 465.2 Tl Tl 1.8 1.1 472.3 472.5 453.6 453.6 152 63 0.0 0.0 CP_4 3278.5 3278.5 ∗ ∗ Tl T l 3278.5 3278.5 ∗ ∗ T l T l 3167.3 3278.3 ∗ ∗ Tl Tl CP_3 10380.4 10380.4 ∗10369.0 Tl T l 0.1 10380.4 10380.0 10054.0 ∗Tl Tl 2.4 10082.7 10379.7 -355477.4 ∗T l Tl 100.0 CR_6 718.4 718.4 619.6 625.3 T l Tl 11.2 6.0 718.4 718.4 617.9 617.9 3405 3594 0.0 0.0 718.4 718.4 608.3 608.3 7 9 0.0 0.0 CR_5 1162.7 1162.7 1003.1 1009.9 Tl Tl 11.0 10.4 1162.6 1162.5 900.7 900.7 Tl T l 4.5 6.0 1162.6 1162.5 632.1 632.1 7 13 0.0 0.0 CR_4 571.6 571.6 561.1 562.6 T l Tl 1.3 0.7 571.6 571.5 536.2 536.2 Tl Tl 1.0 0.0 571.6 571.5 442.6 442.6 43 59 0.0 0.0 CR_3 641.3 641.3 536.1 545.8 T l Tl 12.7 11.4 641.0 641.2 516.0 516.0 T l Tl 13.2 13.3 641.0 641.2 460.6 460.6 18 60 0.0 0.0 CR_2 1017.3 1017.3 996.0 1006.4 Tl T l 2.0 0.8 1017.3 1017.3 975.4 852.0 Tl Tl 2.9 15.1 1017.3 1017.3 872.2 872.2 1034 1616 0.0 0.0 CR_1 3801.5 3801.5 ∗ ∗ Tl T l 3801.5 3800.7 3395.2 ∗Tl Tl 8.9 3762.7 3798.5 3124.6 ∗T l Tl 8.1 PT_1 90096.2 90096.2 60866.3 66477.9 T l Tl 8.5 0.0 90074.2 90091.9 62304.6 62304.6 93 Tl 0.0 0.0 90074.2 90091.9 62034.9 62034.9 19 Tl 0.0 0.0 AI_1 4039.6 4039.6 3792.6 4007.8 Tl Tl 6.1 0.7 4039.4 4039.3 3882.5 3854.2 Tl Tl 1.3 2.1 3938.1 4039.0 3748.6 3736.3 Tl T l 4.7 4.8 AI_3 7100.5 7100.5 ∗ ∗ Tl T l 7100.3 7100.4 6437.2 ∗Tl Tl 9.1 7080.8 7100.4 6474.0 ∗Tl T l 8.4 AI_4 20423.2 20423.2 ∗20328.3 Tl T l 0.3 20422.6 20423.0 19758.3 ∗T l Tl 2.1 20267.6 20422.4 19831.4 19528.2 T l Tl 0.8 3.0 AI_2 3234.7 3234.7 2939.6 3110.1 Tl Tl 9.1 3.8 3234.3 3234.6 2790.6 ∗Tl T l 12.8 3195.4 3234.4 2470.2 2120.6 Tl T l 22.2 33.3 VN_1 18270.0 18270.0 ∗18025.3 Tl T l 0.4 18269.9 18269.8 17571.4 ∗Tl Tl 0.5 18269.9 18269.8 15605.5 15605.5 216 Tl 0.0 0.2 SP_1 9761.4 9761.4 ∗ ∗ Tl T l 9761.4 9760.6 9591.0 ∗Tl Tl 0.7 9719.7 9759.0 9332.0 ∗T l Tl 1.9 OM_3 527.7 527.7 502.1 503.9 T l 1719 0.4 0.0 527.7 527.7 469.8 469.8 Tl Tl 0.1 2.0 519.4 527.7 358.3 358.3 81 117 0.0 0.0 OM_1 983.3 983.3 ∗975.3 Tl T l 0.1 983.2 983.0 955.8 ∗Tl T l 1.8 938.3 982.6 -24368.6 891.1 Tl T l 100.0 3.1 OM_2 299.5 299.5 ∗ ∗ Tl T l 299.5 299.5 ∗ ∗ Tl Tl 299.5 299.5 259.1 ∗716 T l 0.0 LC_1 21061.9 21061.9 ∗21017.5 Tl T l 0.1 21061.6 21059.8 20349.3 20259.2 Tl Tl 0.5 1.4 21061.5 21059.8 20281.9 20007.1 Tl Tl 0.5 2.5 LC_2 8443.5 8443.5 ∗8062.3 Tl T l 4.5 8443.4 8443.0 7938.8 ∗Tl Tl 5.6 8410.7 8442.2 7626.1 6253.1 T l Tl 9.1 25.6 SM_6 17652.6 17652.6 17150.5 17296.3 T l Tl 1.3 0.4 17651.6 17652.1 16939.1 16939.1 3373 T l 0.0 0.0 17646.6 17651.2 16784.5 16784.5 2019 Tl 0.0 1.6 SM_2 28455.5 28455.5 27131.5 28282.4 T l Tl 4.2 0.1 28446.4 28454.1 28066.7 28067.5 T l T l 0.5 0.4 28394.2 28453.9 27804.1 27665.3 Tl T l 0.3 1.0 SM_4 22976.6 22976.6 ∗22845.4 Tl T l 0.2 22971.3 22975.2 22481.3 22369.4 T l Tl 0.8 1.6 22926.9 22972.8 22303.1 22302.8 Tl T l 0.4 0.3 SM_5 10765.4 10765.4 9655.4 10693.8 Tl T l 10.2 0.4 10764.7 10765.1 10455.5 ∗Tl T l 0.9 10734.4 10764.8 10246.5 ∗Tl T l 0.4 SM_3 58355.6 58355.6 ∗57268.3 Tl T l 1.2 58345.3 58355.2 53897.1 ∗T l Tl 5.9 57901.9 58351.9 53382.4 ∗T l Tl 6.9 SM_1 136291.7 136291.6 ∗ ∗ Tl T l 136291.7 136278.5 ∗ ∗ Tl Tl 135908.5 136266.4 ∗ ∗ Tl T l CA_2 290.6 290.6 ∗ ∗ Tl T l 290.6 290.6 ∗ ∗ T l T l 290.4 290.6 243.2 ∗Tl Tl 7.7 AG_2 2540.4 2540.4 2472.0 2504.0 Tl T l 2.6 1.2 2539.9 2540.3 2381.1 2372.2 Tl T l 2.7 3.7 2539.9 2540.3 2154.0 2154.0 54 138 0.0 0.0 AG_1 2743.8 2743.8 ∗2725.7 T l T l 0.6 2743.8 2743.8 2559.9 ∗Tl Tl 5.9 2730.3 2743.7 -142247.9 ∗T l Tl 100.0 AG_4 5909.1 5909.1 ∗5812.7 T l T l 1.6 5909.1 5908.7 5603.0 ∗Tl Tl 3.9 5762.3 5908.5 -148264.8 ∗T l T l 100.0 AG_3 33623.9 33623.9 ∗ ∗ T l T l 33623.3 33622.4 ∗ ∗ Tl Tl 33598.4 33622.4 ∗ ∗ Tl Tl 3.B. Result Tables 69 Instance Name Scenario 1 Scenario 2 Scenario 3 Zlr Z T(s)GAP(%) Zlr Z T (s)GAP(%) Zlr Z T(s)GAP(%) BAP RU BAP RU BAP RU BAP RU BAP RU BAP RU BAP RU BAP RU BAP RU BAP RU BAP RU BAP RU AB_1 538.7 538.7 510.9 531.2 T l Tl 5.0 1.1 538.5 538.7 523.3 522.7 T l T l 1.7 1.9 538.5 538.7 500.7 500.7 377 627 0.0 0.0 AB_2 7213.3 7213.3 ∗ ∗ Tl T l 7213.3 7213.2 ∗ ∗ Tl T l 7213.3 7213.2 6222.8 ∗Tl Tl 13.1 VV_2 3266.8 3266.8 ∗3258.4 Tl T l 0.1 3266.8 3266.4 ∗ ∗ Tl Tl 3252.9 3266.3 ∗ ∗ T l T l VV_1 61951.0 61951.0 ∗22599.5 Tl T l 63.4 61951.0 61943.7 ∗ ∗ T l T l 61016.7 61942.7 ∗ ∗ Tl T l LO_2 69.1 69.1 68.3 68.3 557 29 0.0 0.0 69.1 69.1 65.8 65.8 339 339 0.0 0.0 69.1 69.1 51.3 51.3 84 37 0.0 0.0 LO_1 4343.3 4343.3 ∗ ∗ Tl T l 4343.3 4343.1 ∗ ∗ Tl T l 4343.3 4342.7 ∗ ∗ Tl Tl BH_1 42878.0 42878.0 ∗ ∗ Tl T l 42876.6 42875.7 ∗ ∗ Tl Tl 42876.6 42875.3 40820.1 ∗T l T l 0.0 BH_2 77697.2 77697.2 ∗ ∗ Tl T l 77689.4 77673.4 ∗ ∗ Tl Tl 74591.3 77661.5 ∗ ∗ T l Tl CH_1 1367.9 1367.9 ∗ ∗ Tl T l 1367.9 1367.9 ∗ ∗ T l T l 1361.2 1367.8 ∗ ∗ Tl Tl BC_1 66069.7 66069.7 ∗ ∗ Tl T l 66069.7 66065.4 ∗ ∗ Tl Tl 65517.9 66057.6 ∗ ∗ T l Tl DE_1 6720.9 6720.8 ∗ ∗ Tl T l 6720.9 6720.5 ∗ ∗ Tl Tl 6719.7 6720.4 ∗ ∗ T l T l ∗No feasible solution was found. Tl Time limit of 3600 s was reached. 70 Chapter 3. Allocating Products on Shelves under Merchandising Rules: Multi-level Product Families with Display Directions Table 3.5 – Solution Approach Results Instance Name H-BAP H-BAP-IF H-BAP-IE Scenario 2 Scenario 3 Scenario 2 Scenario 3 Scenario 2 Scenario 3 ZGAP(%) T(s) Z GAP(%) T(s) Z GAP(%) T(s) Z GAP(%) T(s) Z GAP(%) T(s) Z GAP(%) T(s) FL_1 9708.7 2.2 2.1 9761.0 0.0 1.2 9708.7 2.2 2.1 9761.0 0.0 1.2 9645.0 2.9 1.0 9718.7 0.4 0.9 AZ_3 70875.2 0.0 0.6 64203.2 0.0 0.6 70875.2 0.0 0.6 64203.2 0.0 0.6 70287.5 0.8 0.4 61907.8 3.6 0.3 AZ_2 51416.1 0.6 19.3 50758.2 0.9 37.9 51416.1 0.6 19.2 50758.2 0.9 40.0 50968.1 1.4 3.0 50504.1 1.4 7.0 AZ_1 ∗1309.2 ∗4.1 4733.2 2.4 2406.9 4743.1 0.1 6.2 4587.4 5.4 860.3 4723.9 0.5 1.7 LS_1 ∗2359.7 7124.2 0.3 36.0 7115.8 2.8 2975.8 7124.2 0.3 36.0 7169.9 2.1 72.1 7118.7 0.4 2.9 VG_3 17649.1 2.3 1.3 17409.1 0.1 1.1 17649.1 2.3 1.5 17409.1 0.1 1.0 17000.0 5.9 0.4 16878.1 3.2 0.3 VG_2 133028.0 4.3 1.5 135737.0 0.0 1.7 133028.0 4.3 1.8 135737.0 0.0 1.8 131314.0 5.5 0.9 135265.0 0.4 0.9 VG_4 16940.4 2.1 7.4 16040.6 0.0 4.7 16940.4 2.1 7.3 16040.6 0.0 4.9 16485.2 4.7 3.1 16000.1 0.3 1.5 VG_5 68972.8 2.1 90.7 67996.4 2.3 321.1 68972.8 2.1 90.9 67996.4 2.3 324.8 68567.4 2.6 10.9 66622.1 4.3 22.7 VG_1 10870.6 3.1 579.8 10411.8 0.1 25.8 10870.6 3.1 607.3 10411.8 0.1 27.5 10041.4 10.5 49.0 10399.4 0.2 9.1 CP_2 690.2 0.0 0.3 690.2 0.0 0.2 690.2 0.0 0.3 690.2 0.0 0.3 690.2 0.0 0.4 690.2 0.0 0.2 CP_1 463.7 1.7 1177.7 453.6 0.0 42.6 461.4 2.2 1178.4 453.6 0.0 41.5 447.9 5.0 761.0 439.7 3.1 11.9 CP_4 3203.8 2.2 1159.1 -47366100.0 100.0 1158.5 3203.8 2.2 1159.4 -47366100.0 100.0 1158.3 3045.5 7.1 761.3 2638.0 15.0 302.2 CP_3 10204.6 1.0 102.2 -18659500.0 100.0 1176.4 10204.6 1.0 101.3 -18659500.0 100.0 1175.9 10045.8 2.5 34.3 -705417.0 100.0 842.4 CR_6 617.2 0.1 16.2 ∗5.6 617.2 0.1 14.3 608.3 0.0 31.7 483.6 21.7 7.4 541.2 11.0 0.2 CR_5 ∗3.9 632.1 0.0 0.7 843.5 10.6 1794.5 632.1 0.0 0.6 510.5 45.9 1.1 632.1 0.0 0.3 CR_4 493.5 8.9 2.7 442.6 0.0 1.4 493.5 8.9 2.5 442.6 0.0 1.4 492.2 9.1 1.1 442.6 0.0 0.8 CR_3 ∗10.6 460.6 0.0 0.8 469.5 21.1 1795.3 460.6 0.0 0.8 410.5 31.0 2.8 460.6 0.0 0.3 CR_2 ∗25.3 872.2 0.0 9.9 959.9 4.4 1805.5 872.2 0.0 9.3 918.6 8.6 74.2 872.2 0.0 2.2 CR_1 3255.0 12.7 127.7 3165.9 6.9 27.1 3255.0 12.7 117.7 3165.9 6.9 25.1 3181.1 14.6 37.3 3022.6 11.1 8.1 PT_1 ∗8.6 ∗1.7 54840.4 12.0 33.9 62035.0 0.0 2.3 54323.4 12.8 4.2 56182.9 9.4 1.0 AI_1 3762.4 4.4 134.0 3760.7 4.4 27.3 3762.4 4.4 139.8 3760.7 4.4 27.0 3702.1 5.9 20.5 3686.5 6.3 11.6 AI_3 6750.9 4.7 1176.7 6805.2 3.7 246.6 6750.9 4.7 1177.2 6805.2 3.7 225.1 6422.3 9.3 24.4 6465.4 8.5 39.1 AI_4 19444.4 3.7 203.8 19805.5 0.9 35.6 19444.4 3.7 209.7 19805.5 0.9 33.9 19122.0 5.3 7.8 19235.3 3.7 5.5 AI_2 ∗19.8 2616.8 17.5 26.0 2980.7 6.9 449.2 2616.8 17.5 24.8 2852.1 10.9 624.3 2598.6 18.1 9.1 VN_1 16800.0 4.9 25.4 ∗35.4 16800.0 4.9 25.6 15596.8 0.1 467.8 16703.8 5.4 15.2 15481.3 0.8 12.2 SP_1 9545.1 1.1 95.5 9321.3 2.1 1812.3 9545.1 1.1 95.0 9321.3 2.1 1811.1 9376.2 2.9 16.4 9216.7 3.2 4.5 OM_3 355.6 24.4 2.9 307.4 14.2 1.4 355.6 24.4 3.1 307.4 14.2 1.5 335.6 28.6 1.1 300.7 16.1 0.6 OM_1 962.0 1.1 65.5 889.8 3.6 214.1 962.0 1.1 67.1 889.8 3.6 214.6 918.3 5.6 25.8 795.7 13.8 35.5 OM_2 ∗3600.3 259.1 0.0 28.1 ∗3600.3 259.1 0.0 26.7 267.5 10.0 103.1 257.8 0.5 3.8 LC_1 19686.7 3.8 248.7 20276.0 0.5 7.6 19686.7 3.8 246.5 20276.0 0.5 7.6 19475.6 4.8 11.2 20184.8 1.0 1.7 LC_2 8018.9 4.7 533.9 7696.7 8.3 58.5 8018.9 4.7 533.9 7696.7 8.3 58.9 7226.3 14.1 25.7 7519.8 10.4 22.7 SM_6 16469.9 2.8 30.7 16469.9 1.9 30.2 16469.9 2.8 30.9 16469.9 1.9 30.2 16431.2 3.0 2.4 16431.2 2.1 2.1 SM_2 27393.9 2.9 45.8 27672.1 0.7 2020.6 27393.9 2.9 46.1 27672.1 0.7 2021.0 27115.2 3.9 7.2 27763.7 0.4 63.7 SM_4 22018.0 2.9 14.3 22156.8 1.0 23.1 22018.0 2.9 13.9 22156.8 1.0 23.1 21772.4 4.0 2.1 22098.1 1.3 1.8 SM_5 10394.6 1.5 35.6 10002.6 2.8 39.4 10394.6 1.5 35.8 10002.6 2.8 39.3 9704.5 8.0 2.1 10130.1 1.6 1.5 SM_3 54833.9 4.3 1818.2 54013.8 5.8 1686.9 54833.8 4.3 2279.9 54013.7 5.8 1502.0 54637.6 4.6 71.4 52799.9 7.9 82.4 SM_1 132377.0 2.7 3463.2 131061.0 2.8 3283.8 132541.0 2.6 2410.0 131207.0 2.7 2833.8 130469.0 4.1 257.5 129632.0 3.9 466.9 CA_2 ∗621.7 243.5 7.6 21.7 ∗3600.4 243.5 7.6 20.7 ∗2400.4 239.2 9.2 4.8 AG_2 2282.6 6.7 13.1 2132.8 1.0 1.9 2282.6 6.7 12.4 2132.8 1.0 1.9 2043.0 16.5 7.6 2132.8 1.0 0.7 AG_1 2550.4 6.3 2452.3 2558.7 5.0 2398.6 2575.7 5.3 2443.1 2558.8 4.9 2397.4 2399.4 11.8 165.8 2351.8 12.6 1071.1 AG_4 5720.9 1.9 837.3 5505.3 4.2 621.3 5720.9 1.9 838.5 5505.3 4.2 626.2 5559.1 4.7 61.2 5184.0 9.8 210.1 AG_3 32647.5 2.7 3272.7 32094.6 4.3 3285.5 32645.5 2.7 3348.7 32087.0 4.3 3271.9 31195.1 7.0 260.0 31793.4 5.2 140.0 AB_1 513.7 3.5 44.4 500.4 0.1 4.2 513.7 3.5 44.3 500.4 0.1 4.1 507.1 4.7 6.3 500.4 0.1 1.7 AB_2 ∗1165.2 ∗867.6 ∗3601.7 6944.2 3.0 980.5 6987.3 2.8 745.5 6953.4 2.9 92.2 3.B. Result Tables 71 Instance Name H-BAP H-BAP-IF H-BAP-IE Scenario 2 Scenario 3 Scenario 2 Scenario 3 Scenario 2 Scenario 3 ZGAP(%) T(s) Z GAP(%) T(s) Z GAP(%) T(s) Z GAP(%) T(s) Z GAP(%) T(s) Z GAP(%) T(s). VV_2 3244.2 0.3 2529.1 3204.8 1.4 3600.8 3240.2 0.5 2529.5 3204.9 1.4 3600.8 3243.1 0.4 60.4 3230.3 0.6 120.3 VV_1 61597.9 0.1 1330.3 -69175900.0 100.0 1788.8 61597.9 0.1 1520.7 -69175900.0 100.0 1789.1 61596.8 0.1 19.1 60209.9 1.2 1972.9 LO_2 60.4 8.2 1495.2 51.3 0.0 32.7 60.4 8.2 1471.7 51.3 0.0 32.9 60.4 8.2 60.2 51.3 0.0 4.0 LO_1 ∗2871.4 -11239700.0 100.0 1574.3 ∗3602.3 -11239700.0 100.0 1561.0 ∗2400.9 -481437.0 100.0 906.0 BH_1 41637.1 1.9 1852.4 40807.2 0.1 73.8 41592.6 2.0 1856.3 40807.2 0.1 75.4 40791.4 3.9 1156.9 38246.0 6.4 198.0 BH_2 76362.3 1.0 2263.3 -218294000.0 100.0 653.6 76362.3 1.0 2272.3 -218294000.0 100.0 653.6 75697.2 1.8 438.8 73174.9 1.8 212.6 CH_1 1135.0 16.9 3601.6 -393847.0 100.0 1224.4 1147.9 16.0 3601.4 -393847.0 100.0 1202.6 1120.4 18.0 1079.6 -53232.5 100.0 743.9 BC_1 55736.7 15.5 636.7 51320.0 21.4 3407.1 55736.7 15.5 635.9 50416.3 22.8 3410.0 58771.4 10.8 460.2 ∗385.3 DE_1 ∗2964.4 ∗1904.8 ∗3601.7 -27167400.0 100.0 2725.2 6316.2 5.7 1182.6 -2249420.0 100.0 495.0 ∗No feasible solution was found. 72 Bibliography Bibliography R. Bai. An Investigation of Novel Approaches For Optimising Retail Shelf Space Allocation. PhD Thesis. The University of Nottingham, 2005. T. Bianchi-Aguiar, E. Silva, L. Guimaraes, M. A. Carravilla, and J. F. Oliveira. Problem instances for the shelf space allocation problem with family grouping, December 2014. URL http://fe.up.pt/~mtbaguiar/BAP. N. Borin, P. W. Farris, and J. R. Freeland. A model for determining retail product category assortment and shelf space allocation. Decision Sciences, 25(3):359–384, 1994. M. Castelli and L. Vanneschi. Genetic algorithm with variable neighborhood search for the optimal allocation of goods in shop shelves. Operations Research Letters, 42(5):355 – 360, 2014. ISSN 0167-6377. P. Chandon, J. W. Hutchinson, E. T. Bradlow, and S. H. Young. Does In-Store Marketing Work ? Effects of the Number and Position of Shelf Facings on Brand Attention. Journal of Marketing, 73(6):1 – 17, 2009. M. Corstjens and P. Doyle. A Model for Optimizing Retail Space Allocations. Management Science, 27(7):822–833, 1981. R. C. Curhan. The Relationship Between Shelf Space and Unit Sales in Supermarkets. Journal of Maketing Research, 9(4):406–412, 1972. P. Desmet and V. Renaudin. Estimation of product category sales responsiveness to allocated shelf space. International Journal of Research in Marketing, 15(5):443 – 457, 1998. E. D. Dolan and J. J. Moré. Benchmarking optimization software with performance profiles. Mathematical Programming, 91(2):201–213, 2002. X. Drèze, S. J. Hoch, and M. E. Purk. Shelf management and space elasticity. Journal of Retailing, 70(4):301 – 326, 1994. H. Gajjar and G. Adil. Heuristics for retail shelf space allocation problem with linear profit function. International Journal of Retail &Distribution Management, 29(2):144–155, 2011. H. N. Geismar, M. Dawande, B. Murthi, and C. Sriskandarajah. Maximizing revenue through two-dimensional shelf-space allocation. Production and Operations Management, 2014. Available online. J. M. Hansen, S. Raut, and S. Swami. Retail shelf allocation: A comparative analysis of heuristic and meta-heuristic approaches. Journal of Retailing, 86(1):94–105, 2010. M. A. Hariga, A. Al-Ahmari, and A.-R. A. Mohamed. A joint optimisation model for inventory replenishment, product assortment, shelf space and display area allocation decisions. European Journal of Operational Research, 181(1):239 – 251, 2007. Bibliography 73 A. H. Hübner and H. Kuhn. Retail shelf space management model with space-elastic demand and consumer-driven substitution effects. Working paper available at SSRN, 2011. A. H. Hübner and H. Kuhn. Retail category management: State-of-the-art review of quantitative research and software applications in assortment and shelf space management. Omega, 40(2):199 – 209, 2012. H. Hwang, B. Choi, and M.-J. Lee. A model for shelf space allocation and inventory control considering location and inventory level effects on demand. International Journal of Production Economics, 97(2):185 – 195, 2005. M. Kurtulus and L. B. Toktay. Category captainship practices in the retail industry. In Retail Supply Chain Management: Quantitative Models and Empirical Studies, pages 79–98. Springer, 2009. A. Lim, B. Rodrigues, and X. Zhang. Metaheuristics with Local Search Techniques for Retail Shelf-Space Optimization. Management Science, 50(1):117–131, 2004. C. C. Murray, D. Talukdar, and A. Gosavi. Joint optimization of product price, display orientation and shelf-space allocation in retail category management. Journal of Retailing, 86(2):125 – 136, 2010. Special Issue: Modeling Retail Phenomena. T. Öncan, I. K. Altinel, and G. Laporte. A comparative analysis of several asymmetric traveling salesman problem formulations. Computers &Operations Research, 36(3): 637 – 654, 2009. R. Pieters, M. Wedel, and R. Batra. The Stopping Power of Advertising: Measures and Effects of Visual Complexity. Journal of Marketing, 74(5):48–60, 2010. Y. Pochet and L. A. Wolsey. Production Planning by Mixed Integer Programming (Springer Series in Operations Research and Financial Engineering). Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2006. R. A. Russell and T. L. Urban. The location and allocation of products and product families on retail shelves. Annals of Operations Research, 179(1):131–147, 2010. T. L. Urban. An inventory-theoretic approach to product assortment and shelf-space allocation. Journal of Retailing, 74(1):15 – 35, 1998. M.-H. Yang. An efficient algorithm to allocate shelf space. European Journal of Operational Research, 131(1):107–118, 2001. M.-H. Yang and W.-C. Chen. A study on shelf space allocation and management. International Journal of Production Economics, 61(510):309–317, 1999. F. S. Zufryden. A Dynamic Programming Approach for Product Selection and Supermarket Shelf-Space Allocation. Journal of the Operational Research Society, 37(4):413–422, 1986. Chapter 4 Replicating Shelf Space Allocation Solutions Across Retail Stores Teresa Bianchi-Aguiar∗·Maria Antónia Carravilla∗·José F. Oliveira∗ Abstract Consumer-centric merchandising policies require store-specific shelf-space planning to better account for local consumer demand. Nevertheless, the high number of stores and the time spend developing merchandising plans force retailers to cluster the stores, and develop generic shelf space plans. In this paper we introduce the novel problem of transforming generic cluster-based shelf space plans into store-specific plans, a process that is called Replication in this paper. Two mathematical programming formulations are presented to address the Shelf Space Replication Problem, with different levels of practical details. The formulations use a novel inventory-related objective function that balances the products’ inventory level in order to trigger joint shelf replenishments. Based on the formulations, a mathematical programming-based heuristic was also developed. Both approaches were tested using real data from a European Food Retailer that motivated this project, proving their suitability for practical use. Keywords Retail operations ·Shelf space allocation ·Replicating solutions ·Store-specific planograms ·MIP-based heuristic 4.1. Introduction In today’s increasing competitive environment, retailers strive for customer satisfaction and operational efficiency, aiming to improve the stores’ financial performance. To achieve such goal, retail organizations are moving towards demand driven initiatives, with the lemma “every sale counts”, while trying to optimize their two most expensive resources: space and inventory. Shelf space planning is a mid-term operational planning activity that defines the allocation of the products on the shelves for a period of 6-12 months. Two major goals are associated with this activity: maximize selling space effectiveness and tighter inventory control. As a matter of fact, marketing studies have long proved the positive influence of ∗INESC TEC and Faculty of Engineering, University of Porto, Porto, Portugal 75 82 Chapter 4. Replicating Shelf Space Allocation Solutions Across Retail Stores products and no more than one product on each shelf. A small deviation vis allowed between the products of each alignment. If one product is placed in more than one shelf, it should also be vertically aligned, with the same number of facings in all shelves. There are also Qminimum space share requirements to consider (indexed by u∈ Q. The parameters and sets associated with the products are the following: ai(bi) width (height) of product i, li(ui) lower bound (upper bound) on the number of facings of product i, sitotal stock of product ifor each facing, Kinumber of shelves where product iis, Nkset of products of level k, ordered by order of appearance, NL m(NR m) set of products of each left (right) alignment m, quminimum percentage of space to allocate to the products belonging to the space share requirement u, NQ uset of products of each minimum space share requirement u. Under the given operating conditions, the decisions to be made for each product are: the number of facings to be displayed on each shelf and its horizontal location. Both decisions are determined while ensuring that the display area is fully occupied (full shelf merchandising policy). The objective is balancing days-supply, assuming inventory-dependent and shelf-dependent demand. This new problem will hereafter be called SSRP – Shelf Space Replication Problem. 4.3. Model Development This section presents the formulation proposed for the SSRP, as described in the previous section. For clarification purposes, we present two versions of the formulation: a simplified version that only considers one segment (Single-Segment Shelf Space Replication Model), and a more complex version with multiple segments (Multi-Segment Shelf Space Replication Model). The necessary decision variables are presented along the section; however, two sets of decision variables define the overall problem solution (common to both formulations): Withe integer number of facings of product i∈ N on each of the shelves where the product is located, Xithe continuous horizontal location of product i∈ N, measured from the lower-left corner of the planogram to the lower-left corner of the first facing of the product. Note that both the Wand the Xvariables do not distinguish between shelf levels. This fact is because products are required to have a rectangular shape, which imposes the same number of facings in all shelves where the product is, and to be vertically aligned. Before presenting the two formulations, we will first define the objective function for balancing 4.3. Model Development 83 days-supply. 4.3.1 Objective Function The objective of the SSRP is balancing days-supply values across the planogram, using equation (4.1) provided in the previous section. We consider a goal programming-based approach, where the idea is to minimize the deviation of Ri, the days-supply value of each product i, from a common days-supply goal R0.R0is determined to be the average of Rivalues, and the objective function is similar to the variance (or the squared standard deviation). This objective function is provided in equation (4.2). minimize P=X i∈N (Ri−R0)2(4.2) where : R=Pj∈N Rj N The days-supply of each product iis defined in terms of the product demand, Di, which in turn depends on the space allocated to it. A diminishing return polynomial function (resembling a “s-shaped curve”) has been widely used by several researchers in the literature to model space dependent demand. Similarly to Yang and Chen [1999] and Lim et al. [2004], we consider that retailers prefer to operate on the linear portion of the S-shaped curve, by defining minimum and maximum display quantities that place the demand on this linear part. In accordance, the demand can be determined by the linear equation (4.3), where D0 iis the base demand (for the minimum display quantity), γiand αkare scale parameters that reflect the variation in demand with respect to the number of facings of product iand to the shelf kwhere the product is placed (respectively) and ηiis an additional parameter aggregates the shelf impact in case the product is placed on more than one shelf. Di=ηi·(D0 i+γi·Ki·Wi) (4.3) where : ηi=Pk∈K:i∈Nkαk Ki This objective function does not incorporate the time effect on demand and consequently, it does not consider a decreasing demand effect as the shelf inventory is being purchased. We consider instead that the minimum stock between shelf replenishments is enough to accommodate at least one item on each product facing, ensuring that the product is always fully visible. The days-supply values (Ri) are at last determined by equation (4.4). Ri=si·Ki·Wi ηi·(D0 i+γi·Ki·Wi)(4.4) 4.3.1.1 Alternative Objective Function Figure 4.4 shows the days-supply values of two instances with 10 products, where each product is associated with two values: the days-supply value when the product has a min- 84 Chapter 4. Replicating Shelf Space Allocation Solutions Across Retail Stores imum display quantity (in dark gray) and the days-supply value when it has the optimal display quantity (in black). The optimal days-supply values were obtained using objective function (4.2) and considering a single capacity constraint that ensured that the entire space was fully stocked. Both instances are similar, with the exception of one product that has a significantly higher minimum days-supply value in the second instance. The figure shows that, while in the first instance days-supply values are fairly close to each other, in the second instance they were influenced by the low-sales product (that increased the average), resulting in more spread values. Note that this situation occurs very often in shelf space allocation because of long-tale products. Moreover, the family alignments also constraint the products’ facings and may lead to extreme differences in terms of days-supply values. 0 5 10 15 20 25 30 35 40 12345678910 Ri(days-sypply) i (product) R with W = minimum display quantity R with optimal W 0 5 10 15 20 25 30 35 40 12345678910 Ri(days-sypply) i (product) R with W = minimum display quantity R with optimal W Figure 4.4 – Days-supply values of two instances with the optimal values obtained using objective function (4.2) To overcome this fact, we propose an alternative objective function. Consider an iterative approach to the problem, in particular, an improvement heuristic which uses the minimum display quantities (minimum days-supply values) as the initial solution, and iteratively increases the product facings one at a time, choosing at each iteration the product with the lowest minimum days-supply value. The heuristic stops when the capacity is met or when there are no more products that can increase their facings due to the remaining constraints. This heuristic can be interpreted as the problem of maximizing the minimum days-supply values among the products. However, if one product is forced to have a low days-supply value, the iterative approach continues to maximize the minimum of the remaining products (as opposed to the problem of maximizing the minimum value, that does not optimize the remaining values). At the end, all products have close days-supply values, except the ones with high minimum days-supply values (or the ones that have to ensure alignments, when applicable). This is confirmed in Figure 4.5, where the same instances were solved with this improvement heuristic. The alternative objective function tries to mimic this behavior. Consider the following binary decision variables, which correspond to a partition of variables Wiaccording to their range of facings (ui): Wip (=1) if product i∈ N has the pth facing on the planogram, p=1,...,ui. 4.3. Model Development 85 0 5 10 15 20 25 30 35 40 12345678910 Ri(days-sypply) i (product) R with W = minimum display quantity R with optimal W 0 5 10 15 20 25 30 35 40 12345678910 Ri(days-sypply) i (product) R with W = minimum display quantity R with optimal W Figure 4.5 – Days-supply values of the same two instances of Figure 4.4 with the optimal values obtained using the improvement heuristic The parameters Rip are associated with Wip and consist of the days-supply value of each product iprior to introducing the pth facing (note that Rip is a parameter because it does not depend any more on the number of facings). We mimic the iterative procedure by setting variables Wip to one by descending order of the replenishment frequency Fip =1/Rip (for p=1, Fip >max{Fit|t=2,...,ui}), using the linear objective function (4.5). maximize X i∈N ui X p=1 Fip ·Wip (4.5) where : Wi= ui X p=1 Wip,∀i∈ N (4.6) One drawback from this objective function is the fact that the model may not set the products by decreasing order of Fip if there are severe differences in the products’ width (if product iis twice the width of product j, then it is more advantageous to give two facings of product jinstead of one to product i, as long as Fjp +Fj,p+1>Fip). This is not a common case when replicating planograms where the products belong to the same category. Nevertheless, when that happens, it can be compensated with an extra coefficient on the objective function, which increases the Fip value of the largest products. 4.3.2 Single-Segment Shelf Space Replication Model In this subsection we formulate a simplified version of the replication problem where the segments are not considered, with the assumption that the planogram has only one segment. Besides Wi,Wip and Xi, consider the following decision variables: Lishelf length assigned to product i∈ N on each of the shelves where the product is located, XL mthe horizontal location of left alignment m∈ ML, 86 Chapter 4. Replicating Shelf Space Allocation Solutions Across Retail Stores XR mthe horizontal location of right alignment m∈ MR. The Single-Segment Replication Model can be represented by the objective function present in equation (4.5) and the following remaining linear constraints: Ki·Wi≤ui,∀i∈ N (4.7) Ki·Wi≥li,∀i∈ N (4.8) Li−aiWi≥0,∀i∈ N (4.9) X i∈Nk Li=W,∀k∈ K (4.10) Xi=X j∈Nk:j<i Lj,∀k∈ K,i∈ Nk(4.11) XL m−v≤Xi,∀m∈ ML,i∈ NL m(4.12) XL m≥Xi,∀m∈ ML,i∈ NL m(4.13) XR m+v≥Xi+Li,∀m∈ MR,i∈ NR k(4.14) XR m≤Xi+Li,∀m∈ MR,i∈ NR k(4.15) X i∈Nu (ai·Ki·Wi)≥qu,∀u∈ Q (4.16) Wi∈N0,∀i∈ N (4.17) Li,Xi≥0,∀i∈ N (4.18) XL m≥0,∀m∈ ML(4.19) XR m≥0,∀m∈ MR(4.20) Constraints (4.7) and (4.8) impose the lower and upper bounds of the number of facings. Note that Wionly specifies the number of facings on each of the shelves where the product is placed, and it has to be multiplied by the number of shelves. Constraints (4.9) ensure that the shelves have enough space reserved for product facings. (4.10) are capacity constraints that additionally guarantee the Full Shelf Merchandising policy. As the shelves are fully occupied by the products, constraints (4.11) identify the horizontal location of the products as the sum of the lengths from the preceding products. These constraints also guarantee that the products have the desired sequence. The left and right alignments (with the tolerance v) are preserved by constraints (4.12)-(4.13) and (4.14)-(4.15), respectively. Constraints (4.16) introduce the space share requirements and the remaining constraints ensure the integrality and non-negativity properties of the variables. 4.3.3 Multi-Segment Shelf Space Replication Model In the presence of more than one segment, the single-segment formulation may not be suitable as it does not take into account the non-existing shelves and the misalignments throughout the levels. Therefore, we have developed a multi-segment extension, where the decisions regarding the product shelf space and product location consider the existence of segments. Accordingly, consider the following additional variables: 4.3. Model Development 87 Lio shelf length assigned to product i∈ N in segment o∈ O, on each of the levels where the product is located, Yio (=1) if product i∈ N is located in segment o∈ O, Xio the continuous horizontal location of product i∈ N in segment o∈ O, measured from the lower-left corner of the planogram. In this extension, constraints (4.10) and (4.11) are replaced by: X i∈Nk Lio =wok ·eok,∀o∈ O,k∈ K (4.21) Lio ≤Yio ·wok ·eok,∀o∈ O,k∈ K,i∈ Nk(4.22) Yin +Yi+1,o≤1,∀o∈ O,n∈ O :n>o,k∈ K,i∈ N− k(4.23) Xio =X n∈O:n<o wnk +X j∈Nk:j<i Lio,∀o∈ O,k∈ K,i∈ Nk(4.24) Yio +Yi,nextok ≤1+cok,∀o∈ O :nextok >0,k∈ K,i∈ Nk(4.25) bi·Yio ≤hok,∀o∈ O,k∈ K,i∈ Nk(4.26) Xi≤Xio +W·(1−Yio),∀i∈ N,∀o∈ O (4.27) Xi≥Xio −X n∈O:n<o Lin −W·(1−Yio),∀i∈ N,∀o∈ O (4.28) Li=X o∈O Lio,∀i∈ N (4.29) Lio,Xio ≥0,∀i∈ Nk,o∈ O (4.30) Yio ∈ {0,1},∀i∈ Nk,o∈ O (4.31) Note that the sets N− khave all the products from each level kexcept the last. Constraints (4.21) are similar to the previous constraints (4.10) and ensure that the full width of the existing shelves is occupied by the products. Constraints (4.22) relate variables Lio and Yio by stating that the length Lio is equal to zero in case product iis not assigned to segment o. These constraints also guarantee that a product is not assigned to a shelf that does not exist in the store. The product sequence of each level is ensured by constraints (4.23) and (4.24). The first set of constraints ensures the sequence between segments and the second set ensures the sequence inside each segment. The latter also specifies the horizontal location of each product inside each segment. Note that this variable only has a meaningful value if the product is part of the segment. Constraints (4.25) do not allow a product to be on both shelves kand nko in two cases: if the shelves are not consecutive, or if the shelves are misaligned. Constraints (4.26) prevent products from being placed on shelves where they do not fit (because of their height), and finally, the values of Liand Xiare specified with regard to Lio and Xio, respectively. The consideration of segments increases the complexity of the formulation, as we will analyze later, during the computational results. Its motivation is the necessity to take into account the non-existing shelves and misalignments thought the levels, that impose addi- 88 Chapter 4. Replicating Shelf Space Allocation Solutions Across Retail Stores tional constraints to the product’s placements. However, potential benefit may be achieved by aggregating the segments that have similar shelf placements. In the more extreme case, when all segments are equal, we obtain the Single-Segment SSRP formulation. Therefore, both the Single and Multi-Segment formulations have practical relevance. 4.4. MIP-based Heuristic The SSRP is a practical and relevant operational problem in retail and it is crucial to develop methods that can allow its use in practice. Because the SSRP is a mid-term operational planning activity, retailers do not need real time solutions obtained in less than a few seconds. Nevertheless, the high number of planograms that Space Managers have to handle every year is not compatible with high generation times and the European Food Retailer that motivated this work defined “the time to have a cup of coffee” as the maximum period of time space managers would be willing to wait for the solutions. This section starts by describing the methodology currently used by the Space Managers at the European Food Retailer. Then, we propose a MIP-based Heuristic for the problem, based on the formulation presented in section 4.3. 4.4.1 Methodology Currently Used Replicating planograms is a manual and time consuming activity, mainly because of the different product family alignments that need to be taken into consideration when placing the products. The role planogram is, by definition, smaller than the remaining planograms, and the ultimate decision that Space Managers have to make is on the number of facings that each product will have. Nevertheless, aligning products is most of the time a trial and error activity, and managers try to give one extra facing to a product, take one facing from of a product or spread out the facings, so that all alignments are strictly fulfilled. The company has a space planning software that assists in this task by providing realistic views of the shelves to where the products are drag and dropped to create the planograms. This software also has powerful analysis tools. In general terms, the process is as follows. Space Managers start by copying the role planogram to the new space, which leaves an empty space to fill. Product facings are then iteratively increased based on the product’s days-supply values, in an approach similar to the iterative procedure described in section 4.3.1. The process continuously alternates between shelves for preserving the alignments. The days-supply values are automatically computed by the space planning software and are only based on past sales. Therefore, the company does not explicitly take into account the impact that the space has on demand. Moreover, the high number of alignments strongly complicates the process, making it difficult to balance days-supply values. 4.4.2 MIP-based Heuristic Preliminary experiments showed us that by solving the problem using a commercial MIP solver (ILOG CPLEX in our implementation) we were able to generate optimal solutions 4.4. MIP-based Heuristic 89 within the expected period, but only for small sized instances. Therefore, our goal when developing the MIP-based heuristic was to make sure that the approach was scalable, especially in the multi-segment case. Table 4.1 presents the number of decision variables and constraints of both formulations (single and multi-segment) with regard to the problem parameters. Two parameters arise as the most important: the number of segments and the number of products. However, we can also relate the number of segments to the number of products (or vice versa) because the more space is available, the more products the assortment has. Table 4.1 – Size of the formulations as a function of the problem parameters Single-segment SSRP Multi-segment SSRP # Decision Variables PiuiPiui # Constraints 3N+2PmNR m+2PmNL m+Q4N+2PmNR m+2PmNL m+Q +PkNk+K+O(K+2N+PkNk+1 2OPkNk) Figure 4.6 depicts the general idea of the proposed MIP-based heuristic which has three main steps. The first step originates an initial solution for the problem with only the minimum display quantities for the products. The second step iteratively adds the remaining product facings to the planogram until no more space is available. At last, the third step tries to improve the solution by allowing the removal and insertion of new facings. As it is possible to see, this MIP-based heuristic is inspired in the methodology currently used by space managers at Sonae MC. Initial Solution Planogram Filling Planogram Improvement ... ... Figure 4.6 – Steps of the MIP-based Heuristic (for one shelf) Technically, this approach is an integration of two well-known MIP-based improvement heuristics: fix-and-optimize (Pochet and Wolsey [2006]) and local branching (Fischetti and Lodi [2003]). In each iteration, we solve the SSRP formulation with the Wip variables partially constrained in one of two different ways: a subset of the variables are fixed to the values obtained in the incumbent solution (fix-and-optimize), or a limited number of changes can be made to the values obtained in the incumbent solution (local branching). Figure 4.7 depicts the evolution of Wip variables throughout the iterations. The variables 90 Chapter 4. Replicating Shelf Space Allocation Solutions Across Retail Stores are divided into Ksubsets Gk, depending on the products on each shelf k:Wip ∈ Gk:i∈ Ni. Each set has the variables sorted by increasing days-supply values (Rip), so that the products with low days-supply values will be considered first. Within each subset, the first variables to be analyzed correspond to the minimum display quantities for the products (i.e. the first livariables of each product i). At each iteration, the variables in gray are the ones optimized by the formulation. The remaining ones are already fixed to zero (white variables) or to one (dark gray variables). li 1 2 ... k ... ... ... Full ... 1. Initial Solution 3. Planogram Improvement (Local Branching) 1 2 k 1 2 k 1 2 k 1 2 k Wip = 0 Wip = 1 Wip ∈ {0,1} Wip ∈ {0,1} : Max α changes 2. Planogram Filling (Fix-and-optimize) ΣΣ aiWip ≤ min(wko, empty space) ip Wip : i ∈ Nk, p ≤ Wip : i ∈ Nk, p ∈ Pi Ki ... 1 2 kLegend Figure 4.7 – State of Wip variables throughout the iterations Step 1 - Initial Solution – In the first step, the formulation is solved with the number of product facings limited to the minimum display quantities (first part of the Gksubsets), resulting in an initial, feasible, but still empty planogram. As the number of facings of each product ishould be the same across all the shelves where the product is, the number of facings is indeed limited to the first multiple of Ki, greater than or equal to li. Step 2 - Planogram Filling – In the second step, the variables considered at each iteration are limited to a portion of each subset Gk, so that the space occupied by adding those facings does not exceed a maximum length, which we defined as the minimum value between the empty space and the length of one segment. This step ends when the space available is insufficient for any extra facing, or at least one Wip variable was set to zero in all products. This iterative procedure ensures the scalability of the method, and is not expected to strongly deteriorate the solution as the variables are introduced in the formulation according to their expected order of usage. Step 3 - Planogram Improvement – In the third step, a subset Sof the Wip variables is optimized but limited to a maximum of αchanges to the values obtained in the incumbent solution (W0 ip). This improvement phase is done by adding constraint (4.32), which counts 4.5. Experimental Results 91 the number of changes on the variables and limits them to α. As the formulation would not set Wip+1to one without setting Wip first, the subset Scontains, at each time, the β variables with lowest days-supply values (Rip) previously set to one and the βvariables with the highest Rip values previously set to zero. X Wip∈S:W0 ip=1 (1−Wip)+X Wip∈S:W0 ip=0 Wip ≤α(4.32) Note that this MIP-based heuristic is valid for both formulations. The pseudocode is present in Appendix 4.A. 4.5. Experimental Results This section presents a computational study to assess this novel SSRP problem. In particular, we will focus on the suitability of the formulation and the MIP-based heuristic to solve the practical problems for which they were designed. For that purpose, we tested and validated the approaches using real data provided by the company, but some of the parameters were masked to protect the company’s confidentiality. The test data include 20 role planograms (A−T) that were replicated in three stores (1 −3). Only the first corresponds to a real store and the remaining ones were obtained by increasing one segment in store 2 and two segments in store 3 (each segment with approximately 130 cm). Table 4.2 presents the key information of each instance, namely the number of products (N), the number of segments of store 1 (O), the number of segments with different shelf placements (O0), and lastly, the number of left and right alignments (MLand MR, respectively). Note that the instances vary from 26 to 256 products and from 1 to 13 segments, with the expected positive correlation between the number of segments and the number of products. In general, role planograms have a high number of family groups which result in up to 47 alignments. The instances are available online in Bianchi-Aguiar et al. [2015]. Table 4.2 – Problem Instances Regular Planograms Irregular Planograms Instance N O O0MLMRInstance N O O0MLMR A{1,2,3}26 1 1 8 6 M{1,2,3}122 3 2 17 18 B{1,2,3}45 2 1 6 5 N{1,2,3}114 5 2 17 17 C{1,2,3}16 3 1 3 5 O{1,2,3}239 12 2 30 47 D{1,2,3}38 3 1 7 7 P{1,2,3}239 13 2 21 27 E{1,2,3}49 3 1 3 4 Q{1,2,3}154 5 3 44 43 F{1,2,3}190 3 1 20 12 R{1,2,3}172 8 3 27 33 G{1,2,3}240 3 1 32 35 S{1,2,3}256 13 4 36 33 H{1,2,3}188 5 1 12 11 T{1,2,3}156 9 5 24 39 I{1,2,3}205 6 1 12 13 J{1,2,3}107 8 1 11 10 K{1,2,3}67 9 1 10 12 L{1,2,3}171 12 1 23 23 98 Bibliography Bibliography H. Abbott and U. S. Palekar. Retail replenishment models with display-space elastic demand. European Journal of Operational Research, 186(2):586–607, 2008. R. Bai. An Investigation of Novel Approaches For Optimising Retail Shelf Space Allocation. PhD Thesis. The University of Nottingham, 2005. R. Baker and T. L. Urban. A deterministic inventory system with an inventory-leveldependent demand rate. Journal of the Operational Research Society, pages 823–831, 1988. T. Bianchi-Aguiar, M. A. Carravilla, and J. F. Oliveira. Problem instances for the shelf space replication problem, February 2015. URL http://fe.up.pt/~mtbaguiar/ SSRP. N. Borin, P. W. Farris, and J. R. Freeland. A model for determining retail product category assortment and shelf space allocation. Decision Sciences, 25(3):359–384, 1994. P. Chandon, J. W. Hutchinson, E. T. Bradlow, and S. H. Young. Does In-Store Marketing Work ? Effects of the Number and Position of Shelf Facings on Brand Attention. Journal of Marketing, 73(6):1 – 17, 2009. M. Corstjens and P. Doyle. A Model for Optimizing Retail Space Allocations. Management Science, 27(7):822–833, 1981. R. C. Curhan. The Relationship Between Shelf Space and Unit Sales in Supermarkets. Journal of Maketing Research, 9(4):406–412, 1972. P. Desmet and V. Renaudin. Estimation of product category sales responsiveness to allocated shelf space. International Journal of Research in Marketing, 15(5):443 – 457, 1998. X. Drèze, S. J. Hoch, and M. E. Purk. Shelf management and space elasticity. Journal of Retailing, 70(4):301 – 326, 1994. M. Fischetti and A. Lodi. Local branching. Mathematical programming, 98(1-3):23–47, 2003. J. M. Hansen, S. Raut, and S. Swami. Retail shelf allocation: A comparative analysis of heuristic and meta-heuristic approaches. Journal of Retailing, 86(1):94–105, 2010. M. A. Hariga, A. Al-Ahmari, and A.-R. A. Mohamed. A joint optimisation model for inventory replenishment, product assortment, shelf space and display area allocation decisions. European Journal of Operational Research, 181(1):239 – 251, 2007. A. H. Hübner and H. Kuhn. Retail shelf space management model with space-elastic demand and consumer-driven substitution effects. Working paper available at SSRN, 2011. Bibliography 99 A. H. Hübner and H. Kuhn. Retail category management: State-of-the-art review of quantitative research and software applications in assortment and shelf space management. Omega, 40(2):199 – 209, 2012. H. Hwang, B. Choi, and M.-J. Lee. A model for shelf space allocation and inventory control considering location and inventory level effects on demand. International Journal of Production Economics, 97(2):185 – 195, 2005. J. Irion, J.-C. Lu, F. a. Al-Khayyal, and Y.-C. Tsao. A hierarchical decomposition approach to retail shelf space management and assortment decisions. Journal of the Operational Research Society, 62(10):1861–1870, 2011. JDA. Jda planogram generator. JDA Software Group, Inc., 2009. A. Lim, B. Rodrigues, and X. Zhang. Metaheuristics with Local Search Techniques for Retail Shelf-Space Optimization. Management Science, 50(1):117–131, 2004. C. C. Murray, D. Talukdar, and A. Gosavi. Joint optimization of product price, display orientation and shelf-space allocation in retail category management. Journal of Retailing, 86(2):125 – 136, 2010. Special Issue: Modeling Retail Phenomena. Y. Pochet and L. A. Wolsey. Production Planning by Mixed Integer Programming (Springer Series in Operations Research and Financial Engineering). Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2006. R. A. Russell and T. L. Urban. The location and allocation of products and product families on retail shelves. Annals of Operations Research, 179(1):131–147, 2010. T. L. Urban. An inventory-theoretic approach to product assortment and shelf-space allocation. Journal of Retailing, 74(1):15 – 35, 1998. M.-H. Yang and W.-C. Chen. A study on shelf space allocation and management. International Journal of Production Economics, 61(510):309–317, 1999. F. S. Zufryden. A Dynamic Programming Approach for Product Selection and Supermarket Shelf-Space Allocation. Journal of the Operational Research Society, 37(4):413–422, 1986. Chapter 5 Using Analytics to Enhance Shelf Space Management in a Food Retailer Teresa Bianchi-Aguiar∗·Elsa Silva∗·Luis Guimarães∗· Maria Antónia Carravilla∗·José F. Oliveira∗· João Günther Amaral†·Jorge Liz†·Sérgio Lapela† Abstract This paper describes a collaboration project with the Portuguese leading food retailer which addresses shelf space planning, for the allocation of products on shelves. Prior to this project, the shelf space planning process was very time consuming, with an empirical use of space elasticities, lacking formal performance evaluation criteria, and heavily dependent on the space managers’ experience. Our challenge was to bring analytical methods into the practice in order to enhance shelf space management in three axes: process automation, space optimization, and image standardization, without disrupting (but somehow questioning) the company’s policies. This led to the creation of GAP, a decision support system that is today used on a daily basis by the space management team of the company. We developed a modular Operations Research (OR)-approach that systematically applies tailor-made mathematical programming models that were combined with heuristics to improve its efficiency. On top of the algorithmic advances, one of the most relevant features of GAP is its flexibility to incorporate different types of merchandising rules, allowing the company to test several strategies for the product allocation. Nevertheless, it goes beyond the straightforward implementation of merchandising rules and it trades-offcustomization with optimization. Keywords Retail operations ·Shelf space allocation ·MIP-based heuristic 5.1. Introduction Sonae MC is one of the biggest Portuguese companies (ranked the 4th in 2014, with 3.33 billion annual sales) that operates a food retail business in Portugal. It is one of the core ∗INESC TEC and Faculty of Engineering, University of Porto, Rua Dr. Roberto Frias, s/n 4200-465 Porto, Portugal †Sonae MC, Lugar do Espido, Via Norte, 4470-177 Maia, Portugal 101 102 Chapter 5. Using Analytics to Enhance Shelf Space Management in a Food Retailer businesses of the Sonae Group, which also acts in other areas such as specialized retail (selling sports goods, fashion and electronics), shopping centers and telecommunications. Its brand Continente is the country’s food retail market leader, and has been considered one of the most trusted brands in Portugal over the last 13 years. The company is a benchmark in the Portuguese market, after having launched the country’s first hypermarket in 1985. Today it has a network of 478 stores (and additionally 162 stores under franchising) covering the entire country, with three major formats: Continente Bom dia, convenience stores with average sales areas of 800 m2(8,611 square feet); Continente Modelo, supermarkets located in medium sized population centers with an average of 2,000 m2(21,528 square feet); and, finally, Continente, hypermarkets located in prime locations and offering an extensive and varied range of products and services with average sales areas of 9,000 m2(96,875 square feet). In total, Sonae MC has a sales area of 595,000 m2(6,404,527 square feet) and its strategy is to grow its convenience channel and to look for international growth opportunities. Sonae MC is aware of the impact of in-store planning on customer satisfaction, sales effectiveness and operations efficiency. In particular, it believes that a clever product organization on the shelves leads to higher visibility, consumer awareness and demand for the products, as well as reduced inventory holding and handling costs. However, the short product life cycles, the increasing number of products available and the progressively higher number of stores has lead to a continuous need for shelf space planning which turned the process more and more challenging for the company. Innovation is a priority at Sonae MC, which is constantly seeking for opportunities to improve their products, services and processes. This paper describes the development, implementation and impact of an OR-based approach to better plan the allocation of products on the shelves. It is the result of a collaborative work between the Information Systems and Innovation Department (ISI) and the Space Planning Department (SP) of Sonae MC, and a group of researchers from the Industrial Engineering and Management Department of the Faculty of Engineering of the University of Porto (FEUP). Prior to this work, the shelf space planning process was very time consuming, with an empirical use of space elasticities, lacking formal performance evaluation criteria and heavily dependent on the space managers’ experience. The challenge consisted of incorporating analytical methods into the practice in order to automate the process, improve the return on space, and reduce stockouts and inventory costs, without disrupting (but somehow questioning) the company’s policies. Based on these objectives, three axes were defined for the project: Process Automation, Space Optimization, and Image Standardization. The resulting Decision Support System (DSS) is called GAP and is today used by space managers on a daily basis to automatically generate shelf space plans. GAP is developed on top of a modular architecture and systematically applies tailor-made mathematical programming models, combined with heuristics, to derive the best allocation of products on the shelves. The key benefit of the approach is its flexibility to incorporate different types of merchandising (placement) rules, including hierarchies of product families, family precedences, display shapes, and special locations. This customization level allows space managers to control the entire process and to test different strategies for allocating the products. Moreover, GAP goes beyond the straightforward implementation of merchandising rules, 5.2. Shelf Space Management at Sonae MC 103 hence combining customization with optimization. The remainder of this paper is structured as follows. We start by describing how shelf space is managed, firstly in Sonae MC (section 5.2) and secondly in a more generic perspective, both from a practical and theoretic point of view (section 5.3). GAP is presented next, in section 5.4, with a general discussion of its analytical approach and a description of the decision support system. We also offer some details about the project development that were critical for its success. The impact of the project is carefully analyzed in Section 5.5. We end with some brief concluding remarks emphasizing the fact that we are presenting a generic approach that is suitable for other retail companies. Note that this is a practice oriented paper and many details were omitted for the sake of simplicity. Additional papers will be referred throughout the text for more technical details. 5.2. Shelf Space Management at Sonae MC The primary objective of retail is to bridge the gap between the point of production and the point of sales, which stresses the role of logistics and operations in this industry. Sonae MC has a centralized operations management activity, responsible for planning all the operations for the stores nationwide. The space planning department, as its name implies, is engaged with managing the space available at the stores, an activity that comprises two main levels: a macro-space planning level that defines, on a long-term basis, the layout of the stores (divided by categories); and a micro- (or shelf-) space planning level that defines, for each category, the products’ placement on the shelves. Shelf space planning is a midterm activity that updates shelf space plans with an average rate of 2 to 3 times a year for more than 300 categories. This activity fully occupies 23 space managers. Chests Pallets Pegboard Table Polygonal Shelf Bins Shelves Irregular Shelf Placement Figure 5.1 – Planograms with different types of fixtures. Some include more than one fixture type or present irregular shelf placements, resulting in irregular planograms. The traditional micro-space planning tool is a planogram, which is a virtual representation of the shelves, showing exactly where each product should be physically displayed 104 Chapter 5. Using Analytics to Enhance Shelf Space Management in a Food Retailer and the inventory that it should hold. One planogram comprehends plenty of information that has to be carefully planned: the location of the products, the number of facings (visible items), number of items stacked behind and above each facing, packaging style, orientations (front, side, back, top), among others. Besides the most commonly used shelves, stores have also other fixture types such as chests, pallets and pegboards (bars with steel rods sticking out to hold peggable products like pens and pencils). Moreover, planograms are physically made of segments that are stacked together to form an aisle. Each segment has its own shelves, which can be placed vertically aligned with the shelves of the other segments, or be placed differently, forming irregular planograms. Some examples are present in Figure 5.1. At Sonae MC, planograms follow a complex structure of merchandising rules that try to reflect the consumer buying behavior and the strategy of the company (and of the suppliers) for the categories. To do so, the company has a superior customer insight due to its successful loyalty card, which covers 3 out of 4 Portuguese households and is associated with 90% of the sales. Morever, the company maintains key partnerships with suppliers that have a deep knowledge about their categories, assuming the role of category captains. Space managers are also committed to developing planograms with a compelling visual look, and put a great effort on it. Nevertheless, the attractiveness of the planogram is a subjective field and planograms depend on the space manager in charge. Figure 5.2 presents an example of a merchandising manual for a category, where we can see that products are usually grouped by families which are placed in rectangular shapes. Each planogram has a hierarchy of families that typically range from 2 to 5 criteria. For each criterion, the merchandising manual specifies the family type, the display orientation (either vertical or horizontal), the family precedences and, in some cases, additional information about preferred locations. Due to the strategic character of merchandising rules, this figure does not represent a real situation. Yogurts Classic Yogurts Drinkable Yogurts 2nd Criterion 3rd Criterion Main criteria Brand – Vertical . . Brand – Horizontal Own Brand Economic Brand Economic Brand Leader (eye-level) Sub-leader .. Flavor – Vertical Strawberry Mango Peach Type – Vertical Classic Greek Low Fat . . . . Leader sub-leader Own Brand Display Orientation (Vertical, Horizontal) Precedences Preferred Locations (Eye-level, hand-level, bottom, top) Family Type (Brand, Type, Flavor, Package, Size,...) Hierarchical Criteria Levels Figure 5.2 – Merchandising rules for implementing a given category: an example with yogurts. Each manual specifies from 2 to 5 hierarchical criteria levels with different types of information. 5.2. Shelf Space Management at Sonae MC 105 The process of updating shelf space plans has a major interaction with the commercial department, that is responsible for managing categories. The process for a given category is as follows. The category manager (from the commercial department) triggers the process after specifying the product portfolio (assortment) for the stores, as well as the key merchandising rules for their implementation. Product portfolios are not store-specific but are instead specified for clusters of stores with similar sales and space patterns in order to manage complexity and effort. Space managers start by generating a template planogram (known as role planogram) for each cluster, where they carefully check how merchandising rules fit the space. In a collaborative work between the space and category managers, the planogram is then discussed and merchandising rules are tuned. Once validated by the category manager, it is then replicated for the remaining stores, by adjusting the product facings to the space of each store, while maintaining the same allocation rules. Figure 5.3 summarizes this shelf space planning process, where the two key processes are highlighted: The Generation Process and the Replication Process. Note that the company has many categories to update and, at the beginning of each year, the category space planning processes are scheduled for the entire year. Replication Process Planograms for all stores, with the same arrangement as the role Planogram Assortment A Assortment B Role Planogram A Role Planogram B Generation Process Role Planogram for each cluster of stores with same assortment and similar sales and space patterns Guidelines Merchandising Rules Guidelines Merchandising Rules Store A.1 Store A.2 Store A.3 Store B.1 Store B.2 Commercial Department Space Department with collaboration of the Commercial Department Space Department Stores Figure 5.3 – The micro-space planning process has a major interaction with the commercial department and comprises two main processes: Generation and Replication. During the shelf space updating processes, space managers generate an average of 60,000 planograms each year. For this purpose, Sonae MC uses a space planning software from one of the world top three vendors, the JDA Software Group, Inc. This software gathers the necessary capabilities for creating and maintaining the planograms, including a space database with all the key information about the products and store equipments, and a visualization tool that provides realistic views of the shelves, the ability to easily handle products and powerful reporting. Although automatic tools for planogram generation are 106 Chapter 5. Using Analytics to Enhance Shelf Space Management in a Food Retailer available in JDA software, they do not accommodate all the inherent complexity of the Merchandising Rules. Therefore, space managers manually developed their planograms by dragging and dropping the products onto the shelves, in a time consuming activity that lasts on average 3 hours. One of the most difficult challenges that we faced in the beginning of the project was the lack of formal criteria for evaluating planograms. Space managers were creating and evaluating planograms based on their intuition and personal judgment, as opposed to analytical methods. Nevertheless, in most situations, they were empirically considering space elasticities and balancing the product days-supply values. When analyzing shelf inventory, days-supply is a common operational metric, measuring the number of demand days covered by the shelf stock. For balancing days-supply values, space managers were using a software highlighting tool that colored the products according to predefined days-supply intervals and they sought to fit all the products within one interval. Moreover, some categories had alternative objectives such as meeting the brand market-shares. In 2011, the stores went through a successful lean process that, among other things, changed their shelf replenishment policy from just-in-time (shelves were replenished frequently in small quantities during the day) to a single shelf replenishment operation each day, before the morning opening. This change of policy, and the fact that products normally have joint delivery cycles from the central distribution centers, explain the reasoning behind balancing days-supply values across the products. By having all products covered for a similar number of days, the number of shelf replenishment operations are reduced, the stock level for long-tale products is better controlled, stockouts for fast moving products are prevented, and it also possible to reduce the backroom inventory. Sonae MC believed that analytics could help to improve shelf space management going beyond a straightforward planogram automation tool and this is when this projected started. 5.3. Theory and Practice of Shelf Space Management Most shoppers are susceptible to in-store marketing, mainly because of the low level of involvement that consumers have with in-store decisions. Additionally, reduced assortments and stockouts force the search for substitute products, highlighting the role of space management. Experimental studies have been addressing the effect of space variables on the demand of the products. These studies point to three main elasticities: space elasticity measures the increasing responsiveness of demand as more space is allocated to a product, experiencing declined marginal returns at some point (Curhan [1972], Chandon et al. [2009]); location elasticity highlights key display locations that bring a better exposure, such as the eyeor hand-level (Drèze et al. [1994]); lastly, cross elasticity measures the interdependency between adjacent products and is assumed to be positive for complementary products and negative for substitute products (Corstjens and Doyle [1981]). Additionally, the way products are arranged on the shelves can also have an important role on gaining the consumers’ attention. Thus, carefully organizing them in families can increase interest, while disorganized or excessive complexity (i.e. variations in the basic visual content) damages the buying experience (Pieters et al. [2010]). 5.3. Theory and Practice of Shelf Space Management 107 According to a survey to US retailers (Keltz and Sterneckert [2009]), the main drivers for space planning initiatives rely on two main axes: maximizing selling space effectiveness, powered by the aforementioned effects, and tighter inventory control. However, the same survey concludes that the benefits are not meeting the expectations. As a result, space planning investments are required because “conventional assortment analytics and space tools do not deliver the optimization capabilities needed for success”. Software vendors mainly tackle the development of large-scale data processing technologies capable of addressing the complexity of shelf space in practice, but with limited or no use of mathematical optimization, and a complete disregard for consumer demand effects. Therefore, automatically generated planograms are still a mirage for most retailers and they often opt for generic planograms that fit clusters of stores. Shelf space management is an active field of research in retail operations management, under the name Shelf Space Allocation Problem (SSAP). Despite the practical relevance of the problem, there has been somehow a misalignment of the scientific knowledge with the practice as most state-of-the-art mathematical models have strong limitations (Hübner and Kuhn [2012], Bai [2005]). The literature presents a great variety of models, mostly differing in their demand functions, which incorporate different estimates of (some of) the consumer demand effects, ranging from complex multiplicative polynomial forms to simplistic linear profit functions. Nevertheless, most of these models have the common goal of maximizing demand by deciding the product facings on each shelf, without considering their location within the shelves. The most relevant approaches to this work are from Corstjens and Doyle [1981] who were the first to present space elasticity in a polynomial form, Gajjar and Adil [2010] who propose a piecewise linearization to the space elastic demand function, and Yang and Chen [1999], who use an alternative model in the form of a linear multi-knapsack problem. Perhaps the most important practical limitation from the aforementioned literature is that it neglects merchandising rules; more specifically, it disregards the existence of product families that specify associations of products on the shelves. Russell and Urban [2010] and Geismar et al. [2014] are the only authors who define the exact location of the products on the shelves and allocate the space in such a manner that keeps product families together, in uniform and rectangular shapes. Despite this, none of the models were able to solve to optimality instances with more than 10 products. Another key-point is that the shelf space allocation literature has focused less on the cost side of the problem and most models do not explicitly consider inventory related decisions. Two authors stand out in a more inventory-related stream: Baker and Urban [1988] presented the first model that considered the demand in function of the instantaneous inventory level of an item, based on the economic order quantity (EOQ) model, and Urban [1998] proposed the first attempt to include shelf space allocation in the inventory decisionmaking process. Nevertheless, these models are comprehensive and are only solved to optimality for a reduced number of products. The models also include practical limitations: they consider continuous shelf replenishment operations from the backroom and determine individual product replenishment policies. Our approach can also relate to this stream as we give a special emphasis to inventory. Finally, the literature regarding Category Captains is also interesting to this work, and 114 Chapter 5. Using Analytics to Enhance Shelf Space Management in a Food Retailer GAP Replication Given a fully defined planogram (role planogram), the GAP Replication module reproduces a similar product placement for a new store without the need to provide merchandising rules or other type of reasoning behind the planogram construction. The new space is usually larger (in width, as most of the times planograms have the same height) but should have a similar shelf layout to ensure the compatibility between the two planograms. Since the new store has a different demand pattern, the objective is to meet new target number of facings, specified upstream and suitable for this store. We formulated the replication problem as a MIP model. Although we mainly aim to adjust the product facings, the model necessarily determines the products’ location, in order to guarantee that the new planogram fully complies with the role planogram. In particular, the following product placement information is considered: •products are required to keep the same relative position as in the role planogram. In the case of shelves, this means that products maintain the same shelf level and they are placed following the same sequence; •product families are required to keep their uniform rectangular shapes. The family continuity within each shelf is already ensured by keeping the same sequence. The rectangular shape is obtained by vertically aligning the first and the last products of the shape, which we call the left and right alignments. This brings flexibility to consider shapes from the role planogram that may not be necessarily rectangular. In other words, one may say that the role planogram suffers a controlled “expansion” in order to keep all alignments. Note that during this process, we do not consider location effects on demand, as the relative product placement constrains such decision. Although solving the formulation in a commercial solver is able to generate solutions within time limits that are acceptable in practice, we developed a second MIP-based heuristic to ensure the scalability of the approach, especially for the planograms with irregular shelf placements (mis-alignments and interruptions in each shelf level), whose additional constraints greatly impacted the performance of the formulation. Generically speaking, this matheuristic has three main steps. The first step generates an initial solution for the problem with the minimum display quantities for the products. The second step iteratively adds the remaining product facings to the planogram until no more space is available (or no more facings can be added). The last step tries to improve the solution by allowing the removal and insertion of new facings. Technically, this approach is an integration of two well-known MIP-based improvement heuristics: fix-and-optimize and local branching. Thus, in each iteration, we solve the model with some variables partially constrained in one of two different ways: a subset of the variables are fixed to the values obtained in the incumbent solution (fix-and-optimize) or there is a limited number of changes allowed to the values obtained in the incumbent solution (local branching). One of the interesting aspects of this matheuristic is that it mimics the process followed by the space managers when manually replicating planograms. Both the formulation and the matheuritic are formally defined in Bianchi-Aguiar et al. [2015a]. 5.4. GAP Overview 115 Aesthetics The formulations for planogram generation and replication focus on ensuring that the shapes are rectangular and disregard other aesthetic details, resulting in planograms with some display issues, such as such as large and irregular gaps between the products. The Aesthetics module is responsible for improving the attractiveness of the planogram and it considers two key factors for obtaining attractive displays: the way products are spaced throughout the planogram and whether the planogram is fully merchandised (i.e. full of facings). For that purpose, the generation or replication formulation (depending on whether it is a GAP Generation or Replication process) is re-executed again with all the decisions fixed to the incumbent solution, with the exception of the horizontal location of the products. The objective function is changed, firstly to minimize the empty space, and secondly, when no more products fit the planogram, to minimize the maximum spacing between two consecutive products. This latter objective distributes the empty space throughout the products. Infeasibility Analysis Highly customized and detailed merchandising rules lead to significantly constrained generation and replication formulations which can compromise the existence of a feasible solution for the problems. Moreover, the target facings formulation can also be infeasible, which result in too many possible causes for the process ending without a valid solution. To overcome these data related issues, we have developed an Infeasibility Analysis module that searches for the possible infeasibility causes in a structured and logical procedure. It performs multiple runs of the infeasible formulation and, at each one, a problem feature or requirement is removed from the formulation. The process stops after identifying a source for the infeasibility (i.e. whenever the formulation is able to find a valid solution for the relaxed problem). 5.4.2 Decision Support System GAP Optimizer requires the integration of different types of information obtained from multiple sources. If this information is not handled carefully, it may jeopardize the successful use of the application. For that purpose, another important building block is the GAP User Interface that manages all the data handling process, executes the Replication and Generation processes with real time status messages, and presents the generated planograms at the end, together with a full execution report. Among other things, this report provides all the warnings and errors that occurred during the process and when applicable, the infeasibility causes. In other words, this interface is present throughout the entire process, and it works as the liaison with the users. Figure 5.9 depicts the most relevant flows of information as well as snapshots from two interface forms: the project manager for handling the data and the generation manual for managing rules and configurations. The generation manual is one of the key-parts of the overall system. Inspired by handmade merchandising manuals (c.f. Figure 5.2), this form presents a familiar interface (to space managers) for the configuration of merchandising rules in a very intuitive way. Space 116 Chapter 5. Using Analytics to Enhance Shelf Space Management in a Food Retailer Inputs GAP User Interface Output Generation/Replication Manual Project Manager Product Assortment Equipment Product Performance Merchandising Rules Configurations Solution Report Planogram(s) Users IKB Database (JDA) IKB Database (JDA) Users GAP Optimizer Commercial Solver Figure 5.9 – Inputs and Outputs of GAP managers have high flexibility to define these rules, and in each run they can choose the level of customization that they want to have in the generated planograms. For the advanced users, several other configurations are available, from alternative location-elasticity curves and planogram evaluation criteria to control parameters and tolerances. Each generation manual can be saved, consulted and reused in multiple processes. Most importantly, it can evolve as the space managers evaluate planogram solutions and realize possible changes to the planograms. With regard to the IT implementation, the GAP Optimizer is a C++ program with all the models embedded in the code. The company acquired a commercial solver and the formulations are executed using a C++ library from the solver. The GAP User Interface is developed using Windows Forms, and all the communications between the two building blocks use XML files. Both the GAP Optimizer and the GAP User Interface are executed on a dedicated server and all Space Managers have access to the interface using a remote desktop connection in a terminal-server architecture. At the moment, GAP does not have a direct connection with the space database and the information is manually exported and imported to the interface. Given the success of the project, Sonae MC is now studying 5.4. GAP Overview 117 more efficient infrastructures, both for communicating with the space planning database and for accessing the server from the space managers terminals. 5.4.3 Project Development The project kick-offwas on March 2012 and it lasted until July 2014. The two processes, GAP Generation and GAP Replication, were developed sequentially and each one involved three main phases: Requirements Definition,Prototype &Proof-of-concept and Testing & Validation. From the organizational standpoint, it included a team from FEUP, responsible for the complete development of GAP, and two teams belonging to Sonae MC: a team from the Space Department, responsible for validating requirements and testing GAP, and a team from ISI (the Information Systems and Innovation Department), responsible for integrating GAP with the Information Systems of the company. We strongly believe that there were some key factors in GAP’s design and project management which had a crucial contribution to the project’s success. To start with, the decision of dividing GAP in two processes played a vital role both from the space and commercial department perspectives, as it did not disrupt current practices. Starting the implementation with GAP Replication has also proved to be a wise decision mainly for two reasons. Firstly, because the replication process was faster to implement and provided more consensual solutions, contributing to an earlier engagement of the space managers with GAP. Secondly, it allowed us to obtain a deeper knowledge about the complex structure of merchandising rules, which was vital for the GAP Generation. Another key aspect was the close collaboration with the 3 space managers that were part of the project team, whose role was essential all the way from the requirements gathering and problem definition to the testing and validation phases. Weekly meetings between FEUP and the space managers were important milestones to validate new developments. This continuous process conferred great flexibility to GAP and led to the development of an application tailored to the Sonae MC reality. Additionally, the same 3 space managers tested and validated GAP using different categories of products, which was also significant for building (and communicating) their internal confidence in the application. Nevertheless, there were some challenges in this collaboration between academic researchers and industry practitioners who have different objectives, incentives and time horizons. In particular, at the beginning of the project we found a high resistance from the space managers to adapt to the new process. This was gradually overcome as we attempted to keep them updated on the evolution of the project, which improved their commitment to GAP and allowed them to understand the potential of the application. Training sessions were also performed before the roll-out of each of the two processes and, given the systems’ complexity, they were crucial to engage space managers. These sessions included the analysis of solutions with unexpected characteristics obtained while using GAP and the development of a check-list for systematically looking for alternative solutions in these situations. Moreover, the execution report also played a vital role in dealing with the disappointment of space managers when GAP produces a solution that is not expected and, more importantly, when it is not possible to generate one. Lastly, and perhaps one of the most important key factors for the success of the GAP 118 Chapter 5. Using Analytics to Enhance Shelf Space Management in a Food Retailer implementation was the enormous commitment of the space planning and innovation directors and their sponsorship during the whole project. 5.5. Impact Today, GAP is used on a daily-basis by the entire micro-space team at Sonae MC, both for the generation and replication of planograms. This section describes how it enhanced shelf space management in each of the three axes that were identified for the project: Process Automation, Space Optimization and Image Standardization. 5.5.1 Automation: from planogram construction to planogram evaluation Perhaps the first and most straightforward impact of the project was on the space management process, as it led to better processing times as well as a positive change of paradigm. During the first months after the roll-out, all space managers were encouraged to use GAP in their daily tasks, and to register the number of planograms that GAP could generate, as well as the process execution times (including the duration of data handling, creation of the generation/replication manuals and handmade adjustments to the final solution). The execution times were later compared with the legacy process and the results were encouraging: based on a preliminary analysis, space managers were able to automatically generate 80% of the planograms and the category space management processes took on average 48% less time (46% less in the generation processes and 50% less in the replication processes). Moreover, space managers also highlighted that these time reductions can be more significant in the future, after becoming more agile using the new software and by, totally or partially, reusing the generation manuals that they carefully developed for the first processes. Additionally, GAP shifted the space managers’ focus from planogram construction to planogram evaluation, allowing them to concentrate in additional activities, such as market trend studies and experiments with alternative merchandising rules. Therefore, this change of paradigm brought increasing responsibilities to space managers, and gave to them an analytical tool to support their decisions during the meetings with the commercial department. 5.5.2 Optimization: targeting optimality in all customization levels In what concerns optimization, it is necessary to measure independently the impact of GAP Generation and GAP Replication. One of the greatest advantages of GAP Generation is its flexibility to generate either highly customized solutions or more demand driven (and at the same time innovative) solutions, based on what is specified in the generation manual. Figure 5.10 depicts this flexibility by showing three planograms: the first was handmade by a space manager and the remaining two were generated with GAP, firstly using a fully defined generation manual (high customization) and then using the same manual but removing family precedences and display directions (low customization). While the first generated planogram is almost 5.5. Impact 119 similar to the handmade planogram, the second presents an alternative reasoning behind its creation that intended to put the most popular families in the premium vertical and horizontal locations. Hand-made Planogram GAP Planogram High costumization Highlight Level 1 Highlight Level 2 Horizontal Impact Vertical Impact Horizontal Impact Vertical Impact GAP Planogram Low costumization Figure 5.10 – Example of two planograms generated with GAP using two different levels of customization, and comparison with a handmade planogram. Regardless of the customization level, GAP Generation always uses the available degrees of freedom to optimize the number of product facings and the products’ location. To assess the impact of GAP Generation on the planograms’ performance, we have analyzed 25 different generation processes (one of which was the example described above). These examples were carefully selected during the proof-of-concept phase in order to guarantee that all specificities of the categories were covered. The impact was evaluated by measuring four performance metrics: potential sales increase (estimated using the location elasticity curves with a maximum impact of 20%); days-supply balance measured in terms of the average and the standard deviation reductions; and planogram filling rate (defined by the ratio of the linear space utilized and the overall available space). Table 5.1 summarizes the results when generating these planograms using high and low customization levels. The percentage values are relative to the handmade version. GAP Generation is able to improve the manual planogram performance in all four metrics, both in the low and high costumization versions. As expected, reducing the number of rules imposed to the planogram yields additional gains with an average increase of potential sales from 0.4% to 1.4%. We observed that the gains were more relevant in the metrics regarding to the day-supply values (whose average and standard deviation were reduced in 38% and 61% respecitvely), which is consistent with our primary objective. Note that days-supply values have a major impact in replenishment operations, holding costs and product availability. The planograms’ filling rate is also increased in both versions by 3% compared to the handmade planograms. 120 Chapter 5. Using Analytics to Enhance Shelf Space Management in a Food Retailer Table 5.1 – Summary of the planograms’ performance in 25 Generation and Replication processes. GAP Generation GAP Replication Low Customization High Customization Potential sales increase ∗1.4% 0.7% – Average days-supply reduction∗37.6% 35.3% 34.3% Standard deviation days-supply reduction∗60.8% 51.4% 56.3% Space Occupation∗∗ 96.5% 96.7% 97.3% Execution Time (hh:mm:ss) 00:07:12 00:01:50 00:02:10 ∗with respect to the handmade planogram; ∗∗ 94% in handmade planogram GAP Replication, by definition, has less flexibility to optimize, only deciding on the number of facings that products have in the new planograms, subject to many allocation rules that were extracted from the role planogram. Nevertheless, a smarter product facing allocation can optimize the day-supply values. We used the same 25 examples to assess GAP Replication performance by replicating the handmade planograms to the same store. The results are also present in Table 5.1 and prove that we are still able to significantly improve days-supply balancing. This project also caused a deep cultural change in the company. The success of the project motivated the use of OR-approaches (and more generically speaking, of analytical approaches) in other operations planning activities. In particular, it already triggered many other projects with the same OR group from the University of Porto, both in space related problems, such as backroom optimization, and in other related areas, such as marketing, store operations and logistics. 5.5.3 Standardization: knowledge management for a global process Space Managers are divided into groups responsible for subsets of categories. The categories’ know-how is kept inside each group, supported by manuals that report the implementation details (using a template similar to Figure 5.2). Nevertheless, these manuals are frequently limited to the upper criteria levels, giving only a general idea of the reasoning behind the planograms. Consequently, space managers keep most of the category knowhow, which is partially lost when organizational changes occur. GAP also had a major impact on standardizing information and managing knowledge. Firstly, the use of electronic generation manuals (and the possibility of reusing them) centralized the categories’ space planning know-how and made it possible to systematize the tacit knowledge available into information that can be shared among peers. Secondly, it reduced the subjectivity of the process, which is nowadays less dependent of the managers’ experience. 5.6. Concluding Remarks In the highly competitive retail environment of today, retailers can benefit from analytic tools for better decision making and many successful examples are reported in the liter- 5.A. Target Facings Model 121 ature. Shelf space planning is one area that is still to be explored mainly because of its complexity and high dependency on merchandising rules. We believe that this work is an important contribution in this direction both from a theoretical and practical point of view. On the scientific front, we provide innovative mathematical models and efficient algorithms to the shelf space allocation problem and bring more realism to the scientific approaches to this problem. From the application perspective, we give insights on how to tailor analytical approaches to the practice of shelf space management, namely by introducing the replication problem and by allowing users to control the level of customization from solutions, while still applying optimization in every step of the process. We also provide project management details that were critical during GAP implementation in Sonae MC, the major Portuguese retail company. Although this paper describes a real application of shelf space planning, the approach does not intrinsically depend on any company specific policies, as it is based on rules that are defined in run-time. Therefore, it is sufficiently generic to be suitable to other retail companies working in the grocery or similar markets. Its modular nature also enables its adaptation and integration with other realities and IT systems. Acknowledgements The authors are grateful to the remaining elements of the team. A special thanks to the three space managers, Constantino Gomes, Pedro Soares and Susana Borges; and also Frederico Santos, Joel Pacheco, Miguel Camanho and Hélder Matos from ISI. The authors are also grateful to the FCT – Fundação para a Ciência e Tecnologia (Portuguese Foundation for Science and Technology) – for awarding the grants SFRH /BD / 74387 /2010 and SFRH /BPD /98981 /2013. This work is also financed by the ERDF – European Regional Development Fund – through the ON.2 Programme, and by National Funds through the FCT within Smart Manufacturing and Logistics [Project NORTE - 07 - 0124 - FEDER - 000057]. Appendix 5.A Target Facings Model In this appendix, we provide a mathematical formulation of the Target Facings Model. Consider a specific category of a store with overall capacity C. The retailer wants to allocate N products, indexed by i∈ N, with length ai. Each product is associated with a space-to-sales curve presented in Figure 5.5 that is linearized with piecewise lines, obtained using the facings associated with the days-supply intervals (see Figure 5.11). There are Tdays-supply intervals, indexed by n∈ T . For each product i, the minimum and maximum facings of each interval nare dsn iand dsn+1 i. This space-to-sales curve represented in the figure is widely used in the literature and is associated with a polynomial function depending on the space-elasticity parameter as firstly introduced by Corstjens and Doyle [1981]. Other authors already proposed piecewise linear approximations such as Gajjar and Adil [2010]. However, we are the first to consider the problem with days-supply intervals. The objective is to maximize the planogram’s expected demand by determining the 122 Bibliography γ1 0 50 100 150 200 250 300 350 400 0 5 10 15 20 25 30 Demand Shelf Space of product i (Wi) Expected Demand α dsi1 dsi2 dsi3 dsin γ2 γ3 γn dsin+1 γn+1 γT dsin+2 fi2(Wi) fi1(Wi) fi2(Wi) fin(Wi) fin+1(Wi) fiT(Wi) Figure 5.11 – Piecewise linearization of the space elasticity curve considering the dayssupply intervals. number of facings for each product i. The decisions to be made are: γn, which specifies whether the days-supply interval nis selected for all products; and Wn i, which indicates the number of facings of product iif the days-supply interval is γn. The formulation is as follows: Maximize X i∈N X n∈T fn i(Wn i) (5.1) Subject to: X i∈N X n∈T Wn i·ai≤C(shelf-space capacity) (5.2) li≤X n∈T Wn i≤ui,∀i∈ N (minimum and maximum facings) (5.3) dsn i·γn≤Wn i≤dsn i·γn,∀i∈ N,n∈ T (number of facings) (5.4) X n∈DS γn=1 (single day-supply interval) (5.5) Wn i∈ {0,1},∀i∈ N,n∈ T ;γn∈ {0,1},∀n∈ T (integrality) (5.6) Bibliography R. Bai. An Investigation of Novel Approaches For Optimising Retail Shelf Space Allocation. PhD Thesis. The University of Nottingham, 2005. R. Baker and T. L. Urban. A deterministic inventory system with an inventory-leveldependent demand rate. Journal of the Operational Research Society, pages 823–831, 1988. T. Bianchi-Aguiar, M. A. Carravilla, and J. F. Oliveira. Replicating shelf space allocation solutions across retail stores. Working Paper, 2015a. Bibliography 123 T. Bianchi-Aguiar, E. Silva, L. Guimarï¿1 2es, M. A. Carravilla, and J. F. Oliveira. Allocating products on shelves under merchandising rules: multi-level product families with display directions. Working Paper, 2015b. P. Chandon, J. W. Hutchinson, E. T. Bradlow, and S. H. Young. Does In-Store Marketing Work ? Effects of the Number and Position of Shelf Facings on Brand Attention. Journal of Marketing, 73(6):1 – 17, 2009. M. Corstjens and P. Doyle. A Model for Optimizing Retail Space Allocations. Management Science, 27(7):822–833, 1981. R. C. Curhan. The Relationship Between Shelf Space and Unit Sales in Supermarkets. Journal of Maketing Research, 9(4):406–412, 1972. X. Drèze, S. J. Hoch, and M. E. Purk. Shelf management and space elasticity. Journal of Retailing, 70(4):301 – 326, 1994. H. Gajjar and G. Adil. A piecewise linearization for retail shelf space allocation problem and a local search heuristic. Annals of Operations Research, 179(1):149–167, 2010. H. N. Geismar, M. Dawande, B. Murthi, and C. Sriskandarajah. Maximizing revenue through two-dimensional shelf-space allocation. Production and Operations Management, 2014. Available online. A. H. Hübner and H. Kuhn. Retail category management: State-of-the-art review of quantitative research and software applications in assortment and shelf space management. Omega, 40(2):199 – 209, 2012. H. Keltz and K. Sterneckert. The trend toward consumer–centric merchandising requires assortment management and space planning investments. Technical report, AMR Research, September 2009. M. Kurtulus and L. B. Toktay. Category captainship practices in the retail industry. In Retail Supply Chain Management: Quantitative Models and Empirical Studies, pages 79–98. Springer, 2009. R. Pieters, M. Wedel, and R. Batra. The Stopping Power of Advertising: Measures and Effects of Visual Complexity. Journal of Marketing, 74(5):48–60, 2010. R. A. Russell and T. L. Urban. The location and allocation of products and product families on retail shelves. Annals of Operations Research, 179(1):131–147, 2010. T. L. Urban. An inventory-theoretic approach to product assortment and shelf-space allocation. Journal of Retailing, 74(1):15 – 35, 1998. M.-H. Yang and W.-C. Chen. A study on shelf space allocation and management. International Journal of Production Economics, 61(510):309–317, 1999. Appendix A Notation A.1. Shelf Space Allocation Problem Indices kshelves i,jproducts u,mproduct families Parameters Knumber of shelves Mnumber of product families Nnumber of products to display wkwidth of shelf k hkheight of shelf k aiwidth of product i biheight of product i piprofit of product i liminimum number of facings of product i uimaximum number of facings of product i γkeffectiveness of shelf kto generate revenue vmaximum deviation of product families between shelves wmax mwidth of the largest product from each block m Sets Kset of shelves Nset of products Mset of family products (also known as blocks) Nuset of products belonging to each family u Muset of downstream families belonging to each family u 131 132 Appendix A. Notation SHset of families that should have their downstream blocks with horizontal shape SVset of families that should have their downstream blocks with vertical shape Vuset of blocks from the immediate downstream level, either product families (m,n∈ Mu) or products (m,n∈ N) Decision Variables Wik the integer number of facings of product i∈ N on shelf k∈ K Xs ithe continuous horizontal location of product i∈ N, measured from the lower-left corner of the planogram to the lower-left corner of the first facing of the product Tmnk =1 if block mis displayed immediately after block non shelf k∈ K,u∈ M,m,n∈ Vu∪ {0} Ymk =1 if block m∈ V is located on shelf k∈ K Fmnk the continuous flow from block mto block non shelf k∈ K,u∈ M,m,n∈ Vu∪{0} Lik shelf length assigned to product i∈ N on shelf k∈ K Xs mthe horizontal location of the block m∈ V (left coordinate) Xe mthe horizontal location of the block m∈ V (right coordinate) FLmk =1 if k∈ K is the first shelf of block m∈ V LLmk =1 if k∈ K is the last shelf of block m∈ V A.2. Shelf Space Replication Problem Indices klevels osegments i,jproducts mfamily alignments (left and right) pfacings uminimum space share requirements Parameters Knumber of level Onumber of segments Wtotal width of the planogram Nnumber of products Nknumber of products of level k MLnumber of left (right) alignments MRnumber of right alignments Qnumber of minimum space share requirements wok width of shelf (o,k) hok height of shelf (o,k) eok (=1) if shelf (o,k) exists in the planogram. (=0 otherwise) A.2. Shelf Space Replication Problem 133 cok (=1) if shelf (o,k) is aligned with the following shelf (o+1,k) (=0 otherwise) nok (=1) segment of the next existing shelf of level kafter shelf (o,k) (if there is no next shelf, nok =−1) aiwidth of product i biheight of product i lilower bound (upper bound) on the number of facings of product i uiupper bound on the number of facings of product i sitotal stock of product ifor each facing Kinumber of shelves where product iis quminimum percentage of space to allocate to the products belonging to the space share requirement u vmaximum deviation between Didaily demand of product i γiscale parameter that reflects the variation in demand with respect to the number of facings of product i αkscale parameter that reflects the variation in demand with respect to the shelf k where the product is placed Rip the days-supply value of product iprior to introducing the pth facing Fip the replenishment frequency of product iprior to introducing the pth facing (Fip = 1/Rip) Sets Kset of levels Oset of segments Nset of products Nkset of products of level k, ordered by order of appearance N− kset of products of level k, ordered by order of appearance, except the last product MRset of left alignments MRset of right alignments NL mset of products of each left alignment m NR mset of products of each right alignment m Qset of minimum space share requirements NQ uset of products of each minimum space share requirement u Decision Variables Ridays-supply value of product i Withe integer number of facings of product i∈ N on each of the shelves where the product is located Xithe continuous horizontal location of product i∈ N, measured from the lower-left corner of the planogram to the lower-left corner of the first facing of the product, Wip (=1) if product i∈ N has the pth facing on the planogram, p=1,...,ui 134 Appendix A. Notation Lishelf length assigned to product i∈ N on each of the shelves where the product is located XL mthe horizontal location of left alignment m∈ ML XR mthe horizontal location of right alignment m∈ MR Lio shelf length assigned to product i∈ N in segment o∈ O, on each of the levels where the product is located, Yio (=1) if product i∈ N is located in segment o∈ O Xio the continuous horizontal location of product i∈ N in segment o∈ O, measured from the lower-left corner of the planogrammytablesmalllinespace A.3. Target Facings Problem Indices iproducts ndays-supply intervals Parameters Nnumber of products Tnumber of days-supply intervals wiwidth of product i Cplanogram overall linear capacity Sets Nset of products Tset of days-supply intervals Decision Variables γn(=1) if the days-supply interval nis selected to all products Wn ithe number of facings of product iif the days-supply interval is γn Appendix B Planogram Solutions B.1. Example 1 Category A Subcategory A.1 1st Criterion 2nd Criterion Main criteria Family-type 2 – Vertical Family-type 1 – Horizontal 3rd Criterion Family-type 3 – Horizontal Figure B.1 – Merchandising Rules from Example 1 Figure B.2 – Highlight family-type 1 from Example 1 135 136 Appendix B. Planogram Solutions Figure B.3 – Highlight family-type 2 from Example 1 Figure B.4 – Highlight family-type 3 from Example 1 B.2. Example 2 Category B Subcategory B.1 1st Criterion 2nd Criterion Main Criteria 3rd Criterion Subcategory B.2 Subcategory B.3 Family-type 1 – Vertical Family-type 2 – Horizontal Family-type 2 – Horizontal Family-type 3 – Vertical Family-type 3 – Vertical Family-type 3 – Vertical Figure B.5 – Merchandising Rules from Example 2 B.2. Example 2 137 Figure B.6 – Highlight subcategory from Example 2 Figure B.7 – Highlight family-type 1 from Example 2 Figure B.8 – Highlight family-type 2 from Example 2 138 Appendix B. Planogram Solutions Figure B.9 – Highlight family-type 3 from Example 2 B.3. Example 3 Category C Subcat. C.1 1st Criterion 2nd Criterion Main Criteria Family-type 1 Vertical Subcat. C.2 Family-type 1 Horizontal Subcat. C.3 Subcat. C.4 Subcat. C.5 Subcat. C.6 Subcat. C.7 Family-type 1 Horizontal Family-type 1 Vertical Family-type 1 Vertical Family-type 1 Vertical Family-type 1 Vertical Family-type 2 Horizontal Family-type 2 Horizontal Family-type 2 Horizontal Family-type 2 Horizontal Family-type 2 Horizontal Figure B.10 – Merchandising Rules from Example 3 Figure B.11 – Highlight subcategory from Example 3 B.4. Example 4 139 Figure B.12 – Highlight family-type 1 from Example 3 Figure B.13 – Highlight family-type 2 from Example 3 B.4. Example 4 Category D Subcategory D.1 1st Criterion 2nd Criterion Main Criteria Subcategory D.2 Subcategory D.3 Family-type 2 – Vertical Family-type 1 – Horizontal Family-type 1 – Horizontal Family-type 1 – Horizontal Family-type 2 – Horizontal Family-type 2 – Vertical Figure B.14 – Merchandising Rules from Example 4