考虑车位利用效率的停车位共享分配优化

Optimization Model of Shared Parking Space Allocation Based on Genetic Algorithm Online

摘要: 在私家车高度普及、机动车保有量不断增加的背景下，本文针对停车难这一问题对共享停车位进行研究。采用提前预约的方式，对某段时刻内的所有停车需求，根据用户及停车位的信息进行分配优化利用。以需求发起人所匹配到的停车位位置与目的地位置的距离最小为目标函数，考虑用户及停车位的时间窗约束、步行距离约束、停车位合理性约束，构建共享停车位分配优化模型。并基于遗传算法的思想，研究设计相应的求解算法。根据研究结果表明，共享停车位分配优化模型可以较好地实现停车位的合理分配。

Abstract: In the context of the high popularity of private cars and the increasing number of cars, this paper studies the problem of parking difficulties in shared parking spaces. Adopting the method of reservation in advance, all parking demands within a certain period of time will be allocated globally according to the existing shared parking spaces. Taking the minimum distance between the starting position of the parking space and the demand originator and the destination location as the objective function, considering the time window constraint of the passenger and the parking space, the walking distance constraint, and the rationality constraint of the parking space, a shared parking space allocation is optimized model. And based on the idea of genetic algorithm, it researches and designs the corresponding solving algorithm. According to the research results, the shared parking space allocation optimization model can achieve a reasonable allocation of parking spaces.

1. 引言

随着我国城市社会经济的快速发展，机动车保有量持续增长，道路交通拥挤与停车难等问题愈加突出。尤其在商圈、学校、景点等地区人员聚集区域尤为明显，导致车辆占用道路资源，增加车辆行驶成本。但在这些区域附近存在大部分私人停车位，且许多车位拥有者在上班、出差等出行时，存在大量车位未被利用的时间。因此，“共享停车”应运而生，青岛市在2016年生效的《青岛市机动车停车场建设和管理暂行方法》中提出适当建立停车场资源共享协调制度，制定停车资源共享计划 [1]。上海市同在2016年发布的《关于促进本市停车资源共享利用的指导意见》中提出有关政府机关、医院和普通高等学校等事业单位、国有企业等在保障内部安全和秩序的前提下，应将内部停车设施错时对外开放，率先落实停车共享责任 [2]。沈阳在2018年推出首个政府部门共享停车场，计划挖掘6万个共享停车泊位 [3]。那么，如何高效的为车位需求者快速、方便的分配到共享车位是推行共享停车位的重中之重。

现阶段共享停车处于探索阶段，国内外的专家学者从不同方面对其展开研究，期望停车位资源能够高效利用，发挥私人停车资源的潜在价值。在国外，Kim等运用被称为RFPARK的可以覆盖所有停车位的系统，基于匹配理论和方法为驾驶员提供理想的空置停车位 [4]。Shao等提出了二进整数线性规划模型来分配需求停车位，以在停车空间和时间上最大限度地利用停车场或满足尽可能多的需求，并给定一些指标来评估泊车位分配方案 [5]。Xu等提出了TTCD和PC-TTCC两种机制来分析了大城市在正常工作时间内私人停车位的共享问题 [6]。Yang等在对运营商的利益和影响用户停车行为的因素进行综合分析的基础上提出了系统效率最大化的0-1规划模型，更加有效地解决停车位分配问题 [7]。Cai等人提出了一种在路网层级上的停车位分配方法(PSAM)来实现停车场共享停车策略，并设计NSGA-II算法来确定最优策略 [8]。Xiao等提出了一种“按需竞争”的拍卖机制来讨论共享停车收费问题，只考虑了收费问题，未考虑到停车位匹配问题 [9]。在国内，朱成娟、贾斌等人构建了包括政府、私人运营商和出行者的三层Stackelberg博弈模型来研究停车位的分配和定价的问题 [10]。林小围等为解决共享车位使用时间冲突问题，建立了以停车位的时间不冲突为约束、以停车场使用效率最大为目标的停车供需匹配模型 [11]。并且，其为减少各车辆的停车成本和系统停车成本，运用合作博弈理论建立联盟停车成本合理、公平的分配机制来研究停车博弈问题 [12]。卢凯等为解决车辆反复泊车问题，建立了考虑驾驶员心理意愿的以系统虚拟总成本最小的区域停车动态分配与诱导模型 [13]。陈峻等结合车辆停放的时空特性，建立以组合用地停车场泊位综合占有率最小为目标的匹配优化模型，并用5种典型用地的停车泊位进行验证 [14]。路扬等为实现城市网络区域内的停车资源高效利用，建立了考虑优先级和时间窗的网络共享供需匹配优化模型，并基于整数规划逻辑判断理论将模型转化为线性问题进行求解 [15]。

尽管国内外对共享停车位分配问题进行了一定的研究，但依然处于探索阶段。本文依托于当今社会信息技术高速发展。采用预约的模式，采集一段时间内的所有乘客需求信息，结合每个停车位的位置信息以及时间窗信息，考虑乘车人及停车位的时间窗约束、步行距离约束、停车位合理性约束，以需求发起人所匹配的停车位位置与目的地位置的距离最小为目标函数，采用遗传算法对需求人及停车位进行按需分配。使得匹配效果科学合理。

2. 问题的描述

共享停车位系统是在一定的系统刷新时间内，根据需求用户上传的需求时间信息、起点位置信息、终点位置信息。结合现有的共享停车位的可用时间信息、位置信息进行相应的匹配。共享停车位系统根据相应算法得到分配方案，且结合现有的导航APP高德地图、百度地图等，为需求客户提供相应的出发时间以及行驶路线，乘客只需要根据导航的指引行驶到相应的停车位即可。

用数学描述的方法可以描述为：在系统刷新时间内，共有i个客户的停车需求需要满足，其中客户给定的到达及离开时间窗为[T_i, DepT_ij]。系统中存在j个可用停车位，每个停车位的可用时间窗为[T_j1, T_j2]。路网中的任意d_ij两点的位置均已知。根据上述信息结合共享停车位优化模型进行停车位的分配操作(图1)。

Figure 1. Matching process of shared parking spaces

图1. 共享停车位匹配流程

本文涉及到的参数及变量如表1所示。

Table 1. Model parameters and variables

表1. 模型参数及变量

本文的共享停车位优化分配模型的基本假设有：① 不考虑路阻及特殊情况的发生，认为所有车辆均以一定的平均速度按照规定路线到达停车场。② 用户均在给定时间窗下限之前离开停车位。

3. 共享停车位优化模型

3.1. 目标函数

研究构建共享停车位优化模型需要首先构建如下决策变量。本文停车问题需要考虑停车位距离乘客目的地的距离问题，旨在尽可能地对位置优地停车位进行停车时间地组合优化。而对于使用私家车的乘客，在目的地周围一定范围内对接受停车地点的接受能力差别不大，因此仅作为约束条件。因此本文以客户步行距离最小为优化目标。具体形式如公式(1)所示。

$\min Z_{\text{1}}={\displaystyle \underset{x\in O}{\sum }{\displaystyle \underset{j\in D}{\sum }{\displaystyle \underset{m\in M}{\sum }{x}_{ij}{y}_{jm}\cdot d_{jm}}}}$ (1)

本文采用0-1整数规划构建共享停车位优化模型，因此设计如下决策变量：

$x_{ij}=\{\begin{array}{l}1i点的客户到j停车位停车\\ 0否则\end{array}$ $y_{jm}=\{\begin{array}{l}1j停车位的客户终点位置为m\\ 0否则\end{array}$

3.2. 共享停车位的基本约束

在共享停车位系统提供服务的过程中，要保证客户被分配与停车位和目的地之间达成匹配。

$\text{0}<{\displaystyle \underset{j\in D}{\sum }{x}_{ij}}\le \text{1}\forall i\in O$ (2)

${\displaystyle \underset{i\in O}{\sum }{x}_{ij}}={\displaystyle \underset{m\in M}{\sum }{y}_{jm}}\forall j\in D$ (3)

约束(2)表示所有的客户需求必须分配停车位。约束(3)表示对于任意一个停车位来说，若被分配终点则必须有车停放，表示决策变量间的关系。

3.3. 客户步行距离约束

对于停车位分配时，单纯依靠目标函数优化客户步行距离时，为了达到全局最优容易出现某个个体的分配及其不合理，因此需要对客户步行距离的上限进行约束。

$y_{jm}\cdot d_{jm}\le D_0\forall j\in D,\forall m\in M$ (4)

约束(4)表示对于任意一个分配给客户的停车位来说，其位置不可超过距离该客户目的地以D₀为的半径的圆外。

3.4. 时间窗约束

客户在接受停车位分配时，要保证该客户在使用的全过程中，停车位一直处于空闲状态。因此，乘客利用共享停车位优化模型服务时，需提供时间窗区间[T_i, DepT_ij]与停车位初始时间窗[T_j1, T_j2]，即时间窗条件。

但在一次分配中，对于位置较好的停车位来说，容易出现一个停车位在不同时段分配给不同客户的情况发生，因此该停车位的时间窗不能单纯的利用初始时间窗进行约束，因此对该情况也需要约束。具体情况如图2所示。

图2. 公用停车位下冲突时间情形

根据图2的分析可知，停车位1、2、3为三种不可行组合情况，停车位1、2为用户时间窗组合冲突，停车位3为用户停车时间与车位可用时间不符。想要完成停车位的组合优化，仅有停车位4的情况可以实现。

因本文的目的是在尽可能的为乘客挑选位置合理的停车位的基础上对位置优的停车进行重复高效的组合乘客停车并加以利用。所以需要构建如下时间窗约束。

$T_{j1}-B\le Arr{T}_{ij}\cdot x_{ij}-B\cdot x_{ij}\forall i\in O,\forall j\in D$ (5)

$T_{j\text{2}}-B\cdot x_{ij}\le Dep{T}_{ij}\cdot x_{ij}-B\forall i\in O,\forall j\in D$ (6)

$\left(Dep{T}_{pj}-Arr{T}_{kj}\right)\cdot \left(Arr{T}_{pj}-Dep{T}_{kj}\right)\cdot x_{pj}\cdot x_{kj}\ge 0\forall p,k\in O,p\ne k,\forall j\in D$ (7)

$t_{ij}=\frac{d_{ij}}{v_i}\forall i\in O,\forall j\in D$ (8)

$Arr{T}_{ij}=T_i+t_{ij}\forall i\in O,\forall j\in D$ (9)

约束(5) (6)保证了对于任意一辆车在使用停车位时，其占用的时间窗上限和下限均不能超过停车位固有的时间窗区间。约束(7)保证了当一个停车位被不只一位客户选中时，该车位上的任意两个用户的时间窗不能存在冲突。公式(8)表示客户由起点到停车位所需的时间。公式(9)为到达客户停车位的时间。

4. 基于遗传算法的模型优化求解

4.1. 信息预处理

首先通过地图信息，根据每位客户的需求终点位置，根据客户步行距离约束与客户时间窗约束划分每位客户的可用停车位的编号。并保存到对应的客户信息中。

4.2. 遗传算法设计方案

为了方便表达，本文采用十进制编码方案，按照编码顺序依次为对应客户点的停车位编号，其中每一位随机生成的停车位编号均为筛选得到的可行停车位。在遗传群体初始化时，初始种群不宜过小，一般为需求数量的5倍以上。并根据目标函数设计相应的适应度评价函数，如公式(10)所示。按公式(11)计算染色体适应度的概率分布。

$f_i=\frac{Z^{\prime }}{Z_i}$ (10)

$p_i=\frac{f_i}{{\displaystyle \sum f}}$ (11)

采用轮盘赌的方式进行染色体的选择，并直接保留父代种群中最佳染色体到子代中。对选中的两个染色体采用对应位置交叉方式进行交叉。以保证染色体的可行性。在变异算子时，随机生成的算子保证在可行停车位中生成。在上述过程中均采用精英保留策略进行更新个体。重复这一步骤达到设定的迭代次数且种群最优适应度值保持不变时，终止算法并得到优化方案。

优化模型求解算法流程，如图3所示。

Figure 3. Optimization model solution algorithm flow

图3. 优化模型求解算法流程

5. 案例分析

案例介绍

大连市西安路商圈作为大连老牌商圈之一，其周边的停车设施相对完备，对西安路商圈周边的配建停车场和路边停车位进行统计，如表2和表3所示。由表2和表3可以看出，小部分的路边停车场和配建停车场是基本满足停车需求，而还有大部分停车场满足不了停车需求，需要路边停放。这种现状严重导致驾驶员寻找车位难的问题，尤其对于一些小型商区及市场，当周围没有足够的车位供给时，车辆违停等现象时常发生，进而导致影响城市道路的通行效率。但同时西安路商圈周围存在大量居民小区，如图4所示，进而存在大量私人停车位在工作日未利用。

Table 2. On-street parking lot around Xi’an Road commercial district

表2. 西安路商圈周围路边停车场情况

Table 3. The construction of parking lots around Xi’an Road commercial district

表3. 西安路商圈周围配建停车场情况

Figure 4. Distribution of parking spaces in surrounding houses and on the road

图4. 周边住宅及路侧停车位分布

为了缓解驾驶员停车难的问题，本研究选取大连市西安路商圈周边地区为研究对象，考虑利用其周边可用小区停车位为共享停车位对用户进行车位的直接匹配。但因共享停车位问题尚未普及，处于摸索阶段，难以获得真实用户数据。因此本文在该区域内模拟高峰时期的客户需求及停车位信息，根据时间窗约束以及最远步行距离约束，筛选得到可用所有停车位，其中各个用户起点与停车位之间的距离均已知。具体情况如图5所示。

Figure 5. User needs and surrounding parking space information

图5. 用户需求及周边停车位信息

其中共有10个用户需求，乘客信息如表4所示，停车位时间窗信息如表5所示。

Table 4. Passenger information

表4. 乘客信息

Table 5. Parking time window information

表5. 停车位时间窗信息

借助编程软件对共享停车位优化分配模型及算法进行求解，其中各个求解参数如表6所示。

Table 6. List of genetic algorithm parameter settings

表6. 遗传算法参数设置一览表

经过22秒的运行，设置迭代次数为100代，所得的目标函数值与迭代关系如图6所示。

Figure 6. Iteration curve

图6. 迭代曲线

根据图6可知，在迭代40次左右目标函数值趋于稳定。得到的具体解方案如表7所示。

Table 7. Genetic algorithm solution

表7. 遗传算法求解方案

通过上述方案分析可知，对于每一个用户均能够分配到合理的车位停车。且能够对于位置较好的停车位，根据用户及停车位的时间窗信息进行最大化利用。

6. 结论

本文构建了共享停车位优化分配模型，并通过遗传算法进行求解。由案例分析可知，建立的优化分配模型能够合理地完成停车位与用户之间的优化匹配，并且可以对位置优的车位进行多次重复利用，从而达到节省停车位及道路资源的目的。因此，本文的研究有助于解决城市共享单车停车难问题。

NOTES

^*通讯作者。