# A Collaborative Reservation Mechanism of Multiple Parking Lots Based on Dynamic Vehicle Path Planning

Authors: Yuting Xiao; Zhen Cai; Jinglei Li; Mangui Liang; Xiaoyu Long
Journal: Journal of Advanced Transportation
 (2021)

---

## Abstract

With the development of wireless communication and artificial intelligence technology, online parking reservation system can effectively save drivers’ searching time for vacant spaces. However, in the environment with multiple candidate parking lots around the destination, how to coordinate and maximize parking space resources to reduce the travel time is still a practical issue for urban drivers. In order to solve this problem, a collaborative reservation mechanism based on dynamic vehicle path planning is proposed in this paper. By the aid of the dedicated backbone network with a clear division of work responsibilities, the information of traffic and parking lots is collected in real time, based on which the travel time prediction and empty spaces evaluation are executed separately, and then the optimal decision of path planning and parking lot selection can be made and adjusted dynamically by a step-by-step acknowledgement mechanism. The simulation results show that, based on collaborative working and overall planning, our proposed reservation mechanism can effectively raise the utilization rate of the parking lots resources and significantly reduce the travel time for drivers under different traffic environments. Compared to current mechanisms, the collaborative parking reservation mechanism reveals higher feasibility and applicability. It can assist in design and operation of urban traffic management and space resource utilization.


---

## Body

## 1. Introduction

With the development of urbanization and the increase of population density, parking problem is a critical challenge for resident travel, transportation management, and urban planning. Simply increasing the quantity of parking lots is not a sensible and feasible solution due to high construction cost and public space occupancy. By the aid of wireless communication and artificial intelligence technologies, smart city [1, 2] attracted extensive attention from both academic and commercial communities in recent years. As a critical component, urban smart parking [3–6] can not only shorten drivers’ parking searching time, relieve traffic congestion, and reduce air pollution but also improve parking lot operation efficiency and save urban public space and infrastructure costs.However, without collaborative working mechanisms based on real-time communications with vehicles, most of the current urban parking lots are not efficiently utilized, which also increases searching time of drivers. Even though the driver can reserve a space in advance, the travelling time from current position to the parking lot is hard to evaluate accurately due to the complex and time-varying urban traffic condition, which increases the idle time and causes the waste of parking resources. Moreover, around large entertainment centre, shopping mall, or sports stadium in urban area, there are generally more than one parking lots which can be selected to park for drivers. When the vehicle arrives at one parking lot which has just been filled up, queuing for the space or going to another one is a difficult problem it has to face, and even further for the next target, how to determine which parking lot has the maximum probability that there is an empty space when the vehicle arrives is another important challenging issue.In the urban environment with multiple parking lots (not distributed roadside parking spaces), in terms of a complete smart parking process, i.e., from the time vehicles departed from their source places until they parked successfully, there are four main parts:(1)
Travel time estimation and path planning for vehicles(2)
Spare parking space prediction for parking lots(3)
Collaborative scheduling and reservation mechanism between multiple parking lots and vehicles(4)
Empty space searching and parking within facilities, especially large parking lotOnly when these components are all deigned logically and deployed scientifically, drivers can park their vehicles and reach their destinations in the fastest possible time, and parking lots can run efficiently and achieve maximization of utility.According to abovementioned considerations, in this paper, we propose a dynamic and collaborative reservation mechanism for parking vehicles in the environment of multiple candidate parking lots. By the aid of vehicular ad hoc networks (VANETs) [7, 8], traffic information can be collected in real time, based on which, the path travel time of the vehicle is divided into three parts to estimate separately: waiting for signal lights, passing intersections, and driving on straight roads, and then the optimal path to the parking lot can be calculated for the vehicle to adjust its rest route dynamically. On the other side, an improved grey model is constructed to predict the number of spare spaces and the time to wait (if there is no space when the vehicle arrives) for each parking lot, which can effectively support the target selection decision-making for vehicles. Based on the abovementioned deigns and adding the consideration of parking time in the interior of parking lot and walking time to the final destination, we propose the integrated reservation mechanism which can drive all parking lots, share their real-time parking space information, and work collaboratively for incoming vehicles to park successfully and reach their destination as fast as possible.The rest of the paper is organized as follows: Section2 discusses the related work. Section 3 provides the detailed description of the proposed collaborative reservation mechanism including travel time estimation, path planning, parking space prediction, and interaction design between parking lots and vehicles. Section 4 evaluates the performance by simulation. Finally, we conclude this paper in Section 5.


## 2. Related Work

In this section, we summarize the existing related work from two aspects: path planning and parking reservation.For path planning, Ma et al. [9] proposed a real-time road planning method which utilizes a two-level hierarchy consisting of on-road behaviour planning and online path generating to achieve feasible paths for autonomous vehicle in dynamic on-road environment. Wang et al. [10] established a hybrid-VANETs-enhanced intelligent transportation system which utilizes both vehicular ad hoc networks and cellular networks to enable real-time communications and then proposed a real-time path-planning algorithm which improves the overall spatial utilization of a road network and reduces average vehicle travel cost for avoiding vehicles from getting stuck in congestion. In [11], a decentralized and hierarchical real-time path planning algorithm is proposed based on a road side unit architecture in which a city is divided into different areas, each with a road side unit. In [12], Pothan et al. adopted a state lattice strategy for path planning. A path set which incorporates all the geometry, kinematics, and constraints of the vehicle, known as motion primitives, is prefigured. In [13], Wang and Chen proposed a novel global path planning framework based on a hybrid map which consists of three levels: the scene level, the feature level, and the metric level. For path planning in parking lot, Song et al. [14] proposed a laser-based simultaneous localisation and mapping automatic parallel parking and tracking control scheme, which include environment perception and reconstruction, parking path planning, and path following, and Wu et al. [15] addressed the multivehicle cooperative autonomous parking condition by establishing a vehicle kinematics model combined with dynamic constraints and endpoint and collision avoidance constraints. The proposed path planning algorithm takes into account the cost of use but does not take into account the update of the remote path information in the decision-making.In terms of parking reservation, in [16], a navigation and reservation-based parking proposal system are developed for smart cities, which involves the development of small devices that send data to the Internet using the Internet of Things (IoT) technology. Nugraha and Tanamas [17] proposed a dynamic allocation method to reserve parking space using Internet application, which would reduce the need of the driver to explore the entire parking spot by finding the vacant parking lot and do the reservation for the driver. Making full use of cloud-based environment, Karthi and Harris [18] introduced a parking reservation system using Internet of Things, which checks the availability of the parking slot using ultrasonic sensor to determine the presence of the vehicles. In [19], the authors elaborate the work on the reservation-based parking system and focus on the design of the backend system that is created by implementing service oriented architecture which is implemented in a private cloud based on OpenStack infrastructure. In [20, 21], a discriminated release strategy with a space occupancy indicator (SOI) is proposed to determine the display content on the parking VMS, in which an agent-based simulation is introduced to incorporate both parking choice model and traffic assignment algorithm dynamically. A reservation-based optimal parking lot recommendation model in Internet of Vehicle environment is designed in [22]. Based on the users oriented parking information recommendation system, the model considers subjective demands of drivers comprehensively and makes a deep analysis of the evaluation indicators. Mejri et al. [23] proposed a new reservation-based multiobjective smart parking approach which uses a simulated annealing based meta-heuristic to optimize the parking slot assignment problem formulated as a multiobjective integer linear program. In [24], the authors introduce a user-friendly app for users to provide service from finding a parking space to confirming a reserved parking space. In [25], Devi et al. proposed a design and implementation method of intelligent parking reservation technology based on mobile applications. This system automatically recognizes empty parking spaces via proximity sensors, completes the reservation, and uses RFID, GSM, and ATMEGA controllers to park vehicles in corresponding empty parking spaces. The abovementioned schemes only consider efficient parking reservation from the angle of vehicles-to-single parking lot and not coordinate all surrounding parking lots to work together collaboratively, which lead to an unbalanced utilization of public parking resource and an increase of searching time for drivers.


## 3. Collaborative Reservation Mechanism

### 3.1. Problem Statement and Assumptions

In order to maximize and balance the utilization efficiency of multiple surrounding parking lots and then reduce searching time of drivers, the collaborative reservation mechanism facing multiparty communication needs an efficient supporting network. In our design (Figure1), we assume that all parking lots and road side units (RSUs) which are deployed at each intersection constitute the backbone network. As basic network nodes, they can communicate with each other in real time by wired network or cellular network. In contrast, parking vehicles are not introduced into the backbone network. Instead, through equipped on-board devices, they can communicate with nearby (i.e., in the transmission range) RSU or parking lot directly by other certain cost-free wireless network standards, e.g., dedicated short range communication (DSRC), Wi-Fi. Such design can effectively reduce the communication cost for drivers, and the backbone network is deployed and maintained as the urban public infrastructure, which can be managed conveniently and shared to other applications as well.Figure 1
Diagram of supporting network in the collaborative reservation mechanism.Moreover, due to the perspective of the utilization of public resource, in this paper, we do not take into account the pricing strategy and interest competition during different parking lots (not distributed roadside parking spaces) which we consider as the homogenous resource to manage and allocate.The whole reservation mechanism is divided into three parts (path planning, parking space prediction, and integrated design) to describe respectively as follows.


### 3.2. Path Planning for Vehicles

As the route along which the vehicle can reach the destination with the shortest time is the optimal choice in general, the travel time prediction is the determining factor in the decision-making for vehicle’s path planning. In the environment of multiple parking lots around the destination, we evaluate the optimal travel time spent to each of them, which can support the reservation decision in Section 3.4. According to actual urban road traffic environment as shown in Figure2, three times submodels are designed for the whole travel time prediction: the time of waiting for traffic lights, passing the intersection, and running on the road.Figure 2
Three kinds of time spent on the travel.In addition, for the traffic information used in the calculation (e.g., traffic lights state, waiting queue length, and traffic density on road), RSUs at the each intersection are in charge of the data collection work which can be achieved by advanced and sophisticated sensor network and image processing technology nowadays. As it is not the main point of the research, the detailed description is not given in this paper.


#### 3.2.1. Waiting Time for Traffic Lights

Traffic lights have a great impact on the whole travel time. Sometimes, if a vehicle does not pass the stop line in time when the light is about to turn, it has to wait a more period time meeting the red light. Then, they have strong uncertainty and randomness.In general, from the macroscopic and statistical point of view, the mean value of waiting time of all passed vehicles in a certain direction flowing at the intersection can be used to consider as the evaluating value of such direction [26]. However, based on more accurate and real-time collected information at next intersection which current vehicle is about to reach, we can evaluate the waiting time by a microscopic and concrete approach. In this paper, a combination method is adopted, i.e., for the next intersection, we construct a real-time microscopic prediction model, and for following intersections, the statistical average waiting time tflww which can be gathered by RSU is utilized directly.The waiting time at the next intersection is calculated as follows. Firstly, by communication with the control unit of traffic lights, we can obtain its current states, i.e., current phase and remaining timetre. Then, the allowed passing time tGre in current phase and the length tl from current moment to the opening point of next green light can be estimated:(1)tGre=tre,green,0,red,tl=tc−tG−tre,green,tre,red,where tc is the length of a complete signal cycle and tG is the duration of green light.Then, we calculate the required timetq and required number of signal cycle nc for current vehicle to wait:(2)tq=tpu1+nq,nc=tq−tGretG,where tpu is the desired interval time between two successive passed queue vehicles and nq is the vehicle count in the waiting queue and before the current vehicle.Thus, the waiting time at the next intersectiontnextw can be calculated:(3)tnextw=tq,nc=0,tq+t1,nc=1,tq+t1+nc−1tc−tG,nc>1.Note that in order to make correct path planning, the waiting time in each candidate direction at the intersection needs to be evaluated for current vehicle.Finally, we summarize the prediction of waiting time for traffic lights as(4)tw=tnextw,next intersection,tflww,following intersections.


#### 3.2.2. Time of Passing Intersection

As vehicles generally start from the waiting queue and cannot run at the maximum allowed velocities at the beginning, for estimation of passing the intersection area, the acceleration process of vehicle needs to be considered. The required accelerating timetacc to maximum velocity is(5)tacc=vil−vca,where vil is the limited velocity at the intersection and vc is the current velocity when the vehicle just entered the intersection area, and the running distance dacc in tacc is(6)dacc=vil2−vc22a.Then, the passing timetp is calculated as(7)tp=tacc,dacc≥Li,Li−daccvl+tacc,dacc<Li,where Li is the length of the ith direction (i.e., go straight, turn left, or turn right) in the intersection area.


#### 3.2.3. Running Time on Road

Based on fundamental diagram of traffic flow theory, running velocities of vehicles are affected by the traffic density on road, i.e., the larger number of vehicles means the lower average speed due to more interactions [27]. For a road with the length Lr and the traffic density ρ, the running time tr spent on it of one vehicle can be evaluated as(8)tr=1+α1⋅ρβ1Lr−lqminvrl,vdes,where vrl is the limited velocity on the road and vdes is the desired velocity of the vehicle itself and lq is the length of waiting queue at downstream intersection. Likewise, queue in each direction needs to be considered separately to support the path planning. Besides, α1 and β1 are the adjustable parameters.


#### 3.2.4. Path Planning

When the vehicle which wants to evaluate the optimal parking lot and the fastest travel path to its destination enters the region near the intersection (which means there is enough time and sufficient space to change lane for turning direction), it sends a routing request to the RSU through wireless communication. The RSU which is in the backbone network makes the decision by estimating its own data and the exchanged information from other RSUs.As we described in above sections, a road and its downstream intersection constitute a path unit, and the time spent on ittu includes the waiting time for traffic lights, the time passing the intersection, and the running time on the road:(9)tu=tw+tp+tr.Then, the total travel time of theith candidate path Pi from current decision intersection to the jth certain parking lot can be summarized as(10)tjtPi=∑tu+te,te=tw+tp+1+α1⋅ρβ1⋅Llastminvrl,vdes,where te means the time spent on last path segment, i.e., from the last intersection to the parking lot, and Llast is the distance from the upstream intersection (i.e., the last intersection) to the position of the parking lot.Utilizing dynamic programming algorithm, fromn candidate paths, we can obtain the optimal path which has the shortest time:(11)Popt=argmintjtPi,i=0,1,…n.Note that, for adjusting calculation quantity to suit the computing capability of the RSU and the network communicating capacity, we can set the threshold to reduce the number of candidate paths to be considered, e.g., the physical distance or the number of intersections in the path.


### 3.3. Parking Space Prediction

For the vehicle, when it arrives at its target parking lot, whether there is an empty space for it at such a moment needs to be considered in advance, before the decision-making of path planning. In our design, based on gathered real-time information of the arrived and the left vehicles, each parking lot is in-charge of predicting the number of empty parking spaces in it by the aid of the grey prediction model.Firstly, the number of vehicles which arrived at the parking lot is recorded per unit period. We adopt the combination of the real-time valueXA−c0i and the historical average value XA−h0i of that at the same time in all weeks in the last year as the input data:(12)XA0i=α2⋅XA−c0i+β2⋅XA−h0i,where α2 and β2 are the weighting factors, and the input sequence, i.e., the data in last n periods, can be expressed as(13)XA0i=XA01,XA02,…,XA0n.Then, by accumulated generating operation, the new sequence is obtained as(14)XA1=XA11,XA12,…,XA1n,XA1k=∑i=1kXA0i,k=1,2,…,n.where XA1 needs to satisfy the first order differential equation:(15)dXI1dt+a⋅XA1=u,where a and u can be calculated by the least square estimation. Therefore, the number in last k + 1 unit periods is evaluated as(16)XA1^k+1=XA11−uae−ak+ua.Then, the number of entered vehicles at timek + 1 is(17)XA0^k+1=XA1^k+1−XA1^k.By the similar approach, the number of the left vehiclesXL0^k+1 can be estimated as well. Finally, we can obtain the number of empty parking spaces at time n + 1:(18)Xn+1=0,X0^n+1<0,Xmax,X0^n+1>Xmax,X0^n+1,others,X0^n+1=XEn−XA0^n+1+XL0^n+1,where Xmax is the capacity of parking lot and XEn is the actual number of empty spaces at time n.


### 3.4. Time of Waiting Empty Parking Space

When the parking lot is filled to capacity, how much time will the vehicle need to wait for an empty space is an important problem to be considered. In other words, if the waiting time is too long, the vehicle should turn to other parking lots. Furthermore, the prediction of waiting time should be executed in advance before the vehicle arrives, which can help it to make a more accurate selection.Assuming the current time ist0 and the vehicle will arrive at ta, then as mentioned in the above section, the number of vehicles arriving at each period from t0 to ta can be calculated as XA^ti, and the number of vehicles XL^ti which will leave at each period can be evaluated as well. Then, the number of vehicles which will not enter the parking lot and have to wait outside at time ta is(19)XWta=XEt0−∑XA^ti−XL^ti.IfXWta>0 which means there are vehicles queuing in front of the arrived vehicle, it needs to wait all of them to enter the parking lot. In other words, it can park until at least XWta+1 vehicles which have parked in the parking lot leave. From ta+1, we calculate the number of the left vehicles in each unit period in turn until(20)∑tj=ta+1tmXL^tj>XWta,where tm is the time required to wait for an empty space.Thus, the waiting time outside the parking lotto can be concluded as(21)to=0,XWta≤0,argmin∑tj=ta+1xXL^tj>XWta,XWta>0.


### 3.5. Time of Parking inside and Walking to Destination

So far, we provide the evaluations of optimal travel time and the empty space waiting time, respectively. In order to reach the destination successfully, there are still two steps to be considered for the driver: parking in the interior of the parking lot and walking to the destination.For the former, in large construction facility, searching empty space holds the major time expenditure in the whole parking process. Generally speaking, higher occupancy means harder searching and more time used for the driver. Then, we provide the following calculation model to represent the time of parking inside:(22)ti=α3⋅eβ3⋅Xta+to/Xmax+tk,where Xta+to means the predicted number of empty parking spaces when the vehicle enters this parking lot, tk is the average parking time in an empty space, and α3, β3 are the adjustable parameters. Note that other factors such as internal building structure and deployment of assisted navigation equipment have impacts on parking as well. However, this issue is not the focus in this paper, more detailed discussion is not given here.For the latter, the walking time from the parking lot to the destination can be evaluated as(23)tf=dpvw,where dp is the path distance and vw is the average human walking velocity.Then, for a certain parking lotj, from the time when the vehicle reaches the intersection area and generates a request of path planning to the time it arrives at its final destination, the total time can be evaluated as(24)tjtotal=tjtPopt+tjo+tji+tjf,where Popt is the optimal path from current position to parking lot j.


### 3.6. Collaborative Reservation Mechanism

When the vehicle which has the demand of parking around a certain destination reaches any intersection, it sends the request packet with the destination position and other specific and optional requirements (e.g., path query range and time limit) to the RSU by the wireless communication. Every RSU can communicate with all parking lots and a central server through the dedicated backbone network. They deal with the parking planning and reservation work collaboratively. We provide their respective functions in the whole reservation scheme below from three aspects as shown in Figure3: information collection, response to path planning request, and real-time reservation.Figure 3
Respective functions of RSU, parking lot, and central server. (a) Information collection. (b) Response to path planning request. (c) Real-time reservation.
(a)(b)(c)RSU is in charge of collecting the traffic information in the area of its intersection and all connected roads, evaluating the travel time on each path unit in real-time, i.e., in (9), and submits the results to the central server to record periodically. In its area, for the vehicle which sends the request of path planning, the RSU inquires for the predicted travel time of path units in other areas (i.e., from current intersection to the destination) from the central server (note that the searching scope depends on concrete requirements of the request vehicle) and, after the search results are received, it sends all of them with its own data back to the vehicle. When the vehicle submits the reservation or cancellation application after the decision-making, the RSU is responsible for forwarding it to the corresponding parking lot in time.Parking lot is responsible for gathering its own real-time state information including the number of empty spaces and entering and leaving vehicles, executing the time predictions as we present in Sections3.3–3.5 and then sending the results to the central server to record and update periodically. For the reservation and cancellation from vehicles, the parking lot adjusts its available capacity in real-time correspondingly. Furthermore, if the step confirmation message is not received within the time limit from the vehicle which has reserved parking space, the parking lot will cancel its reservation.Central server in the backbone network establishes records for all RSUs (i.e., all path units) and parking lots, maintains this information according to the received periodical updates, and provides query services to the vehicles which have demands of parking. In the proposed scheme, beyond centralized information storage, the central server is not in charge of related computation work (i.e., the tasks of travel time evaluation, path planning, parking space prediction, and so on) and does not participate in actual reservation process, which can reduce the working load of it effectively. In other words, it only plays a role of real-time database server in the whole collaborative reservation mechanism.In addition, after the vehicle received the query results from the central server (relayed by nearby RSU), the decisions of path planning and parking lot selection are executed locally. According to the decision result, the reservation message is sent to corresponding parking lot to order a space (through the RSU as well). Firstly, the predicted arrival time should be included in the message, which can help the parking lot to manage and allocate its parking resource rationally and efficiently. Secondly, as realistic traffic conditions are changed frequently and some influence factors cannot be precisely considered, there is the inevitable estimated bias in the predict travel time from the place where the vehicle initiates the reservation to the parking lot. In order to alleviate this impact, in our scheme, a step-by-step acknowledgement mechanism is proposed as follows. Besides the time of arriving at the parking lot, the vehicle also packs the predicted time of arriving at next intersection into the reservation message. The parking lot adds this time by the factor of tolerate transmission timeγγ≥0 as the limited time, within which if there is no confirmation arrives in time or a cancellation message is received from the vehicle, the parking lot cancels the reserved parking space.On the other side, when the vehicle arrives at next intersection, it executes the decision-making of path planning and parking lot selection again. As shown in Figure4, if the new result shows the parking lot selection is changed, a cancellation message should be send to the reserved parking lot in last decision (and a reservation message is send to the new selected parking lot); if there is no change and the current time is earlier than the intersection arrival time in last prediction, the vehicle sends step confirmation message which includes the predicted times of arriving at parking lot and next intersection in the new prediction to the parking lot; otherwise, if the current time is later, the vehicle should resend the reservation message.Figure 4
Step-by-step acknowledgement reservation process.Note that keeping communication and querying real-time information frequently can improve the accuracy of decision-making for the vehicle. However, it easily leads to a noticeable overhead to the backbone network, especially under the environment of a large number of demanding vehicles. In our proposed mechanism, we limit that the operation is only executed when the vehicle reaches the intersection area, which can alleviate the communicating and computing loads, and at the same time, while ensuring the practicability and applicability, since in general circumstance, the vehicle can change path only while passing the intersection.


## 3.1. Problem Statement and Assumptions

In order to maximize and balance the utilization efficiency of multiple surrounding parking lots and then reduce searching time of drivers, the collaborative reservation mechanism facing multiparty communication needs an efficient supporting network. In our design (Figure1), we assume that all parking lots and road side units (RSUs) which are deployed at each intersection constitute the backbone network. As basic network nodes, they can communicate with each other in real time by wired network or cellular network. In contrast, parking vehicles are not introduced into the backbone network. Instead, through equipped on-board devices, they can communicate with nearby (i.e., in the transmission range) RSU or parking lot directly by other certain cost-free wireless network standards, e.g., dedicated short range communication (DSRC), Wi-Fi. Such design can effectively reduce the communication cost for drivers, and the backbone network is deployed and maintained as the urban public infrastructure, which can be managed conveniently and shared to other applications as well.Figure 1
Diagram of supporting network in the collaborative reservation mechanism.Moreover, due to the perspective of the utilization of public resource, in this paper, we do not take into account the pricing strategy and interest competition during different parking lots (not distributed roadside parking spaces) which we consider as the homogenous resource to manage and allocate.The whole reservation mechanism is divided into three parts (path planning, parking space prediction, and integrated design) to describe respectively as follows.


## 3.2. Path Planning for Vehicles

As the route along which the vehicle can reach the destination with the shortest time is the optimal choice in general, the travel time prediction is the determining factor in the decision-making for vehicle’s path planning. In the environment of multiple parking lots around the destination, we evaluate the optimal travel time spent to each of them, which can support the reservation decision in Section 3.4. According to actual urban road traffic environment as shown in Figure2, three times submodels are designed for the whole travel time prediction: the time of waiting for traffic lights, passing the intersection, and running on the road.Figure 2
Three kinds of time spent on the travel.In addition, for the traffic information used in the calculation (e.g., traffic lights state, waiting queue length, and traffic density on road), RSUs at the each intersection are in charge of the data collection work which can be achieved by advanced and sophisticated sensor network and image processing technology nowadays. As it is not the main point of the research, the detailed description is not given in this paper.


### 3.2.1. Waiting Time for Traffic Lights

Traffic lights have a great impact on the whole travel time. Sometimes, if a vehicle does not pass the stop line in time when the light is about to turn, it has to wait a more period time meeting the red light. Then, they have strong uncertainty and randomness.In general, from the macroscopic and statistical point of view, the mean value of waiting time of all passed vehicles in a certain direction flowing at the intersection can be used to consider as the evaluating value of such direction [26]. However, based on more accurate and real-time collected information at next intersection which current vehicle is about to reach, we can evaluate the waiting time by a microscopic and concrete approach. In this paper, a combination method is adopted, i.e., for the next intersection, we construct a real-time microscopic prediction model, and for following intersections, the statistical average waiting time tflww which can be gathered by RSU is utilized directly.The waiting time at the next intersection is calculated as follows. Firstly, by communication with the control unit of traffic lights, we can obtain its current states, i.e., current phase and remaining timetre. Then, the allowed passing time tGre in current phase and the length tl from current moment to the opening point of next green light can be estimated:(1)tGre=tre,green,0,red,tl=tc−tG−tre,green,tre,red,where tc is the length of a complete signal cycle and tG is the duration of green light.Then, we calculate the required timetq and required number of signal cycle nc for current vehicle to wait:(2)tq=tpu1+nq,nc=tq−tGretG,where tpu is the desired interval time between two successive passed queue vehicles and nq is the vehicle count in the waiting queue and before the current vehicle.Thus, the waiting time at the next intersectiontnextw can be calculated:(3)tnextw=tq,nc=0,tq+t1,nc=1,tq+t1+nc−1tc−tG,nc>1.Note that in order to make correct path planning, the waiting time in each candidate direction at the intersection needs to be evaluated for current vehicle.Finally, we summarize the prediction of waiting time for traffic lights as(4)tw=tnextw,next intersection,tflww,following intersections.


### 3.2.2. Time of Passing Intersection

As vehicles generally start from the waiting queue and cannot run at the maximum allowed velocities at the beginning, for estimation of passing the intersection area, the acceleration process of vehicle needs to be considered. The required accelerating timetacc to maximum velocity is(5)tacc=vil−vca,where vil is the limited velocity at the intersection and vc is the current velocity when the vehicle just entered the intersection area, and the running distance dacc in tacc is(6)dacc=vil2−vc22a.Then, the passing timetp is calculated as(7)tp=tacc,dacc≥Li,Li−daccvl+tacc,dacc<Li,where Li is the length of the ith direction (i.e., go straight, turn left, or turn right) in the intersection area.


### 3.2.3. Running Time on Road

Based on fundamental diagram of traffic flow theory, running velocities of vehicles are affected by the traffic density on road, i.e., the larger number of vehicles means the lower average speed due to more interactions [27]. For a road with the length Lr and the traffic density ρ, the running time tr spent on it of one vehicle can be evaluated as(8)tr=1+α1⋅ρβ1Lr−lqminvrl,vdes,where vrl is the limited velocity on the road and vdes is the desired velocity of the vehicle itself and lq is the length of waiting queue at downstream intersection. Likewise, queue in each direction needs to be considered separately to support the path planning. Besides, α1 and β1 are the adjustable parameters.


### 3.2.4. Path Planning

When the vehicle which wants to evaluate the optimal parking lot and the fastest travel path to its destination enters the region near the intersection (which means there is enough time and sufficient space to change lane for turning direction), it sends a routing request to the RSU through wireless communication. The RSU which is in the backbone network makes the decision by estimating its own data and the exchanged information from other RSUs.As we described in above sections, a road and its downstream intersection constitute a path unit, and the time spent on ittu includes the waiting time for traffic lights, the time passing the intersection, and the running time on the road:(9)tu=tw+tp+tr.Then, the total travel time of theith candidate path Pi from current decision intersection to the jth certain parking lot can be summarized as(10)tjtPi=∑tu+te,te=tw+tp+1+α1⋅ρβ1⋅Llastminvrl,vdes,where te means the time spent on last path segment, i.e., from the last intersection to the parking lot, and Llast is the distance from the upstream intersection (i.e., the last intersection) to the position of the parking lot.Utilizing dynamic programming algorithm, fromn candidate paths, we can obtain the optimal path which has the shortest time:(11)Popt=argmintjtPi,i=0,1,…n.Note that, for adjusting calculation quantity to suit the computing capability of the RSU and the network communicating capacity, we can set the threshold to reduce the number of candidate paths to be considered, e.g., the physical distance or the number of intersections in the path.


## 3.2.1. Waiting Time for Traffic Lights

Traffic lights have a great impact on the whole travel time. Sometimes, if a vehicle does not pass the stop line in time when the light is about to turn, it has to wait a more period time meeting the red light. Then, they have strong uncertainty and randomness.In general, from the macroscopic and statistical point of view, the mean value of waiting time of all passed vehicles in a certain direction flowing at the intersection can be used to consider as the evaluating value of such direction [26]. However, based on more accurate and real-time collected information at next intersection which current vehicle is about to reach, we can evaluate the waiting time by a microscopic and concrete approach. In this paper, a combination method is adopted, i.e., for the next intersection, we construct a real-time microscopic prediction model, and for following intersections, the statistical average waiting time tflww which can be gathered by RSU is utilized directly.The waiting time at the next intersection is calculated as follows. Firstly, by communication with the control unit of traffic lights, we can obtain its current states, i.e., current phase and remaining timetre. Then, the allowed passing time tGre in current phase and the length tl from current moment to the opening point of next green light can be estimated:(1)tGre=tre,green,0,red,tl=tc−tG−tre,green,tre,red,where tc is the length of a complete signal cycle and tG is the duration of green light.Then, we calculate the required timetq and required number of signal cycle nc for current vehicle to wait:(2)tq=tpu1+nq,nc=tq−tGretG,where tpu is the desired interval time between two successive passed queue vehicles and nq is the vehicle count in the waiting queue and before the current vehicle.Thus, the waiting time at the next intersectiontnextw can be calculated:(3)tnextw=tq,nc=0,tq+t1,nc=1,tq+t1+nc−1tc−tG,nc>1.Note that in order to make correct path planning, the waiting time in each candidate direction at the intersection needs to be evaluated for current vehicle.Finally, we summarize the prediction of waiting time for traffic lights as(4)tw=tnextw,next intersection,tflww,following intersections.


## 3.2.2. Time of Passing Intersection

As vehicles generally start from the waiting queue and cannot run at the maximum allowed velocities at the beginning, for estimation of passing the intersection area, the acceleration process of vehicle needs to be considered. The required accelerating timetacc to maximum velocity is(5)tacc=vil−vca,where vil is the limited velocity at the intersection and vc is the current velocity when the vehicle just entered the intersection area, and the running distance dacc in tacc is(6)dacc=vil2−vc22a.Then, the passing timetp is calculated as(7)tp=tacc,dacc≥Li,Li−daccvl+tacc,dacc<Li,where Li is the length of the ith direction (i.e., go straight, turn left, or turn right) in the intersection area.


## 3.2.3. Running Time on Road

Based on fundamental diagram of traffic flow theory, running velocities of vehicles are affected by the traffic density on road, i.e., the larger number of vehicles means the lower average speed due to more interactions [27]. For a road with the length Lr and the traffic density ρ, the running time tr spent on it of one vehicle can be evaluated as(8)tr=1+α1⋅ρβ1Lr−lqminvrl,vdes,where vrl is the limited velocity on the road and vdes is the desired velocity of the vehicle itself and lq is the length of waiting queue at downstream intersection. Likewise, queue in each direction needs to be considered separately to support the path planning. Besides, α1 and β1 are the adjustable parameters.


## 3.2.4. Path Planning

When the vehicle which wants to evaluate the optimal parking lot and the fastest travel path to its destination enters the region near the intersection (which means there is enough time and sufficient space to change lane for turning direction), it sends a routing request to the RSU through wireless communication. The RSU which is in the backbone network makes the decision by estimating its own data and the exchanged information from other RSUs.As we described in above sections, a road and its downstream intersection constitute a path unit, and the time spent on ittu includes the waiting time for traffic lights, the time passing the intersection, and the running time on the road:(9)tu=tw+tp+tr.Then, the total travel time of theith candidate path Pi from current decision intersection to the jth certain parking lot can be summarized as(10)tjtPi=∑tu+te,te=tw+tp+1+α1⋅ρβ1⋅Llastminvrl,vdes,where te means the time spent on last path segment, i.e., from the last intersection to the parking lot, and Llast is the distance from the upstream intersection (i.e., the last intersection) to the position of the parking lot.Utilizing dynamic programming algorithm, fromn candidate paths, we can obtain the optimal path which has the shortest time:(11)Popt=argmintjtPi,i=0,1,…n.Note that, for adjusting calculation quantity to suit the computing capability of the RSU and the network communicating capacity, we can set the threshold to reduce the number of candidate paths to be considered, e.g., the physical distance or the number of intersections in the path.


## 3.3. Parking Space Prediction

For the vehicle, when it arrives at its target parking lot, whether there is an empty space for it at such a moment needs to be considered in advance, before the decision-making of path planning. In our design, based on gathered real-time information of the arrived and the left vehicles, each parking lot is in-charge of predicting the number of empty parking spaces in it by the aid of the grey prediction model.Firstly, the number of vehicles which arrived at the parking lot is recorded per unit period. We adopt the combination of the real-time valueXA−c0i and the historical average value XA−h0i of that at the same time in all weeks in the last year as the input data:(12)XA0i=α2⋅XA−c0i+β2⋅XA−h0i,where α2 and β2 are the weighting factors, and the input sequence, i.e., the data in last n periods, can be expressed as(13)XA0i=XA01,XA02,…,XA0n.Then, by accumulated generating operation, the new sequence is obtained as(14)XA1=XA11,XA12,…,XA1n,XA1k=∑i=1kXA0i,k=1,2,…,n.where XA1 needs to satisfy the first order differential equation:(15)dXI1dt+a⋅XA1=u,where a and u can be calculated by the least square estimation. Therefore, the number in last k + 1 unit periods is evaluated as(16)XA1^k+1=XA11−uae−ak+ua.Then, the number of entered vehicles at timek + 1 is(17)XA0^k+1=XA1^k+1−XA1^k.By the similar approach, the number of the left vehiclesXL0^k+1 can be estimated as well. Finally, we can obtain the number of empty parking spaces at time n + 1:(18)Xn+1=0,X0^n+1<0,Xmax,X0^n+1>Xmax,X0^n+1,others,X0^n+1=XEn−XA0^n+1+XL0^n+1,where Xmax is the capacity of parking lot and XEn is the actual number of empty spaces at time n.


## 3.4. Time of Waiting Empty Parking Space

When the parking lot is filled to capacity, how much time will the vehicle need to wait for an empty space is an important problem to be considered. In other words, if the waiting time is too long, the vehicle should turn to other parking lots. Furthermore, the prediction of waiting time should be executed in advance before the vehicle arrives, which can help it to make a more accurate selection.Assuming the current time ist0 and the vehicle will arrive at ta, then as mentioned in the above section, the number of vehicles arriving at each period from t0 to ta can be calculated as XA^ti, and the number of vehicles XL^ti which will leave at each period can be evaluated as well. Then, the number of vehicles which will not enter the parking lot and have to wait outside at time ta is(19)XWta=XEt0−∑XA^ti−XL^ti.IfXWta>0 which means there are vehicles queuing in front of the arrived vehicle, it needs to wait all of them to enter the parking lot. In other words, it can park until at least XWta+1 vehicles which have parked in the parking lot leave. From ta+1, we calculate the number of the left vehicles in each unit period in turn until(20)∑tj=ta+1tmXL^tj>XWta,where tm is the time required to wait for an empty space.Thus, the waiting time outside the parking lotto can be concluded as(21)to=0,XWta≤0,argmin∑tj=ta+1xXL^tj>XWta,XWta>0.


## 3.5. Time of Parking inside and Walking to Destination

So far, we provide the evaluations of optimal travel time and the empty space waiting time, respectively. In order to reach the destination successfully, there are still two steps to be considered for the driver: parking in the interior of the parking lot and walking to the destination.For the former, in large construction facility, searching empty space holds the major time expenditure in the whole parking process. Generally speaking, higher occupancy means harder searching and more time used for the driver. Then, we provide the following calculation model to represent the time of parking inside:(22)ti=α3⋅eβ3⋅Xta+to/Xmax+tk,where Xta+to means the predicted number of empty parking spaces when the vehicle enters this parking lot, tk is the average parking time in an empty space, and α3, β3 are the adjustable parameters. Note that other factors such as internal building structure and deployment of assisted navigation equipment have impacts on parking as well. However, this issue is not the focus in this paper, more detailed discussion is not given here.For the latter, the walking time from the parking lot to the destination can be evaluated as(23)tf=dpvw,where dp is the path distance and vw is the average human walking velocity.Then, for a certain parking lotj, from the time when the vehicle reaches the intersection area and generates a request of path planning to the time it arrives at its final destination, the total time can be evaluated as(24)tjtotal=tjtPopt+tjo+tji+tjf,where Popt is the optimal path from current position to parking lot j.


## 3.6. Collaborative Reservation Mechanism

When the vehicle which has the demand of parking around a certain destination reaches any intersection, it sends the request packet with the destination position and other specific and optional requirements (e.g., path query range and time limit) to the RSU by the wireless communication. Every RSU can communicate with all parking lots and a central server through the dedicated backbone network. They deal with the parking planning and reservation work collaboratively. We provide their respective functions in the whole reservation scheme below from three aspects as shown in Figure3: information collection, response to path planning request, and real-time reservation.Figure 3
Respective functions of RSU, parking lot, and central server. (a) Information collection. (b) Response to path planning request. (c) Real-time reservation.
(a)(b)(c)RSU is in charge of collecting the traffic information in the area of its intersection and all connected roads, evaluating the travel time on each path unit in real-time, i.e., in (9), and submits the results to the central server to record periodically. In its area, for the vehicle which sends the request of path planning, the RSU inquires for the predicted travel time of path units in other areas (i.e., from current intersection to the destination) from the central server (note that the searching scope depends on concrete requirements of the request vehicle) and, after the search results are received, it sends all of them with its own data back to the vehicle. When the vehicle submits the reservation or cancellation application after the decision-making, the RSU is responsible for forwarding it to the corresponding parking lot in time.Parking lot is responsible for gathering its own real-time state information including the number of empty spaces and entering and leaving vehicles, executing the time predictions as we present in Sections3.3–3.5 and then sending the results to the central server to record and update periodically. For the reservation and cancellation from vehicles, the parking lot adjusts its available capacity in real-time correspondingly. Furthermore, if the step confirmation message is not received within the time limit from the vehicle which has reserved parking space, the parking lot will cancel its reservation.Central server in the backbone network establishes records for all RSUs (i.e., all path units) and parking lots, maintains this information according to the received periodical updates, and provides query services to the vehicles which have demands of parking. In the proposed scheme, beyond centralized information storage, the central server is not in charge of related computation work (i.e., the tasks of travel time evaluation, path planning, parking space prediction, and so on) and does not participate in actual reservation process, which can reduce the working load of it effectively. In other words, it only plays a role of real-time database server in the whole collaborative reservation mechanism.In addition, after the vehicle received the query results from the central server (relayed by nearby RSU), the decisions of path planning and parking lot selection are executed locally. According to the decision result, the reservation message is sent to corresponding parking lot to order a space (through the RSU as well). Firstly, the predicted arrival time should be included in the message, which can help the parking lot to manage and allocate its parking resource rationally and efficiently. Secondly, as realistic traffic conditions are changed frequently and some influence factors cannot be precisely considered, there is the inevitable estimated bias in the predict travel time from the place where the vehicle initiates the reservation to the parking lot. In order to alleviate this impact, in our scheme, a step-by-step acknowledgement mechanism is proposed as follows. Besides the time of arriving at the parking lot, the vehicle also packs the predicted time of arriving at next intersection into the reservation message. The parking lot adds this time by the factor of tolerate transmission timeγγ≥0 as the limited time, within which if there is no confirmation arrives in time or a cancellation message is received from the vehicle, the parking lot cancels the reserved parking space.On the other side, when the vehicle arrives at next intersection, it executes the decision-making of path planning and parking lot selection again. As shown in Figure4, if the new result shows the parking lot selection is changed, a cancellation message should be send to the reserved parking lot in last decision (and a reservation message is send to the new selected parking lot); if there is no change and the current time is earlier than the intersection arrival time in last prediction, the vehicle sends step confirmation message which includes the predicted times of arriving at parking lot and next intersection in the new prediction to the parking lot; otherwise, if the current time is later, the vehicle should resend the reservation message.Figure 4
Step-by-step acknowledgement reservation process.Note that keeping communication and querying real-time information frequently can improve the accuracy of decision-making for the vehicle. However, it easily leads to a noticeable overhead to the backbone network, especially under the environment of a large number of demanding vehicles. In our proposed mechanism, we limit that the operation is only executed when the vehicle reaches the intersection area, which can alleviate the communicating and computing loads, and at the same time, while ensuring the practicability and applicability, since in general circumstance, the vehicle can change path only while passing the intersection.


## 4. Performance Evaluation

### 4.1. Simulation Environment and Parameter Settings

In order to evaluate the performance of our proposed collaborative reservation mechanism (CRM), in this paper, we adopt Veins [28] software which is a discrete event simulation architecture based on the traffic simulation software SUMO [29] and network simulation software OMNeT++ [30]. Veins can drive them to run in synchronization and facilitate urban traffic simulation under a certain network environment.As shown in Figure5, a 6830 m∗6200 m rectangle area which contains 106 streets and 50 intersections is constructed to simulate the urban road network environment. Each bidirectional street has four lanes and the velocity limit of 60 km/h. For the signal lights at each intersection, the green light durations for going straight and turning left are set to 40 s and 20 s, respectively, and turning right is allowed constantly. Furthermore, the velocity limit passing the intersection is set to 45 km/h. Around the destination are three parking lots: A, B, and C with the capacities of 200, 430, and 350 parking spaces and the average walking time to destination of 521, 624, and 660 seconds, respectively. In order to shorten the simulation time, we set that half of their parking spaces has been occupied at the beginning.Figure 5
Construction of urban road network and parking lots.All vehicles in the simulation are inserted into the map from a random edge street. However, according to whether the vehicle demands to park, we divide them into two classes: background vehicles and parking vehicles. In order to simulate actual traffic environment, background vehicles only travel through the map following random paths and do not seek to park. In contrast, parking vehicles which have the same destination and should park in one of the three parking lots are our main observation objects, and we set the generating rate of parking vehicles dynamically over time following the distribution below (Figure6) to simulate the parking rush hour. Then, we can directly evaluate the performance in a relative actual environment with different stress levels. For the setting of staying time in parking lot, each parked vehicle holds a stochastic duration time following a uniform distribution U (60, 180) (min). When the time is up, it will leave.(25)ft=12⋅e−t−120/722.Figure 6
Distribution of parking vehicle generating rate.In the simulation, the performance of CRM is evaluated from two aspects: the total travel time of drivers and the efficient utilization of parking lots. For comparison, the traditional mechanism in which the vehicle selects the nearest parking lot directly and makes a random decision of waiting or turning to others when current parking lot is full is also executed in the same conditions.The duration of each test is 300 min identically and similar tests with different random seeds run for enough times to calculate the average value of result. Table1 summarizes some key parameters in the simulation.Table 1
Simulation parameter.
ParameterValueSimulation area6830 m∗6200 mDuration of green light (straight/left turning)40/20 sIntersection velocity limit45 km/hParking lot capacity (A/B/C)200/430/350Walking time to destination (A/B/C)521/624/660 sGenerating rate of background vehicles1∼10 veh/sStaying time of parked vehicleU (60, 180) minMAC layer of wireless communicationDCF of IEEE 802.11Transmission range of wireless communication250 mSimulation time300 min


### 4.2. Travel Time Evaluation

In this section, the total travel time which is the duration from the time when the vehicle generates the first request of path planning to the time the driver arrives at the destination (i.e., including the walking time from parking lot to the destination) is evaluated. Obviously less travel time means more accurate planning decision of reservation mechanism. The average travel time of drivers who arrive the destination in five different time segments is calculated respectively to observe the performance under different stress levels. In addition, the generating rate of background vehicles is set to 5 veh/s.As presented in Figure7, the average travel time in CRM is less than that in the traditional mechanism in each time segment. Especially, as shown in Figure 5, when the time becomes the 120th minute in the simulation, the generation rate of parking vehicles reaches the peak point. Accordingly, the drivers arriving in the time segment 130–160 minutes needed to spend more travel time than others due to their more waiting time for empty parking spaces. As we can see, the value of traditional mechanism which is 1694.25 s increases sharply than its result in segment 70–100 minutes by 346.02 s. In contrast, there is a relatively less growth in CRM (170.11 s), which is because the real-time and collaborative working mechanism provides the support of more accurate traffic and parking lots information, which practically assists vehicles to select correct parking lot and avoid unnecessary waiting time.Figure 7
Travel time of vehicles in different time segment.In order to evaluate the performance under different traffic environment, as shown in Figure8, we vary background vehicle generating rate (from 1 to 10 veh/s) to calculate the average travel time in entire experiment process. With the increasing of traffic density, the running time spent on the road for vehicles increases accordingly, and both the average travel time in CRM and traditional mechanism increase gradually from low to high density. However, the results of CRM are significantly better than that of traditional mechanism. Especially, when the background vehicle generating rate is 10 veh/s, the difference reaches the maximum value: 395.54 s. Traditional mechanism is hard to make adjustment timely according to environment changes. In the design of CRM, aided by the collection of real-time traffic information and multiple parking lots information, the step-by-step acknowledgement mechanism can support the vehicle to evaluate and make decision dynamically for its parking lot selection and path planning at each intersection which it passes.Figure 8
Travel time under different traffic environments.To estimate the collaborative capacity of CRM in stress environment, in this experiment, 80% of parking vehicles are inserted into the map from the left edge. In the traditional mechanism, most of the parking vehicles select parking lot C which is nearest to them as their targets, and then this parking lot is filled up rapidly which leads to more waiting time or travelling time on turning to other parking lots for subsequent arrived vehicles. As shown in Figure9, the average travel time of traditional mechanism is 84.62 s longer than that in the last test. On the contrary, based on the real-time information collection and the dynamic collaborative mechanism, CRM considers the future trends of empty parking spaces in each parking lot. Thus, the vehicle can select the optimal target according to dynamic environment and effectively avoid wasting time. The results outperform that in traditional mechanism obviously.Figure 9
Travel time of vehicles from the same direction.


### 4.3. Results and Analysis

Making full use of limited parking space resource to reduce travel time for drivers is the design objective of CRM. In this section, we evaluate the performance from the viewpoint of parking lots utilization. The stress environment in the last test continues to be used (i.e., 80% of parking vehicles are inserted into the map from the left edge), and five time points (80/110/140/170/220 minutes) are chosen to gather the occupancy of each parking lot.Figure10(a) shows the results of traditional mechanism in which there are some imbalances between three parking lot occupancies, especially by further calculation, the average standard deviation of the values at first three time points is 25.87%. Since most of the parking vehicles are generated from the left edge, parking lot C is generally their optimal choice in an ideal situation. However, with the growth of the occupancy ratio, it inevitably increases their searching time for empty space in the interior of parking lot, waiting time for empty space at the outside or travel time for returning to another parking lot when lot C is finally filled up. Without dynamic adjustment according to real-time environment, simply selecting the nearest parking lot as the target may lead to the increasing of total travel time and the wasting of parking space resources, instead of saving time, especially during the peak period.Figure 10
Parking lots utilization at different time points. (a) Traditional mechanism. (b) CRM.
(a)(b)As shown in Figure10(b), the results of CRM are obviously better than that of traditional mechanism. The average standard deviation of the occupancies at first three time points is 10.54% which means there is a relatively balanced utilization on three parking lots. In CRM, the vehicle makes decision dynamically based on the real-time state of parking lot and traffic condition, which can make full use of the parking space resource and provide a comprehensive evaluation on the whole travel time, i.e., from its current position to the final destination. To sum up, the results prove the validity and advantage of CRM which is designed based on collaborative working and overall planning.


## 4.1. Simulation Environment and Parameter Settings

In order to evaluate the performance of our proposed collaborative reservation mechanism (CRM), in this paper, we adopt Veins [28] software which is a discrete event simulation architecture based on the traffic simulation software SUMO [29] and network simulation software OMNeT++ [30]. Veins can drive them to run in synchronization and facilitate urban traffic simulation under a certain network environment.As shown in Figure5, a 6830 m∗6200 m rectangle area which contains 106 streets and 50 intersections is constructed to simulate the urban road network environment. Each bidirectional street has four lanes and the velocity limit of 60 km/h. For the signal lights at each intersection, the green light durations for going straight and turning left are set to 40 s and 20 s, respectively, and turning right is allowed constantly. Furthermore, the velocity limit passing the intersection is set to 45 km/h. Around the destination are three parking lots: A, B, and C with the capacities of 200, 430, and 350 parking spaces and the average walking time to destination of 521, 624, and 660 seconds, respectively. In order to shorten the simulation time, we set that half of their parking spaces has been occupied at the beginning.Figure 5
Construction of urban road network and parking lots.All vehicles in the simulation are inserted into the map from a random edge street. However, according to whether the vehicle demands to park, we divide them into two classes: background vehicles and parking vehicles. In order to simulate actual traffic environment, background vehicles only travel through the map following random paths and do not seek to park. In contrast, parking vehicles which have the same destination and should park in one of the three parking lots are our main observation objects, and we set the generating rate of parking vehicles dynamically over time following the distribution below (Figure6) to simulate the parking rush hour. Then, we can directly evaluate the performance in a relative actual environment with different stress levels. For the setting of staying time in parking lot, each parked vehicle holds a stochastic duration time following a uniform distribution U (60, 180) (min). When the time is up, it will leave.(25)ft=12⋅e−t−120/722.Figure 6
Distribution of parking vehicle generating rate.In the simulation, the performance of CRM is evaluated from two aspects: the total travel time of drivers and the efficient utilization of parking lots. For comparison, the traditional mechanism in which the vehicle selects the nearest parking lot directly and makes a random decision of waiting or turning to others when current parking lot is full is also executed in the same conditions.The duration of each test is 300 min identically and similar tests with different random seeds run for enough times to calculate the average value of result. Table1 summarizes some key parameters in the simulation.Table 1
Simulation parameter.
ParameterValueSimulation area6830 m∗6200 mDuration of green light (straight/left turning)40/20 sIntersection velocity limit45 km/hParking lot capacity (A/B/C)200/430/350Walking time to destination (A/B/C)521/624/660 sGenerating rate of background vehicles1∼10 veh/sStaying time of parked vehicleU (60, 180) minMAC layer of wireless communicationDCF of IEEE 802.11Transmission range of wireless communication250 mSimulation time300 min


## 4.2. Travel Time Evaluation

In this section, the total travel time which is the duration from the time when the vehicle generates the first request of path planning to the time the driver arrives at the destination (i.e., including the walking time from parking lot to the destination) is evaluated. Obviously less travel time means more accurate planning decision of reservation mechanism. The average travel time of drivers who arrive the destination in five different time segments is calculated respectively to observe the performance under different stress levels. In addition, the generating rate of background vehicles is set to 5 veh/s.As presented in Figure7, the average travel time in CRM is less than that in the traditional mechanism in each time segment. Especially, as shown in Figure 5, when the time becomes the 120th minute in the simulation, the generation rate of parking vehicles reaches the peak point. Accordingly, the drivers arriving in the time segment 130–160 minutes needed to spend more travel time than others due to their more waiting time for empty parking spaces. As we can see, the value of traditional mechanism which is 1694.25 s increases sharply than its result in segment 70–100 minutes by 346.02 s. In contrast, there is a relatively less growth in CRM (170.11 s), which is because the real-time and collaborative working mechanism provides the support of more accurate traffic and parking lots information, which practically assists vehicles to select correct parking lot and avoid unnecessary waiting time.Figure 7
Travel time of vehicles in different time segment.In order to evaluate the performance under different traffic environment, as shown in Figure8, we vary background vehicle generating rate (from 1 to 10 veh/s) to calculate the average travel time in entire experiment process. With the increasing of traffic density, the running time spent on the road for vehicles increases accordingly, and both the average travel time in CRM and traditional mechanism increase gradually from low to high density. However, the results of CRM are significantly better than that of traditional mechanism. Especially, when the background vehicle generating rate is 10 veh/s, the difference reaches the maximum value: 395.54 s. Traditional mechanism is hard to make adjustment timely according to environment changes. In the design of CRM, aided by the collection of real-time traffic information and multiple parking lots information, the step-by-step acknowledgement mechanism can support the vehicle to evaluate and make decision dynamically for its parking lot selection and path planning at each intersection which it passes.Figure 8
Travel time under different traffic environments.To estimate the collaborative capacity of CRM in stress environment, in this experiment, 80% of parking vehicles are inserted into the map from the left edge. In the traditional mechanism, most of the parking vehicles select parking lot C which is nearest to them as their targets, and then this parking lot is filled up rapidly which leads to more waiting time or travelling time on turning to other parking lots for subsequent arrived vehicles. As shown in Figure9, the average travel time of traditional mechanism is 84.62 s longer than that in the last test. On the contrary, based on the real-time information collection and the dynamic collaborative mechanism, CRM considers the future trends of empty parking spaces in each parking lot. Thus, the vehicle can select the optimal target according to dynamic environment and effectively avoid wasting time. The results outperform that in traditional mechanism obviously.Figure 9
Travel time of vehicles from the same direction.


## 4.3. Results and Analysis

Making full use of limited parking space resource to reduce travel time for drivers is the design objective of CRM. In this section, we evaluate the performance from the viewpoint of parking lots utilization. The stress environment in the last test continues to be used (i.e., 80% of parking vehicles are inserted into the map from the left edge), and five time points (80/110/140/170/220 minutes) are chosen to gather the occupancy of each parking lot.Figure10(a) shows the results of traditional mechanism in which there are some imbalances between three parking lot occupancies, especially by further calculation, the average standard deviation of the values at first three time points is 25.87%. Since most of the parking vehicles are generated from the left edge, parking lot C is generally their optimal choice in an ideal situation. However, with the growth of the occupancy ratio, it inevitably increases their searching time for empty space in the interior of parking lot, waiting time for empty space at the outside or travel time for returning to another parking lot when lot C is finally filled up. Without dynamic adjustment according to real-time environment, simply selecting the nearest parking lot as the target may lead to the increasing of total travel time and the wasting of parking space resources, instead of saving time, especially during the peak period.Figure 10
Parking lots utilization at different time points. (a) Traditional mechanism. (b) CRM.
(a)(b)As shown in Figure10(b), the results of CRM are obviously better than that of traditional mechanism. The average standard deviation of the occupancies at first three time points is 10.54% which means there is a relatively balanced utilization on three parking lots. In CRM, the vehicle makes decision dynamically based on the real-time state of parking lot and traffic condition, which can make full use of the parking space resource and provide a comprehensive evaluation on the whole travel time, i.e., from its current position to the final destination. To sum up, the results prove the validity and advantage of CRM which is designed based on collaborative working and overall planning.


## 5. Conclusion

In this paper, we propose a collaborative reservation mechanism in the environment of multiple adjacent candidate parking lots. Based on the real-time information collection of traffic condition and parking lots states, the whole travel time from current position to the final destination is divided into four parts to be modelled and predicted, and then, the optimal decision is made from the overall angle, which can support drivers to efficiently utilize limited parking space resource to reduce their travel time. The simulation results show that our proposed CRM outperforms the traditional mechanism in terms of travel time saving and parking lots utilization under different traffic environments.



---

*Source: 8876069-2021-01-08.xml*