LOU Kaihao, YANG Yongjian, YANG Funing, ZHANG Xingliang

Abstract: Out-door billboard advertising plays an important role in attracting potential customers. However, whether a customer can be attracted is influenced by many factors, such as the probability that he/she sees the billboard, the degree of his/her interest, and the detour distance for buying the product. Taking the above factors into account, we propose advertising strategies for selecting an effective set of billboards under the advertising budget to maximize commercial profit. By using the data collected by Mobile Crowdsensing (MCS), we extract potential customers’implicit information, such as their trajectories and preferences. We then study the billboard selection problem under two situations, where the advertiser may have only one or multiple products. When only one kind of product needs advertising, the billboard selection problem is formulated as the probabilistic set coverage problem. We propose two heuristic advertising strategies to greedily select advertising billboards, which achieves the expected maximum commercial profit with the lowest cost. When the advertiser has multiple products, we formulate the problem as searching for an optimal solution and adopt the simulated annealing algorithm to search for global optimum instead of local optimum. Extensive experiments based on three real-world data sets verify that our proposed advertising strategies can achieve the superior commercial profit compared with the state-of-the-art strategies.

Keywords: billboard advertising; mobile Crowdsensing; probabilistic set coverage problem; simulated annealing; optimization problem