可视化城市级停车场服务能力动态覆盖模型

张康帅 彭 磊

1(华南理工大学 机械与汽车工程学院 广州 510641)

2(中国科学院深圳先进技术研究院 深圳 518055)

1 引 言

随着国内小型载客汽车和私家车保有量的快速增长，现有的停车设施愈发难以满足日益增长的停车需求。为了提高现有停车设施的利用率，北京、上海、成都、深圳等城市均已提出建设城市级停车诱导系统(City-wide Parking Guidance Systems，CPGS)的计划。CPGS 通过向驾驶员提供其收集处理的城市各处停车场实时信息，减少驾驶员搜寻停车场的时间以提高停车设施和道路的利用率[1]。CPGS 可视为一种能够响应城市中驾驶员在任意位置、任意时间停车需求的信息物理(Cyber-Physical)搜索引擎[2]。由于城市中车辆、停车场众多且停车需求频繁，因此为 CPGS 设计良好的信息结构从而提升其工作效率具有较大的实际意义。

传统 CPGS 对收集数据的处理方式通常是简单地根据空车位率将停车场状态分为充足、中等、短缺等状态[3]，没有对数据进行深度挖掘，或根据一些其他指标对停车场进行定量评估[4]，故其所得的结果通常是静态的。这些方法通常着眼于单个停车场，忽略了不同停车场之间的相互影响。受 Google 提出的网页排序算法 PageRank[5]的启发，在前期研究中，我们将城市中的所有停车场建模为以停车场为节点、连接它们的道路为边的复杂网络[6]。其中停车场的一些静态参数(如容量和价格等)，被用于对初始服务能力进行建模，而停车巡游行为被建模为车辆在停车场之间转移的概率，即网络的动力学特性，该模型被命名为 ParkingRank[7]。起初因为没有考虑可用车位数的变化对网络动力学的影响，此时模型是静态的；后来通过导入可用车位数变化的相关数据对其进行了改进，使其可以根据停车场的静态参数、实时可用车位数和停车场之间的空间关系，对停车场实时服务能力进行定量评估并据此对停车场进行排序[8]。

为了使 ParkingRank 算法可以与现有信息系统集成起来，本文在该主题上做了进一步的工作。其中的关键在于使人们(尤其是城市管理人员)可以更直观、高效地去理解 ParkingRank 计算结果的可视化方法，在此基础上人们可以制定更合理的计划和管理决策。由于停车场与连接它们的道路共同构成了地理空间网络，因此首选的可视化方案是覆盖模型。其中该模型广泛应用于与地理空间相关的应用。覆盖模型通过兴趣点(Point of Interest，POI)的 Voronoi 图(或 Thiessen 多边形)[9]无缝且不重叠的覆盖研究范围，以可视的方式显示一些有用的信息，如 POI 的密度、各 POI 的服务区域等，从而可以快速清晰地传递信息。同时，在此基础上还可以进行更深入的研究，如新站点选址和 POI 网络的健壮性评估。相较现有信息系统中，以空车位率或车位使用率为指标的热力图[10]来展示大规模停车场实时信息的方式，覆盖模型可以提供更丰富的信息。

Voronoi 图是一种空间分割算法，可以根据给定的生成点将空间划分为互斥的多边形区域。它具有区域内任意点到该区域生成点的距离比到其他区域生成点的距离都短的特点，这种距离通常采用欧式距离衡量，有时也会使用曼哈顿距离。由于这一特性，这些区域是表示 POI 服务或工作区域的理想方式，如通信基站[11]、地铁站[12]或医院[13]的服务区域，且在此基础上可进一步研究选址优化，进行健壮性分析等[14-15]。

原始的 Voronoi 图仅根据生成点的位置坐标来计算多边形。但是，停车场的实际情况较为复杂，这是因为停车场的服务能力总是随可用车位数的变化而变化，甚至受到周围停车场的影响。因此，若要为每个停车场计算合适的多边形，不仅要考虑停车场的位置，还要考虑影响服务能力的因素，并将其映射到距离值上。停车场的服务区域应是动态的，代表停车场服务能力的多边形应根据其服务能力的变化而放大或缩小，且被约束在合适区域内，使其符合停车场服务区域的实际情况。因此，本文提出了一种带边界约束的加权 Voronoi 图来满足停车场网络的要求。

加权 Voronoi 图通过使用加权欧式距离来增加与地理空间无关因素的影响。其中，加权 Voronoi 图通常使用基于栅格的方法构建[16]。该方法首先将平面离散为点，然后根据定义直接构建。另一种更准确快速的方法是拓扑叠加法，可以生成乘法加权的 Voronoi 图[17]。拓扑叠加法基于 Apollonius 圆，它是到两个固定点的距离保持恒定比率的点的轨迹，生成点对应的多边形区域可以通过其与所有比其权重大的生成点形成的 Apollonius 圆的交集，减去与比其权重小的生成点形成的所有 Apollonius 圆来获得。

本文需要解决的另一个问题是大型停车场网络的高效计算。与 PageRank 一样，ParkingRank 也是基于图的计算，图的大小将极大地影响计算效率。对于拥有超过 10 000 个停车场的城市(在如今的中国非常普遍)，直接使用 ParkingRank 算法计算每个停车场的服务能力是一项非常耗时的工作。在本文中，我们尝试通过聚类分割整个城市的停车场网络，从而加快计算速度，使实现城市级停车场的动态覆盖变得可行。

2 城市级停车场服务能力覆盖模型

2.1 停车场服务能力的量化

本文中，停车场服务能力的量化通过 ParkingRank 算法[7-8]实现，在这里仅对其关键步骤进行介绍。首先，根据公式(1)计算每个停车场的初始服务能力，即当停车场都为空且不考虑不同停车场之间的相互作用时的服务能力。

2.2 边界约束加权 Voronoi 图

停车场的服务能力将作为可视化过程中加权 Voronoi 图的加权项。但是，根据加权 Voronoi 算法，如果某点的权重远大于其相邻点，则对应的 Apollonius 圆会扩大到包围其相邻点。这种情况对于某些对象也许是合理的，但对于停车场，这将导致大型停车场周围的一些小型停车场被嵌入大型停车场的服务区域中，从而失去自己的服务区域。从停车引导的角度看，这些小型停车场对于其附近车辆都是不可见的，即 CPGS 会引导所有车辆前往少数大型停车场，这与司机选择就近停车的现实情况不符。

为了解决这个问题，停车场服务区域的边界应被限制在适当范围内，以避免侵入较弱邻居的边界并最终将其包围。本文在 Delaunay 三角剖分的帮助下改进了加权 Voronoi 图。由于 Delaunay 三角剖分最大化了最小角，避免创建细长的三角形，使 Delaunay 三角形“形状规则”，且具有唯一性(任意 4 点不能共圆)。

其中，a、bx、by和c由以下行列式计算：

由于 Delaunay 三角剖分的性质确保了停车场组成的 Delaunay 三角形中不会嵌入其他停车场，因此，如果将 Apollonius 圆的变化限制在该三角形内，那么就可以解决原始加权 Voronoi 图停车场服务区域包围的问题。

对于任意停车场，如果假定停车场p和pi、pj组成一个 Delaunay 三角形q，那么 3 个停车场的服务能力分别为PRp、PRi和PRj。则停车场p在 Delaunay 三角形q中所占的面积Poly(p,q) 为：

图1 使用边界约束加权 Voronoi 图进行覆盖的示例Fig. 1 Example of coverage by boundary constrained weighted Voronoi diagram

2.3 将覆盖范围扩展至城市级停车场网络

图2 使用 MeanShift 进行停车场聚类的示例Fig. 2 Example of clustering the parking lots by MeanShift

图 2 为一个聚类过程的示例。其中，图 2(a)为实际的停车场位置，每个点代表一个停车场，点的大小代表其初始服务能力的强弱。图 2(b)为聚类过程，其中“停车场”开始移至高密度位置，总体而言，小型停车场倾向于移至较大型停车场；聚类完成后，停车场将汇聚到地图上的不同点，如图 2(c)所示。图 2(d)将聚类中的停车场重新映射到其真实位置，同一聚类中的停车场采用相同的颜色表示。

至止，整个城市中的停车场组成的网络已经被划分为许多子网络，这些子网络由相对较少的停车场组成。通过在每个子网络上并行应用服务能力量化和可视化算法，可以在合理时间内实现整个城市范围内停车场的覆盖。在这种情况下，停车场服务能力量化和可视化的时间复杂度约为 ，其中 是子网络中停车场的平均数量。若 足够小(如小于20)，则计算效率将大幅提高。

3 仿真与分析

3.1 仿真场景

深圳是中国最发达的城市之一，拥有超过 300 万辆汽车和约 13 000 个停车场。本次仿真选择了深圳市中心城区之一的罗湖区，共涉及超过 1 000 个停车场。如果直接对如此大量的停车场进行服务能力量化和可视化，那么计算所需时间过长，无法反映整个城市停车场服务能力的实时变化。因此，本文尝试使用第 2 小节提出的方法来进行计算。此次仿真中共涉及 1 096 个停车场，表 1 是详细的停车场数据表。其中，位置为停车场的 GPS 坐标；价格为停车首小时收费；可用车位率是可用停车位数与总停车位数的比值，其采样间隔为 15 min。

3.2 仿真与分析

首先，使用聚类的方法将 1 096 个停车场拆分成多个子网络，以减轻后续的计算压力。考虑到司机通常将车停在目的地附近步行几分钟可达的停车场内，因此可以将超参数dnbhd设置为与此相关的值。正常成年人 3～4 min 可以走 300 m，故在本次仿真中，dnbhd被设置为 220 m，这使得聚类中的任何停车场到其最近停车场的欧氏距离不超过 220 m，同时每个子网中停车场数目不会太多(如超过 50 个)。

如图 3 所示，当聚类完成时，1 096 个停车场被分为 141 个子网，每个子网具有 1～29 个停车场，且每个聚类的服务区域以不同颜色进行区分。其中每个停车场聚类的服务区域，是使用初始服务能力为加权得到的聚类中各停车场服务区域的并集。图 3 的右下部分是图中蓝色矩形包围区域的放大，其中有 4 个小型停车场网络。

因为每个小型停车场网络包含的停车场数最多为 29 个，相对较少，故可以直接应用服务能力量化和可视化算法，而不必担心其计算延迟。

图 4 是一个小型停车场网络，位于图 3 右下角放大的局部区域左侧。此小型网络包含 11 个停车场，具体分为 3 种类型：ID 编号为 4、5、6、9 的是住宅类停车场，ID 编号为 10、11 的是商业类停车场，ID 编号为 1、2、3、7、8 的是隶属于办公室的停车场。

表1 停车场数据详表Table 1 The detailed carparks data sheet

图3 1 096 个停车场通过 MeanShift 形成的 141 个聚类Fig. 3 1 096 carparks form 141 clusters by MeanShift

图4 一个聚类中包含的小停车场网络Fig. 4 A tiny carpark network included in a cluster

图5 停车场网络中停车场服务能力随时间的变化Fig. 5 Time-varying service capabilities of the tiny carpark network

根据给定的信息和地理空间关系(如表 1 所示)，可以基于 ParkingRank 算法来量化该聚类中停车场的服务能力。图 5 为图 4 中 11 个停车场在工作日和休息日的服务能力变化情况。由于停车场的可用车位数随时间改变，因此停车场的服务能力也随时间改变。通常情况下，休息日去办公的人减少，办公室停车场(ID 编号为 1、2、3、7、8)的服务能力相较工作日有明显的提升。

图6 不同时刻停车场网络的可视化覆盖Fig. 6 Visualized coverage of the tiny carpark network at different moments

此外，可以根据量化出的服务能力同步可视化这个停车场网络。图 6 清楚地显示了停车场服务区域随服务能力的变化情况。图 6 分别为午夜、早晨、中午和晚上 4 个典型时刻的可视化效果，相应的服务能力在图 5 中用红色垂直点线突出显示。在午夜(图 6(a, e))，大多数人们在家中睡觉，汽车聚集在居民楼的停车场(ID 编号为 4、5、6、9)中，可用停车位的短缺使其服务能力大大降低，而公共场所停车场在此时有足够的停车位，从而具有较强的服务能力。因此，住宅类停车场的服务区域看起来比其他区域小得多。类似地，当人们去办公室(图 6(b, c, f, g))或在晚上娱乐(图 6(d, h))时，停车场的服务区域将根据他们服务能力的变化而不断变化，同时停车场服务区域的连通性在整个过程中保持良好。此外，由于休息日上班人数减少、在家休息的人数增多，办公室停车场(ID 编号为 1、2、3、7、8)的服务区域相较工作日明显增大。同时，休息日外出娱乐的人数增多，商业类停车场(ID 编号为 10、11)爆满，导致其服务区域锐减(对比图 6(c, g))。显然，这种覆盖在停车场网络的可视化是合理可行的。

3.3 与现有方案的对比

Wang 和 Shi[12]利用基于最短距离、最小时间等参数的 Voronoi 图来划分地铁站的服务区域，由于得到的服务区域是静态的，所以这种方法仅适用于服务能力相对稳定且没有显著差异的 POI。而本文所提出方法得到的服务区域是动态的，可以表现停车场服务能力随可用车位数变化而变化的性质。曹昉等[19]提出一种变权重加权 Voronoi 图，根据变电站负载率和供电半径动态调整权重，动态地划分城市电网中变电站的供电范围，但这种权重调整方式利用了变电站间隔较远且分布较为均匀的性质；而本文提出的方法利用了停车场服务区域主要受相邻停车场影响的特点，为密集且分布不均的 POI 服务区域划分提供了方案。此外，前述提到的两种改进 Voronoi 图均需使用基于栅格的方法构建，计算量较大，不适合需要实时更新的场合的应用。

本文提出的方法与传统加权 Voronoi 图[9]的比较如图 7 所示。图中展示的是根据停车场初始服务能力分别应用原始加权 Voronoi 图和本文方法的覆盖结果，在没有边界限制的情况下(图 7(a))，一些服务能力较强的停车场可以任意扩大服务区域，并最终包围临近停车场。在这种情况下，由于许多小型停车场变成了孤立的节点，仅与较强的节点有连接，使网络的连通性大大受损。相反，本文方法(图 7(b))的结果中每个停车场的边界都是由相邻的停车场而不是最强大的停车场决定的，整个停车场网络的连通性较好，更符合实际情况。

图7 原始加权 Voronoi 图和边界约束加权 Voronoi 图覆盖效果的比较Fig. 7 Coverage comparison between original weighted and boundary constrained weighted Voronoi

此外，在本模型中，由于预先将停车场分入不同的子网络，减小计算量的同时实现后续过程在各聚类上并行，使得用各停车场服务区域动态覆盖整个城市成为可能。

4 总结与展望

本文提出了一个可视的城市级停车场动态覆盖模型。首先，借助 MeanShift 算法将整个城市中的停车场分入多个聚类，形成许多小型停车场网络。然后，使用 ParkingRank 算法量化了每个小型停车场网络内停车场的服务能力。最后，通过边界约束加权 Voronoi 图将量化的停车场服务能力映射到地理空间上，形成可视服务区域，由于每个停车场的边界都是由相邻的停车场而不是最强大的停车场决定的，使得网络连通性比原始加权 Voronoi 图更具优势。在仿真部分，本文建立了包含深圳市罗湖区所有停车场的动态覆盖实例，这是首次建立包含城市中所有停车场的大规模动态覆盖模型，仿真结果表明了本模型的合理性和可理解性。

可视的城市级停车场动态覆盖涉及复杂网络、交通流等多方面的理论、方法和技术，本文模型在以下几个方面还存在一些限制与不足，需要做进一步的工作。例如，在停车场网络动力学中并没有考虑实时交通状况对司机停车巡游行为的影响。此外，本文在停车场聚类过程中直接使用了不同停车场之间的欧式距离，在未来工作中将考虑使用道路距离或改用其他聚类方法并对聚类效果进行评估。