Maximizing Revenue Through Two‐Dimensional Shelf‐Space Allocation

Abstract

We consider the problem of optimally allocating contiguous rectangular presentation spaces in order to maximize revenues. Such problems are encountered in the arrangement of products in retail shelf‐space and in the design of feature advertising displays or webpages. Specifically, we allow (i) the shape of a product's presentation to have a vertical as well as a horizontal component and (ii) displays to extend across multiple shelves for in‐store presentations. Since the vertical location of the shelf on which a product is displayed affects its sales, each vertical location is assigned its own effectiveness with regard to revenue generation. The problem of maximizing the total weighted revenue of a display is strongly NP‐hard. Therefore, we decompose it into two subproblems. The first consists of allocating products to different cabinets. In the second, within each cabinet, each product's units are arranged in a contiguous rectangle and assigned a location. These subproblems are solved using an innovative approach that uses a combination of integer programming and an algorithm for the maximum‐weight independent set problem. Based on computational studies on both real‐world and simulated data, we demonstrate the efficiency and effectiveness of our approach. Specifically, the revenue generated by this scheme is within 1% of the optimum for actual data and within 5% for simulated data.

Keywords

shelf‐space allocation two‐dimensional display retail location effects

Get full access to this article

View all access options for this article.

References

Adler

Gibbons

Matias

. 2002. Scheduling space‐sharing for internet advertising. J. Sched. 5: 103–119.

Anderson

E. E.

Amato

H. N.

. 1974. A mathematical model for simultaneously determining the optimal brand‐collection and display‐area allocation. Oper. Res. 22(1): 13–21.

Bai

Kendall

. 2008. A model for fresh produce shelf‐space allocation and inventory management with freshness‐condition‐dependent demand. INFORMS J. Comput. 20(1): 78–85.

Bai

van Woensel

Kendall

Burke

E. K.

. 2012. A new model and a hyper‐heuristic approach for two‐dimensional shelf‐space allocation. 4OR: A Q. J. Oper. Res. 11(1): 31–55.

Baker

B. S.

Schwarz

J. S.

. 1983. Shelf algorithms for two‐dimensional packing problems. SIAM J. Comput. 12(3): 508–525.

Baker

B. S.

Coffman

E. G.

Rivest

R. L.

. 1980. Orthogonal packings in two dimensions. SIAM J. Comput. 9(4): 846–855.

Balaji

Swaminathan

Kannan

. 2009. Approximating maximum weighted independent set using vertex support. World Acad. Sci. Eng. Technol. 4(4): 211–216.

Bass

F. M.

1969. A new product growth model for consumer durables. Manage. Sci. 15: 215–227.

Berlyne

D. E.

1958. The influence of complexity and novelty in visual figures on orienting responses. J. Exp. Psychol. 55(3): 289–296.

10.

Bhattacharya

Comerford

. 2006. DVD supply chain: The emerging challenge to media profitability. http://www.infosys.com/industries/media-entertainment/white-papers/Documents/DVD-supply-chain.pdf (accessed date February 25, 2013).

11.

Borin

Farris

P. W.

Freeland

J. R.

. 1994. A model for determining retail product category assortment and shelf allocation. Decis. Sci. 25(3): 359‐384.

12.

Bultez

Naert

. 1988. SH.A.R.P.: Shelf allocation for retailers' profit. Mark. Sci. 7(3): 211–231.

13.

Chung

. 2010. Demand‐forecasting, product‐allocation, and production‐scheduling applications at blockbuster, Ph.D Thesis, University of Texas at Dallas.

14.

Chung

Dawande

Sriskandarajah

. 2011. A short‐range scheduling model for blockbuster's order processing operation. Interfaces 41(5): 466–484.

15.

Chung

Niu

S. C.

Sriskandarajah

. 2012. A sales forecast model for short‐life‐cycle products new releases at blockbuster. Prod. Oper. Manag. 21(5): 851–873.

16.

Coffman

E. G.

Garey

M. R.

Johnson

D. S.

Tarjan

R. E.

. 1980. Performance bounds for level‐oriented two‐dimensional packing algorithms. SIAM J. Comput. 9(4): 808–826.

17.

Corstjens

Doyle

. 1981. A model for optimizing retail space allocations. Manage. Sci. 27(7): 822–833.

18.

Corstjens

Doyle

. 1983. A dynamic model for strategically allocating retail space. J. Oper. Res. Soc. 34(10): 943–951.

19.

Curhan

R. C.

1972. The relationship between shelf space and unit sales in supermarkets. J. Mark. Res. 9(4): 406–412.

20.

Desmet

Renaudin

. 1998. Estimation of product category sales responsiveness to allocated shelf space. Int. J. Res. Mark. 15: 443–457.

21.

Drèze

Hoch

S. J.

Purk

M. E.

. 1994. Shelf management and space elasticity. J. Retail. 70(4): 301–326.

22.

Gamarnik

Goldberg

Weber

. 2010. PTAS for maximum‐weight independent set problem with random weights in bounded degree graphs. In Proceedings of 21‐st ACM‐SIAM Symposium on Discrete Algorithms, (SODA), Society for Industrial and Applied Mathematics Philadelphia, PA, USA.

23.

Hansen

J. M.

Raut

Swami

. 2010. Retail shelf allocation: A comparative analysis of heuristic and meta‐heuristic approaches. J. Retail. 86(1): 94–105.

24.

Hifi

1997. A genetic algorithm‐based Heuristic for solving the weighted maximum independent set and some equivalent problems. J. Oper. Res. Soc. 48(6): 612–622.

25.

Hwang

Choi

Lee

M.‐J.

. 2005. A model for shelf‐space allocation and inventory control considering location and inventory level effects on demand. Int. J. Prod. Econ. 97: 185–195.

26.

Internet Advertising Bureau . 2014. IAB display advertising guidelines. http://www.iab.net/guidelines/508676/508767/displayguidelines (accessed date July 17, 2014).

27.

Laya

. 2014. Blockbuster is still a hit—south of the border. Business Week. http://www.businessweek.com/articles/2014-02-06/in-mexico-blockbuster-video-chain-lives-on (accessed date February 12, 2014).

28.

Lim

Rodrigues

Zhang

. 2004. Metaheuristics with local search techniques for retail shelf‐space optimization. Manage. Sci. 50(1): 117–131.

29.

Murray

C. C.

Talukdar

Gosavi

. 2010. Joint optimization of product price, display orientation and shelf‐space allocation in retail category management. J. Retail. 86(2): 125–136.

30.

Niu

S.‐C.

2002. A stochastic formulation of the bass model of new‐product diffusion. Mathemat. Probl. Eng. 8: 249–263.

31.

Niu

S.‐C.

2006. A piecewise‐diffusion model of new‐product demands. Oper. Res. 54: 678–695.

32.

Pelillo

. 2009. Heuristics for maximum clique and independent set, Floudas

C. A.

and Pardalos

P. M.

, eds. Encyclopedia of Optimization. Springer, New York, 1508–1520.

33.

Pieters

Wedel

Batra

. 2010. The stopping power of advertising: Measures and effects of visual complexity. J. Mark. 74: 48–60.

34.

Pieters

Wedel

Zhang

. 2007. Optimal feature advertising design under competitive clutter. Manage. Sci. 53(11): 1815–1828.

35.

Sakai

Togasaki

Yamazaki

. 2003. A note on greedy algorithms for the maximum weighted independent set problem. Discrete Appl. Math. 126: 313–322.

36.

Sawhney

M. S.

Eliashberg

. 1996. A parsimonious model for forecasting gross box‐office revenues of motion pictures. Mark. Sci. 15(2): 113–131.

37.

Trukhanov

Balasubramaniam

Balasundaram

Butenko

. 2013. Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations. Comput. Optim. Appli. 56: 113–130.

38.

Van Nierop

Fok

Franses

P. H.

. 2008. Interaction between shelf layout and marketing effectiveness and its impact on optimizing shelf arrangements. Manage. Sci. 27(6): 1065–1082.

39.

Yang

M.‐H.

2001. An efficient algorithm to allocate shelf space. Eur. J. Oper. Res. 131: 107–118.

40.

Yang

M.‐H.

Chen

W.‐C.

. 1999. A study on shelf‐space allocation and management. Int. J. Prod. Econ. 60–61: 309–317.

41.

Zufryden

F. S.

1986. A dynamic programming approach for product selection and supermarket shelf‐space allocation. J. Oper. Res. Soc. 37(4): 413–22.

42.

Zytkowska

. 2003. A micro‐marketing model for optimizing shelf space allocation. Master's Thesis, Tilburg University, The Netherlands.