ReCovNet: Reinforcement learning with covering information for solving maximal coverage billboards location problem

Abstract

Maximizing billboard coverage with limited resources and different objective goals plays a vital role in social activities. The Maximal Coverage Billboard Location Problem (MCBLP) is complex, especially for multi-objective functions. A multi-objective spatial optimization model was developed using mixed-integer linear programming based on MCBLP to formulate the spatial optimization problem of determining billboard locations. Combining the distinctive features of location problems, we have developed a new approach called ReCovNet that utilizes Deep Reinforcement Learning (DRL) to solve the MCBLP. We applied the ReCovNet to address a real-world billboard location problem in New York City. To assess its performance, we implemented various algorithms such as Gurobi solver, Genetic Algorithm (GA) and a deep learning baseline called Attention Model (AM). The Gurobi reports the optimal solutions, while GA and AM serve as benchmark algorithms. Our proposed approach achieves a good balance between efficiency and accuracy and effectively solves MCBLP. The ReCovNet introduced in our study has potential to improve advertising effectiveness, and our proposed approach offers novel insights for addressing the MCBLP.

Keywords

• Maximal coverage billboards location problem (MCBLP)
• Attention model
• Mixed-integer linear programming
• Deep reinforcement learning
• Spatial optimization