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

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