随着中国经济持续快速发展，城市汽车保有量增长迅猛，然而城市停车空间严重匮乏，停车位满足率仅有20%，停车问题已经成为阻碍城市发展的瓶颈之一^[1].城市的停车空间分为地面停车场和地下车库2种，通常来说，相同面积地下车库的造价为地面多层车库的2~3倍，而地下车库的造价与总建筑面积直接相关^[2].目前设计师通过尝试并对比少量方案完成地下车库车位排布，整个过程极度依赖设计师经验.笔者旨在通过算法实现地下车库车位的自动化排布，提升设计效率，同时增加停车空间车位容量，提高其利用率，缩小地下车库建筑面积，增加项目收益.

停车场中车位排布方案的设计与停车场自身特点紧密相关，不同类型的停车场适用不同的求解方法.现有车位排布问题的研究对象可分为矩形或三角形停车场和不规则轮廓停车场.矩形或三角形停车场按照车位排列的紧密程度又可进一步分为传统停车场和高密度停车场，传统停车场的设计通常基于停车位单元(PSU, parking space unit)进行，Iranpour和Tung、宋、Abdelfatah以及Syahrini等^[3-6]均以此为基础，根据车位数最多的目标，建立数学模型计算最佳车位角度；而高密度停车场专门为自动驾驶车辆设计，它允许部分车位不与车道相连，Ferreira等^[7]设计了一种车辆按排平行叠放的方式，Nourinejad等^[8]基于这种方式，设计了一种启发式算法，Timpner等^[9]设计了另一种高密度停车方式，这种方式中车辆垂直于道路紧密堆叠成k排(k stacks)，Banzhaf和Quedenfeld^[10]利用这种方式，建立混合整数规划模型，计算停车区域最优车位排布方案.针对不规则轮廓的停车场，现有文献提出的方法需要人的介入，Guo等^[11]分3步进行车位排布，首先将停车区域人工分成多个矩形块，接着通过数学模型确定每个块中的最佳车位排布方案，最后人工移去堵住通道的车位完成块之间的衔接.

上述方法针对轮廓简单的区域可完全由算法实现车位排布，但针对不规则轮廓需要人的参与，且上述文献均未考虑有障碍物的情况，也没有专门针对地下车库的研究内容.因此，为了解决具有复杂轮廓且内部有障碍物的地下车库的车位排布问题，对地下车库车位排布进行了规则提取，建立数学模型并设计算法求解.

1 规则提取 1.1 地下车库车位排布特点

以最大化车位数为目标的地下车库排车问题可概括如下：给定车库轮廓，在障碍物以外的区域，对车位、车道和承重柱的位置进行合理安排，在保证地下车库设计规范的前提下，使车库内的车位数最多.根据对地下车库实际工程图的总结，结合胡静^[2]和陈歌^[12]对地下车库设计的理论研究，笔者将地下车库车位排布问题的特点总结如下：

1) 车库轮廓复杂，存在斜边；2)车库内部有障碍物；3)车库内可安排多种尺寸的车位；4)不同角度的车位排列灵活；5)车道需构成连通的网络；6)承重柱的分布有最大距离限制.

1.2 规则

规则1   为减少决策变量的数目，同时考虑到承重柱分布的最大距离限制，根据地下车库设计规范，将车位和承重柱组合成图 1所示2种类型的车位模块进行排布.

规则2   为充分利用车库的全部面积，为车库轮廓和障碍物的每一条边安排一个与之相切的车位模块或车道.

规则3   为使角度不同的车位能灵活地组合，基于排车区域轮廓形状和障碍物分布进行区域划分，并保证每个分区内车位方向一致.

1.3 算法流程

结合地下车库车位排布问题的特点及提取得到的规则，设计了一种三阶段算法，算法流程示意图见图 2，算法步骤描述如下.

阶段1   外圈车位排布.确定车库轮廓和障碍物周边是否安排车位，若安排，确定车位模块的位置及最大长度；

阶段2  区域划分.对非车库轮廓或障碍物周边区域，进行区域划分，得到分区方案及每个分区中的车位模块位置和最大长度；

阶段3   排车方案确定及可视化.根据承重柱分布的最大距离限制，确定阶段1和阶段2得到的车位模块内车位和承重柱的具体位置.

笔者主要对第1阶段外圈车位排布问题展开研究，第2阶段区域划分则参考刘彦鹏等^[13]提出的多边形剖分算法进行，单个分区内车位模块位置的确定通过Syahrini等^[6]设计的方法完成，第3阶段车位模块内车位和承重柱的具体位置确定经遍历实现.

2 模型建立

在图 3所示的地下车库中，外圈车位排布问题可以描述为：给定车库轮廓和其内部的障碍物，车库轮廓内点的集合记为W，障碍物内点的集合记为R.记I={1, 2, …, ξ}为车库轮廓和障碍物的下标集合，ξ为车库轮廓和障碍物的个数，障碍物可以有多个，但车库轮廓有且只有一个，J_i={1, 2, …, η_i}为车库轮廓或障碍物i的顶点下标集合，η_i为车库轮廓或障碍物i的顶点个数.记e_ij∈E, i∈I, j∈J_i为从车库轮廓或障碍物i的某点出发，沿逆时针方向顺序排列的第j和第j+1个(若j+1$ \notin $J_i，则为第j和第1个)顶点组成的向量，其中向量e_ij的起点和终点分别为(a_ij^-, b_ij^-)和(a_ij⁺, b_ij⁺), i∈I, j∈J_i.定义向量ρ₁沿逆时针方向转至与向量ρ₂同向时扫过的角度为向量ρ₁和向量ρ₂的旋转角. α_ij∈A, i∈I, j∈J_i为向量e_ij+1和向量e_ij(若j+1$ \notin $J_i，则为向量e_ij和向量e_ij)的旋转角，θ_ij∈B, i∈I, j∈J_i为x轴正半轴与向量e_ij的旋转角.

在外圈车位排布问题中，车位模块紧靠车库轮廓或障碍物的某一条边排列，因此定义车位模块ij为沿着向量e_ij所在边排列的车位模块. λ_ij∈Λ, i∈I, j∈J_i是决定沿着向量e_ij所在边是否安排车位的0-1变量；t_ij∈T, i∈I, i∈J_i表示车位模块ij的类型，t_ij∈{0，1}，t_ij=0时，车位模块类型为图 1中的水平式，t_ij=1时，车位模块类型为图 1中的垂直式；d_tij和f_tiji∈I, j∈J_i分别表示车位模块类型为t_ij时单个车位的长度和宽度；n_ij∈N, i∈I, j∈J_i表示车位模块ij的车位数.记车位模块ij在车库轮廓或障碍物边(或边的延长线)上的2个顶点的坐标分别为P_ij^-=(x_ij^-, y_ij^-)∈P^-和P_ij⁺=(x_ij⁺, y_ij⁺)∈P⁺, i∈I, j∈J_i.记承重柱边长为s.

外圈车位排布问题的相关参数及变量示意图见图 4.

地下车库外圈车位排布问题受到4种约束.

约束1  不重叠约束：车位模块彼此不重叠.

约束2  几何位置约束：车位模块均在车库轮廓内，且不与障碍物重叠.

约束3  车位模块位置约束：外圈车位模块必须与车库轮廓或障碍物相切.

约束4  车位模块顶点位置约束：外圈车位模块的顶点与所在边的顶点有最大距离限制.

λ_ij：沿着向量e_ij所在边安排车位时取1；否则为零. λ_ij∈Λ, i∈I, j∈J_i.

t_ij:车位模块i_j的类型.

t_ij∈T, i∈I, j∈J_I.

P_ij^-，P_ij⁺：车位模块ij在车库轮廓或障碍物边(或边的延长线)上的2个顶点的坐标，其中P_ij^-=(x_ij^-，y_ij^-)，P_ij⁺=(x_ij⁺，y_ij⁺). P_ij^-∈P^-, P_ij⁺∈P⁺, i∈I, j∈J_i.

n_ij：车位模块ij中的车位数. ${n_{ij}} \in \mathbb{N} $, i∈I, j∈J_i.

针对地下车库外圈车位排布问题给出如下定义.

定义1  定义C_ij∈C，i∈I，j∈J_i为车位模块ij内点的集合.

定义2  定义w_ij∈ω, i∈I, j∈J_i为车位模块ij的宽度，当λ_ij=0时，w_ij等于0；当λ_ij=1且t_ij=0时，w_ij等于f_tij；当λ_ij=1且t_ij=1，w_ij等于d_tij.

定义3   定义l_ij∈L, i∈I, j∈J_i为车位模块ij的长度，l_ij等于$\sqrt {{{\left({x_{ij}^ + - x_{ij}^ - } \right)}^2} + {{\left({y_{ij}^ + - y_{ij}^ - } \right)}^2}} $.

定义4  定义Γ_ij, i∈I, j∈J_i为车位模块ij中承重柱的数量，根据图 1和t_ij的取值含义可知，当t_ij= 0时，Γ_ij等于1+n_ij；当t_ij=1时，Γ_ij等于.

定义5  定义δ_ij^-∈Δ^-, i∈I, j∈J_i为不考虑车位模块不重叠约束和几何位置约束时，点(x_ij^-, y_ij^-)与点(a_ij^-b_ij^-)的距离，如图 5(a)所示，当${\alpha _{ij - 1}} \in \left({0, \frac{\pi }{2}} \right)$时，δ_ij^-=v₂v₃=v₁v₃-v₁v₂，即δ_ij^-等于$\frac{{{w_{ij}} - 1}}{{\sin {\alpha _{ij - 1}}}} - {w_{ij}}\cot \; {\alpha _{ij - 1}}$；当α_ij-1∈[π 2 π)时，如图 5(b)所示，δ_ij^-= v₁v₂，即δ_ij^-等于${\alpha _{ij - 1}} \in \left[{\frac{\pi }{2}\pi } \right)$；否则为0.类似地，定义δ_ij⁺∈Δ⁺(i∈I, j∈J_i)为不考虑车位模块不重叠约束和几何位置约束时，点(x_ij⁺, y_ij⁺)与点(a_ij⁺, b_ij⁺)的距离，当${\alpha _{ij - 1}} \in \left[{0, \frac{\pi }{2}} \right)$时，δ_ij⁺等于$\frac{{{w_{ij}}}}{{\sin \; {\alpha _{ij - 1}}}} - {w_{ij + 1}}\; \cot \; {a_{ij}}$，当${\alpha _{ij - 1}} \in \left[{\frac{\pi }{2}\pi } \right)$时，δ_ij⁺等于$\frac{{{w_{ij}}}}{{\sin \; {\alpha _{ij - 1}}}}$；否则为0.

定义6  定义γ(W, R, C)为以W轮廓、以R为障碍物的地下车库，当外圈车位模块为C时，剩余区域最多能排下的车位数.

定义7   定义Ω(x₁, y₁, x₂, y₂)为以(x₁, y₁)为起点，以(x₂, y₂)为终点的向量.

根据对地下车库外圈车位排布问题的描述，对地下车库外圈车位排布建立如下模型：

$ \max \sum\limits_{i \in I} {\sum\limits_{j \in {J_i}} {{n_{ij}}} } + \gamma \left( {W,R,C} \right) $

(1)

$ \begin{array}{l} {\rm{s}}.\;{\rm{t}}.\\ \;\;\;\;\;\;\left( {1 - {\lambda _{ij}}} \right){l_{ij}} = 0,\;\;\forall i \in I,j \in {J_i} \end{array} $

(2)

$ s{\mathit{\Gamma }_{ij}} + {n_{ij}}\left[ {{d_{{t_{ij}}}}\left( {1 - {t_{ij}}} \right) + {f_{{t_{ij}}}}} \right] \le {l_{ij}},\;{\forall _i} \in I,j \in {J_i} $

(3)

$ {C_{ij}} \cap {C_{i'j'}} = \emptyset ,\;\forall i,i' \in I,j,j' \in {J_i}:ij \ne i'j' $

(4)

$ {C_{ij}} \cap W = {C_{ij}},\;\;\forall i \in I,j \in {J_i} $

(5)

$ {C_{ij}} \cap R = \emptyset ,\;\;\forall i \in I,j \in {J_i} $

(6)

$ \mathit{\Omega }\left( {x_{ij}^ - ,y_{ij}^ - ,a_{ij}^ - ,b_{ij}^ - } \right)\left\| {{\mathit{\boldsymbol{e}}_{ij}},\forall i \in I,j \in {J_i}} \right. $

(7)

$ \mathit{\Omega }\left( {x_{ij}^ + ,y_{ij}^ + ,a_{ij}^ - ,b_{ij}^ - } \right)\left\| {{\mathit{\boldsymbol{e}}_{ij}},\forall i \in I,j \in {J_i}} \right. $

(8)

$ \left( {a_{ij}^ + - x_{ij}^ - } \right)\left( {x_{ij}^ - - a_{ij}^ - + \delta _{ij}^ - \cos {\theta _{ij}}} \right) \ge 0,\forall i \in I,j \in {J_i} $

(9)

$ \left( {a_{ij}^ - - x_{ij}^ + } \right)\left( {x_{ij}^ + - a_{ij}^ + - \delta _{ij}^ + \cos {\theta _{ij}}} \right) \ge 0,\forall i \in I,j \in {J_i} $

(10)

$ \left( {b_{ij}^ + - y_{ij}^ - } \right)\left( {y_{ij}^ - - b_{ij}^ - + \delta _{ij}^ - \sin {\theta _{ij}}} \right) \ge 0,\forall i \in I,j \in {J_i} $

(11)

$ \left( {b_{ij}^ - - y_{ij}^ + } \right)\left( {y_{ij}^ + - b_{ij}^ + - \delta _{ij}^ + \sin {\theta _{ij}}} \right) \ge 0,\quad \forall i \in I,j \in {J_i} $

(12)

在上述模型中，目标函数为最大化车库中的全部车位数.式(2)保证λ_ij=0时沿着向量e_ij所在边没有安排车位；式(3)保证车位模块的长度符合图 1中车位和承重柱的组合要求；式(4)保证车位模块之间不重叠；式(5)保证车位模块在车库轮廓内；式(6)保证车位模块与障碍物之间不重叠；式(7)和式(8)保证车位模块ij与向量e_ij所在边相切；式(9)~(12)保证车位模块的顶点与车库轮廓或障碍物顶点的距离不超过限制.

3 算法设计

地下车库车位排布问题的决策变量为上述模型中的λ_ij和t_ij，即沿着车库轮廓或障碍物的边是否安排车位、安排何种类型的车位.通过对遗传算法(GA，genetic algorithm)、蚁群算法和粒子群算法的比较，选择遗传算法对地下车库车位排布模型进行求解^[14-16].下面具体说明为地下车库外圈车位排布问题设计的遗传算法的内容.

1) 染色体编码

遗传算法采用实数编码，染色体上的基因代表地下车库对应边是否安排车位模块、安排何种类型的车位模块.染色体定义为$G = {\left\{ {{g_m}} \right\}_{m \in D}}, D = \left\{ {1, 2, \cdots, \sum\limits_{i \in I} {{\eta _i}} } \right\}$，其取值与模型决策变量对应关系如下：

$ \begin{array}{*{20}{c}} {\left( {{\lambda _{ij}},{t_{ij}}} \right) = \left\{ {\begin{array}{*{20}{l}} {\left( {0,0} \right),{g_m} = 0}\\ {\left( {1,0} \right),{g_m} = 1}\\ {\left( {0,0} \right),{g_m} = 2} \end{array}} \right.,}\\ {m = \sum\limits_{r = 1}^i {{\eta _r}} + j} \end{array} $

(13)

2) 适应度函数

根据对模型目标函数的分析，选择车库中全部车位数作为遗传算法的适应度函数，即

$ f\left( u \right) = \max \sum\limits_{i \in I} {\sum\limits_{j \in {J_i}} {{n_{ij}}} } + \gamma \left( {W,R,C} \right) $

(14)

3) 遗传操作

遗传算法的遗传操作包括选择、交叉和变异，下面具体说明这3个过程的内容.

① 选择

遗传算法采用轮盘赌作为选择策略，每个个体被选中的概率为

$ p{r_u} = \frac{{f(u)}}{{\sum\limits_{u' = 1}^u f \left( {u'} \right)}} $

(15)

其中：f(u)是个体的适应度函数，U为种群数量.

② 交叉

交叉操作按照设置的交叉概率判断交叉是否进行，若进行则从个体中选择父亲F和母亲M，并在染色体上随机选择2个位置r₁和r₂，保证1＜r₁＜r₂＜l，其中l是染色体的长度，经交叉操作后，子代O位置m=r₁, r₁+1, …, r₂的基因来自父亲F，其余基因来自母亲M.

③ 变异

变异采用基本位变异，按照设置的变异概率值，随机选择染色体上的单个基因，用它的等位基因将其替换.

④ 自适应策略

将自适应策略应用在遗传算法中，使进入下一轮迭代的新种群由父代和子代合并生成，新种群中保留的父代与子代的数量由父代个体的适应度值决定，新种群具体构成如下：

$ {\eta _{\rm{O}}} = \left\lceil {\frac{{\sum\limits_{u = 1}^U f (u)}}{{\mathop {\max }\limits_{u'} f\left( {u'} \right)}}} \right\rceil $

$ {\eta _{\rm{F}}} = U - {\eta _{\rm{O}}} $

其中：ηO为新种群中子代个体的数量，ηF为新种群中父代个体的数量，f(u)为个体的适应度函数，U为种群规模.遗传算法的算法流程如下.

算法：地下车库外圈车位排布的遗传算法

输入：外轮廓W，障碍物R，轮廓及障碍物顶点V，轮廓内角及障碍物外角角度A，轮廓及障碍物边的角度B，遗传算法种群规模U，遗传算法交叉概率Pr_c，遗传算法变异概率Pr_m，遗传算法最大迭代次数K

输出：沿边是否安排车位的决策变量Λ^*，车位模块类型T^*，车位模块顶点坐标P^-*和P^+*

1 k←1，U_c=U

·Pr_c，U_m=U ·Pr_m

2 P←根据U随机产生初始种群

3 for k=1 to K do

4   for each p∈p do

5     (Λ, T)←根据p赋值

6     W←计算车位模块宽度

7     Δ^-, Δ⁺←计算车位模块顶点偏移量

8     P^-←V-Δ^-cos B

9     P⁺←V+Δ⁺sin B

10       P^-, P⁺←根据不重叠约束和几何位置约束调整P^-, P⁺

11     L←车位模块长度

12     C←车位模块内点的集合

13     N←车位模块内车位数

14     $f \leftarrow \sum\limits_{{n_{ij}} = N} {{n_{ij}}} + \gamma (W,R,C)$

15   end for

16   P′←根据轮盘赌策略从P中选择U个个体

17   for i=1 to U_c do

18     p₁, p₂←p₁, p₂∈P′

19     p′ ₁, p′ ₂←p₁, p₂经两点交叉后得到子代

20     P′←(P′-{p₁, p₂})∪{p′ ₁, p′ ₂}

21   end for

22   for i=1 to U_m do

23     p←p∈P′

24     p′←p经过单点变异后得到子代

25     P′←(P′-{p})∪{p′}

26 end for

27     P←对P和P′采用自适应策略

28 end for

29 Λ^*, T^*, P^-*, P^+*←f最大的Λ, T, P^-, P⁺

4 实例验证

为验证基于规则的地下车库外圈车位排布启发式算法的精度和有效性，对实际地库图纸进行求解分析.算法采用Matlab编程，实验环境为4核、内存8 G、处理器CPU为3.40 GHz的计算机.设置种群数U∈{48, 72, 100}，交叉概率Pr_c∈{0.7, 0.8, 0.9}，变异概率Pr_m∈{0.2, 0.4, 0.6}进行正交试验，最终选定种群数量为48，交叉概率为0.8，变异概率为0.6，详细运算情况见表 1.

针对上述图纸，算法给出的车位排布方案整体优于设计师提供的方案.其中图纸1、2、3、4、6算法给出的车位排布方案与设计师提供的基本相同，图纸5算法给出的车位排布方案与设计师提供的有明显差别，而图纸7设计师未提供排车方案.图纸5和图纸7的排车结果如图 6、图 7所示.

5 结束语

对地下车库车位排布问题进行了规则提取，建立了基于规则的外圈车位排布模型，并开发启发式算法求解，实际工程图纸的车位排布结果验证了算法的精度和有效性，得到如下结论：

1) 对地下车库车位排布问题提取了规则，创新性地针对轮廓复杂且内部有障碍物的地下车库，建立了外圈车位排布问题的数学模型；

2)提出的启发式算法可以得到保证整体车位数最多的外圈车位排布方案，该算法在运算时间方面满足设计师的要求，可以提高地下车库的设计效率；与人工车位数的对比表明该算法满足设计师对排车结果精度的要求，通过该算法可以增加地下车库车位容量，提高项目收益；

3)车位排布结果的可视化功能，可以为设计师提供地下车库设计辅助决策依据.