Keywords
shelf space allocation problem
media planning
knapsack
heuristics
Categories
How to Cite
Abstract
Resource allocation is a complex challenge that extends across diverse disciplines, each presenting its distinct considerations and demands. This intricate task involves the distribution of resources in a manner that meets the needs and objectives of various sectors. In this study, we propose an innovative mushroom picker heuristics to knapsack-like resource allocation problems, mainly with product categorization, wherein each potential solution is metaphorically likened to a mushroom. The heuristic process comprises several stages: first, the preparation of the forest ground, followed by the identification of distinct mushroom clearings, then the search for mushrooms within these clearings, and finally, the decision-making process regarding the selection and collection of mushrooms. Through this heuristic framework, we aim to elucidate effective strategies for solution discovery and decision-making in complex problem domains. Twelve tuning parameters are presented to reduce the solution space. We provide an explanation of the application of the proposed mushroom picking heuristics on the basis of two problems: (1) the shelf space allocation in retail and (2) the commercial to TV break placement in media planning. This algorithm can also be used to solve other problems that can be modelled as knapsack problems.
References
Landa-Silva D, Marikar F, Le K (2009) Heuristic approach for automated shelf space allocation. In: Proceedings of the ACM Symposium on Applied Computing. pp 922–928
Drèze X, Hoch SJ, Purk ME (1994) Shelf management and space elasticity. J Retail 70:301–326. https://doi.org/10.1016/0022-4359(94)90002-7
Yang MH, Chen WC (1999) Study on shelf space allocation and management. Int J Prod Econ 60:309–317. https://doi.org/10.1016/S0925-5273(98)00134-0
Lim A, Rodrigues B, Zhang X (2004) Metaheuristics with Local Search Techniques for Retail Shelf-Space Optimization. Manage Sci 50:117–131. https://doi.org/10.1287/mnsc.1030.0165
Czerniachowska K, Lutosławski K, Kozina A, et al (2021) Shelf space allocation problem with horizontal shelf division. In: Procedia Computer Science. Elsevier, pp 1550–1559
Czerniachowska K, Lutoslawski K, Fojcik M (2022) Heuristics for shelf space allocation problem with vertical and horizontal product categorization. In: Procedia Computer Science. pp 195–204
Czerniachowska K, Hernes M (2020) A genetic algorithm for the shelf-space allocation problem with vertical position effects. Mathematics 8:1–20. https://doi.org/10.3390/math8111881
Czerniachowska K, Sachpazidu-Wójcicka K, Sulikowski P, et al (2021) Genetic algorithm for the retailers’ shelf space allocation profit maximization problem. Appl Sci 11:. https://doi.org/10.3390/app11146401
Borin N, Farris P (1995) A sensitivity analysis of retailer shelf management models. J Retail 71:153–171. https://doi.org/10.1016/0022-4359(95)90005-5
Yang MH (2001) Efficient algorithm to allocate shelf space. Eur J Oper Res 131:107–118. https://doi.org/10.1016/S0377-2217(99)00448-8
Hansen JM, Raut S, Swami S (2010) Retail Shelf Allocation: A Comparative Analysis of Heuristic and Meta-Heuristic Approaches. J Retail 86:94–105. https://doi.org/10.1016/j.jretai.2010.01.004
Reeves C (1996) Modern heuristic techniques. Mod heuristic search methods
Borin N, Farris PW, Freeland JR (1994) A Model for Determining Retail Product Category Assortment and Shelf Space Allocation. Decis Sci 25:359–384. https://doi.org/10.1111/j.1540-5915.1994.tb01848.x
Urban TL (1998) An inventory-theoretic approach to product assortment and shelf-space allocation. J Retail 74:15–35. https://doi.org/10.1016/S0022-4359(99)80086-4
Binguler AHE, Bulkan S, Agaoğlu M (2015) A Heuristic Approach for Shelf Space Allocation Problem. J Mil Inf Sci 4:38. https://doi.org/10.17858/jmisci.89213
Gajjar HK, Adil GK (2011) A dynamic programming heuristic for retail shelf space allocation problem. Asia-Pacific J Oper Res 28:183–199. https://doi.org/10.1142/S0217595911003120
Gajjar HK, Adil GK (2011) Heuristics for retail shelf space allocation problem with linear profit function. Int J Retail Distrib Manag 39:144–155. https://doi.org/10.1108/09590551111109094
Desmet P, Renaudin V (1998) Estimation of product category sales responsiveness to allocated shelf space. Int J Res Mark 15:443–457. https://doi.org/10.1016/S0167-8116(98)00018-4
Corstjens M, Doyle P (1983) A dynamic model for strategically allocating retail space. J Oper Res Soc 34:943–951. https://doi.org/10.1057/jors.1983.207
Gajjar HK, Adil GK (2010) A piecewise linearization for retail shelf space allocation problem and a local search heuristic. Ann Oper Res 179:149–167. https://doi.org/10.1007/s10479-008-0455-6
Marshall RJ, Johnston M, Zhang M (2014) Developing a hyper-heuristic using grammatical evolution and the capacitated vehicle routing problem. Lect Notes Comput Sci (including Subser Lect Notes Artif Intell Lect Notes Bioinformatics) 8886:668–679. https://doi.org/10.1007/978-3-319-13563-2_56
Castelli M, Vanneschi L (2014) Genetic algorithm with variable neighborhood search for the optimal allocation of goods in shop shelves. Oper Res Lett 42:355–360. https://doi.org/10.1016/j.orl.2014.06.002
Yu VF, Maglasang R, Tsao YC (2020) A reduced variable neighborhood search-based hyperheuristic for the shelf space allocation problem. Comput Ind Eng 143:. https://doi.org/10.1016/j.cie.2020.106420
Bai R (2010) An investigation of novel approaches for optimising retail shelf space allocation. Control 217
Czerniachowska K (2022) A genetic algorithm for the retail shelf space allocation problem with virtual segments. OPSEARCH 59:364–412. https://doi.org/10.1007/s12597-021-00551-3
Bai R, van Woensel T, Kendall G, Burke EK (2013) A new model and a hyper-heuristic approach for two-dimensional shelf space allocation. 4OR 11:31–55. https://doi.org/10.1007/s10288-012-0211-2
Mihiotis A, Tsakiris I (2004) A mathematical programming study of advertising allocation problem. Appl Math Comput 148:373–379. https://doi.org/10.1016/S0096-3003(02)00853-6
García-Villoria A, Salhi S (2015) Scheduling commercial advertisements for television. Int J Prod Res 53:1198–1215. https://doi.org/10.1080/00207543.2014.951095
Fleming PJ, Pashkevich MA (2007) Optimal advertising campaign generation for multiple brands using MOGA. IEEE Trans Syst Man Cybern Part C Appl Rev 37:1190–1201. https://doi.org/10.1109/TSMCC.2007.900651
Czerniachowska K (2019) Scheduling TV advertisements via genetic algorithm. Eur J Ind Eng 13:81–116. https://doi.org/10.1504/EJIE.2019.097926
Danaher PJ (2023) Optimal Microtargeting of Advertising. J Mark Res 60:564–584. https://doi.org/10.1177/00222437221116034
West D, Ford JB, Farris PW (2014) How corporate cultures drive advertising and promotion budgets: Best practices combine heuristics and algorithmic tools. J Advert Res 54:149–162. https://doi.org/10.2501/JAR-54-2-149-162
Åstebro T, Elhedhli S (2006) The effectiveness of simple decision heuristics: Forecasting commercial success for early-stage ventures. Manage Sci 52:395–409. https://doi.org/10.1287/mnsc.1050.0468
Kolsarici C, Vakratsas D, Naik PA (2020) The Anatomy of the Advertising Budget Decision: How Analytics and Heuristics Drive Sales Performance. J Mark Res 57:468–488. https://doi.org/10.1177/0022243720907578
Danenberg N, Kennedy R, Beal V, Sharp B (2016) Advertising budgeting: A reinvestigation of the evidence on brand size and spend. J Advert 45:139–146. https://doi.org/10.1080/00913367.2015.1090938
Evangelista VM, Regis RG (2020) A multiobjective approach for maximizing the reach or GRP of different brands in TV advertising. Int Trans Oper Res 27:1664–1698. https://doi.org/10.1111/itor.12481
Alaei R, Ghassemi-tari F (2011) Development of a Genetic Algorithm for Advertising Time Allocation Problems. J Ind Syst Eng 4:245–255
Ghassemi Tari F, Alaei R (2013) Scheduling TV commercials using genetic algorithms. Int J Prod Res 51:4921–4929. https://doi.org/10.1080/00207543.2013.778431
Kimms A, Müller-Bungart M (2007) Revenue management for broadcasting commercials: the channel’s problem of selecting and scheduling the advertisements to be aired. Int J Revenue Manag 1:28–44. https://doi.org/10.1504/IJRM.2007.011192
Pisinger D (1995) Algorithms for Knapsack Problems
Martello S, Toth P (1987) Algorithms for Knapsack Problems. North-holl Math Stud 132:213–257. https://doi.org/10.1016/S0304-0208(08)73237-7
Pisinger D (1999) An exact algorithm for large multiple knapsack problems. Eur J Oper Res 114:528–541. https://doi.org/10.1016/S0377-2217(98)00120-9
Connolly D, Martello S, Toth P (1991) Knapsack Problems: Algorithms and Computer Implementations. J Oper Res Soc 42:513. https://doi.org/10.2307/2583458
Araman VF, Popescu I (2010) Media revenue management with audience uncertainty: Balancing upfront and spot market sales. Manuf Serv Oper Manag 12:190–212. https://doi.org/10.1287/msom.1090.0262
Araman VF, Popescu I (2011) Media Revenue Management with Audience Uncertainty: Balancing Upfront and Spot Market Sales. SSRN Electron J. https://doi.org/10.2139/ssrn.1291729
Friedman L (1971) Calculating TV Reach and Frequency. J Advert Res 11:21–26
Guerriero F, Miglionico G, Olivito F (2016) Managing TV commercials inventory in the Italian advertising market. Int J Prod Res 54:5499–5521. https://doi.org/10.1080/00207543.2016.1162919
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Copyright (c) 2024 Kateryna Czerniachowska