本发明属于空间优化选址技术领域，涉及数字标牌最大覆盖模型和数字标牌空间优化选址方法，具体涉及一种基于数字标牌最大覆盖模型的数字标牌空间优化选址方法。

背景技术：

数字标牌是指通过大屏幕终端显示设备，在公共场所发布商业、娱乐和财经等信息的多媒体视听系统。与传统的电视广告、报纸广告相比，数字标牌可以根据不同受众群体，进行个性化、定制化广告投放。目前，数字标牌广告已经逐渐成为户外广告发展的主流趋势,支撑户外广告整体增长。通过动态创意的数字户外技术，广告主打造有吸引力的创意活动，可以为城市增添魅力。同时，一个好的数字户外广告活动可以对受众产生积极的影响。因此，合理的布设数字标牌不仅可以使市民生活更加便利，也可以促进城市的智能互联建设，为社会带来了一定的利用价值。

为了使数字标牌发挥更大的利用价值，学者以数字标牌为研究对象的研究主要分为两类：第一类是管理学科学者对数字标牌有关消费者行为学研究。roux等人通过建立可调节中介模型，提出数字标牌可以改善消费者购物环境。提出marion等通过分析购物者对购物环境中播放广告的数字标牌的反应，得到在商场利用数字标牌播放广告会对顾客产生积极的情绪，并增加冲动性购买和商店忠诚度。简言之，数字标牌可以改善消费环境，促进零售氛围，刺激消费行为。第二类是信息学科学者对数字标牌管理以及内容分发的系统建设研究：chen等提出了一种大型的动态平铺显示系统，该系统使用带有微型pc或智能设备的各种中小型屏幕来动态拼接超大尺寸显示器，具有成本低、实用性高以及灵活可拓展性高的特点。以大数据技术为代表的新兴技术促进了数字标牌终端管理、自动排期、内容分发等智能化平台研发。在数字标牌点位特征分析和空间选址分析方面，zhang等使用核密度分析方法和k-means聚类方法对北京市现有数字标牌分布情况进行分析，得到现有数字标牌的分布特征。xie等构建了数字标牌位置推荐模型实现了将数字标牌点位数据和多源地理特征数据进行融合进而推荐适合布设的区位。wang等使用数字标牌点位数据和poi等地理特征数据，融合huff模型和bp神经网络算法构建数字标牌选址模型，实现对北京市六环路以内的数字标牌选址实验。

综上，目前数字标牌空间选址技术仍主要集中在消费者行为、信息系统建设研究和位置推荐研究方面，而欠缺结合地理环境、布设成本和用户需求等方面的约束进行空间优化布局选址的技术方案。

技术实现要素：

为了克服上述现有技术的不足，本发明提供一种高效科学的基于数字标牌最大覆盖模型的数字标牌空间优化选址方法，通过要素处理、构建模型、求解模型和模型验证，自动地完成对数字标牌的优化选址，实现数字标牌的空间优化。本发明方法综合考虑多源要素，优化选址结果的参考依据强、时效性高、精准性高、数字标牌影响效果佳。

本发明提供的技术方案是：

一种基于最大覆盖模型的数字标牌空间优化选址方法，包括：要素处理、构建数字标牌最大覆盖模型、求解模型以及模型验证过程；具体步骤包括：

1)要素选取及处理，得到数字标牌多尺度建模因子序列：

包括但不限于数字标牌布设成本和位置信息、出租车行驶轨迹数据、微博签到点位置数据以及(大众点评)商业网点位置数据作为数字标牌区位建模因子，构造空间化的数字标牌区位建模因子，得到数字标牌区位建模因子的多尺度缓冲区数据，包括各区位建模因子数值及对应的坐标值；执行如下操作：

1_1)筛选得到数字标牌区位建模因子；

对城市数字标牌布设产生直接影响、且相互之间独立性和可操作性均较强的影响因素进行筛选，将数字标牌布设成本(如采用每15s播放价格作为布设成本)、数字标牌位置信息、微博签到点位置数据、出租车行驶轨迹数据以及(大众点评)商业网点位置数据作为数字标牌区位建模因子；

1_2)对数字标牌区位建模因子进行空间化处理，得到空间化数字标牌区位建模因子数据；

1_3)最后，以数字标牌位置(空间化点数据)为中心，建立设定范围(如50m-200m)的多尺度缓冲区，并将空间化数字标牌区位建模因子数据分别与数字标牌多尺度缓冲区进行空间连接操作，使数字标牌区位建模因子都能在统一的尺度上进行可视化以及建模，从而得到数字标牌多尺度建模因子序列；

2)构建数字标牌最大覆盖模型：分析数字标牌多尺度建模因子序列特征，并使用分位数作为参考，对多尺度建模因子序列进行重采样分级处理，得到分级数据，并构建数字标牌最大覆盖模型；执行如下操作：

2_1)分析数字标牌多尺度缓冲区数据中微博签到点位置数据、出租车行驶轨迹数据等各类因子的特征；

2_2)使用分位数作为分级参考，对数字标牌多尺度缓冲区数据进行重采样分级处理，得到多个(0至4五个级别)分级数据，作为各个数字标牌区位建模因子的分数；

2_3)依据各数字标牌区位建模因子的分数，以最大化覆盖人数为目标函数，数字标牌布设成本(数字标牌每15s播放价格)、数字标牌布设数量、出租车行驶轨迹、微博签到点位置以及大众点评商业网点位置等数字标牌区位建模因子的分数为约束条件，构建数字标牌最大覆盖模型。

其中，目标函数定义为式(1)：

目标函数旨在最大化覆盖研究区域内的受众；x＝{x1，x2，...，xn}表示n个数字标牌位置的决策二进制变量，如果第i块数字标牌被选择，那么xi＝1否则xi＝0；v＝{v1，v2，...，vi，...，vn}，其中vi表示相应第i块数字标牌设定(50m-200m)范围内覆盖的受众的数量。

约束函数定义为：

si＞1(2)

hi＞1(3)

ti＞1(5)

其中，t＝{t1，t2，...，ti，...，tn}，ti表示第i块数字标牌在设定(50m-200m)范围内覆盖的出租车轨迹的分级数；s＝{s1，s2，...，si，...，sn}，si表示第i块数字标牌在设定(50m-200m)范围内覆盖的大众点评商业网点的分级数；h＝{h1，h2，...，hi，...，hn}，hi表示第i块数字标牌在设定(50m-200m)范围内覆盖的微博签到点的分级数；公式(2)定义了第i块数字标牌缓冲区的大众点评分级数应大于1；公式(3)定义了第i块数字标牌缓冲区的微博签到分级数应大于1；公式(4)设置数字标牌总数等于p；公式(5)设置第i个数字标牌缓冲区的出车轨迹分级数应大于1；公式(6)表示布设数字标牌的总成本应小于c，c为常数。

3)构建数字标牌空间优化选址方法求解模型：利用改进的遗传算法求解数字标牌最大化覆盖模型，求解结果即为数字标牌优化选址结果，并使其最大化覆盖区域内的受众；

首先是将每一个解作为染色体进行编码；其次，初始化种群信息，以数字标牌最大覆盖模型的目标函数为适应度函数；最后，依据数字标牌最大覆盖模型的约束函数执行遗传算子选择、交叉、变异过程，将传统的人工设定选择、交叉以及变异概率修改为依据约束条件对算子进行选择、排序，自适应地选择符合条件的算子，通过多次迭代，得到的求解结果即为数字标牌优化选址结果；执行如下操作：

3_1)染色体编码

在改进的遗传算法中，针对最优化问题的可能解决方案以字符串形式编码(染色体)。数字标牌最大覆盖模型的可能解决方案是从包含m个数字标牌的集合中选择k个数字标牌，数字标牌集合l＝{l1，l2，...lm}，染色体从集合{1,2,…,m}中选择。因此，将染色体编码为一个整数字符串{t1,t2,…,tk}，表示被选择的k个数字标牌的索引。例如，如果m＝100且k＝5，则染色体{2，34，75，87，92}表示根据数字标牌最大覆盖模型的要求选择l2，l34，l75，l87和l92这五个数字标牌作为选址结果，编码在染色体上。

3_2)种群初始化

初始种群由p条染色体组成(即，p个数字标牌)，其中p是用户定义的参数，称为种群大小。初始种群的每个染色体都是通过从{1,2,…,m}集合中选择。

3_3)适应度函数计算

染色体的适应度表示其中编码的适应度相对于数字标牌最大覆盖模型的优点。数字标牌最大覆盖模型的目的是使覆盖受众的数量最大化。因此，如公式(1)所示，将数字标牌覆盖受众数量作为染色体的适应度，式(1)即为适应度函数，并进行适应度函数计算使得适应度最大化。

3_4)遗传算子：三个遗传算子，即选择，交叉和突变，用来从当前种群中创造出下一代种群(即，p个数字标牌的集合)。遗传算法的交叉率和突变率通常是根据实际情况和经验来选择的，但交叉率和变异率太大，会导致种群适应度的较大波动。交叉率和突变率很小，这将导致搜索缓慢而过早地收敛。本发明采用改进的自适应交叉算子和突变算子，首先判断当前种群是否符合数字标牌最大覆盖模型中的约束条件，若符合条件则计算种群的适应度函数值，判断其与平均适应度值之间的关系进而执行交叉和突变操作，公式如下：

其中，pc1和pc2是交叉率；pm1和pm2是突变率；fmax和favg是每一代种群的最大适应度值和平均适应度值；f'是交叉个体的适应度值；f是突变个体的适应度值。从公式(7)和公式(8)，可以看出，当f和f'小于favg时，使用较大的pc1和pm1值可以提高遗传算法的搜索能力。当遗传算法处于后期且f大于favg时，通过自适应方法降低交叉率和突变率，以确保遗传算法的稳定性并逐渐接近最优解。因此，使用自适应思想来改进交叉和突变算子使遗传算法具有更好的适应性和全局收敛性。

模型有效性验证：

本发明具体实施时，利用覆盖率(优化选址结果覆盖的受众数量与研究区域内受众数量之间的比值)、覆盖数量(优化选址结果覆盖的受众数量)和算法运行时间三个评价指标对数字标牌空间优化选址方法进行有效性验证。本发明方法综合考虑多源要素，优化选址结果的参考依据强、时效性高、精准性高、数字标牌影响效果佳。

与现有技术相比，本发明的有益效果是：

本发明提供了一种高效科学的基于最大覆盖模型的数字标牌空间优化选址方法，通过要素处理、构建模型、求解模型以及模型验证，自动地完成对数字标牌的优化选址，实现数字标牌的空间优化布局。本发明方法综合考虑多源要素，选址结果的参考依据强、时效性高、精准性高、数字标牌影响效果佳，能够满足众多广告主和媒体商的利益需求，可推广到具有数字标牌空间优化选址需求的多种应用领域。

附图说明

图1是本发明提供的数字标牌优化选址方法的流程框图。

图2是数字标牌区位因子空间化处理的流程框图。

图3是数字标牌最大覆盖模型构建的流程框图。

图4是改进的遗传算法求解方法的流程框图。

图5是200米尺度缓冲区下改进的遗传算法迭代过程示意图；

其中p为数字标牌布设数量，横坐标为迭代次数；纵坐标为覆盖受众数量。

图6是各尺度缓冲区下改进的遗传算法求解结果的覆盖率对比示意图。

图7是各尺度缓冲区下改进的遗传算法求解结果的受众覆盖数量对比示意图。

图8是200米尺度缓冲区下遗传算法迭代过程示意图。

图9是200米尺度下三种算法求解结果的覆盖率对比示意图。

图10是200米尺度下三种算法求解结果受众覆盖数量对比示意图。

图11是200米尺度下三种算法的求解时间对比示意图。

图12是本发明实施例中数字标牌优化选址结果图。

具体实施方式

下面结合附图，通过实施例进一步描述本发明，但不以任何方式限制本发明的范围。

本发明提供一种高效科学的基于数字标牌最大覆盖模型的数字标牌空间优化选址方法，通过要素处理、构建模型、求解模型和模型验证，自动地完成对数字标牌的优化选址，实现数字标牌的空间优化。图1表示了本发明提供的数字标牌优化选址方法的流程。如图1所示，以北京市城区六环路内为例，本发明方法具体实施包括如下具体步骤：

1)数字标牌区位建模因子选取并进行空间化处理

考虑到资料获取的难易程度以及影响因素难以量化等原因，本发明主要按照基础性、前瞻性、易获取、可定量、区域全覆盖等原则，筛选对数字标牌产生直接影响、而相互之间独立性和可操作性均较强的数字标牌每15s播放价格和位置信息、微博签到点数据、出租车轨迹数据以及大众点评商业网点数据作为本发明的数字标牌区位建模因子，然后对因子进行空间化处理。

收集了北京市六环路以内5823块户外数字标牌基础数据以及数字标牌影响要素数据。其中，数字标牌基础数据包括数字标牌地理位置以及数字标牌每15s的平均播放价格；数字标牌影响要素数据主要包括从统计口径获得的该市城区六环路内大众点评商业网点数据、微软出租车轨迹数据以及新浪微博的社交网络签到数据。

1_1)数字标牌区位建模因子空间化

数字标牌区位建模因子空间化处理如附图2，首先，将收集的数字标牌每15s播放价格和位置信息、微博签到点数据、出租车轨迹数据以及大众点评商业网点数据等数字标牌影响因素数据作为数字标牌区位建模因子，对其进行数据预处理，删除奇异数据、填充缺失值；其次，将修正后的建模因子进行投影转换，并通过空间连接操作将其关联到该城市建筑物空间实体中(本研究采用了2013年全国第三次经济普查时采集制作的该城市建筑物数据)，完成数据空间化，形成数字标牌区位建模因子空间数据。

1_2)构建数字标牌多尺度建模因子序列

以数字标牌点数据为中心，建立50m-200m的多尺度缓冲区，并将数字标牌区位建模因子空间数据与数字标牌50m-200m缓冲区进行空间连接操作，使所有建模因子都能在统一的尺度上进行可视化以及建模，从而得到数字标牌多尺度建模因子序列。

2)构建数字标牌最大覆盖模型

数字标牌最大覆盖模型构建过程如图3所示，分析数字标牌多尺度建模因子序列的特征，并使用分位数作为参考对多尺度建模因子序列进行重采样分级处理，得到分级数据并构建数字标牌最大覆盖模型。

2_1)分析数字标牌多尺度建模因子序列的特征；使用分位数最为分级参考，对数字标牌多尺度建模因子序列进行重采样分级处理，得到0至4五个级别的分级数据作为各因子的分数。

2_2)构建数字标牌最大覆盖模型。其中，依据上述得到的各类因子的分数，以最大化覆盖人数为目标函数，数字标牌布设成本(数字标牌每15s播放价格)、数字标牌布设数量、各类因子的分数为约束条件，构建数字标牌最大覆盖模型。

其中，目标函数定义为：

公式(1)为目标函数，旨在最大化覆盖研究区内受众；x＝{x1,x2,…,xn}表示n个数字标牌位置的决策二进制变量,如果数字标牌被选择，那么xi＝1否则xi＝0；v＝{v1,v2,…,vn}表示相应第i块数字标牌50m-200m范围内覆盖的受众的数量。

约束函数定义为：

si>1(2)

hi>1(3)

ti>1(5)

其中，t＝{t1,t2,…,tn}表示第i块数字标牌在50m-200m范围内覆盖的出租车轨迹的分级数；s＝{s1,s2,…,sn}表示第i块数字标牌在50m–200m范围内覆盖的大众点评商业网点的分级数；h＝{h1,h2,…,hn}表示第i块数字标牌在50m–200m范围内覆盖的微博签到点的分级数；公式(2)定义了第i块数字标牌缓冲区的大众点评分级数应大于1；公式(3)定义了第i块数字标牌缓冲区的微博签到分级数应大于1；公式(4)设置数字标牌总数等于p；公式(5)设置第i个数字标牌缓冲区的出车轨迹分级数应大于1；公式(6)表示布设数字标牌的总成本应小于c。

3)构建数字标牌空间优化选址方法求解数字标牌最大覆盖模型

基于改进的遗传算法的数字标牌最大覆盖模型解决方案的总体过程如图4所示。求解数字标牌最大覆盖选址模型属于np-hard问题，本发明通过引入遗传算法求解此模型。并对遗传算法加以改进，使其适应数字标牌空间优化选址问题，从而实现构建数字标牌空间优化选址方法。本发明首先是将每一个解作为染色体进行编码；其次，初始化种群信息，以数字标牌最大覆盖模型的目标函数为适应度函数；最后，依据数字标牌最大覆盖模型的约束函数执行遗传算子选择、交叉、突变过程，将传统的人工设定选择、交叉以及变异概率修改为依据约束条件对染色体进行排序，筛选符合约束条件的染色体，并按覆盖人数对染色体进行排序，自适应的选择符合条件的染色体，最终通过多次迭代得到稳定的优化选址结果。

3_1)染色体编码、初始化种群、适应度函数计算

首先，将已布设的数字标牌作为染色体，并对其进行编码。数字标牌优化选址的可能解决方案是从包含m个数字标牌的集合中选择k个数字标牌作为选址结果，数字标牌集合l＝{l1，l2，...lm}。因此，将染色体编码为一个整数字符串{t1,t2,…,tk}表示被选选择的k个数字标牌的索引，每个元素li∈l，i＝1，2，…,k。

其次，初始化种群。初始种群由p条染色体组成，其中p参数称为种群大小。初始种群的每个染色体都是通过从{1,2,…,m}集合中选择。具体实施时，将p分别设为10,50,100,200,300，…，2500，进行对组对比实验，查看不同p值下，数字标牌覆盖受众的情况。最后，设置遗传算法的适应度函数为模型目标函数—最大覆盖受众，在迭代过程中计算选取不同的染色体，记录其值的变化，并以此作为后续对染色体进行排序时的评价标准，使遗传算法更加适应数字标牌最大覆盖模型求解问题。

3_2)遗传算子：在本发明中，改进选择、交叉、突变概率值的设定过程，首先将数字标牌最大覆盖模型带入遗传算子的计算过程中，判断染色体是否符合最大覆盖模型中微博签到分级数量限制、大众点评商业网点分级数量限制以及出租车轨迹分级数量限制等约束条件，在符合各约束条件的前提下，计算其适应度函数值及适应度函数值的平均值，并对符合条件的种群进行排序，选择超过适应度函数平均值的种群进入下一次迭代，以此类推，直到迭代结束，得到相对较优的解作为数字标牌优化选址的结果。

其中，以200米数字标牌缓冲区为例。当缓冲区尺度为200米时，符合数字标牌最大覆盖模型的数字标牌数量为2500。当p值从10增加至2500时，以数字标牌多尺度建模因子为输入，改进的遗传算法的迭代图如附图5所示，其中横坐标为迭代次数，纵坐标为求解结果覆盖受众的数量。首先，随着迭代次数的增加，曲线逐渐趋于平缓，说明结果已接近最优解；其次，随着p值的增加，覆盖受众的数量逐渐增多，当p值为2500时，覆盖受众数量已接近180000。

4)数字标牌空间优化选址方法有效性验证：

为了验证数字标牌空间优化选址模型的性能，并使模型的选址结果更为准确可靠，本发明采用覆盖率(优化选址结果覆盖的受众与研究区内受众总和之间的比值)、覆盖数量(优化选址结果覆盖的受众数量)和算法运行时间三个评价指标对数字标牌空间优化选址方法进行有效性验证。

a.覆盖率

覆盖率是指优化选址结果覆盖的受众与研究区内受众总和之间的比值。

b.覆盖数量

覆盖数量是指优化选址结果覆盖的受众数量。

c.算法运行时间

算法运行时间是指使用算法求解数字标牌最大覆盖模型所使用的时间。

4_1)本发明使用覆盖率、覆盖数量和算法运行时间作为评价指标，从求解的正确性和时效性两个方面评估本发明。

当p值从10增加到2500时，50米至200米数字标牌缓冲区下的覆盖率的对比如附图6所示。随着缓冲区尺度的增加，数字标牌覆盖受众的覆盖率逐渐增加，当数字标牌缓冲区为200米时，覆盖率相对较高。

当p值从10增加到2500时，50米至200米数字标牌缓冲区下的覆盖数量的对比如附图7所示。随着缓冲区尺度的增加，数字标牌覆盖受众的覆盖数量逐渐增加，当数字标牌缓冲区为200米时，覆盖数量相对较高。

综上所述，算法随着数字标牌缓冲区尺度的增加，覆盖率和覆盖数量依次增加。当缓冲区尺度为200米时，求解结果的覆盖率和覆盖数量同时相对较高。说明算法的正确性和有效性得到了验证，但时效性相对较弱。

4_2)为了进一步验证本发明提出的基于最大覆盖选址模型的数字标牌优化选址方法的有效性，本发明将改进的遗传算法与已有的遗传算法和gurobi软件求解进行对比。

其中，以200米数字标牌缓冲区尺度为例，使用已有的遗传算法求解数字标牌最大覆盖模型，迭代过程如附图8所示。当数字标牌缓冲区尺度为200米时且p值从10增加值2500，随着迭代次数增加，曲线趋于平缓，且随着p值增加，覆盖数量逐渐增多，当p值为2500时，覆盖数量已超过170000。

当数字标牌缓冲区尺度为200米时，改进的遗传算法与现有的遗传算法和gurobi软件求解方法进行对比，对比结果如附图9至附图11所示。从附图9和附图10中可以看出，随着p值增加，改进的遗传算法的覆盖率和覆盖数量明显高于已有的遗传算法和gurobi软件求解方法，且引入遗传算法求解数字标牌最大覆盖模型的覆盖率和覆盖数量均高于gurobi软件求解方法。同时，从附图11中可以看出引入遗传算法求解模型所使用的时间明显高于gurobi软件求解方法。

综上，在引入遗传算法求解模型后，覆盖率和覆盖数量高于gurobi软件求解方法，但程序运行时间明显高于gurobi软件求解方法。再次证明了使用改进的遗传算法求解数字标牌最大覆盖模型，其求解的正确性和有效性相对较高，但时效性较差。

基于最大覆盖模型的数字标牌优化选址结果如附图12所示。从图中可以看出，当p值为10时，优化选址结果主要分布在三里屯、奥林匹克公园、798艺术园区以及中央商业区等人流量较大、数字标牌可视性较强的区域；随着p值增加，优化选址结果以北京市地铁2号线环路为中心呈现放射性分布，且北部多于南部，东部多于西部。

需要注意的是，公布实施例的目的在于帮助进一步理解本发明，但是本领域的技术人员可以理解：在不脱离本发明及所附权利要求的精神和范围内，各种替换和修改都是可能的。因此，本发明不应局限于实施例所公开的内容，本发明要求保护的范围以权利要求书界定的范围为准。