Optimization design and evaluation of parking route based on automatic assignment mechanism of parking lot

Abstract

The congestion causes of parking lot were analyzed with causal chain method and a questionnaire about individual demand of parking users was carried out. The results show that more than 90% of the users hope parking spaces can be automatically assigned to them when it’s difficult to find a parking space. The layout principles of WiFi in parking lot were provided. The automatic assignment mechanism of parking lot was given considering the individual demand of parking users and the avoidance of traffic conflicts. Some attribute decision factors such as lane occupancy conditions, travel distance, walking distance, and the occupancy situation of parking space on both sides were selected and optimal parking lot assignment model was established. Optimal paths were calculated through Dijkstra algorithm, and the information about the assignment location and path was sent to the drivers’ cell phones. The driver’s compliance was evaluated by comparing the driver’s parking trajectory with system recommended path. Finally, a large parking lot in Beijing was taken as an example. The results can offer constructive suggestions on parking route design and parking assignment mechanism, which can make the use of the limited parking resources more effectively.

Introduction

With the development of economy and incensement of car ownership, the supply–demand difference problem of parking spaces has become more and more prominent. Recently, the intelligent parking guidance system is widely used in the super-large underground parking garage and plays a role to improve the parking efficiency. Due to the problems such as the unreasonable traffic organization design and assignment and guidance of parking lot, the existing parking system gradually cannot meet the parking needs and lead to a series of problems such as longer searching time for parking space. The problems were analyzed with causal chain method and listed as follows: ¹ (1) because the drivers do not know the actual location of empty parking space, they have to drive blindly and disorderly in the parking lot that causes traffic congestion. (2) The parking management administrators cannot obtain the space utilization rate in different parking zones timely, so that they cannot make the right decision to adjust resource allocation. The parking management administrators had to arrange a lot of manpower to maintain the order of the parking lot, which increases the management cost; (3) because the GPS does not work well in the underground parking garage, the existing parking system generally lacks the information exchange with the drivers and does not satisfy their needs. They cannot monitor the parking trajectory of vehicles and effectively guide the drivers in the parking lot, which results in poor satisfaction of users. ² Therefore, how to use the limited parking resources effectively has become an urgent problem needed to be solved by parking lot managers. An automatic assignment mechanism of parking lot considering the users’ information demand is proposed and discussed to solve all the above problems.

Literature review

Parking issues need to be studied with systematic perspective because they involve various indicators such as ecological capacity, social capacity, financial capacity, psychological capacity, efficiency of service, and other various indicators.^3–5 The core concept to solve the parking problems in large parking lots is to accomplish scientific guidance of drivers’ parking behavior through the optimal design of intelligent parking system. The strategies that can be taken include the optimal design of parking route, parking guidance and information distribution, vehicle guidance, and reverse searching. Domestic and foreign scholars have conducted a lot of research in these areas and achieved many important research results.

In the research of parking route design, based on the principle of separating pedestrians and vehicles, the driving routes of vehicles in parking lots are designed with reasonable traffic organization and optimization design. The parking intelligent management systems were divided into vehicle guidance subsystem and vehicle management subsystem. ⁶ The identification of empty parking space, parking space assignment, and guidance of parking spaces are key elements of auto parking guidance systems. The auto parking guidance systems are widely used in the cubic parking system. The storage/retrieval queuing system was utilized in stacker crane in cubic parking system, and some efficiency analyses were taken based on the queuing theory. ⁷ As we all know, both cubic parking system and auto parking guidance system are so expensive that they cannot be widely used in the underground parking lots. Automatic parking guidance system is used in the parking lots in Singapore. The drivers just need to drive the vehicles to the entrance of parking lot. Vehicles will be guided to the lane in which the traffic volume is smaller through the vehicle flow detection system. The Sipark parking guidance systems was utilized in Germany Munich Airport. The parking system will search for an empty parking space automatically through empty parking space detection system and show the messages through the message board to the drivers. This system only can tell the drivers where the empty parking spaces are, but do not tell the drives which empty parking space they can park and how to reach the empty parking space. The Sipark parking guidance systems can reduce the congestion in the parking lot to some extent, but did not solve the key problems such as the assignment and guidance of parking spaces. In recent times, the focus of parking guidance has changed from the outside of the parking lot to the inside. Liu discussed the design of vehicle guidance and reversed searching system. She pointed out that parking space detection was the basis of parking intelligent management, and real-time monitoring of parking spaces was the precondition for providing accurate parking space information to managers and drivers. ⁸ C Ye ⁹ put forward the principle and solution of parking guidance system in the parking lot. A technology which can be used in parking space detection is discussed by some researchers. It can be concluded that WiFi system has a wider effective coverage and low environmental requirements. Through the deployment of WiFi hotspots as well as a range of software and algorithms, the location of intelligent terminals can be detected. There are a variety of algorithms to implement wireless location, such as time of arrival (TOA), time difference of arrival (TDOA), angle of arrival (AOA), receive signal strength (RSS) (algorithm based on signal strength value), and the combination of several algorithms mentioned above. ¹⁰

In summary, drivers’ information demand has not been considered in parking behavior research. The existing parking guidance system is lack of effective methods to track the parking trajectory and guide parking. Parking users still perform for self-organizing to search parking spaces in the large parking lot. The automatic parking garage can achieve automatic assignment of parking spaces, but the investment is so huge that the applications are limited. Thus, to solve all above questions, a parking behavior model under automatic assignment mechanism of parking lot was established considering the individual demand of parking users. A questionnaire about individual demand of parking users was carried out. Then, the layout principles of WiFi in parking lot were provided based on WiFi location technology. The location fingerprint information were collected and matched to determine the real-time vehicle location, which can be utilized to collect drivers’ actual parking trajectory. The automatic assignment mechanism of parking lot was given. Some attribute decision factors such as the lane occupancy conditions, travel distance, walking distance, and the occupancy situation of parking spaces on both sides were selected, and the optimal parking lot assignment model was established. Optimal paths were calculated through Dijkstra algorithm, and the information about the assignment parking location and path was sent to the drivers’ cell phones. The study can provide data support to improve the efficiency of parking lots.

Methodology

Introduction of parking management system

The optimization design process of intelligent parking management system based on WiFi location technology is shown in Figure 1.^10,11 Parking management system is divided into three modules: parking lot management, user management, and space assignment and route distribution. Through the WiFi location technology, parking management module obtains and timely updates the occupancy situation information of parking lot. In user management module, the system obtains users’ registration information and individual needs of parking space which provide basis for automatic assignment of parking spaces. Based on auto-assignment mechanism of parking lot, the individual demand of parking users is considered in the parking space assignment and route distribution module.

Figure 1.

Parking management system.

Based on the discussion of the drivers’ microcosmic choice behavior and the avoidance of traffic conflicts, the automatic assignment model of parking spaces was established to assign the parking spaces and measure the parking routes. Finally, the real-time induction messages were sent by WiFi. At the same time, the parking users’ compliance level to recommended route should be considered. By tracking the users’ driving trajectory, the system will timely discover the vehicles which did not follow the recommended route and then will send a message to remind the user. When the user enters the parking space, the system will update the information of empty parking space automatically. The core contents of three modules are introduced below.

Related technology

WiFi-based positioning technology

Compared to traditional GPS positioning and mobile cellular network locating, ¹² WiFi positioning advantages in the indoor environment. A schematic view of WiFi indoor positioning stage is substantially shown in Figure 2. The parking user’s mobile receives information from three parking wireless access points (APs). Then, a database is established, and positioning calculation is carried out using the weighted nearest neighbor (WNN) method. The reference point can be found to determine the user’s location, which has the minimum Euclidean distance to the collection points. The positioning result and the path trajectory can be shown on the mobile by WiFi.

Figure 2.

WiFi indoor positioning stage schematic.

In order to ensure the positioning requirements that all areas are covered by three AP hotspots at least, AP hotspots in parking lot are laid at intervals of 15 m referring to general indoor installation experience. In the actual installation environment, AP signals will wear and tear if there are too many walls in one direction within 15 m. In order to avoid the above situation, the intervals to place the AP device should be less than 15 m. When a driver connects WiFi in the parking lot with their mobile, fingerprint information of WiFi position can be collected at the same time to match with the datum in the offline database. The reference point which has the minimum Euclidean distance to collection point has been found so that the position of the vehicle can be matched. Installation and layout of the AP devices in the parking lot are shown in Figure 3. shows the position where the AP device is installed on the roof of the corresponding position.

Figure 3.

AP device layout diagram.

Investigation and analysis of the individual needs of the parking users

In order to solve the problem of finding parking space for a long time and driving disorderly, the automatic assignment mechanism of parking lot was given considering the individual demand of parking users. Hence, a questionnaire about individual demand of parking users was carried out. ¹³ The survey consists of the following parts: socioeconomic and demographic characteristics, assignment demand of parking spaces when parking spaces are numerous and tight, route navigation requirements, and willingness to obey and perform the assigned parking spaces.

Because of the difference existed in the users’ driving skills, the corresponding location attribute preferences of parking spaces are also different. As shown in Figure 4, 70% of users who are unfamiliar to driving would like to select the parking space where no car parked on both sides. In addition, the users who have general driving skills would like to select the parking lot where no car parked on both sides and only one side of car-free parking. Because skilled drivers are confident with their parking skill, they can accept any parking space situations.

Figure 4.

Relation between driving skill and parking space preference.

Attribute preference results of parking spaces are shown in Figure 5. It can be concluded that 50% of respondents hope the parking space is close to the elevator and easy to reach the destination by vertical transportation after parking and shorter walk distance. Second, 23% of respondents select the parking space which is close to the exit of the parking lot. Approximately 14% and 11% of the respondents hope for the shortest parking time and shortest parking distance, respectively.

Figure 5.

Attribute preferences of parking space.

The results of the survey showed that more than 90% of the users hope parking space can be automatically assigned to them and route guidance can be provided when parking spaces are tight. They are willing to comply with the allocation result.

Optimal parking lot assignment model considering user needs

In order to avoid conflicts caused by drivers’ blindly searching and low efficiency of the parking lot, automatic assignment mechanism of parking lot is proposed and established. Automatic assignment mechanism of parking lot consists of three parts: optimal parking lot assignment according to user needs and attributes of parking space, calculation and distribution of the shortest parking path, and assessment of the compliance rate of parking lot assignment. First, calculate the optimal parking assignment spaces considering both the traffic conflict avoidance and the maximum satisfaction of the parking users’ needs. Second, calculate the shortest path between vehicles’ current position and the empty parking space with Dijkstra shortest path algorithm.^14–16 Finally, providing real-time route guidance information to users by the WiFi, tracking the parking trajectory and checking the parking users’ compliance status.

In the third part, the “obey willingness factor to allocation result” is proposed and added. The value is between 0 and 1. The bigger the value is, the more parking users are willing to comply with the allocation result. To analyze and discuss the automatic assignment mechanism of parking lot, we assume that people are willing to comply with the allocation result to avoid the conflicts caused by drivers’ blindly searching. In this article, the “obey willingness factor to the allocation result” is assumed to be 1.0. The following measures can be taken to ensure the user to comply with the allocation result. (1) Voice messages reminding the parking users to follow the allocation sent by the parking management system. If the user still failed to follow the allocated result and chose their nearby parking space, the system will immediately update the parking lot information and the parking space can participate in next allocation. (2) Credit scoring system is established. The driver will be deducted a certain score when he fails to comply with allocation result. Parking fees will be increased when reaching a certain score.

Not only the conflicts between the front and the rear vehicles should be avoided during the assignment process but also the drivers’ choice behavior and subjective preference factors should be considered. Therefore, the parking space assignment problem is converted into a multi-attribute decision-making problem. Each empty parking space has four attributes such as vehicle driving distance, walking distance to the elevator, parking occupancy on both sides, and lane occupancy condition. To improve the efficiency of parking, parking space which is on the same lane with the front vehicle should be excluded first to avoid the conflicts between the front and the rear vehicles. Lane occupancy condition is defined to be “yes” when the front vehicle car and the rear vehicle are on the same lane. Second, the attribute weights of driving distance, walking distance to reach the elevator, and parking space occupancy on both sides are determined. All above four indicators affecting user’s parking space choice can be divided into two categories: one is the cost index, such as driving distance and walking distance. The lower the index value is, the better the effect is. Another type is benefit index, such as the vehicle occupancy condition on both sides of empty parking spaces. The higher the index value is, the better the effect is. In order to eliminate the influences of different physical dimensions, the index is normalized as following^17–19

$$\mathrm{Benefit\; index}:{\mathrm{Z}}_{\mathrm{ij}}={\mathrm{y}}_{\mathrm{ij}}/{{\mathrm{y}}_{\mathrm{j}}}^{\max }$$

(1)

$$\mathrm{Cost\; index}:{\mathrm{Z}}_{\mathrm{ij}}={{\mathrm{y}}_{\mathrm{j}}}^{\min }/{\mathrm{y}}_{\mathrm{ij}}$$

(2)

where Z_ij is the attribute value under normalization process. y_ij is the original property value. y_j^max is the maximum value in attributes column of the decision table. And y_j^min is the minimum value in attributes column of the decision table.

The attribute values of each empty parking space are calculated and then the weighted sum is given. The parking space with the maximum weighted sum will be recommended as the optimal parking space by the intelligent parking management system.

Case study

A large parking lot in Beijing was taken as an example to be optimized. The layout of parking lot is shown in Figure 6.

Figure 6.

Layout of parking lot.

When the rear vehicle (No. 2) reaches the entrance of the parking lot, suppose the parking space (E12) had been assigned to the front vehicle (No. 1), the parking guidance system will count the number of the empty parking spaces. The results show that there are seven empty parking spaces left, which are located at B5, B17, C8, C9, D9, E10, and E16. The multiple attribute decision table of empty parking spaces is shown in Table 1.

Table 1.

Multiple attribute decision table of empty parking space.

Location	Lane occupied condition	Driving distance (m)	Walking distance (m)	Parking space occupancy on both sides
B5	No	118	75	Car Parking on one side
B17	No	96	24	Car Parking on both sides
C8	Yes	239	81	Car Parking on one side
C9	Yes	236	85	Car Parking on one side
D9	No	55	63	Car Parking on both sides
E10	No	84	74	No Car Parking on both sides
E16	Yes	201	22	Car Parking on both sides

To avoid the conflicts between the front and the rear vehicles, the three parking spaces whose numbers were C8, C9, and E16 were excluded first because the parking trajectory to these parking spaces conflict with the assigned parking trajectory of the front vehicle. The attribute weights of driving distance, walking distance to the elevator, and parking space occupancy on both sides were calculated to determine the optimal parking space.

In order to eliminate the influences of different physical dimensions, the index is normalized with functions (1) and (2). The results are listed in Table 2.

Table 2.

Normalized attribute decision table.

	Driving distance (m)	Walking distance (m)	Parking space occupancy on both sides	Comprehensive weighted sum
B5	0.4661	0.3200	0.7500	0.4640
B17	0.5729	1.0000	0.2500	0.7057
D9	1.0000	0.3810	0.2500	0.5030
E10	0.6548	0.3243	1.0000	0.5759

According to the investigation and analysis of the individual needs of the parking users, the weight coefficient of driving distance, walking distance to the elevator, and parking space occupancy on both sides were determined, respectively, as 0.25, 0.5, and 0.25. The comprehensive weighted sum of each empty parking space was calculated. It can be seen that the comprehensive weighted sum of parking space B17 is the maximum one, which indicated that parking space B17 is the optimal one and should be assigned to vehicle (No. 2).

To evaluate the parking system with automatic assignment mechanism under WiFi positioning technology, an evaluation index system is established. The evaluation index system is composed of six indexes, such as the reduced parking time for each vehicle, fuel consumption saving, equivalent cost of time and fuel consumption savings, CO emissions reduction, HC emissions reduction, and NO_X emissions reduction. An underground parking lot with 1000 vehicles coming in and out in 1 day was evaluated, and the results are listed in Table 3. It can be seen that the parking time from the entrance to the parking space is obviously reduced for each vehicle. The velocity of the vehicle in the parking lot is conversely improved. The optimal design of the parking lot can not only improve the parking environment but also reduce the driver’s economic loss.

Table 3.

Evaluation index.

Index	Evaluation result
The reduced parking time for each vehicle	5 min
Fuel consumption saving	87.5 L
Equivalent cost of time and fuel consumption savings	€2500
CO emissions reduction	16.71 kg
HC emissions reduction	2.111 kg
NOX emissions reduction	1.950 kg

Conclusion

To solve parking lot problems, automatic assignment mechanism of parking lot is proposed considering the individual demand of parking users’ based on the WiFi positioning technology. Conclusions can be given as follows:

1. Compared to traditional GPS positioning and mobile cellular network locating, WiFi positioning technology have some advantages in the indoor environment. The layout principles of AP devices in parking lot are provided based on WiFi location technology. AP hotspots in parking lot are laid at intervals of 15 m.

2. A questionnaire about individual demand of parking users was carried out. The results of the survey showed that more than 90% of the users hope parking space can be automatically assigned to them and route guidance can be provided when a parking space is hard to be found. They are willing to comply with the assignment results.

3. Some attribute decision factors such as the lane occupancy conditions, travel distance, walking distance, and the occupancy situation of parking space on both sides were selected, and the optimal parking lot assignment model was established. A large parking lot in Beijing was taken as an example to be optimized.

To evaluate the parking system with automatic assignment mechanism, the “obey willingness factor to the allocation result” is assumed to be 1.0, which indicated that drivers are willing to comply with the allocation result to avoid conflicts caused by drivers’ blindly searching. The influence of “obey willingness factor to allocation result,” which is below 1.0, will be studied in the future to improve the model with more flexibility and greater applicability.