1. 引言
随着我国汽车保有量的持续上升,城市停车难现象愈演愈烈,为解决城市“停车难”问题,具有共享经济理念的共享停车研究应运而生。共享停车旨在利用现有停车资源解决停车问题,不仅改造成本小,改造周期短,还可以为参与者和社会带来经济效益,是目前解决停车问题最有效的经济手段。共享停车是指单位或者个人通过共享停车平台出租车位的使用时间,实行停车需求者有偿错时错峰共享,在满足社会停车需求的同时获得经济效益的社会活动。当前解决停车难题的途径主要有三种:一是通过扩建停车场来增加停车场设施,以应对车辆增加;二是通过高密度停车和立体矩阵停车等方式,在单位面积内增加停车位;三是利用不同建筑用地的停车时间特点,推行停车共享策略。然而,扩建停车场存在两个主要问题:一是会占用大量宝贵土地资源,这对土地有限的城市并不适用;二是需要大量的投入,包括人力和物力成本,造成成本过高。立体矩阵停车方案虽然占地面积小、初始投资低,但运营和维护成本较高,许多公共立体停车系统使用率不高、经营效益不佳,这些因素使得该方案难以普及。综合上述分析,盘活现有停车资源才是最高效的解决途径,其重要方法和技术便是共享停车。
如今计算机网络技术、地理信息技术和5G通信技术的发展迅速,城市停车系统也朝着信息化和智能化的方向前进,停车困难不仅降低了车主的用车体验而且造成了城市交通拥堵,为解决此问题,大批学者对共享停车进行了大量研究。文献 [1] 通过时间序列预测时间重要度,从车辆停车需求与共享泊位供给的区间重叠度和灰距离熵出发,旨在尽可能减少热点时间的预约,从而减少泊位空闲时间碎片,提升泊位利用率。文献 [2] 通过将共享停车平台收益和用户从停车场到目的地的步行距离作为优化目标,研究者建立了预约请求式的共享泊位分配模型,并提出了利用蒙特卡洛方法对该模型进行求解。文献 [3] 提出停车设施的选择概率不仅受到设施的停车吸引力系数影响,还与设施的停车收费价格、停车相关步行时间以及生成点与设施之间的实际行程时间相关,共同影响着选择行为。文献 [4] 以提升停车位利用率为出发点,确定新建停车场的规模。文献 [5] 通过区分通勤和非通勤车辆的停车特点,研究了在通勤时间不同用地类型建筑物停车设施的供需情况以及用户行为选择。系统分析了区域内不同用途地块共享停车的可行性。文献 [6] 针对城市中心居住区停车难的情况以及停车行为的特点,通过调整停车许可证的发放数量和变动停车费用,以控制固定和弹性停车需求,从而在合理范围内优化停车资源配置。文献 [7] 提出通过根据停车需求者的个人信用风险等级来匹配泊位,以此来降低违约风险。文献 [8] 研究分析了共享停车供给与需求的不准时特征,并发现在给定时段,最佳的预约泊位数不仅受到该时段停车需求的不准时影响,还与邻近时段的停车需求量相关。文献 [9] 研究分析了共享泊位匹配中提高泊位利用率和满足停车需求者的满意度两个方面的影响。
以构建车辆与泊位的匹配模型和优化共享停车服务平台方面,研究者也进行了大量的研究。以最大化参与各方的经济利益。文献 [10] 将粒子群算法成功融入泊位共享停车场引导系统中。文献 [11] 引入了二进制多目标粒子群算法,以实现用户需求与共享停车位的有效合理分配。文献 [12] 创新性地引入了双层目标的粒子群算法,从而实现了泊位共享分配的全局综合最优化。文献 [13] 通过多目标粒子群算法,在最大化共享停车泊位利用率和最小化步行距离两个目标之间进行搜索,成功地优化了共享停车泊位的分配方案。文献 [14] 通过以步行距离的差异定义共享车位的异质性,研究者建立了跨区域泊位分配的随机动态规划模型。该研究指出在车位具有异质性的情况下,采用跨区域分配能有效提高共享平台的收益和车位利用率。然而,当车位的异质性较强时,平台可能不愿意采用跨区域分配策略。文献 [15] 采用滚动时域方法对实时获取的共享停车供需信息进行滚动式动态匹配,研究结果显示,过多的泊位供给或需求均不能提升系统的性能,但为需求增加一定的时间有助于系统的良好运行。文献 [16] 在考虑最大化泊位利用率和减少步行距离这两个目标的前提下,构建了共享停车的泊位分配模型,并利用粒子群算法对模型进行求解。文献 [17] 通过对停车需求的到达时间和停泊时长分布进行分析,研究者建立了一个模型,以优化共享停车收益为目标并确定最佳的共享泊位数量和保留非共享泊位的数量。文献 [18] 利用通信技术、网络技术、大数据和云计算等技术手段,设计并开发了城市级智慧停车综合管理系统。文献 [19] 通过建立平衡优化模型,研究者从共享停车平台定价的角度,分析了租用泊位价格和停车服务费用对停车需求选择行为的影响。文献 [20] 创建了一个考虑到停车需求的无人驾驶环境下的交通均衡模型,探究了停车场费用对道路网络均衡状态的影响。文献 [21] 依据用户偏好建立了基于停车许可证的最佳分配–定价模型,采用调优法对停车许可证进行拍卖,激发共享泊位持有者的参与意愿。通过这种方式,构建了一种共享停车泊位分配、定价和收益分享机制,以实现停车资源的有效管理。文献 [22] 引入一种浮动收费策略,以动态方式调整共享停车泊位的定价标准。与传统的固定收费模式相比,这种收费模式能够显著提升泊位的利用率,增幅可达60%以上。
同时共享停车也是近年来推进智慧交通而被广泛关注的研究领域,现有的有人驾驶车辆停车研究大多集中于车辆的行车规划路线以及停车场选择,以减少乘客的等待时间和步行时间。因新时代智慧城市建设规模的加速扩大,无人驾驶技术渐渐进入人们的生活,无人驾驶车辆的出现,让人们看到了其在停车时自主移位的特征,即具有自主泊车功能,此功能在共享停车领域可大大减少共享泊位空闲时间,提高泊位利用率,同时也减少了因不必要的车辆移位而产生交通事故的风险概率。有人驾驶车辆停车与无人驾驶车辆在停车时的本质区别是无人驾驶车辆具有自主移位的特征,而有人驾驶车辆没有这一特征,为方便有人驾驶车辆拥有变化泊位的特征,进而深入发掘共享停车资源的时空利用价值,本文引进泊车服务机器人(Parking Valet Robot-PVR)来辅助有人驾驶车辆在停车需求未满足时变换泊位。现许多研究着眼于有人驾驶和无人驾驶车辆的共享停车供需匹配、定价等问题,少有研究引入PVR协助有人驾驶车辆进行泊位变换,我们站在当下无人驾驶技术不太成熟的境遇,有必要从有人驾驶车辆的角度出发,制定切实可行的解决有人驾驶车辆停车难的方案,促进当下社会交通秩序的良好发展。
2. 共享停车供需匹配模型
2.1. 模型基本假设条件
本模型构建的基本假设条件如下:(a) 根据预约式共享停车需求与供给匹配的特征,假设停车需求的具体时间段和泊位供给的具体时间段已知;(b) 为保证任一有停车需求的车辆都可得到服务,假设有停车需求的车辆数小于任意时刻的供给泊位数;(c) 考虑到实际情况,任何一辆车的共享需求时段和任何一个泊位提供的共享停车时段都是连续的整段时间;(d) 在共享停车系统中,有人车在停放后一般不会发生移车行为;(e) 假设自动泊车机器人仅在泊位供给和停车需求首末时刻进行移位,因此移位时间对车辆停车时间的影响可忽略。
2.2. 时段分割方法
为便于后续模型优化的研究以及体现自动泊车机器人可帮助车辆变换泊位的特征,当车辆最初所停泊的共享泊位时间终止时,若该车辆仍有停车需求,那么可以和停车信息服务中心沟通,由服务中心派出的自动泊车机器人帮助该车辆移动到一个新的停车泊位。
为了刻画上述特征,有必要将共享停车需求时间段和泊位的共享时间段加以分割,形成长度较短的小时间段。具体分割方法如下:首先将所有车辆的停车需求时间和泊位供给时间的起止时刻放入一个时间点集合;其次,去除上述时间点集合中的重复元素,并按升序的顺序对剩余时间点进行排序,得到一个有序的起止时刻序列;根据上述得到的有序集合,针对每辆车的共享需求时间段进行分割,将包含在车辆停车需求的起止时间内的有序集合的时间点作为分割点,从而得到车辆共享停车需求的分割时段;针对每个共享泊位的共享时间段进行分割,根据上述得到的有序集合,将包含在一个共享泊位共享时间段内的有序集合的时间点作为分割点,从而得到各个共享泊位的分割时段。若车辆在连续的两个小时间段内分别停放在不同的泊位上,则可以推断其在自动泊位机器人的帮助下进行了移位操作。
一般而言,非等长的时间段划分可以减少总的时段数量,这样有效减少了模型的计算时长。但是非等长的时段划分降低了车辆与泊位匹配的灵活性。因此得到的最终解可能劣于在等长时段下得到的解。
2.3. 参变量介绍
表示一辆有共享停车需求的车辆,V表示所有相关车辆的集合。
表示一个共享泊位,P为所有共享泊位集合。
表示车辆v到达停车场的时间,同时也是车辆
开始停车计时的时间。
表示车辆v共享停车需求结束的时间。
表示泊位p可以开始共享停车的时间。
表示泊位p结束共享停车服务的时间。
表示一个分割时段,
表示将共享停车总时间划分为
个时段后的其中一个分割时间段。
表示在分割时段k车辆v的停车需求,如果
为1,则该时段车辆 有共享停车的需求;否则,此时段车辆v无停车需求。
表示共享泊位p在k时段是否提供共享停车服务,若提供停车服务,
取值为1;否则,取值为0。
是一个决策变量,若在时段k车辆v停泊在共享泊位p上,则
取值为1,否则取值为0。
表示自动泊车机器人将车辆从泊位p移到泊位q所行驶的距离。
表示车辆v在泊车过程中,自动泊车机器人助其发生一次泊位改变所产生的惩罚性系统成本,为便于后续分析,假设
的单位与距离的计量单位一致。
2.4. 数学模型
利用上述的参变量介绍和时段分割方法,在满足共享停车需求条件下,以最小化车辆移位距离和移位惩罚为目标的共享停车时空匹配模型为
(1)
(2)
(3)
(4)
式(1)为目标函数,由两个加和项组成,其中第一个加和项表示车辆利用自动泊车机器人在两个连续的分割时段分别停泊在不同泊位时需要移位的距离之和;式(1)的第二个加和项表示车辆利用自动泊车机器人移车次数所产生的惩罚性系统成本之和,假设此成本为等价距离,
计量单位与距离相同。式(2)表示在给定分割时段停泊在给定泊位的车辆数必须小于或等于该泊位在此时段的泊位供给数。式(3)表示在给定分割时段下,给定车辆的共享停车需求必须得到满足。式(4)是对决策变量取值范围的限定。由目标函数(1)和约束(2)~(4)构成的数学模型完整描述了车辆利用自动泊车机器人条件下的共享停车供需匹配问题。如果先对约束式(2)和(3)分别进行加和,然后比较,将得到下面的隐含约束条件:
(5)
匹配模型在式(5)的约束条件下,该模型必须满足所有可接受的预约式共享停车需求,这里的“可接受”是指在任意时刻泊位的总供给数要大于等于该时刻的停车需求总量。
与现有的仅考虑有人驾驶车辆的共享停车匹配模型相比较,本文的模型无论在目标函数还是约束条件下都显得更加简洁。由于本文的研究将共享停车匹配系统划分为统一的较小时段的停车供需,因此减少了以往研究中的较多繁琐约束,如供需的时间段前后时间点匹配的相关约束。另外,新模型中的目标函数与以往研究模型中最大化泊位利用率和供需匹配数目有所不同,本文的目标函数式(1)以车辆停泊过程中的移车次数最少和距离最小化为目标,所以本文的模型在解决共享停车匹配问题时更加有效。隐含约束式(5)表明新模型旨在匹配可接受的预约式共享停车需求,并且匹配结果必须满足所有可接受的停车需求。可接受的预约式共享停车需求只需要满足在任意时刻停车的供给大于等于该时刻停车的需求即可,而无需考虑车辆停车需求时间是否被泊位的供给时间所覆盖,这与处理有人驾驶车辆停车需求时的情况不同。因此,我们可以得出结论,新模型所得到的泊位利用率将高于仅考虑有人驾驶车辆停车需求的情况。
由式(1)~(4)构成的数学模型属于纯整数二次规划模型(Pure Integer Quadratic Programming-PIQP),根据目标函数和约束式的特殊形式,也可视为一类特殊的二次分配问题模型。现有研究证实二次分配问题是一类极难的NP-hard问题,也是NP-Complete问题。在现有的研究中尚未发现被人们所接受的全局精确最优解的有效方法。通常,一般的线性化技术方法只能给出问题较好的目标值下界,而启发式方法也只能确保算出问题的局部最优解或近似最优解。
3. 鲸鱼优化算法
3.1. 可行解匹配结构分析
定义1 (匹配):
表示在给定时段k车辆v停泊于泊位p,称其为一个匹配。显然,
对应
。对于在分割时段k没有车辆停泊于泊位p的情况,记为
,称其为一个空匹配。显然,空匹配
与条件
,
对应。
定义2 (匹配组):在满足条件
和
下,为
中所有车辆从
中选择唯一停放泊位,从而在k时段形成一个车辆与泊位的匹配集合。用
表示时段k的一个合理匹配集合。
定义3 (匹配图):对应集合
中的分割时间段,分别存在相应的匹配组
。把上述
个匹配组放入一个集合
,称该集合为一个匹配图。综上,
利用匹配和匹配组的概念可以推出一个匹配图以对应模型(1~4)的一个可行解。
3.2. 鲸鱼优化算法简介
鲸鱼优化算法(Whale optimization algorithm, WOA是2016年澳大利亚格里菲斯大学的Mirjalili等提出的一种新的群体智能优化算法,其优点在于操作简单,调整的参数少以及易跳出局部最优。在鲸鱼算法中,每个鲸鱼的位置代表了一个最优解。如
表示当前最优候选解的位置向量。在鲸鱼捕猎过程中,每只鲸鱼会有两种行为:第一种行为是包围猎物,鲸鱼将会随机选择向着最优位置的鲸鱼游去或是随机选择一只鲸鱼作为自己的目标,并向其靠近;第二种行为是气泡网攻击,鲸鱼环形游动喷出气泡来驱赶猎物。在每一代的游动中,鲸鱼们会随机选择这两种行为中其一来进行捕猎。
鲸鱼在包围猎物时会选择向着最优位置的鲸鱼游动或者向着一只随机鲸鱼游动,其数学模型如式(6)和式(7)所示
时,
(6)
时,
(7)
其中:
表示
代,第i个鲸鱼的位置,
表示第t代,当前最优鲸鱼即最优解的位置,A为区间
内的随机数。a为初值是2,随迭代次数递减为0的收敛因子,C为均匀分布在区间
的随机数,
表示随机选择的鲸鱼个人的位置向量。
鲸鱼在捕猎时会喷出气泡形成气泡网来驱赶猎物,同时鲸鱼为了使用气泡来驱赶猎物,也会通过螺旋上升不断更新自身的位置。使用气泡网时,鲸鱼的位置更新公式如下:
(8)
其中,b为一常数,l为均匀分布在
内的随机数。
此外,在鲸鱼进行气泡网攻击猎物时,执行包围捕食和和螺旋更新位置的概率均为
,当
时,执行式(6)或式(7);当
时,执行式(8)。
3.3. 鲸鱼优化算法求解流程
步骤0将停车场景划分为车辆停入、车辆离开、车辆移出、车辆移入、车位打开和车位关闭六个事件,其中车辆停入、离开和车位的打开、关闭事件的时间已知,将这些事件按照时间顺序排列。
步骤1初始化。设定算法种群解空间维度WoA_dim、最大迭代数NIteration、鲸鱼螺旋搜索形状常数b、步长
等参数。使用均匀随机算法初始化鲸鱼种群在求解空间中的位置,鲸鱼处于
(停车需求车辆总数*停车位总数)维的空间中,其中第Sj (停车位总数)*(k − 1)~Sj (停车位总数)*(k)的鲸鱼位置代表第
辆车对于停车位的优先选择权重
;
步骤2将每个鲸鱼在多维空间的位置带入目标函数求解函数中可得到每个车对于停车位选择的权重O。初始化系统仿真时间T,随着仿真推移逐步发生各个事件,当前事件为车辆停入时,寻找当前已开启且无车停入的车位并按照该车的选择权重O升序排列停入;当事件为车辆离开时,将车位腾出记为空闲车位;当事件为车位开启时,标记该车位为空闲车位;当事件为车位关闭时,生成车辆移出事件且事件的剩余时间为零,标记该车位为禁停车位;当事件为车辆移出事件时,若存在空闲车位,则车辆按照优先权重停入,生成并完成移入事件,将停入车位标记为禁停车位;另外,当事件为车辆移出事件时,若不存在空闲车位,则修改车辆移出事件的剩余时间为该时间之后最早的另一个事件的剩余时间。随着仿真推移,系统记录每一个停车位在每一个关键节点的车辆停入信息并计算目标函数。
步骤3计算个体适应度。由步骤2可得每个鲸鱼的目标函数值,选择目标函数最小的鲸鱼作为最优鲸鱼。
步骤4更新参数A、C、p、l。根据3.2节鲸鱼个体更新位置的规则,按模型式(6)、式(7)和式(8)更新鲸鱼的位置。
步骤5若迭代次数达到上限NIteration,则退出算法终止,否则转步骤2。
4. 仿真实验
利用MATLAB R2022b程序语言实现本文鲸鱼优化算法,使用的计算机处理器为Intel(R) Core(TM) i5-8265U CPU,运行此算法一次所需要的的计算时间小于千分之一秒(即0.001秒)在仿真实验中算法设定的参数如下:最大迭代数NIteration = 100、种群解空间维度WoAdim = 12*36、步长
、鲸鱼螺旋搜索形状常数
。下面分析一个具有20辆具有停车需求车辆、12个共享泊位和36个分割时段的共享停车供需匹配问题。表1给出了相关的停车需求,表2给出共享泊位的开放时间。从区间[0.01, 0.1]中按照均匀分布特征随机选取一个数值作为两个相异泊位间的距离(单位为km),具体泊位间车辆移位距离在矩阵
中给出,矩阵
中第i行第j列的元素值表示从第i个泊位移到第j个泊位车辆需行驶的距离(km)。
Table 1. Parking demand of vehicles
表1. 车辆停车需求
Table 2. Opening time of sharing berths
表2. 泊位共享开放时间
假设任何车辆移位1次的惩罚性系统成本为10 (km),这样如果最终优化的目标函数值为50.108,则可以推断出车辆进行了5次移位,移位产生的总距离为0.108 km。图1给出了该算法三次运行结果,在三次优化中,最初目标函数值分别为50.281、50.363、50.423,最终目标函数值均为40.276。由图1中最优目标函数值变化可知:鲸鱼优化算法效率较高,即在算法迭代的初期,最优目标函数值迅速得到较好的近似最优解,然后快速达到收敛。本文还采用了Lingo优化软件对上述案例进行求解,但由于问题模型具有NP-hard的性质,经过数小时的计算,Lingo仍未能找到问题的可行解。
Figure 1. Variation of the objective values of the best individuals with the increasing generations
图1. 目标函数值随迭代次数增加的变化
图2给出了经该算法计算3次得到的最佳匹配矩阵图,经过计算,算法第一次和第二次的优化图相同,第三次优化的矩阵图稍有不同,但最优目标函数值相同,再一次证明了该算法的可靠性。在图2中第一行的数字表示分割时段的序号,第一列第一行的“Sn”表示共享泊位的序号。矩阵图中其他元素的意义规定如下:“/”表示对应泊位在分割时段不开放;“_”为对应泊位在分割时段开放泊车服务,但没有被占用;数字“n”表示对应泊位在相应分割时段被序号为n的车辆占用。其中图2(a)为算法第一次优化和第二次优化的最佳匹配矩阵图,图2(b)为算法运行第三次的最优匹配图。从计算结果来看,该算法有效解出该模型的最优解,即共享停车系统供需匹配的最优矩阵图,由图2(a)可得,车辆1,3,8,16在泊车过程中需利用PVR各进行一次泊位变换,移位总距离为0.276 km,与最优目标值40.276对应一致;由图2(b)可得,车辆1,3,8,17需在泊车过程中需利用PVR各进行一次泊位变换,并且移位总距离为0.276 km,与最优目标值40.276对应一致。
(a) 第一次和第二次计算结果(b) 第三次计算结果
Figure 2. The matrix of the best matches
图2. 最优匹配矩阵图
表3列出鲸鱼优化算法运行10次的统计学结果,并计算出其均值和方差,由结果可知鲸鱼优化算法在计算此问题上具有相当高的效率和可靠性,具有解决有人驾驶车辆智能化共享停车供需匹配的能力。
Table 3. Statistical results of running the program 10 times
表3. 程序运行10次的统计学结果
5. 结论
为了使有人驾驶车辆在停车时能够利用无人驾驶车辆自主移位的特征,最大化满足车辆停车需求,提高泊位使用率。本文引进了泊位机器人辅助车辆移位,从而实现智能化停车。首先,本文以最小化有人驾驶车辆在停车场或特定停车区域的移车次数和系统成本为目标函数,建立PVR条件下的预约式智能共享停车供需匹配模型。接着,由于该模型具有NP-hard特征,故采用启发式方法来求解,我们基于鲸鱼优化算法具有操作简单、调整参数少以及跳出局部最优能力强等优点,选择用鲸鱼优化算法来解决此问题。最后,在仿真案例中利用该算法对模型计算了三次且给出了三次计算的对比图以及车辆与泊位的最优匹配矩阵图,结果表明该算法三次迭代图趋势大致相同,证实了该模型和算法的可靠性,相较于目标函数初始值,改进的鲸鱼优化算法优化后成本减少了约20%。本研究可为城市“停车难”问题提供解决方案,促进城市智慧交通的建设。
基于本文的研究,未来潜在研究包括:(a) 本文研究的是单停车场或特定停车区域下的共享停车匹配问题,未来可拓展到多停车场间的匹配问题;(b) 基于当前“充电难”的问题,未来可将充电桩的充电策略加入停车位匹配研究中,以车辆移车次数最小和客户满意度最高为优化目标。
NOTES
*通讯作者。