Abstract: It is usually hard to match the supply of parking berth and the parking demand due to their different spatial and temporal distribution features. Sharing parking is an effective way to cope with the above problem by providing the slots unoccupied by its owner in a given time period for those with parking demand during the time period. Since it is very rare to supply a slot with a proper parking time window for every parking demand, the Parking Valet Robot (PVR) is adopted to deal with the above problem. PVR can move a car from a slot to another slot if the allowable parking time of the former slot is end. When using PVR, the related operation cost and the potential risk due to the using of PVR need to be considered. To solve the problem how to reduce the unnecessary translocation operation and lower the accident risk due to frequently translocation operation at the same time remaining the benefit of using PVR, this paper formulated a supply-demand matching optimization model that satisfies the reserved parking demand and designed a harmony search algorithm to solve the new model.
To formulate the sharing parking supply-demand matching problem, the parking demand time intervals and the slot supply time intervals were divided into small time slices which have the start and end time instants of the above time intervals as the delimiters. The matching of demand and supply in a given time slice is viewed as a music pitch. Put all the pitches in all time slices together to form the music harmony. Assume that the number of available supply slots is bigger than the number of vehicles with parking demand in every time slice. Obviously, the harmony defined as above is corresponding to a solution to the sharing parking supply-demand matching problem. From a given harmony, we can obtain the detailed parking schedule of any vehicle. The distance of moving during the slot change by PVR for a vehicle and the operational cost induced by slot change can be figured out easily. The sum of the total moving distance and the weighted operational cost of PVR will be used as the optimization objective. The constraints on the supply and demand of sharing parking represented by a series of similar constraints in all the time slices. The formulated model of sharing parking supply and demand matching with PVR is a nonlinear quadratic integer program. The model can be viewed as a special quadratic assignment model which is a well-known NP-hard problem. To solve the above model, the above-mentioned conceptions of pitch and harmony are used to design an effective harmony search algorithm. The key operation of pitch adjustment in harmony search algorithm is realized by swapping the positions of two vehicles parked in two slots in a time slice. The above swapping operation can avoid generating infeasible solution to the matching problem during the solving procedure if the original harmony composed of pitches of all the time slices is a proper one.
To verify the effectiveness and robustness of the proposed harmony search algorithm for the sharing parking matching problems, problems of different scales are employed in the numerical analyses. The results obtained by the new harmony algorithm are compared with those given by the classic genetic algorithm. The comparison demonstrated that the new harmony algorithm outperforms the genetic algorithm in terms of the final parking pattern with smaller operational cost and shorter moving distance. The utilization rate of the slots is greater than 80% for all the test problems except one. The computational time of the new harmony algorithm is only about 1 to 2 seconds for all the cases. The sensitivity analyses of the parameters showed the following conclusions: a. To increase the possibility of adjusting the new pitch can noticeably improve the final result; b. The number of adjusting a given pitch should be proper because a too small or too large one will generate a negative effect on the final result; c. The size of the harmony memory and the probability of using the known harmony have no obvious influence on the final result.

Key words: parking space sharing, parking valet robot, harmony search, quadratic assignment

摘要： 泊车服务机器人(PVR)可以方便变换车辆泊位的特征为深入发掘共享停车资源的时空利用价值提供了契机。针对“如何在利用好PVR上述优点的同时,减少不必要的移位操作,并降低频繁移位操作带来的事故风险”的问题,建立了满足已知可接受停车需求的预约式共享停车供需匹配优化模型,并设计了对应的和声搜索算法。通过将不同时段的车辆与泊位匹配集合视为对应时段的声调,并进一步将不同时段声调的组合视为和声,建立了模型可行解与和声搜索算法基本概念的映射关系。利用同一时段内任意两个共享泊位上停放车辆的泊位互换实现对该时段声调的微调。数值算例的分析验证了模型与算法的有效性。新的理论不仅可以有效减少共享停车服务中PVR不必要的移位操作,而且给出了存在PVR服务条件下实现合理供需匹配的有效方法。

关键词: 共享停车, 泊车服务机器人, 和声搜索, 二次分配