Fatmanur Akdoğan UZUN, Doğan ALTAN, Ercan PEKER, Mahmut Altuğ ÜSTÜN, Sanem SARIEL

Optimization of real-world outdoor campaign allocations

In this paper, we investigate the outdoor campaign allocation problem OCAP , which asks for the distribution of campaign items to billboards considering a number of constraints. In particular, for a metropolitan city with a large number of billboards, the problem becomes challenging. We propose a genetic algorithm-based method to allocate campaign items effectively, and we compare our results with those of nonlinear integer programming and greedy approaches. Real-world data sets are collected with the given constraints of the price class ratios of billboards located in İstanbul and the budgets of the given campaigns. The methods are evaluated in terms of the efficiency of the constructed plans and the construction time of the planning. The results reveal that the genetic algorithm-based approach gives close to optimal results in the shortest scheduling time for the OCAP, and it scales linearly with the increasing data sizes.

Keywords:

Out-of-home advertisement, billboard scheduling, campaign allocation, genetic algorithms, optimization,

PDF

___

[1] Lichtenthal JD, Yadav V, Donthu N. Outdoor advertising for business markets. Industrial Marketing Management 2006; 35 (2): 236-247.
[2] Committee OA. Essentials of Outdoor Advertising. New York, NY, USA: Association of National Advertisers, 1958.
3] Little JD, Lodish LM. A media planning calculus. Operations Research 1969; 17 (1): 1-35.
[4] Kelley L, Jugenheimer D, Sheehan KB. Advertising Media Planning. New York, NY, USA: Taylor and Francis, 2012.
[5] Mehta A. Online matching and ad allocation. Foundations and Trends® in Theoretical Computer Science 2013; 8 (4): 265-368. doi: 10.1561/0400000057
[6] Gale D, Shapley L. College admissions and the stability of marriage. American Mathematical Monthly 1962; 69 (1): 9-15. doi: 10.1080/00029890.1962.11989827
[7] Hylland A, Zeckhauser RJ. The efficient allocation of individuals to positions. Journal of Political Economy 1979; 87 (2): 293-314. doi: 10.1086/260757
[8] Teo CP, Sethuraman J. The geometry of fractional stable matchings and its applications. Mathematics of Operations Research 1998; 23 (4): 874-891. doi: 10.1287/moor.23.4.874
[9] Roth AE, Sonmez T, Unver MU. Kidney exchange. Quarterly Journal of Economics 2004; 119 (2): 457-488. doi: 10.1162/0033553041382157
[10] Roth AE. The evolution of the labor market for medical interns and residents: a case study in game theory. Journal of Political Economy 1984; 92 (6): 991-1016. doi: 10.1086/261272
[11] Roth AE. The economist as engineer: game theory, experimentation, and computation as tools for design economics. Econometrica 2002; 70 (4): 1341-1378. doi: 10.1111/1468-0262.00335
[12] Manlove DF. Hospitals/Residents problem. In: Kao MY (editor). Encyclopedia of Algorithms. New York, NY, USA: Springer US, 2008, pp. 926-930.
[13] Adany R, Kraus S, Ordonez F. Allocation algorithms for personal TV advertisements. Multimedia Systems 2013; 19 (2): 79-93. doi: 10.1007/s00530-012-0284-y
[14] Chen Y, Berkhin P, Anderson B, Devanur NR. Real-time bidding algorithms for performance-based display ad allocation. In: 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; San Diego, CA, USA; 2011. pp. 1307-1315.
[15] Zhang P, Bao Z, Li Y, Li G, Zhang Y et al. Trajectory-driven influential billboard placement. In: 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining; London, UK; 2018. pp. 2748-2757.
[16] Huang M, Fang Z, Xiong S, Zhang T. Interest-driven outdoor advertising display location selection using mobile phone data. IEEE Access 2019; 7: 30878-30889. doi: 10.1109/ACCESS.2019.2903277
[17] Naik PA, Mantrala MK, Sawyer AG. Planning media schedules in the presence of dynamic advertising quality. Marketing Science 1998; 17 (3): 214-235. doi: 10.1287/mksc.17.3.214
[18] Cosgun O, Gultas I, Serarslan MN. Application of a mathematical model to an advertisement reservation problem. An International Journal of Optimization and Control: Theories & Applications (IJOCTA) 2012; 3 (1): 23-33. doi: 10.11121/ijocta.01.2013.00133
[19] Zhang X. Mathematical models for the television advertising allocation problem. International Journal of Operational Research 2006; 1 (3): 302-322. doi: 10.1504/IJOR.2006.009303
[20] Turner J. Ad slotting and pricing: new media planning models for new media. PhD, Carnegie Mellon University, Pittsburgh, PA, USA, 2010.
[21] Turner J, Scheller-Wolf A, Tayur S. OR PRACTICE—scheduling of dynamic in-game advertising. Operations Research 2011; 59 (1): 1-16. doi: 10.1287/opre.1100.0852
[22] Zhao P. Collaborative real-time interactive billboard networks. MSc, University of Waterloo, Waterloo, Ontario, Canada, 2015.
[23] Nautiyal A, McCabe K, Hossari M, Dev S, Nicholson M et al. An advert creation system for next-gen publicity. In: Joint European Conference on Machine Learning and Knowledge Discovery in Databases; Dublin, Ireland; 2018. pp. 663-667.
[24] Cetin E, Esen ST. A weapon–target assignment approach to media allocation. Applied Mathematics and Computation 2006; 175 (2): 1266-1275. doi: https://doi.org/10.1016/j.amc.2005.08.041
[25] Keskinturk T, Cetin E. A genetic algorithm metaheuristic for the weapon-target based media allocation problem. Alphanumeric Journal 2015; 3 (1): 1-6. doi: 10.17093/aj.2015.3.1.5000128271

Turkish Journal of Electrical Engineering and Computer Science-Cover

ISSN: 1300-0632
Yayın Aralığı: Yılda 6 Sayı
Yayıncı: TÜBİTAK

Arşiv