Meta-Heuristic Algorithms based on Integer Programming for Shelf Space Allocation Problems

Öz

Retail shelf space management, which is one of the most complex aspects of retailing, can be defined as determining when, where and in what quantities products will be displayed and dynamically updating the display considering changing market conditions. Although it is an important problem, research papers that study rectangular arrangement of products to optimize profit are limited. In this paper, we determine rectangular facing units of products to maximize profit for shelf space allocation and the display problem. To solve our two-dimensional shelf space allocation problem, we develop two matheuristic algorithms by using integer programming and genetic algorithm (TP-GA) and integer programming and firefly algorithm (TP-ABA) meta-heuristics together. The performances of the mathheuristics were compared with a real-world dataset from a bookstore. TP-GA and TP-ABA methods were able to generate near-optimal solutions with an average of 4.47% and 4.57% GAPs, respectively. We can also solve instances up to 900 products. These matheuristic algorithms, which are successful in the two-dimensional shelf assignment problem, can also be used to solve similar problems such as allocation of books in a bookstore, allocation of product families in a grocery store, or display of advertisements on websites.

Anahtar Kelimeler

• two-dimensional shelf space allocation problem
• integer programming
• genetic algorithm
• Firefly algorithm
• Matheuristic algorithms

Proje Numarası

217M920

Raf Atama Yönetimi için Tamsayılı Programlama Destekli Meta-Sezgisel Algoritmalar

Öz

Perakendeciliğin en karmaşık yönlerinden biri olan perakende raf alanı yönetimi, ürünlerin hangi miktarlarda ne zaman ve nerede teşhir edileceğini belirlemek ve değişen piyasa şartlarını dikkate alarak belirlenen sergilemeyi dinamik olarak güncellemek olarak tanımlanabilir. Önemli bir problem olmasına rağmen ürünlerin dikdörtgensel yerleşimini maksimum kâr amacıyla gerçekleştiren çalışmalar sınırlıdır. Bu çalışmada raf alanı tahsisi ve sergileme problemi için ürünlerin dikdörtgensel sergilenme adetlerinin belirlenmesi ürün kalınlıkları da dikkate alınarak gerçekleştirilmiş ve kârın maksimizasyonu amaçlanmıştır. İki boyutlu raf alanı tahsisi problemi çözümü için tamsayılı programlama ile genetik algoritma (TP-GA) ve tamsayılı programlama ile ateş böceği algoritması (TP-ABA) meta-sezgiselleri birlikte kullanılarak iki matsezgisel algoritma geliştirilmiştir. Bir kitabevinden alınan gerçek veriler kullanılarak oluşturulan veri seti ile matsezgisellerin performansları karşılaştırılmıştır. TP-GA ve TP-ABA matsezgiselleri ile sırasıyla ortalama %4,47 ve %4,57 optimale yakın çözümler elde edilmiştir. Geliştirilen matsezgiseller ile 900’e kadar ürünlü problemler çözülebilmiştir. İki boyutlu raf atama probleminde başarılı olan bu matsezgisel yöntemler, kitabevinde kitapların yerleşimi, perakendecilikte ürün ailelerinin yerleşimi veya İnternet sitelerinde reklamların gösterimi gibi benzer özellik taşıyan problemlerin çözümünde de kullanılabilir.

Anahtar Kelimeler

• iki boyutlu raf alanı tahsisi problemi
• tamsayılı programlama
• genetik algoritma
• ateş böceği algoritması
• matsezgisel algoritmalar

Destekleyen Kurum

TÜBİTAK

Proje Numarası

217M920

Teşekkür

Bu çalışma, TÜBİTAK tarafından 3001 Programı kapsamında 217M920 numaralı proje ile desteklenmiştir.

Kaynakça

1. Bai, R. (2005). An investigation of novel approaches for optimising retail shelf space allocation (Doktora Tezi). University of Nottingham. Erişim adresi: http: //www.cs.nott.ac.uk/~pszgxk/papers/BaiPhDThesis.pdf
2. Bai, R. ve Kendall, G. (2008). A Model for Fresh Produce Shelf Space Allocation and Inventory Management with Freshness Condition Dependent Demand. INFORMS Journal on Computing, 20(1), 78–85.
3. Bai, R., van Woensel, T., Kendall, G. ve Burke, E. K. (2013). A new model and a hyper-heuristic approach for two-dimensional shelf space allocation. 4OR, 11(1), 31–55. doi:10.1007/S10288-012-0211-2.
4. Bianchi-Aguiar, T. (2015). The Retail Shelf Space Allocation Problem:New Optimization Methods Applied to a Supermarket Chain (Doktora Tezi). Porto University. Erişim adresi: https://www.proquest.com/pqdtglobal/ docview/1914884710/51880A1B027E4DC8PQ.
5. Bianchi-Aguiar, T., Silva, E., Guimaraes, L., Carravilla, M. A. ve Oliveira, J. F. (2018). Allocating products on shelves under merchandising rules: Multi-level product families with display directions. Omega (United Kingdom), 76, 47–62. doi:10.1016/j.omega.2017.04.002.
6. Bianchi-Aguiar, T., Hübner, A., Carravilla, M. A. ve Oliveira, J. F. (2021). Retail shelf space planning problems: A comprehensive review and classification framework. European Journal of Operational Research, 289(1), 1–16. doi: 10.1016/j.ejor.2020.06.018.
7. Buttle, F. (1984). Merchandising. European Journal of Marketing, 18(6–7), 104–123.
8. Chandon, P., Hutchinson, J. W., Bradlow, E. T. ve Young, S. H. (2009). Does In-Store Marketing Work? Effects of the Number and Position of Shelf Facings on Brand Attention and Evaluation at the Point of Purchase. Journal of Marketing, 73(6), 1–17. doi:10.1509/jmkg.73.6.1.

9. Chen, M. C. ve Lin, C. P. (2007). A data mining approach to product assortment and shelf space allocation. Expert Systems with Applications, 32(4), 976–986. doi: 10.1016/j.eswa.2006.02.001.
10. Chen, Y. L., Chen, J. M. ve Tung, C. W. (2006). A data mining approach for retail knowledge discovery with consideration of the effect of shelf-space adjacency on sales. Decision Support Systems, 42(3), 1503–1520. doi: 10.1016/j.dss.2005.12.004.
11. Corstjens, M. ve Doyle, P. (1981). A Model for Optimizing Retail Space Allocations. Management Science, 27(7), 822–833. doi:10.1287/mnsc.27.7.822.
12. Cox, K. K. (1970). The Effect of Shelf Space upon Sales of Branded Products. Journal of Marketing Research, 7(1), 55-58. doi:10.2307/3149507.
13. Curhan, R. C. (1972). The Relationship between Shelf Space and Unit Sales in Supermarkets. Journal of Marketing Research, 9(4), 406–412. doi: 10.1177/002224377200900408.
14. Çağlar Gençosman, B. ve Beğen, M. A. (2022). Exact optimization and decomposition approaches for shelf space allocation. European Journal of Operational Research, 299(2), 432–447. doi: 10.1016/j.ejor.2021.08.047.
15. Dreze, X., Hoch, S. J. ve Purk, M. E. (1994). Shelf management and space elasticity. Journal of Retailing, 70(4), 301–326. doi:10.1016/0022-4359(94)90002-7.
16. Frontoni, E., Marinelli, F., Rosetti, R. ve Zingaretti, P. (2017). Shelf space re-allocation for out of stock reduction. Computers and Industrial Engineering, 106, 32–40. doi:10.1016/j.cie.2017.01.021.
17. Geismar, H. N., Dawande, M., Murthi, B. P. S. ve Sriskandarajah, C. (2015). Maximizing Revenue Through Two-Dimensional Shelf-Space Allocation. Production and Operations Management. doi:10.1111/poms.12316.
18. Hamming, R. W. (1950). Error Detecting and Error Correcting Codes. Bell System Technical Journal, 29(2), 147–160.
19. Hansen, J. M., Raut, S. ve Swami, S. (2010). Retail Shelf Allocation: A Comparative Analysis of Heuristic and Meta-Heuristic Approaches. Journal of Retailing, 86(1), 94–105. doi:10.1016/j.jretai.2010.01.004.
20. Hansen, P. ve Heinsbroek, H. (1979). Product selection and space allocation in supermarkets. European Journal of Operational Research, 3(6), 474–484. doi:10.1016/0377-2217(79)90030-4.
21. Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, USA. doi:10.7551/mitpress/1090.001.0001.
22. Hübner, A.H. ve Kuhn, H. (2012). 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. doi:10.1016/j.omega.2011.05.008.
23. Hübner, A. (2017). A decision support system for retail assortment planning. International Journal of Retail & Distribution Management, 45(7–8), 808–825. doi:10.1108/IJRDM-09-2016-0166.
24. Hübner, A., Schäfer, F. ve Schaal, K. N. (2021). Maximizing Profit via Assortment and Shelf‐Space Optimization for Two‐Dimensional Shelves. Production and Operations Management, 29(3), 547-570. doi:10.1111/poms.13111.
25. Hwang, H., Choi, B. ve 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(2), 185–195. doi:10.1016/j.ijpe.2004.07.003.
26. Hwang, H., Choi, B. ve Lee, G. (2009). A genetic algorithm approach to an integrated problem of shelf space design and item allocation. Computers & Industrial Engineering, 56(3), 809–820. doi:10.1016/j.cie.2008.09.012.
27. Karthikeyan, S., Asokan, P. ve Nickolas, S. (2014). A hybrid discrete firefly algorithm for multi-objective flexible job shop scheduling problem with limited resource constraints. International Journal of Advanced Manufacturing Technology, 72(9–12), 1567–1579. doi:10.1007/s00170-014-5753-3.
28. Kök, A. G., Fisher, M. L. ve Vaidyanathan, R. (2015). Assortment planning: Review of literature and industry practice. International Series in Operations Research and Management Science, 223, 175–236. doi:10.1007/978-1-4899-7562-1_8.
29. Kotzan, J. A. ve Evanson, R. V. (1969). Responsiveness of drug store sales to shelf space allocations. Journal of Marketing Research, 6(4), 465–469.
30. Lim, A., Rodrigues, B. ve Zhang, X. (2004). Metaheuristics with Local Search Techniques for Retail Shelf-Space Optimization. Management Science, 50(1), 117-131. doi: 10.1287/mnsc.1030.0165.
31. Martello, S. ve Toth, P. (1990). An exact algorithm for large unbounded knapsack problems. Operations Research Letters, 9(1), 15–20. doi:10.1016/0167-6377(90)90035-4.
32. Nafari, M. ve Shahrabi, J. (2010). A temporal data mining approach for shelf-space allocation with consideration of product price. Expert Systems with Applications, 37(6), 4066–4072. doi:10.1016/j.eswa.2009.11.045.
33. Özcan, T. (2010a). Perakende raf alanı yönetimi: Literatür incelemesi ve bir karar destek aracı tasarımı. İstanbul Üniversitesi İşletme İktisadi Enstitüsü Yönetim Dergisi, 21(67), 84–103.
34. Özcan, T. (2010b). Perakende Endüstrisinde Raf Alanı Tahsis ve Mağaza Yerleşim Optimizasyonuna Bütünleşik Bir Model Önerisi. İÜ Mühendislik Bilimleri Dergisi, 1(1), 55–63.
35. Özcan, T. ve Esnaf, Ş. (2013). A Discrete Constrained Optimization Using Genetic Algorithms for A Bookstore Layout. International Journal of Computational Intelligence Systems, 6(2), 261–278. doi:10.1080/18756891.2013.768447.
36. Özçelik, T. Ö. ve Gündüz, G. (2019). Sezgisel Algoritmaları Kullanarak Raf Optimizasyonu Çalışması ve Bir Yazılım Uygulaması. Avrupa Bilim ve Teknoloji Dergisi, (16), 977–982. doi: 10.31590/ejosat.606566.
37. Rabbani, M., Salmanzadeh-Meydani, N., Farshbaf-Geranmayeh, A. ve Fadakar-Gabalou, V. (2018). Profit maximizing through 3D shelf space allocation of 2D display orientation items with variable heights of the shelves. OPSEARCH, 55(2), 337–360. doi:10.1007/s12597-018-0335-z.
38. Russell, R. A. ve Urban, T. L. (2010). The location and allocation of products and product families on retail shelves. Annals of Operations Research, 179(1), 131–147. doi:10.1007/S10479-008-0450-y.
39. Van Nierop, E., Fok, D. ve Franses, P. H. (2008). Interaction between shelf layout and marketing effectiveness and its impact on optimizing shelf arrangements. Marketing Science, 27(6), 1065–1082. doi:10.1287/mksc.1080.0365.
40. Yalçıner, A. Y. ve Can, B. (2019). Tam Sayılı Programlama ve Simülasyon ile Raf Alanı Optimizasyonu: Bir Ambalaj Firmasında Uygulama. Avrupa Bilim ve Teknoloji Dergisi, Özel Sayı, 375–388. doi: 10.31590/ejosat.638609.
41. Yang, M. H. ve Chen, W. C. (1999). A study on shelf space allocation and management. International Journal of Production Economics, 60–61, 309–317. doi:10.1016/S0925-5273(98)00134-0.
42. Yang, M. H. (2001). Efficient algorithm to allocate shelf space. European Journal of Operational Research, 131(1), 107–118. doi:10.1016/S0377-2217(99)00448-8.
43. Yang, X. S. (2008). Nature-Inspired Metaheuristic Algorithms, Beckington, UK: Luniver Press.
44. Yang, X. S. (2009). Firefly algorithms for multimodal optimization. Lecture Notes in Computer Science. doi:10.1007/978-3-642-04944-6_14.
45. Zhao, J., Zhou, Y. W. ve Wahab, M. I. M. (2016). Joint optimization models for shelf display and inventory control considering the impact of spatial relationship on demand. European Journal of Operational Research, 255(3), 797–808. doi: 10.1016/j.ejor.2016.05.025.