基于分离障碍物的地下车库车位排布算法

2023-02-08冯嘉宇王潇霆

智能计算机与应用 2023年1期

冯嘉宇，王潇霆，沈炜

（浙江理工大学信息学院，杭州 310018）

0 引言

城市车位短缺是制约现代城市发展的新问题［1］。地下车库为缓解车位短缺提供了一个成本更低的方案［2］，广大开发商也开始研究如何在地下车库中排布才能得到更多的车位［3］，以获取更高的经济效益。目前，地下车库的车位排布仍以人工设计为主，但是由于外边界不规则和内部的障碍物等问题［4］，人工设计的效率较低。因此，一些专家学者开始将自动化设计运用于解决地下车库的车位排布问题。

车位排布算法和工业生产中的二维排样算法很相似。早在1981 年，Fowler 等［4］就已证明了不带约束条件的排样问题是NP 完全问题。因此，在排样问题基础上添加了更多约束条件的车位排布问题也是一个NP 完全问题。对于车位排布问题，现存的多数算法都是从传统排样问题中优化得到的。Abdelfatah 等［5］提出了一种适用于矩形区域的设计线性规划模型，并考虑了车道夹角；Kong 等［6］通过调整车位的长和宽，运用混合整数非线性模型计算车位长和宽的变化对于最终可排列车位数量的影响；Huang 等［7］设计了一套基于模拟退火算法的矩形区域内车位排布问题的通用算法；Syahrini 等［8］则通过线性规划模型设计了一套适用于三角形区域的车位排列算法；Ihda 等［9］提出了一种适用于平行四边形区域的线性规划模型；Ferreira 等［10］设计了一种车位平行叠放的排布方式，用于优化矩形高密度停车场的车位排布；Timpner 等［11］提出了停车空间优化模型；Banzhaf 等［12］通过建立混合整数规划模型，将普通停车场改造为高密度停车场；Nourinejad 等［13］使用排队论构建了混合整数模型，并通过benders 分解算法进行车位排布。但是，上述这些研究都集中于地表停车场，而没有考虑障碍物的约束。

对于带障碍物约束的地下车库的排列研究，徐涵喆［14］等设计了一种基于遗传算法的外圈车位排布启发式算法。黄逸彬等［15］则通过对不规则停车场区域进行图形分割后，运用粒子群算法进车位排布。利润等［16］通过网格化，将原问题区域划分为多个可应用排布算法的子区域，提出了一种基于贪婪分割的地下车位排布算法。但是这些研究者都没有充分利用到每栋楼中承重墙之间的空间，同时车位与边界、障碍物之间存在的夹角也造成了大量的面积浪费。

为了充分利用停车场空间，尽可能最大化车位数量，本文提出了一种根据内部障碍物位置划分为内圈和外圈之后，再对两个区域进行分离处理的启发式自动化排布算法。该算法可以适用于内部障碍物大致平行的任意不带曲边的地下车库；可以通过计算合理排布车位、车位和承重柱的位置；可以将排布结果可视化呈现，辅助人工设计。

1 问题描述

车位排布问题通过输入一个地下车库的外边界和内部所有的障碍物，需要在满足约束条件的情况下，实现车位数量的最大化。

1.1 约束条件

地下车库车位排布的约束条件，在传统排样问题基础上，根据车位排布场景的特殊性，其主要约束条件为：

（1）外边界约束：任意车位模块、车道不得超过外边界所包含的范围。

（2）内部障碍物约束：任意车位模块、车道不得与内部障碍物重叠。

（3）车位与车道分离的约束：车位模块不能与车道重叠。

（4）连通性约束：必须保证每个车位可以驶入车道，所有车道之间必须相互连通。

由于约束条件4 中的入口和出口需要在车位排布完成之后由人工确定，故本文只需保证各个车位模块之间有车道连通即可。

1.2 约束条件的数学模型

地下车库的外边界可以用一个点的集合Pborder＝｛（x1，y1），（x2，y2），…，（xn，yn）｝，构成一个封闭的多边形Sborder。在地下车库内，存在多个多边形表示的内部障碍物Tbar ＝｛T1，T2，…，Tm｝，每个内部障碍物也由一个点的集合构成＝｛（x1，y1），（x2，y2），…，（xn，yn）｝。

外边界和内部障碍物作为输入条件，满足：

定义Pm为车位的集合，R为车道的集合，则存在如下约束：

其中，式（2）表示外边界约束；式（3）、式（4）表示内部障碍物约束；式（5）表示车位与车道分离的约束。

车道集合R ＝｛R1，R2，…，Rm｝是由多个多边形组成的集合。车道的连通需要通过不同车道之间的相交来实现，所以对于所有的车道，需满足：

同时每个车位必须有车道相邻接。对于表示任意车位的矩形ABCD，将其四边向外延长车位宽度β，如图1 所示。延长后满足：

图1 车位向外延长Fig.1 Parking Spaces extend outwards

1.3 车位模块

车位模块是由在同一方向上邻接同一车道的车位排列形成的平行四边形，按照倾角的不同，可以分为 0°、30°、45°、60°、90° 和垂直式［17］。IL Chodash［18］等人通过分析0°、30°、45°、60°、90°5 种不同角度的停车位在现实停车场中的表现，发现90°的车位模块在67%的场景中都可以保证车位数量的最大化。赵志强［19］等用车道面积与车位面积衡量车位实际占用面积，发现90°的车位模块占用面积最少。综合这些结论，本文在车位排布中主要采用90°的车位模块，在宽度不够时采用0°的车位模块。

车位模块中采用每若干个车位之间设置承重柱的方式构建柱网。其中，两个相邻承重柱之间的车位数量取决于承重柱的最大间隔。车位模块中的每个车位都是长为α、宽为β的矩形，对于承重柱的最大间距d，在90°的车位模块中需要在每个车位之间插入一个承重柱，0°的车位模块则为

1.4 算法流程

本文提出的算法，主要分为以下4 个阶段：

（1）划分内外区域：根据外边界和内部障碍物的坐标，用矩形包裹所有障碍物后，划分为矩形内部和矩形外部。

（2）矩形内部区域车位排布：通过像素分割栅格化内部区域［20］并建立矩阵；通过矩阵计算，得到矩形内部区域车位数量最多的排布方案，并保证与外部区域连通。

（3）矩形外部区域车位排布：对矩形外部区域进行分割，使用遗传算法计算得到矩形外部区域车位数量最多的排布方案。

（4）车位坐标计算和可视化：根据车位模块的位置，计算车位坐标。

本文主要对第1 和第2 阶段进行研究，第3 阶段矩形外部区域的车位排布，主要参考徐涵喆［16］等提出的遗传算法排布方案，第4 阶段车位模块的坐标则通过遍历计算得到。

2 模型建立

2.1 内部矩阵构建

设定一个长和宽均平行或垂直于内部障碍物的最小矩形Srec，使得Tbar⊆Srec，则矩形外部区域Soutside为：

记Srec平行于x轴方向的边长为a，平行于y轴方向的边长为b，左上角顶点的坐标为（x0，y0）。按照分割精度δ分割Srec上的点，可以得到所有点坐标的集合Prec：

构建初始矩阵A0，其中所有元素满足：

根据A0中的元素值，得到A(i，j)，i∈

矩阵A即为描述矩形内部区域的模型。其中-1 表示有障碍物，0 表示空旷。

2.2 分割精度选择

在判断每个正方形是否空旷时，因为不包含任何障碍物才认为是空旷的，所以存在一定的面积损失［19］。例如：对于长6 m、宽2.5 m 的停车位来说，δ为0.5 m 时每个正方形损失会占单车位1／60 的面积，δ为0.25 m 时占1／240。所以δ越小，损失的正方形面积也越小。但是，当δ缩小时，所需计算次数和内存是以O（n2）复杂度增长，导致计算效率的下降。

为了选择合适的δ值，在考虑整除特性的基础上，选择1 cm、2 cm、5 cm 3 种不同的分割精度，对3张不同的地下车库图纸在i7 9750H 处理器、16 GB内存环境下进行了分割实验。根据实验结果，为兼容一般计算机的性能，最终决定δ取5 cm。

2.3 外圈的凹角处理

矩形外部区域Soutside中不包含任何障碍物，所以只用遗传算法就可以计算。遗传算法的关键在于对Soutside中外边界点集Pborder的凹角分割策略。参考刘彦鹏等［21］提出的简单多边形剖分算法，若凹角范围在采用作垂线的方式切割；在内，采用作延长线的方式切割。因为每个凹点均存在两条对应边，所以存在两种不同的切割策略，可得到m ＝2n。其中，n为Pborder凹点的数量。

3 算法设计

3.1 内部矩形中主楼内部空隙排布

定义最小闭包矩形为包裹每栋主楼的且平行于坐标轴的最小矩形。记地下车库中主楼的闭包矩形集合为B ＝｛B1，B2，…，Bn｝，满足：

式（12）表示各个矩形之间不存在重叠，式（13）表示在这些矩形之外不存在其它障碍物。每个矩形可以包含4 个点的点集PB ＝｛（x1，y1），（x2，y1），（x2，y2），（x1，y2）｜x1＜x2，y1＞y2｝。每栋楼空隙的车位排列算法流程如下：

输入矩阵A，矩阵左上角元素的坐标（x0，y0），主楼的包裹矩形集合B，车位长宽α、β，主楼数量n

输出车位集合L1，修改后的矩阵A

经该流程处理后，得到如图2 所示的可视化结果。

图2 一栋楼内空隙中的车位排布Fig.2 The arrangement of parking Spaces in the voids of a building

3.2 内部矩形中主楼内部空隙排布

对于矩阵A，给出如下定义：

定义1若Z⊆A且Z ＝0，则称Z为A的全0子矩阵。用全0 子矩阵中元素的个数来表示矩阵的大小，对应矩形的面积。

定义2若对于A的全零子矩阵Zm，不存在另一个全0 子矩阵Z0使得Zm⊆Z0，则称Zm为A的极大全0 子矩阵。

定义3若一个矩形内不包含任何障碍物，则称其为全空矩形。

定义4在内部矩形区域内，若对于一个全空矩形，不能被任何一个其它的全空矩形完全包裹，则称其为极大全空矩形。

对于全空矩形内的车位排布，可以充分利用矩形的直角特性［22］，采用两排90°的车位模块间隔一条过道的模式依次循环，在不足时采用0°的车位模块代替，如图3 所示。

图3 矩形区域内的车位模块设置Fig.3 Parking Spaces extend outwards

内部矩形中剩余部分的车位排布算法流程如下：

输入上一步修改后的矩阵A，矩阵左上角元素的坐标（x0，y0），车位长宽α、β，车位集合L1

3.3 矩形外部排布

矩形外部使用遗传算法对于每一切割区域进行计算，并考虑计算结果造成的L1、L2中车位堵塞损失，计算得到每种切割方案可排布车位数后，取其中车位数量最多的切割方案。

对于与车道集合R1有重合部分的车位模块，根据车道切割成若干子车位模块之后，计算车位的坐标。最终可以得到矩形外部排布的车位集合L3和车道集合R2。

4 实例验证

为验证基于分离障碍物的地下车库车位排布启发式算法的效果和计算速度，对5 张不同的地下车库图纸进行计算。采用4 核、3.40 GHZ 处理器、内存为16 GB 的计算机进行实验，矩形内部区域分割精度δ为5 cm，车道和车位模块长度均为6 m，承重柱边长0.5 m，编程语言为python3.8.1。得到的计算结果见表1。