自动代客泊车背景下的共享停车供需匹配模型及对应禁忌搜索算法

Shared parking supply-demand matching model and designed tabu search algorithm based on autonomous valet parking

为了减少自动代客泊车车辆在停车场或指定停车区域内的车辆移位次数和距离,从而降低相关的成本和潜在事故风险,在满足共享停车需求的条件下构建了相应的车辆和泊位匹配优化模型。考虑到无人驾驶车辆停车中可自由移位的特征,将共享停车的需求和供给在时间上加以细分,与决策变量和可行解对应定义了匹配、匹配条和匹配图的概念;通过概念转换将求解匹配图的有效邻居转换为经典指派问题,并利用匈牙利算法加以求解;针对匹配模型的NP-hard特征,设计了对应的禁忌搜索算法。数值分析不仅验证了模型的合理性和求解算法的有效性,也证实模型与方法可处理有人驾驶的共享停车匹配问题。结果表明,利用自动代客泊车可以进一步提升共享泊位利用率,增加可停放的共享车辆数。

In order to reduce the number and total distance of changing parking spaces in a parking lot or a given parking area through autonomous valet parking(AVP),in doing so to lower the related cost and the potential accident risk,this paper formulated a vehicle-slot matching optimization model which satisfied the shared parking requirement.In view of the feature of autonomous vehicle freely translocating during parking,this paper defined the match,match slice and match map corresponding to decision variable and feasible solution by subdividing the shared parking demand and supply in time.By conception replacement,the paper changed the searching effective neighbor of match map into the classic assignment problem and solved it with Hungarian algorithm.In view of the NP-hard feature of the matching model,this paper proposed a designed tabu searching algorithm.Numerical analysis not only verified the rationality of this model and the effectiveness of the algorithm,but also proved that the model and algorithm could deal with the shared parking of conventional vehicles.The results show that AVP can improve the utility of shared parking berths and increase the number of served vehicles.