A Heuristic Approach for Shelf Space Allocation Problem

Abstract

A shelf space allocation problem (SSAP) is a special form of multi constraint knapsack problem. The main difference between knapsack problem and SSAP is that a knapsack problem has only capacity constraints. Commercial space management systems use many different heuristic approaches for allocating shelf space due to NP-hard complexity of the SSAP. These heuristics are usually based on simple intuitive rules that could be easily used in practice to implement shelf space allocation decisions. In this paper, a new heuristic is developed to obtain good allocation of shelf space for different products in order to increase profitability under different constraints such as limited shelf space and elasticity factors.

Keywords

• Evolutionary algorithms, heuristic methods, shelf space allocation problem

References

1. Anderson, E.E. & Amato, H.N. (1973). A Mathematical Model for Simultaneously Determining the Optimal Brand-Collection and Display-Area Allocation. Oper. Res., 22, 13-21.
2. Beasley, J.E. (1985). An exact two-dimensional non-guillotine cutting tree search procedure. Oper. Res., 33, 49–64.
3. Bos, J. (1993). A quadratic assignment problem solved by simulated annealing. Journal of Environmental Management, 37(2), 127-145.
4. Burkard, R.E., & Çela, E. (1995). Heuristics for bi-quadratic assignment problems and their computational comparison. European Journal of Operations Research 83, 283-300.
5. Burkard, R.E., Çela, E., Pardalos, P.M., & Pitsoulis, L. (1998). The quadratic assignment problem. In P.P. Pardalos & M.G.C. Resende (Eds.), Handbook of Combinatorial Optimization (pp. 241-238). Dordrecht, Netherlands: Kluwer Academic Publishers.
6. Burkard, R.E. & Rendl, F. (1984). A thermodynamically motivated simulation procedure for combinatorial optimization problems. European Journal of Operations Research, 17(2), 169-174.
7. Carvalho, J.M.V. (1999). Exact solution of bin‐packing problems using column generation and branch‐and‐bound. Annals of Operations Research, 86, 629-659.
8. Chen, M.C., & Lin, C.P. (2007). A data mining approach to product assortment and shelf space allocation. Expert Systems with Applications, 32, 976–986.

9. Chiang, W.C. & Chiang, C. (1998). Intelligent local search strategies for solving facility layout problems with the quadratic assignment problem formulation. European Journal of Operational Research, 106(2-3), 457-488.
10. Corstjens, M., & Doyle, P. (1981). A Model for Optimizing Retail Space Allocations. Management Science 27, 822-833.
11. Dreo, J., Petrowski, A., Siarry, P., & Taillard, E. (2006). Metaheuristics for Hard Optimization: methods and case studies. Berlin, Germany: Springer. ISBN: 10-3-540-23022-X.
12. Dreze, X., Hoch, S.J., & Purk M.E. (1994). Shelf Management and Space Elasticity. Journal of Retailing 70, 301-326.
13. Eisend, M. (2014). Shelf space elasticity: A meta-analysis. Journal of Retailing, 90(2), 168-181.
14. Erol, A.H. (2010). A heuristic solution algorithm for the quadratic assignment problems. Master thesis, Marmara University, Institute for Graduate Studies in Pure and Applied Sciences, Turkey; Supervisor: Asst. Prof. Dr. Serol Bulkan.
15. Fadıloğlu, M.M., Karaşan, O.E., & Pınar, M.Ç. (2007). A Model and Case Study for Efficient Shelf Usage and Assortment Analysis. Annals of Operations Research, 180(1), 105-124.
16. Fancher, L.A. (1991). Computerized space management: A strategic weapon. Discount Merchandiser, 31(3), 64-65.
17. Fekete, S.P., & Schepers, J. (2001). New classes of fast lower bounds for bin packing problems. Mathematical Programming, 91(1), 11-31.
18. Fekete, S.P., & Schepers, J. (1998). New classes of lower bounds for bin packing problems, in: R.E. Bixby, E.A. Boyd & R.Z. Rı́os-Mercado (Eds.), Integer Programming and Combinatorial Optimization (IPCO 98), Lecture Notes in Computer Science, 1412 (pp. 257–270), Berlin , Germany: Springer.
19. Gilmore, P.C., & Gomory, R.E. (1961). A linear programming approach to the cutting stock problem. Oper. Res., 9, 849–859.
20. Hadjiconstantinou, E., & Christofides, N. (1995). An exact algorithm for general, orthogonal, two-dimensional knapsack problems. Eur. J. Oper. Res., 83, 39–56.
21. Hwang, H., Choi, B., & Lee, G. (2009). A genetic algorithm approach to an integrated problem of shelf space design and item allocation. Computers & Industrial Engineering, 56 , 809–820.
22. Hwang, H., Choi, B., & Lee, M.J. (2005). A model for shelf space allocation and inventory control considering location and inventory level effects on demand. International Journal of Production Economics, 97, 185–195.
23. Ji, P., Wu, Y., & Liu, H. (2006). A Solution Method for the Quadratic Assignment Problem (QAP), The Sixth International Symposium on Operations Research and Its Applications (ISORA’06), Xinjiang, China, August 8–12, 106–117.
24. Kirkpatrick, S., Gelatt, C., & Vecchi, M. (1983). Optimization by simulated annealing. Science, 220, 671–680.
25. Lim, A., Rodrigues, B., & Zhang, X. (2004). Metaheuristics with local search techniques for retail shelf-space optimization. Management Science, 50(1), 117–131.
26. Lodi, A., Martello, S., & Vigo, D. (1999). Heuristic and Metaheuristic Approaches for a Class of Two-Dimensional Bin Packing Problems. Informs Journal of Computing, 11(4), 345-357.
27. Lodi, A., Martello, S., & Vigo, D. (2002). Recent advances on two-dimensional bin packing problems. Discrete Applied Mathematics, 123 (1–3), 379–396.
28. Martínez-de-Albéniz V. & Roels, G. (2011). Competing For Shelf Space. Production and Operations Management, 20(1), 32-46.
29. Mavridou, T. & Pardalos, P.M. (1997). Simulated annealing and genetic algorithms for the facility layout problem: A survey. Computational Optimization and Applications, 7, 111-126.
30. Michael, D., & Moffitt, M.D. (2013). Multidimensional Bin Packing Revisited, Principles and Practice of Constraint Programming, Lecture Notes in Computer Science, 8124, 513-528.
31. Misevicius, A. (2000). An intensive search algorithm for the quadratic assignment problem. Informatica, 11, 145-162.
32. Misevicius, A. (2003). A modification of tabu search and its applications to the quadratic assignment problem. Information Technology and Control, 27, 12-20.
33. Nissen, V. & Paul, H. (1995). A modification of threshold accepting and its application to the quadratic assignment problem. OR Spektrum, 17(2-3), 205-210.
34. Peng, T., Huanchen, W. & Dongme, Z. (1996). Simulated annealing for the quadratic assignment problem: A further study. Computers and Industrial Engineering, 31(3-4), 925-928.
35. Pisinger, D. (1995). Algorithms for Knapsack Problems. PhD Thesis, University of Copenhagen, Department of Computer Science, Denmark.
36. Stützle, T. (1998). Applying iterated local search to the permutation flow shop problem. Technical Report, AIDA-98-04, FG Intellektik, TU Darmstadt, Germany.
37. Tian, P., Wang, H.C. & Zhang, D.M. (1996). Simulated annealing for the quadratic assignment problem: A further study. Computers and Industrial Engineering, 31(3-4), 925-928.
38. Tian, P., Ma, J. & Zhang, D.-M. (1999). Application of the simulated annealing algorithm to the combinatorial optimization problem with permutation property: An investigation of generation mechanism. European Journal of Operational Research, 118(1), 81-94.
39. Tsuchiya, K., Nishiyama, T. & Tsujita, K. (2001). A deterministic annealing algorithm for a combinatorial optimization problem using replicator equations. Physica D: Nonlinear Phenomena, 149(3), 161-173.
40. Siu, F. & Chang, R.K.C. (2002). Effectiveness of optimal node assignments in wavelength division multiplexing networks with fixed regular virtual topologies. Computer Networks, 38(1), 61-74.
41. Thonemann, U.W. & Bölte, A. (1994) An improved simulated annealing algorithm for the quadratic assignment problem. School of Business, Working paper, Department of Production and Operations Research, University of Paderborn, Germany.
42. Yang, M.H. (2001). An effective algorithm to allocate shelf space. European Journal of Operational Research, 131, 107-118.
43. Yang, M.H., & Chen, W.C. (1999). A study on shelf space allocation and management. International Journal of Production Economics, 60-61, 309-317.
44. Yip, P.P.C. & Pao, Y.H. (1994). A guided evolutionary simulated annealing approach to the quadratic assignment problem. IEEE Transactions on Systems Man and Cybernetics, 24(9), 1383-1387.
45. Zufryden, F.S. (1986). A dynamic programming approach for product selection and supermarket shelf-space allocation. Journal of Operations Research Society, 37(4), 413-422