Abstract

Under limited resources and different objectives, maximizing the coverage of billboards plays a crucial role in social activities. The Maximal Coverage Billboards Location Problem (MCBLP) is very complex, especially for multi-objective functions. Based on the MCBLP, a mixed integer linear programming (MILP) model is established to determine the spatial optimization problem of billboard locations. Combining the salient features of the location problem, this study develops a new method called ReCovNet, which utilizes deep reinforcement learning (DRL) to solve the MCBLP. This study applies ReCovNet to solve the actual billboard location problem in New York City. To evaluate its performance, we implement various algorithms, such as Gurobi solver, genetic algorithm (GA), and a deep learning baseline called attention model (AM). Gurobi reports the best solution, while GA and AM are used as benchmark algorithms. The method proposed in this study achieves a good balance between efficiency and accuracy and effectively solves the MCBLP. The ReCovNet introduced in the study has the potential to improve advertising effectiveness and provides new insights for solving the MCBLP.

Background

Outdoor advertising on billboards has proven to be a popular marketing medium because it can effectively establish a commercial brand image. Due to the fixed billboards in specific locations that are visible to all passers-by, it can reach multiple target groups simultaneously, thereby enhancing the market share of the product in the surrounding area. Although the passing audience may only have a few seconds to notice the advertisement, a certain percentage of customers will be exposed to it regularly. Therefore, the information on the billboard will automatically deepen the audience's photographic memory, enabling them to remember the advertising information. In short, when companies want to increase the market awareness of products or brands in specific areas, outdoor advertising is particularly effective.

When using billboards, companies decide where to use them based on their marketing budget. The goal is to choose the best set of billboard display locations that can maximize the aggregate effect within their marketing constraints. Among them, how to choose the best billboard locations to maximize their overall effectiveness has been a classic problem in recent years.

In this study, New York City, known for its high population density, was selected. This urban area consists of five boroughs, namely Brooklyn, Queens, Manhattan, the Bronx, and Staten Island, and is often considered to be the southernmost region of New York State. This location is ideal for research because of its high population density, heavy traffic, diverse demographic structure, and complex transportation patterns, including both car and pedestrian traffic, especially in Manhattan where public transportation is crucial.

Fig 1：Spatial units in New York City.

Framework

The entire system workflow includes five layers: infrastructure layer, dataset layer, processing layer, ReCovNet layer, and representation layer. The infrastructure layer consists of hardware and software for processing data and running spatial models. The dataset layer includes LandScan data, two research areas of Uber Movement dataset, and billboard dataset. These datasets are cleaned and converted into a format that can be used in the data processing layer. When processing data, KD tree is used to perform effective nearest neighbor search on point-based datasets, thus constructing a spatial index. This spatial index improves the computational efficiency of spatial analysis for spatial optimization problems. The ReCovNet layer takes location and coverage information as input, combines the neighboring information between nodes, and generates end-to-end solutions for optimization problems. Finally, the representation layer displays the visualization results of the solution.

Fig 2：Workflow of solving the problem of billboard site location.

Result

This article proposes a reinforcement method called ReCovNet, which combines attention mechanisms to solve the problem of maximizing the coverage of billboard locations. The location coordinates of billboards and LandScan populations are input into ReCovNet. The model processes the raw data to obtain the probability of selecting each point as a billboard site. Subsequently, a set of locations is selected and a target value is given, representing the demand that the selected billboard location set satisfies. Figure 2 shows the LandScan dataset sites and candidate billboard sites.

Fig 3：LandScan spatial units and candidate billboard sites.

After demonstrating the effectiveness of the model on generated datasets, we attempted to verify the applicability of ReCovNet. Compared to the Gurobi solver, the ReCovNet model proposed in this study exhibited superior efficiency and provided competitive objective outputs. Although there are still some gaps between the objective values of ReCovNet and the optimal solutions, these gaps are usually small compared to GA. More importantly, our method shows significant advantages in solving time. Compared to genetic algorithms, this method reduces the solving time by half, and compared to the Gurobi solver, it achieves more than ten times the solving time.

In Table 1, a similar trend can be observed, with Gurobi providing the highest objective value and ReCovNet having the fastest speed. ReCovNet always provides better solutions than GA in a relatively short period of time. Figures 4 and 5 provide visualizations of the problems for 20 billboard sites and 30 billboard sites within a radius of influence.

Tab 1：Comparison of Gurobi, GA, and ReCovNet with M=20, 30, 40 and R=2000.

Fig 4：Visualization of billboard locations in New York City, with a service distance of 2000 meters and 30 stops.

Fig 5：Visualization of billboard locations in New York City, with a service distance of 2000 meters and 20 stops.

Innovation

(1) Innovation of research model

A new method, the RecovNet model, which uses deep reinforcement learning (DRL) to solve the MCBLP problem, is introduced to accurately describe the process of billboard location selection, as shown in Figure 6.

By applying our model and method to solve the real-world billboard placement challenge in New York, involving 1,109 demand points and 839 billboards, our method has significant efficiency advantages compared to other methods and effectively narrows the gap with the optimal solution.

(2) Innovation of research objects

It has been applied in New York, a city with high population density, busy traffic, diverse population and complex transportation patterns, and has demonstrated significant efficiency advantages compared to other methods, effectively narrowing the gap with the optimal solution.

Fig 6：Network structure of ReCovNet.

Conclusion

The maximum coverage billboard location problem (MCBLP) is a variant of the maximum coverage location problem, which has wide and critical applications in the real world. Modern solvers (such as Gurobi solver) can generate optimal solutions. However, as the size of the dataset increases, the running time increases exponentially. Therefore, in order to overcome this challenge, this paper considers a new method to more effectively handle MCBLP while maintaining comparable objective values. We integrate the structure of reinforcement learning and the idea of attention model to construct the ReCovNet model. In experiments, Gurobi solver undoubtedly performs best in terms of optimal coverage. There is a trade-off between optimal value and running time: although ReCovNet cannot surpass Gurobi when considering the target value, ReCovNet's running time is significantly less than Gurobi. This proves the advantage of ReCovNet when efficiency is a key factor.

In the future, we will continue to develop the ReCovNet model and study MCBLP from two different perspectives. The geospatial big data computing framework (Heitzler et al., 2017; Wang et al., 2019) is worth developing to improve the performance of the model. Secondly, we intend to study the integration of ReCovNet with deep learning models. This integration can further improve the efficiency of the model. By pursuing these directions, we are keen to optimize the ReCovNet model to make it suitable for solving more real-world problems with high efficiency and accuracy.