AVP条件下的共享停车供需匹配模型及自适应演化算法

• 何胜学

Shared Parking Demand-supply Match Model and Self-adaptive Evolutionary Algorithm with Autonomous Valet Parking

• HE Sheng-xue

摘要：为了充分利用无人车在停车过程中可以灵活移位的特征,提高预约式共享停车中停车需求与供给的匹配效率,同时降低总的车辆移位距离与伴随风险,建立了共享停车供需匹配优化模型,并给出了一种自适应式演化求解算法。首先,将共享停车需求和供给起止时间点作为分界点,将停车需求与泊位供给划分为小时段上的需求与供给。接着,以最小化总的移车距离和移车惩罚成本为目标,在满足所有可接受停车需求条件下,建立了具有二次分配特征的共享停车供需匹配模型。以分割时段为基础,定义车辆与泊位的匹配、匹配组和匹配图概念;通过分析给定时段上车辆是否需要进行泊位调换的条件和泊位变换对目标函数值的影响,给出了在所有时段上进行自适应式泊位调整的策略;通过引入变异操作有效避免自适应式优化算法过早陷入局部收敛。 结果表明:所建的优化模型可以合理刻画实际的共享停车供需匹配;通过算法优化,不仅增加了实际可接受的停车需求,而且与随机的匹配结果相比,停车过程中的车辆移位次数可降低到不足初始值的5%;新的自适应式演化算法求解中等规模的匹配问题,所需要的计算时间小于1 s,因此算法可应用于实际的共享停车平台在线泊位分配。研究结果将有助于无人驾驶条件下智慧停车理论的进一步推广。

Abstract

In order to make full use of the feature of flexible translocation of autonomous vehicle during parking, improve the efficiency of matching the shared parking demand and supply in the booked parking, and reduce the total translocation distance and the associated risk, a shared parking demand-supply matching optimization model is established, and a self-adaptive evolution algorithm is designed to solve the above model. First, regarding viewing the start and end time instants as the demarcation points, and the parking demand and supply are divided into small time intervals. Then, taking minimizing the total translocation distance and penalty cost of as the objective, under the condition of satisfying all the acceptable parking demand, a shared parking demand-supply matching model with second assignment feature is constructed. Based on the segmented time interval, the concepts of matching, matching group and matching map between vehicle and berth are defined. By analyzing the condition of whether berth adjustment for vehicle is needed in a given time interval and the influence of berth adjustment on the value of the objective function, a strategy for adaptive berth adjustment in all time intervals is given. The self-adaptive optimization algorithm is effectively prevented from falling into local convergence prematurely by introducing mutation operation. The result shows that (1) the established model can reasonably describe the actual supply and demand matching of shared parking; (2) the algorithm optimization not only increased the actual acceptable parking demand, but also reduced the number of vehicle translocations during parking to less than 5% of the initial value compared with random matching result; (3) the new self-adaptive evolutionary algorithm requires less than 1 s to solve the medium-scale matching problem, so the algorithm can be applied to the actual online berth assignment of shared parking platform. The research result will facilitate the smart parking theory under the situation of autonomous driving.

关键词

   智能交通 / 共享停车 / 二次分配 / 自动代客泊车 / 自适应演化

Key words 

ITS / shared parking / secondary assignment / autonomous valet parking / self-adaptive evolution

何胜学. AVP条件下的共享停车供需匹配模型及自适应演化算法. 公路交通科技. 2022, 39(3): 117-124 https://doi.org/10.3969/j.issn.1002-0268.2022.03.015

何胜学. Shared Parking Demand-supply Match Model and Self-adaptive Evolutionary Algorithm with Autonomous Valet Parking. Journal of Highway and Transportation Research and Development. 2022, 39(3): 117-124 https://doi.org/10.3969/j.issn.1002-0268.2022.03.015