摘要
在有限的资源和不同的目标下，最大限度地提高广告牌的覆盖率在社会活动中起着至关重要的作用。最大覆盖广告牌位置问题（Maximal Coverage Billboards Location Problem, MCBLP）非常复杂，尤其是对于多目标函数而言。基于MCBLP的混合整数线性规划建立了多目标空间优化模型，以确定广告牌位置的空间优化问题。结合位置问题的显著特征，本研究开发了一种名为ReCovNet的新方法，该方法利用深度强化学习（Deep Reinforcement Learning, DRL）来解决MCBLP。本研究应用ReCovNet来解决纽约市实际的广告牌位置问题。为了评估其性能，我们实现了各种算法，例如Gurobi 求解器、遗传算法（Genetic Algorithm, GA）和名为注意力模型（Attention Model, AM）的深度学习基线。Gurobi报告最佳解决方案，而 GA 和 AM 则用作基准算法。本研究提出的方法在效率和精度之间实现了良好的平衡，并有效地解决了MCBLP。研究中引入的 ReCovNet 具有提高广告效果的潜力，并为解决 MCBLP 提供了新的见解。
背景
广告牌上的户外广告已被证明是一种流行的营销媒介，因为它可以有效地建立商业品牌形象。由于特定位置的固定广告牌对所有路人都可见，因此可以同时到达多个目标群体，从而加强产品在周边地区的市场占有率。虽然路过的观众可能只有几秒钟的时间注意到广告，但一定比例的客户会定期接触到它。因此，广告牌上的信息会自动加深观众的摄影记忆，使他们能够记住广告信息。简而言之，当公司想要提高特定领域产品或品牌的市场知名度时，户外广告特别有效。
使用广告牌时，企业会根据其营销预算决定在哪里使用广告牌。目标是选择一组最佳的广告牌展示位置，这些广告牌展示位置可以在其营销允许范围内最大限度地提高聚合效果。其中，对于应该如何选择最佳的广告牌位置，以最大限度地提高其整体效果是近年来一个经典问题。
在该研究中，选择了以其高人口密度而闻名的纽约市。这个市区由五个行政区组成，即布鲁克林、皇后区、曼哈顿、布朗克斯区和史坦顿岛，通常被认为是纽约州最南端的地区。这个位置非常适合研究，因为它的人口密度高，交通繁忙，人口结构多样化，交通模式复杂，包括汽车和步行交通，特别是在公共交通至关重要的曼哈顿。
图1：纽约市的空间单位
技术路线
整个系统工作流程包括五层：基础设施层、数据集层、处理层、ReCovNet层和表示层。由硬件和软件组成的基础设施层用于处理数据和运行空间模型。数据集图层包括LandScan数据、两个研究区域的Uber Movement数据集以及 广告牌数据集。这些数据集经过清理并转换为模型可在数据处理层中使用的格式。在处理数据时，利用KD树在基于点的数据集上进行有效的最近邻搜索，从而构建了一个空间索引。该空间指数提高了空间优化问题空间分析的计算效率。ReCovNet层将位置和覆盖率信息作为输入，将节点之间的相邻信息组合在一起，并生成优化问题end2end的解决方案。最后，表示层展示了解决方案的可视化结果。
图2：解决广告牌站点位置问题方法的工作流程
结果
本文提出了一种称为ReCovNet的强化方法，该方法结合了注意力机制，以解决最大覆盖广告牌位置问题。广告牌和LandScan人口的位置坐标在ReCovNet中输入。通过模型对原始数据进行处理，获得了选择每个点作为广告牌站点的概率。随后，选择一组位置，并给出目标值，表示所选广告牌位置集满足的需求。图2显示了LandScan数据集站点和候选广告牌站点。
图 3：LandScan空间单位和候选广告牌站点
在证明了模型在生成的数据集上的有效性之后，试图验证 ReCovNet 的适用性。与 Gurobi 求解器相比，本研究提出的 ReCovNet 模型表现出卓越的效率，并提供了具有竞争力的目标输出。虽然 ReCovNet 的目标值和最优解决方案之间仍然存在一些差距，但与 GA 相比，这些差距通常较小。更重要的是，我们的方法在求解时间方面显示出明显的优势。与遗传算法相比，此方法将求解时间缩短了一半，与Gurobi求解器相比，它实现了求解时间的十倍以上。
在表1中，可以观察到类似的趋势，Gurobi 给出了最高的目标值，而ReCovNet 速度最快。ReCovNet总能在相对较短的时间内提供比GA更好的解决方案。图4和图5提供了20个广告牌站点和30个影响半径内2个广告牌站点的问题的可视化结果。
表 1：Gurobi、GA和ReCovNet在M=20、30、40中的对比，R=2000
图 4：纽约市广告牌位置的可视化，服务距离为2000米，有30个站点
图 5：纽约市广告牌位置的可视化，服务距离为2000米，有20个站点
创新
（1）研究模型的创新
引入了一种利用深度强化学习（Deep Reinforcement Learning，DRL）来解决MCBLP问题的新方法——ReCovNet模型，如图 6，旨在准确地描述广告牌位置选择的过程。
通过应用我们的模型和方法来解决纽约现实世界的广告牌放置挑战，涉及1109个需求点和839个广告牌，我们的方法与其他方法相比具有显著的效率优势，并有效地缩小了与最优解决方案的差距。
（2）研究对象的创新
在纽约这样一个充满高人口密度、繁忙交通、多元人口和复杂交通模式的城市进行了实际应用，并展示出与其他方法相比的显著效率优势，有效地缩小了与最优解之间的差距。
图 6：ReCovNet网络结构
结论
最大覆盖广告牌位置问题 （MCBLP） 是最大覆盖位置问题的一种变体，在现实世界中具有广泛而关键的应用。现代求解器（例如 Gurobi 求解器）可以生成最佳解。但是，随着数据集大小变大，运行时间呈指数级增长。因此，为了克服这一挑战，本文考虑了一种新方法，以更有效地处理MCBLP，同时保持可比的客观值。我们整合了强化学习的结构和注意力模型的思想，构建了ReCovNet模型。在实验中，Gurobi 求解器无疑在最佳覆盖率方面表现最佳。在最佳值和运行时间之间存在权衡：虽然在考虑目标值时，ReCovNet 无法超越 Gurobi，但 ReCovNet 的运行时间明显少于 Gurobi。这证明了ReCovNet在效率是一个关键因素时的优势。
未来，我们将继续开发 ReCovNet 模型，并从两个不同的角度研究 MCBLP。地理空间大数据计算框架（Heitzler et al., 2017; Wang et al., 2019）值得开发，目的是提高模型的性能。其次，我们打算研究ReCovNet与深度学习模型的集成。这种集成可以进一步提高模型的效率。通过追求这些方向，我们热衷于优化ReCovNet 模型，使其适用于以高效率和高精度解决更多现实世界的问题。