# Research on Parking Service Optimization Based on Permit Reservation and Allocation

Authors: Duo Xu; Huijun Sun
Journal: Journal of Advanced Transportation
 (2022)

---

## Abstract

Parking facilities in central urban areas have limited supply, high utilization, and turnover rate, leading to the high parking cost. To draw the issues of parking uncertainty, high search time, and underutilization of parking lots, this study shows the application of permits in parking management. It first analyzes the characteristics and costs of “arrival priority” and “reservation priority” modes, and then, it proposes the parking permit reservation and allocation mode based on “service order optimization” and designs an “ant colony-genetic” algorithm to solve the optimal service order. The numerical example shows that the measures of quantity control and matching optimization are effective in parking management. The parking reservation mode of “service order optimization” has advantages in parking lot utilization rate, service demand quantity, and total parking cost.


---

## Body

## 1. Introduction

Parking has an important influence on the choice of vehicle travel mode and road traffic order. As the number of vehicles in cities continues to grow, parking problem becomes increasingly prominent. Although each vehicle travels only 1 hour a day on average, finding a parking space takes a lot of time and cost [1]. Studies by Axhausen et al. show that the time spent by vehicles searching for parking spaces accounts for about 30% to 50% of the total travel time [2, 3]; Vuchic reveals that the cost of vehicle parking accounts for about 70% cost of a single trip [4]. Many scholars have studied the parking search time by way of empirical research, which is generally between 3 minutes and 15 minutes (see references [5–10] for details).As pointed out by Inci, parking problems are “invisible” [11]. On the one hand, cruise vehicles searching for parking spaces are mixed with normal traffic flow and are difficult to identify. Some studies have tried to estimate this ratio, but have not reached a consistent conclusion [12–14]. On the other hand, some travelers adjust the departure time [15] and parking location [16] to avoid parking difficulties. Instead, the parking lot utilization rate is low, making managers underestimate the severity of the parking problem.The parking problem is mainly caused by the contradiction between supply and demand, so traffic demand management has been regarded as an effective measure to alleviate this problem. Parking charging (including static charging and dynamic charging) is the earliest management method applied in the parking field and receives much attention from scholars. We can refer to the research overview of Inci et al. [17, 18]. Generally speaking, charging has the advantages of effectively adjusting demand and internalizing some external costs into manager’s income. The disadvantages of charging are as follows: firstly, the adjustment accuracy is low and there is hysteresis, which makes managers retain some parking spaces to cope with fluctuations in demand and then achieve maximal system efficiency. For example, the SFpark project in San Francisco sets charging on the premise of keeping 15% of the parking spaces vacant [19]. Gu et al. believed that the optimal fee should make parking facility usage rate reach 85%–95% [20]. In addition, the charge itself does not contain information. Even if the parking supply can (exactly) meet the demand, travelers arriving later still need to spend certain time searching for vacant parking spaces. When there are few parking spaces, the search cost will increase rapidly [21–23].With the development of the Internet and communication technologies, managers have strengthened their control over parking behavior, and a parking management mode based on quantity control has appeared. Montgomery pioneered the application of quantitative control concepts (Crocker and Dales) for managing environmental pollution externalities into parking management as an alternative to price control [24–26]. Yang and Wang first proposed a tradable parking credit management model in which managers issue parking permits to travelers, and travelers can trade and use parking permits in light of actual needs [15]. Subsequently, many scholars have done research on permit management issues in parking [27–34]. The advantage of the parking permit mode is that it can split the direct connection between charging and demand into two independent parts, with price corresponding to application, and supply corresponding to allocation. The disparity between the application and the allocated amount only appears in the scheduled allocation stage of the permit. Therefore, no actual cost is incurred during travel. At the same time, the permit can contain parking space information, thus greatly reducing the parking search time for late arrivals.In addition, some scholars have studied the short-term parking space reservation allocation strategy for special situations (e.g., unpunctuality or uncertainty in travelers’ arrival/departure time, and time-limited opening spaces for shared parking) [35–39], trading mechanisms [40, 41], and optimization algorithms [42–49]. Through simulated experiments and empirical experiments, it is found that parking reservation and allocation can significantly reduce drivers’ search costs and emissions.Based on the existing research, this paper studies the problem of high parking costs caused by the contradiction between supply and demand and proposes an improved parking permit management mode to overcome the shortcomings of traditional charging mode and permit reservation mode in terms of parking uncertainty (go back and forth between parking lots), long search time, and underutilization of parking lots. It also looks forward to the application of the model in the management of shared parking resources (integrating and utilizing different types of park supplies).The remainder of this paper is organized as follows. The next section establishes assumptions and defines the symbols used. Section3 analyzes and compares the parking costs of the two modes of “arrival priority” and “reservation priority,” and finds the factors that restrict service capacity. Section 4 proposes the parking permit mode of “service order optimization” and designs the “ant colony-genetic” algorithm for solving the optimal service order. Section 5 analyzes the effects of various parking management modes through numerical examples. Section 6 provides conclusions and recommendations for future studies.


## 2. Assumptions

This study takes the parking behavior of a certain (nonunique) business district (CBD) in the city as the research object and establishes the following hypotheses based on the actual vehicle travel and parking in the city .A1. Road network and parking lot. In the linear road network model, the departure point of travelers is at one end of the road, and the business district is at the other end of the road. There are two types of parking lots around the commercial area, parking lot 1 with limited capacity at the destination, and parking lot 2 with no capacity limitation within walking distance acceptable to travelers around the destination. The parking lot opening time includes a limited number of time panes (defined as a unit time, such as 15 minutes). Figure1 depicts K parking lot, W panes in parking lot 1:Parking lot 1 at the destination in A1 is the main research object of this paper, its supply is limited; parking lot 2 around the destination is the second best choice when travelers cannot choose parking lot 1, which can be regarded as a generalized parking lot that may actually consist of multiple parking lots. For the establishment of parking lot 2, on the one hand, it reflects the satisfiability of parking needs; that is, travelers can generally complete parking by choosing a parking lot that is far away; on the other hand, when there is no vacant parking space in parking lot 1, travelers will go to and from two parking lots, which reflects travelers’ search process.A2. Parking management mode. This paper sets three parking lot management modes: “arrival priority,” “reservation priority,” and “service order optimization” modes. Where the “arrival priority” mode corresponds to general charging, the “reservation priority” and “service order optimization” modes correspond to the scheduled allocation of parking permits.The “arrival priority” mode represents the current charging management mode adopted by the city, and this paper sets it as the control group 1. The “reservation priority” mode is set as the control group 2 in this paper, and neither of the two control groups is set with specific optimization goals. The “service order optimization” mode is the experimental group of this paper, and the manager’s goal is to minimize the total cost of travelers.A3. Travelers and itinerary. There are differences in parking demand, which are represented by two variables, different arrival time and parking duration. Travelers prefer the nearest parking lot 1. Without guidance information, travelers will search for parking spaces in parking lot 1 one by one. If parking cannot be completed, they will go back and forth to parking lot 2, as shown in Figure2. With the presence of guidance information (parking permit), the traveler decides whether to go to the parking lot 1 according to whether the parking space in the parking lot 1 is successfully reserved.Travelers have no specific experiences regarding parking lots and other people’s travel plans. Therefore, without exact information guidance, travelers can only park according to the principle of minimum perceived cost, which is a blind behavior. It should be noted that even if the usage of parking lot 1 is posted on the surrounding roads in the form of variable information boards, etc., when travelers drive from parking lot 2 (or a location closer to the departure point) to parking lot 1, parking status of parking lot 1 may still change (travelers who are closer to the destination than the target traveler fills up the parking space, or some vehicles leave when travels drive to the parking lot 1), so the above guidance information still cannot be defined as “exact information.”A4. Parking cost. According to the traveler’s itinerary, two types of costs are set. One is the travel cost, including the cost of vehicle driving before reaching the parking lot and the cost of walking to the destination after parking. The other is the search cost, which appears in the process of searching for a parking space in the parking lot.All travelers experience the driving process from the departure point to the parking lot 2. For simplicity, the overlapping cost in this part is ignored. There are three types of travel costs based on whether the traveler directly parks in parking lot 1 or 2 and goes to and from parking lot 1 and 2. Parking lot 2 is a generalized parking lot, which may include multiple parking lots and multiple parking entrances. Travelers can easily find parking spaces. Therefore, it is assumed that the parking search cost only exists in parking lot 1. In addition, parking fees are internal costs (transferred from travelers to managers), so this paper will not consider them separately.Figure 1
Schematic diagram of the available period of lot 1.Figure 2
The parking process of travelers in moden.The symbols and parameters are defined in Table1.Table 1
Nomenclature.
NotationInterpretationWNumber of time panes opened in the parking lot every dayxMDistance between parking lot 1 and parking lot 2tiExpected arrival time (pane) of traveleriliParking duration (panes) of traveleriziParking reservation time of traveleriNdh,iArrival number at parking lot 1 between the arrival time interval of travelerh and iniOccupied spaces number in parking lot 1 when traveleri arrivesuiReserved panes number in parking lot 1 when traveleri reservesjModes, including “arrival priority,” “reservation priority,” and “service order optimization” and modes, including “arrival priority”-n, “reservation priority”-r, and “service order optimization”-r∗KThe total number of parking spaces in the parking lot 1 (k=1,2,...,K indicates the number of parking spaces)probjkiIn modej, the probability of a traveler i parking at the position k of parking lot 1probjiIn modej, the probability that any pane of parking lot 1 is occupied after the traveler i completes the parking reservationχi0-1 variable, in moder, whether the traveler i successfully finds parking space in the parking lot 1χk,wi0-1 variable, in moder∗, whether the traveler i gets the parking position k at pane w in the parking lot 1αThe value of timeλUnit search time without information guidanceε0<ε<1, the search time reduction factor under information guidancevcCar velocityvwWalking velocityCjtiIn modej, the travel cost of traveler iCjsiIn modej, the search cost of traveler iTCjThe total system cost of the modej


## 3. Parking Cost in “Arrival Priority” and “Reservation Priority” Modes

According to A3 and A4, the travel costCjti of the traveler i in the mode j is as follows:(1)Cjti=αxMvci∈lot1,j∈n,r,r∗,αxMvwi∈lot2,j∈r,r∗,αxM1vw+2vci∈lot1−lot2,j=n,where the mode n corresponds to situation one and situation three; that is, the traveler completes the parking in the parking lot 1 or turns back to the parking lot 2 after arriving at the parking lot 1. The permit modes r and r∗ correspond to the first two situations; that is, the traveler successfully or unsuccessfully reserves the permit for parking lot 1.Similarly, the traveleri’s search cost Cjsi in the mode j is as follows:(2)Cjsi=αkλi∈lot1,j=n,αKλi∈lot1−lot2,j=n,αεkλi∈lot1,j∈r,r∗,0i∈lot2,j∈r,r∗.Without information guidance, when traveleri searches until the k th parking space in parking lot 1 (1≤k≤K), the time it takes is kλ; if the traveler returns from parking lot 1 to parking lot 2, then he will search the entire parking lot 1, and the search time is Kλ. When parking space information is acquired, the search time is reduced by ε times.From equations (1) and (2), the total traveler cost in the mode j is as follows:(3)TCj=∑NCjti+Cjsi.


### 3.1. Parking Cost in “Arrival Priority” Mode

In moden, travelers arrive at the parking lot in the order of travel plans. According to the definition, ni is the number of parking spaces occupied when traveler i arrives at parking lot 1 (including those who have not parked but arrive before the traveler i), and Ndi−1,i is the number of vehicles leaving the parking lot within the arrival time interval of two adjacent travelers. When ni<K, travelers can complete parking in parking lot 1. ni can be expressed as follows:(4)ni=minK,ni−1+1−Ndi−1,ii>1,0i=1.Equation (4) has two meanings. One is that when the earliest traveler arrives at the parking lot, the number of parking spaces used in the parking lot is 0; the other is that when the i th traveler arrives at the parking lot 1, the number of parking spaces used is the number of parking spaces used by the i−1 traveler minus the number of vehicles leaving the parking lot within the arrival time interval of the i−1 and i th traveler. Where the maximum number of parking spaces used does not exceed K, the number of leaving vehicles does not exceed the number of vehicles already in the parking lot, Ndi−1,i≤ni−1.In case of large utilization rate and turnover rate of parking space in the parking lot 1, the parking spaces that have been used can be regarded as randomly distributed in the parking lot. Assume that used parking spaces have equal probability distribution in the parking lot, then for traveleri, the probability that any parking space is used can be expressed as follows:(5)probni=niK.When we search in order, the probabilitiesprobn1i and probnki of parking at the 1st position and the k th parking space are, respectively, as follows:(6)probn1i=1−probni=1−niK,(7)probnki=1−niKniKk−1.When the number of parking spaces used isni (ni<K), the traveler can definitely find a parking space from the first to ni+1 parking space (the worst case is that the previous ni parking space is occupied). The expected value ECnsi of search cost Cnsi can be expressed as follows:(8)ECnsi=∑k=1nikλ⋅probnkini<K,Kλni=K.WhenK value is large, equation (8) is approximately equal to(9)ECnsi=KλK−nini<KKλni=K.According to equation (1), the travel cost Cnti of traveler i in the mode n is as follows:(10)Cnti=αxMvci∈lot1,αxM1vw+2vci∈lot1−lot2.According to equations (9) and (10), the expected parking cost of travelers in the mode n is as follows:(11)ECni=KλK−ni+αxMvc,i∈lot1,Kλ+αxM1vw+2vc,i∈lot1−lot2.With the increase in parking demand, the utilization rate of parking space in the parking lot 1 will gradually increase. The parking cost curve can be plotted as shown in Figure3.Figure 3
Parking cost of parking lot 1 in varying utilization rate.Figure3 shows that with the increasing utilization rate of parking space in the parking lot 1, the search cost and parking cost of travelers also gradually increase; when the parking lot is close to full use state, the search cost and parking cost increase significantly. When parking lot 1 has no vacant parking space available, travelers return to parking lot 2, and the travel cost jumps, leading to a jump in parking costs.Since the parking demand is irregular, the system cannot reach an equilibrium state, and the leap-like changes in parking cost reflect the phenomenon in which vehicles cruise between parking lots in reality.The total system cost is the sum of the parking costs of all travelers, namely,(12)TCn=∑NECni.The expected parking cost of traveleri depends on the value ni, so the equation (12) can be expressed as follows:(13)TCn=∑Nfreqni⋅Cni,where freqni represents the frequency of ni occurrence and satisfies ∑Nfreqni=N.The parking space is used multiple times in a day. When the parking lot 1 is in a state of high utilization for a long time (e.g., the parking space utilization rate is between 0.9 and 1.0) and it is at a high turnover speed, the total parking cost in “arrival priority” mode will always be high. This situation corresponds to the fact that the parking lot has a large number of cruising vehicles inside and around it due to the prominent contradiction between supply and demand.


### 3.2. Parking Cost in “Reservation Priority” Mode

To deal with the problem of increased parking costs caused by high parking rates and high turnover rates, methods of increasing charges and reducing parking rates are proposed. For example, the SFpark project maintains the parking lot vacancy rate at about 15%. This method is equivalent to striving for lower system costs at the cost of partial parking resources.The parking permit mode can well solve this problem. In the permit reservation moder, the manager allocates parking permits containing time and location information according to demand, thereby solving the problem of parking uncertainty. If travelers successfully reserve a parking space in the parking lot 1, they will know exactly where the parking space is, so they can drive directly to the target parking space, without having to search the parking lot at a slower speed one by one; if they fail to reserve parking lot 1, they will go directly to the parking lot 2, without need to go to and from parking lot 1 and parking lot 2.In moder, the order of parking service demand is the predetermined order zi. According to the travel plan, travelers make reservations in parking lot 1 in the order from 1st to Kth parking space. If there is no vacant parking space, then choose parking lot 2.According to assumption A1,K parking spaces in parking lot 1 have a total of KW time-space units available for reservation at time period W. When traveler i makes reservations for parking lot 1, if ui time-space unit is occupied, ui can be expressed as follows:(14)ui=∑q|zq<ziχqlq,i,q∈N,where χq indicates whether the q th vehicle has completed the reservation in the parking lot 1, and q|zq<zi indicates the collection of travelers who reserve parking lot earlier than i.Assume that the parking demand is equally probabilistic within the range of time and space, the probability that each time and space unit of the parking lot is used can be expressed as follows:(15)probri=uiKW.For traveleri, he can park only when a parking space is vacant in consecutive li periods of time. Based on this, the probability probr1i and probrki that he finds parking at the first position and the k th position can be calculated, respectively, as follows:(16)probr1i=∏w=0li−11−W⋅probriW−w,probrki=probr1i⋅1−probr1ik−1.Then, the probability that the traveleri can complete the parking and the expected search cost are as follows:(17)∑Kprobrki=1−1−probr1iK,(18)ECrsi=∑k=1Kεkλ⋅probr1i⋅1−probr1ik−1.When theK value is large, the equation (18) approximately equals to(19)ECrsi=ελprobr1i,According to equation (1), the travel cost Crti of traveler i in the mode r can be expressed as follows:(20)Crti=αxMvci∈lot1,αxMvwi∈lot2.According to equations (19) and (20), the expected value of parking cost in the mode r can be expressed as follows:(21)ECri=∑Kprobrki⋅ECrsi+αxMvc+1−∑Kprobrki⋅αxMvw.The first term in equation (21) represents the traveler’s expected parking cost in parking lot 1, and the second term represents the traveler’s parking cost in parking lot 2.The total cost of the moder system is the sum of the parking costs of all travelers(22)TCr=∑NECri.


### 3.3. Comparison between “Arrival Priority” and “Reservation Priority” Modes

Sections3.1 and 3.2 analyze the parking lot utilization rate under the two parking service modes of “arrival priority” and “reservation priority,” the probability that travelers can complete parking in parking lot 1, and the cost of parking for travelers. This section compares the performance of the two modes around the above factors.


#### 3.3.1. Parking Service Rate of Parking Lot 1

According to equations (5) and (15), the probability that a single time pane of a parking space in parking lot 1 is vacant determines the expected value of the probability that a traveler stops there. Equations (5) and (15) are based on equations (4) and (14), respectively. In the mode n and mode r, the order of parking service demand is different, and the characteristics of the needs of the traveler group are different, so it is hard to compare parking probability of a specific traveler. Without loss of generality, suppose that the two modes have served i demand, and the demand is evenly distributed in the time dimension. The service capacity of the two modes can be judged by the probability of being served when the i+1 demand arrives.If the previousi demand occupies a total of ∑ilq (q∈i) panes in parking lot 1, then the average probability probji (probni=probri) that each pane is occupied is as follows:(23)probji=∑ilqKW.For the moden, the probability that the i+1 th traveler can complete parking in the first parking space of parking lot 1 is as follows:(24)probn1i+1=1−probni.Based on this, the probability of completing parking in parking lot 1 can be calculated as follows:(25)∑Kprobnki+1=1−probniK.For the moder, the traveler’s reservation is affected by two factors: whether the current parking space is vacant and whether there is no reservation during the future parking time. Then, the probability that the traveler completes the reservation in the first parking space of parking lot 1 is as follows:(26)probr1i+1=∏w=0li−11−W⋅probriW−w.Based on this, the probability of completing the parking reservation in parking lot 1 can be calculated as follows:(27)∑Kprobrki+1=1−1−∏w=0li−11−W⋅probriW−wK.Observe the right side of equations (25) and (27). From probni=probri, it can be easily proved that(28)∏w=0li−11−W⋅probriW−w≤1−probni.Whenli=1, that is, when the parking duration of all travelers is 1, the equal sign of equation (27) holds. When the probability that each pane of parking lot 1 is occupied is probri⟶0, the difference between the left and right sides of the Eq. is small, and vice versa.The above conclusions are easy to understand. The parking space of parking lot 1 in moden is only affected by whether they are vacant at the current time; in the mode r, travelers who actually depart late may also reserve parking permits early. Therefore, travelers need make sure that a certain parking space is available in time period ti,ti+li−1 to make successful reservation. When the parking lot is used to a certain extent, the probability of continuous vacancy is lower compared to the previous case.Let us take a simple example to illustrate the problem. Suppose the number of parking spaces in parking lot 1 isK=2, the opening hours W=5, the number of travelers N=4, and the travel plan ti=i and li=2.As shown in Figure4, if travelers arrive in chronological order, the number of demand that the parking lot can serve is 4. According to the reservation mode, there is a certain possibility (such as sequence 1243, 1423, 1432, 4123, 4132, and 4312) that only 3 service needs can be met.Figure 4
The impact of service order on the use of lot 1.


#### 3.3.2. Parking Cost

The cost of parking for travelers includes search cost and travel cost. The search cost of the two modes can be calculated by equations (8) and (18), respectively.It is easy to prove that when some travelers choose parking lot 2, the search cost of this part of travelers in the moder is 0, and the search cost in the mode n is Kλ, so the mode r is more efficient.When all travelers can be served by parking lot 1, the expected search cost of thei th traveler in the two modes is as follows:(29)ECjsi=∑k=1Kkλ⋅probj1i⋅1−probj1ik−1j=n,∑k=1Kεkλ⋅probj1i⋅1−probj1ik−1j=r.According to equations (24) and (26), there is probr1i≤probn1i. Equation (29) shows that if we ignore that parking space information improves the search efficiency of travelers in the mode r (i.e., ε<1), mode r has lower efficiency than mode n.Considering the two situations comprehensively, it can be inferred that when the utilization rate and turnover rate of parking lot 1 are low (most travelers can complete parking in lot 1), the moden may be more effective; when the utilization rate and turnover rate of parking lot 1 are high (some travelers need to complete parking in lot 2), the efficiency of mode r is higher.In the same way, for the travel cost, the expected travel cost of thei th traveler in the two modes is as follows:(30)ECjti=Ρ⋅αxMvc+1−Ρ⋅2αxMvc+αxMvwj=n,Ρ⋅αxMvc+1−Ρ⋅αxMvwj=r,where P=∑Kprobjki.According to equations (25) and (27), in equation (30), ∑Kprobrki≤∑Kprobnki, it means that the traveler has higher probability of parking in parking lot 1 in the mode n, but if he parks in parking lot 2, the travel cost will be higher compared to mode r. Based on this, it can be inferred that when parking space in parking lot 1 can meet all needs, the two modes have the same travel cost; as the demand further increases, it is possible that all travelers park in parking lot 1 in the charging mode, but in the parking permit mode, some travelers need to choose parking lot 2, and the charging mode is more efficient at this time. When there is large demand and both modes have many travelers who choose parking lot 2, the parking permit mode is more efficient.In summary, when the parking lot faces a large supply and demand contradiction, the “reservation priority”-based parking permit mode is more efficient, and when the parking lot supply is relatively sufficient, the “arrival priority”-based parking charging mode is more efficient. This is because during the parking permit reservation process, travelers still need to ensure that the parking spaces remain vacant for a period of time. This factor affects the service capacity of the parking lot.


## 3.1. Parking Cost in “Arrival Priority” Mode

In moden, travelers arrive at the parking lot in the order of travel plans. According to the definition, ni is the number of parking spaces occupied when traveler i arrives at parking lot 1 (including those who have not parked but arrive before the traveler i), and Ndi−1,i is the number of vehicles leaving the parking lot within the arrival time interval of two adjacent travelers. When ni<K, travelers can complete parking in parking lot 1. ni can be expressed as follows:(4)ni=minK,ni−1+1−Ndi−1,ii>1,0i=1.Equation (4) has two meanings. One is that when the earliest traveler arrives at the parking lot, the number of parking spaces used in the parking lot is 0; the other is that when the i th traveler arrives at the parking lot 1, the number of parking spaces used is the number of parking spaces used by the i−1 traveler minus the number of vehicles leaving the parking lot within the arrival time interval of the i−1 and i th traveler. Where the maximum number of parking spaces used does not exceed K, the number of leaving vehicles does not exceed the number of vehicles already in the parking lot, Ndi−1,i≤ni−1.In case of large utilization rate and turnover rate of parking space in the parking lot 1, the parking spaces that have been used can be regarded as randomly distributed in the parking lot. Assume that used parking spaces have equal probability distribution in the parking lot, then for traveleri, the probability that any parking space is used can be expressed as follows:(5)probni=niK.When we search in order, the probabilitiesprobn1i and probnki of parking at the 1st position and the k th parking space are, respectively, as follows:(6)probn1i=1−probni=1−niK,(7)probnki=1−niKniKk−1.When the number of parking spaces used isni (ni<K), the traveler can definitely find a parking space from the first to ni+1 parking space (the worst case is that the previous ni parking space is occupied). The expected value ECnsi of search cost Cnsi can be expressed as follows:(8)ECnsi=∑k=1nikλ⋅probnkini<K,Kλni=K.WhenK value is large, equation (8) is approximately equal to(9)ECnsi=KλK−nini<KKλni=K.According to equation (1), the travel cost Cnti of traveler i in the mode n is as follows:(10)Cnti=αxMvci∈lot1,αxM1vw+2vci∈lot1−lot2.According to equations (9) and (10), the expected parking cost of travelers in the mode n is as follows:(11)ECni=KλK−ni+αxMvc,i∈lot1,Kλ+αxM1vw+2vc,i∈lot1−lot2.With the increase in parking demand, the utilization rate of parking space in the parking lot 1 will gradually increase. The parking cost curve can be plotted as shown in Figure3.Figure 3
Parking cost of parking lot 1 in varying utilization rate.Figure3 shows that with the increasing utilization rate of parking space in the parking lot 1, the search cost and parking cost of travelers also gradually increase; when the parking lot is close to full use state, the search cost and parking cost increase significantly. When parking lot 1 has no vacant parking space available, travelers return to parking lot 2, and the travel cost jumps, leading to a jump in parking costs.Since the parking demand is irregular, the system cannot reach an equilibrium state, and the leap-like changes in parking cost reflect the phenomenon in which vehicles cruise between parking lots in reality.The total system cost is the sum of the parking costs of all travelers, namely,(12)TCn=∑NECni.The expected parking cost of traveleri depends on the value ni, so the equation (12) can be expressed as follows:(13)TCn=∑Nfreqni⋅Cni,where freqni represents the frequency of ni occurrence and satisfies ∑Nfreqni=N.The parking space is used multiple times in a day. When the parking lot 1 is in a state of high utilization for a long time (e.g., the parking space utilization rate is between 0.9 and 1.0) and it is at a high turnover speed, the total parking cost in “arrival priority” mode will always be high. This situation corresponds to the fact that the parking lot has a large number of cruising vehicles inside and around it due to the prominent contradiction between supply and demand.


## 3.2. Parking Cost in “Reservation Priority” Mode

To deal with the problem of increased parking costs caused by high parking rates and high turnover rates, methods of increasing charges and reducing parking rates are proposed. For example, the SFpark project maintains the parking lot vacancy rate at about 15%. This method is equivalent to striving for lower system costs at the cost of partial parking resources.The parking permit mode can well solve this problem. In the permit reservation moder, the manager allocates parking permits containing time and location information according to demand, thereby solving the problem of parking uncertainty. If travelers successfully reserve a parking space in the parking lot 1, they will know exactly where the parking space is, so they can drive directly to the target parking space, without having to search the parking lot at a slower speed one by one; if they fail to reserve parking lot 1, they will go directly to the parking lot 2, without need to go to and from parking lot 1 and parking lot 2.In moder, the order of parking service demand is the predetermined order zi. According to the travel plan, travelers make reservations in parking lot 1 in the order from 1st to Kth parking space. If there is no vacant parking space, then choose parking lot 2.According to assumption A1,K parking spaces in parking lot 1 have a total of KW time-space units available for reservation at time period W. When traveler i makes reservations for parking lot 1, if ui time-space unit is occupied, ui can be expressed as follows:(14)ui=∑q|zq<ziχqlq,i,q∈N,where χq indicates whether the q th vehicle has completed the reservation in the parking lot 1, and q|zq<zi indicates the collection of travelers who reserve parking lot earlier than i.Assume that the parking demand is equally probabilistic within the range of time and space, the probability that each time and space unit of the parking lot is used can be expressed as follows:(15)probri=uiKW.For traveleri, he can park only when a parking space is vacant in consecutive li periods of time. Based on this, the probability probr1i and probrki that he finds parking at the first position and the k th position can be calculated, respectively, as follows:(16)probr1i=∏w=0li−11−W⋅probriW−w,probrki=probr1i⋅1−probr1ik−1.Then, the probability that the traveleri can complete the parking and the expected search cost are as follows:(17)∑Kprobrki=1−1−probr1iK,(18)ECrsi=∑k=1Kεkλ⋅probr1i⋅1−probr1ik−1.When theK value is large, the equation (18) approximately equals to(19)ECrsi=ελprobr1i,According to equation (1), the travel cost Crti of traveler i in the mode r can be expressed as follows:(20)Crti=αxMvci∈lot1,αxMvwi∈lot2.According to equations (19) and (20), the expected value of parking cost in the mode r can be expressed as follows:(21)ECri=∑Kprobrki⋅ECrsi+αxMvc+1−∑Kprobrki⋅αxMvw.The first term in equation (21) represents the traveler’s expected parking cost in parking lot 1, and the second term represents the traveler’s parking cost in parking lot 2.The total cost of the moder system is the sum of the parking costs of all travelers(22)TCr=∑NECri.


## 3.3. Comparison between “Arrival Priority” and “Reservation Priority” Modes

Sections3.1 and 3.2 analyze the parking lot utilization rate under the two parking service modes of “arrival priority” and “reservation priority,” the probability that travelers can complete parking in parking lot 1, and the cost of parking for travelers. This section compares the performance of the two modes around the above factors.


### 3.3.1. Parking Service Rate of Parking Lot 1

According to equations (5) and (15), the probability that a single time pane of a parking space in parking lot 1 is vacant determines the expected value of the probability that a traveler stops there. Equations (5) and (15) are based on equations (4) and (14), respectively. In the mode n and mode r, the order of parking service demand is different, and the characteristics of the needs of the traveler group are different, so it is hard to compare parking probability of a specific traveler. Without loss of generality, suppose that the two modes have served i demand, and the demand is evenly distributed in the time dimension. The service capacity of the two modes can be judged by the probability of being served when the i+1 demand arrives.If the previousi demand occupies a total of ∑ilq (q∈i) panes in parking lot 1, then the average probability probji (probni=probri) that each pane is occupied is as follows:(23)probji=∑ilqKW.For the moden, the probability that the i+1 th traveler can complete parking in the first parking space of parking lot 1 is as follows:(24)probn1i+1=1−probni.Based on this, the probability of completing parking in parking lot 1 can be calculated as follows:(25)∑Kprobnki+1=1−probniK.For the moder, the traveler’s reservation is affected by two factors: whether the current parking space is vacant and whether there is no reservation during the future parking time. Then, the probability that the traveler completes the reservation in the first parking space of parking lot 1 is as follows:(26)probr1i+1=∏w=0li−11−W⋅probriW−w.Based on this, the probability of completing the parking reservation in parking lot 1 can be calculated as follows:(27)∑Kprobrki+1=1−1−∏w=0li−11−W⋅probriW−wK.Observe the right side of equations (25) and (27). From probni=probri, it can be easily proved that(28)∏w=0li−11−W⋅probriW−w≤1−probni.Whenli=1, that is, when the parking duration of all travelers is 1, the equal sign of equation (27) holds. When the probability that each pane of parking lot 1 is occupied is probri⟶0, the difference between the left and right sides of the Eq. is small, and vice versa.The above conclusions are easy to understand. The parking space of parking lot 1 in moden is only affected by whether they are vacant at the current time; in the mode r, travelers who actually depart late may also reserve parking permits early. Therefore, travelers need make sure that a certain parking space is available in time period ti,ti+li−1 to make successful reservation. When the parking lot is used to a certain extent, the probability of continuous vacancy is lower compared to the previous case.Let us take a simple example to illustrate the problem. Suppose the number of parking spaces in parking lot 1 isK=2, the opening hours W=5, the number of travelers N=4, and the travel plan ti=i and li=2.As shown in Figure4, if travelers arrive in chronological order, the number of demand that the parking lot can serve is 4. According to the reservation mode, there is a certain possibility (such as sequence 1243, 1423, 1432, 4123, 4132, and 4312) that only 3 service needs can be met.Figure 4
The impact of service order on the use of lot 1.


### 3.3.2. Parking Cost

The cost of parking for travelers includes search cost and travel cost. The search cost of the two modes can be calculated by equations (8) and (18), respectively.It is easy to prove that when some travelers choose parking lot 2, the search cost of this part of travelers in the moder is 0, and the search cost in the mode n is Kλ, so the mode r is more efficient.When all travelers can be served by parking lot 1, the expected search cost of thei th traveler in the two modes is as follows:(29)ECjsi=∑k=1Kkλ⋅probj1i⋅1−probj1ik−1j=n,∑k=1Kεkλ⋅probj1i⋅1−probj1ik−1j=r.According to equations (24) and (26), there is probr1i≤probn1i. Equation (29) shows that if we ignore that parking space information improves the search efficiency of travelers in the mode r (i.e., ε<1), mode r has lower efficiency than mode n.Considering the two situations comprehensively, it can be inferred that when the utilization rate and turnover rate of parking lot 1 are low (most travelers can complete parking in lot 1), the moden may be more effective; when the utilization rate and turnover rate of parking lot 1 are high (some travelers need to complete parking in lot 2), the efficiency of mode r is higher.In the same way, for the travel cost, the expected travel cost of thei th traveler in the two modes is as follows:(30)ECjti=Ρ⋅αxMvc+1−Ρ⋅2αxMvc+αxMvwj=n,Ρ⋅αxMvc+1−Ρ⋅αxMvwj=r,where P=∑Kprobjki.According to equations (25) and (27), in equation (30), ∑Kprobrki≤∑Kprobnki, it means that the traveler has higher probability of parking in parking lot 1 in the mode n, but if he parks in parking lot 2, the travel cost will be higher compared to mode r. Based on this, it can be inferred that when parking space in parking lot 1 can meet all needs, the two modes have the same travel cost; as the demand further increases, it is possible that all travelers park in parking lot 1 in the charging mode, but in the parking permit mode, some travelers need to choose parking lot 2, and the charging mode is more efficient at this time. When there is large demand and both modes have many travelers who choose parking lot 2, the parking permit mode is more efficient.In summary, when the parking lot faces a large supply and demand contradiction, the “reservation priority”-based parking permit mode is more efficient, and when the parking lot supply is relatively sufficient, the “arrival priority”-based parking charging mode is more efficient. This is because during the parking permit reservation process, travelers still need to ensure that the parking spaces remain vacant for a period of time. This factor affects the service capacity of the parking lot.


## 3.3.1. Parking Service Rate of Parking Lot 1

According to equations (5) and (15), the probability that a single time pane of a parking space in parking lot 1 is vacant determines the expected value of the probability that a traveler stops there. Equations (5) and (15) are based on equations (4) and (14), respectively. In the mode n and mode r, the order of parking service demand is different, and the characteristics of the needs of the traveler group are different, so it is hard to compare parking probability of a specific traveler. Without loss of generality, suppose that the two modes have served i demand, and the demand is evenly distributed in the time dimension. The service capacity of the two modes can be judged by the probability of being served when the i+1 demand arrives.If the previousi demand occupies a total of ∑ilq (q∈i) panes in parking lot 1, then the average probability probji (probni=probri) that each pane is occupied is as follows:(23)probji=∑ilqKW.For the moden, the probability that the i+1 th traveler can complete parking in the first parking space of parking lot 1 is as follows:(24)probn1i+1=1−probni.Based on this, the probability of completing parking in parking lot 1 can be calculated as follows:(25)∑Kprobnki+1=1−probniK.For the moder, the traveler’s reservation is affected by two factors: whether the current parking space is vacant and whether there is no reservation during the future parking time. Then, the probability that the traveler completes the reservation in the first parking space of parking lot 1 is as follows:(26)probr1i+1=∏w=0li−11−W⋅probriW−w.Based on this, the probability of completing the parking reservation in parking lot 1 can be calculated as follows:(27)∑Kprobrki+1=1−1−∏w=0li−11−W⋅probriW−wK.Observe the right side of equations (25) and (27). From probni=probri, it can be easily proved that(28)∏w=0li−11−W⋅probriW−w≤1−probni.Whenli=1, that is, when the parking duration of all travelers is 1, the equal sign of equation (27) holds. When the probability that each pane of parking lot 1 is occupied is probri⟶0, the difference between the left and right sides of the Eq. is small, and vice versa.The above conclusions are easy to understand. The parking space of parking lot 1 in moden is only affected by whether they are vacant at the current time; in the mode r, travelers who actually depart late may also reserve parking permits early. Therefore, travelers need make sure that a certain parking space is available in time period ti,ti+li−1 to make successful reservation. When the parking lot is used to a certain extent, the probability of continuous vacancy is lower compared to the previous case.Let us take a simple example to illustrate the problem. Suppose the number of parking spaces in parking lot 1 isK=2, the opening hours W=5, the number of travelers N=4, and the travel plan ti=i and li=2.As shown in Figure4, if travelers arrive in chronological order, the number of demand that the parking lot can serve is 4. According to the reservation mode, there is a certain possibility (such as sequence 1243, 1423, 1432, 4123, 4132, and 4312) that only 3 service needs can be met.Figure 4
The impact of service order on the use of lot 1.


## 3.3.2. Parking Cost

The cost of parking for travelers includes search cost and travel cost. The search cost of the two modes can be calculated by equations (8) and (18), respectively.It is easy to prove that when some travelers choose parking lot 2, the search cost of this part of travelers in the moder is 0, and the search cost in the mode n is Kλ, so the mode r is more efficient.When all travelers can be served by parking lot 1, the expected search cost of thei th traveler in the two modes is as follows:(29)ECjsi=∑k=1Kkλ⋅probj1i⋅1−probj1ik−1j=n,∑k=1Kεkλ⋅probj1i⋅1−probj1ik−1j=r.According to equations (24) and (26), there is probr1i≤probn1i. Equation (29) shows that if we ignore that parking space information improves the search efficiency of travelers in the mode r (i.e., ε<1), mode r has lower efficiency than mode n.Considering the two situations comprehensively, it can be inferred that when the utilization rate and turnover rate of parking lot 1 are low (most travelers can complete parking in lot 1), the moden may be more effective; when the utilization rate and turnover rate of parking lot 1 are high (some travelers need to complete parking in lot 2), the efficiency of mode r is higher.In the same way, for the travel cost, the expected travel cost of thei th traveler in the two modes is as follows:(30)ECjti=Ρ⋅αxMvc+1−Ρ⋅2αxMvc+αxMvwj=n,Ρ⋅αxMvc+1−Ρ⋅αxMvwj=r,where P=∑Kprobjki.According to equations (25) and (27), in equation (30), ∑Kprobrki≤∑Kprobnki, it means that the traveler has higher probability of parking in parking lot 1 in the mode n, but if he parks in parking lot 2, the travel cost will be higher compared to mode r. Based on this, it can be inferred that when parking space in parking lot 1 can meet all needs, the two modes have the same travel cost; as the demand further increases, it is possible that all travelers park in parking lot 1 in the charging mode, but in the parking permit mode, some travelers need to choose parking lot 2, and the charging mode is more efficient at this time. When there is large demand and both modes have many travelers who choose parking lot 2, the parking permit mode is more efficient.In summary, when the parking lot faces a large supply and demand contradiction, the “reservation priority”-based parking permit mode is more efficient, and when the parking lot supply is relatively sufficient, the “arrival priority”-based parking charging mode is more efficient. This is because during the parking permit reservation process, travelers still need to ensure that the parking spaces remain vacant for a period of time. This factor affects the service capacity of the parking lot.


## 4. Optimal Allocation of Parking Space Permits

The parking demand of travelers is aggregated to the total demand of the parking lot. In the case that the total demand for parking is determined, the management’s different service orders (such as in the order of arrival or in the order of reservation) will result in completely different parking lot use forms and parking costs. Through the previous analysis, it can be seen that the service order will greatly affect the system efficiency. If the service order of parking permits can be optimized, the advantages of the two modes can be taken into account. In view of this, this section studies the parking permit allocation mode to improve the service order. In this mode, the manager first collects parking demand in a predetermined form and decides the allocation way of parking permits according to the optimal goal of the system.


### 4.1. Optimal Allocation Model for Parking Permits

In the parking permit moder∗ that optimizes the order of services, managers need to formulate strategies based on the needs of travelers and the supply of parking lots. Parking permit allocation strategy χk,wi meets(31)∑Nχk,wi≤1,k∈K;w∈W,(32)∑K∑Wχk,wi≤1,k∈K;w∈W,(33)χk,wi⋅W−w−li≥0,k∈K;w∈W,(34)χk,wi⋅∑δ=1liχk,w+δq=0,i≠q;k∈K;w∈W.Equation (31) indicates that any parking space is allocated at most once in a period of time, equation (32) indicates that any travel demand is allocated with at most one parking permit, and equation (33) indicates that the traveler’s parking time needs to be in the opening hours of the parking lot. Equation (34) means that during the traveler’s parking period, the parking space cannot be allocated to other travelers.The conservation condition for the allocation of parking permits is as follows:(35)χi=∑k=1K∑w=1Wχk,wi.For alli∈N, k∈K, and w∈W, the costs of travelers in the mode r∗ can be expressed as follows:(36)Cr∗si=ελ∑k=1K∑w=1Wk⋅χk,wi,(37)Cr∗ti=αxMvc⋅χi+αxMvw⋅1−χi.Equation (36) indicates that if the traveler parks in the parking lot 1, the search cost depends on the location of the parking space; otherwise, no search cost will be incurred. Equation (37) indicates that the travel cost of a traveler who parks in parking lot 1 is the travel cost over the distance xM. Otherwise, it is the walking cost.The total cost of parking for travelers can be the sum of search and travel costs:(38)TCr∗=∑i=1NCr∗i.The goal of the system is to minimize the total parking costTCr∗. Since whether the traveler allocates a permit for parking lot 1 is determined by χk,wi, according to equation (38), the objective function of the system is as follows:(39)minTCr∗=∑i=1NCr∗χk,w−1i.The constraint conditions are shown in equation (31)–(34).


### 4.2. Optimization Allocation Algorithm Based on “Genetic-Ant Colony”

According to the conclusion of Section3, the higher the utilization rate of the parking lot, the more difficult it is to meet the parking demand of current travelers, and the greater the possibility that χk,wi is 0. That is, whether the parking demand is met is affected by the order. The compactness of the manager’s service toward demand determines the utilization rate of parking lot 1, as well as the total cost of parking. The problem described in equation (39) can be transformed into solving the problem of a set of optimal service order SEQ∗.The sorting combination ofN travel demand is limited, so there is a minimum system cost. The optimization of the service order is similar to the traveling salesman problem (TSP). Considering that ant colony algorithm and genetic algorithm have better performance in local and global search, respectively, this paper uses the algorithm combining ant colony and genetics to find the optimal allocation order.In the ant colony algorithm, we suppose that the service order corresponds to the path of ant colony, a single demand corresponds to a node on the path, and the total cost of parking based on different sorting of demands is the path cost of the ant colony. The ants of the current generation generate a set of path information after traversal to obtain the optimal path set of the current generation and update the pheromone concentration of the node transfer based on this. The genetic algorithm is nested in the ant colony algorithm, thus preventing the ant colony algorithm from falling into the local optimum. The path information corresponds to the gene sequence, and the nodes on the path correspond to single genes. Each time the ant colony algorithm forms a set of path information, the path information is mutated and optimized, and the optimal path is retained. The algorithm flow can be expressed as follows:Step 1 is initialization. Set the number and initial position of the ant colony, pheromone and related update parameters, genetic variation parameters, the maximum number of iterations, etc.Step 2: generate ant colony traversal path (demand distribution order). The ant determines the initial position and transfer direction according to the pheromone, and continuously searches for the unreached position to traverse all the demands.Step 3: determine both parents of the ant colony (calculate the cost of the distribution plan). According to the cost of each ant (allocation plan), determine the current optimal plan as parent I, and all plans in this generation as parent II.Step 4: ant colony cross-mutation and optimization (find the optimal allocation plan). The genes of both parents cross and mutate. Part of the gene sequence of parent I ants is extracted and combined with each ant gene of parent II, and the offspring ant colony equivalent to the parent II in number is generated by mutation. The ant colonies of the parent-child generations are optimized to update the pheromone.Step 5: repeat steps 1 to 4 until the maximum number of iterations is reached.The search behavior of ants is based on pheromone, and the pheromone update Eq. adopts the ant cycle model. Suppose the number of ants isM, and denote the pheromone matrix with τN×N. τi,q represents the pheromone concentration for arranging the travel demand q after the travel demand i is arranged, then(40)τi,qt+1=1−ρτi,qt+Δτi,q,i≠q,(41)Δτi,q=∑KΔτi,qk,(42)Δτi,qk=Qlm.In equations (40)–(42), t is the number of stages, ρ is the evaporation rate of pheromone, Q is the fixed parameter of pheromone update, and lm is the total cost of each parking demand after the m th ant traverses.The choice of them th ant’s search behavior at each step is determined by the transition probability pijk.(43)piqm=τi,qγ∑Sτi,sγ,S⊂allowedm,0else.In equation (43), allowedm is the set of locations currently searchable by the ant m, and γ is the parameter. Since the distance between adjacent points is the same, the influence of ant visibility in the traditional model is ignored.After the ant colony completes the node traversal, it reproduces and optimizes once. Suppose the optimal solutionGt until the stage t is the parent side; the solution FMt (M in number) searched by the ant colony in stage t is the other parent. The genes of both parents can be expressed as follows:Parent I:(44)Gt=g1t,g2t,…git,…,gNt,i∈N.Parent II:(45)FMt=f11tf12t…f1it…f1Ntf21tf22t…f2it…f2Nt…⋅⋅⋅…⋅⋅⋅……fm1tfm2t…fmit…f1Nt………………fM1tfM2t…fMit…fMNt,m∈M;i∈N.Both parental generations produceM offspring OMt through the following cross-mutation process. The crossover part is randomly generated from the parental generation Gt. M arrays X,Y are randomly generated as the starting point and ending point of the crossover, which are expressed as follows:(46)X=x1,x2,…,xM,Y=y1,y2,…,yM,∀xm≤N,∀ym≤N,∀xm≤ym,m∈M.The gene sequence in the parental generationGt of the m cross-selection in stage t can be expressed as gxmt,gxm+1t,…,gymt.The gene sequence selected by the parentGt is combined with the parent FMt. Find and delete the same elements as sequence Gmt=gxmt,gxm+1t,…,gymt in the sequence Fmt=fm1t,fm2t,…,fmNt, and the relative positions of the remaining elements remain unchanged. Insert the sequence Gmt into the xm position of the original Fmt to form the original offspring. Figure 5 shows the gene sequences of both parents.Figure 5
The gene sequence of both parents in the ant colony algorithm.Assume that the gene sequence of the parental generationG contains only two adjacent elements gxmt and gymt, which are, respectively, equal to the element fm2t and fmN−2t in the parental generation F. After crossover, the gene sequence composition of the offspring O is shown in Figure 6. The genes of the offspring O are composed of genes G and F. Where the relative positions of other elements in F do not change, the gene sequence in G is inserted into position xm to ym.Figure 6
The offspring gene sequence in the ant colony algorithm.The offspring will mutate with a lower probabilityη. Let the mutation behavior be the inversion of the access point of the gene sequence; that is, the gene sequence Γmt=gymt,gym−1t,…,gxmt inserted at the xm position. The original offspring forms the final offspring after the mutation process. Figure 7 shows the gene sequence after mutation (if any) in the offspring of Figure 6. Compared with the original offspring, the order of genes at positions xm and ym is reversed.Figure 7
The offspring gene sequence containing the variant gene.


#### 4.2.1. Optimization

After the genetic algorithm cross-mutation in staget, the parent F and the offspring O have a total of 2M solutions. In order to update the pheromone efficiently, the ant colony conducts internal optimization, selects the first M solutions according to the pros and cons of the solution, and updates the pheromone according to the cost. Compare the optimal solution at this stage with that before the stage t and select the best to generate a new parent Gt+1.


## 4.1. Optimal Allocation Model for Parking Permits

In the parking permit moder∗ that optimizes the order of services, managers need to formulate strategies based on the needs of travelers and the supply of parking lots. Parking permit allocation strategy χk,wi meets(31)∑Nχk,wi≤1,k∈K;w∈W,(32)∑K∑Wχk,wi≤1,k∈K;w∈W,(33)χk,wi⋅W−w−li≥0,k∈K;w∈W,(34)χk,wi⋅∑δ=1liχk,w+δq=0,i≠q;k∈K;w∈W.Equation (31) indicates that any parking space is allocated at most once in a period of time, equation (32) indicates that any travel demand is allocated with at most one parking permit, and equation (33) indicates that the traveler’s parking time needs to be in the opening hours of the parking lot. Equation (34) means that during the traveler’s parking period, the parking space cannot be allocated to other travelers.The conservation condition for the allocation of parking permits is as follows:(35)χi=∑k=1K∑w=1Wχk,wi.For alli∈N, k∈K, and w∈W, the costs of travelers in the mode r∗ can be expressed as follows:(36)Cr∗si=ελ∑k=1K∑w=1Wk⋅χk,wi,(37)Cr∗ti=αxMvc⋅χi+αxMvw⋅1−χi.Equation (36) indicates that if the traveler parks in the parking lot 1, the search cost depends on the location of the parking space; otherwise, no search cost will be incurred. Equation (37) indicates that the travel cost of a traveler who parks in parking lot 1 is the travel cost over the distance xM. Otherwise, it is the walking cost.The total cost of parking for travelers can be the sum of search and travel costs:(38)TCr∗=∑i=1NCr∗i.The goal of the system is to minimize the total parking costTCr∗. Since whether the traveler allocates a permit for parking lot 1 is determined by χk,wi, according to equation (38), the objective function of the system is as follows:(39)minTCr∗=∑i=1NCr∗χk,w−1i.The constraint conditions are shown in equation (31)–(34).


## 4.2. Optimization Allocation Algorithm Based on “Genetic-Ant Colony”

According to the conclusion of Section3, the higher the utilization rate of the parking lot, the more difficult it is to meet the parking demand of current travelers, and the greater the possibility that χk,wi is 0. That is, whether the parking demand is met is affected by the order. The compactness of the manager’s service toward demand determines the utilization rate of parking lot 1, as well as the total cost of parking. The problem described in equation (39) can be transformed into solving the problem of a set of optimal service order SEQ∗.The sorting combination ofN travel demand is limited, so there is a minimum system cost. The optimization of the service order is similar to the traveling salesman problem (TSP). Considering that ant colony algorithm and genetic algorithm have better performance in local and global search, respectively, this paper uses the algorithm combining ant colony and genetics to find the optimal allocation order.In the ant colony algorithm, we suppose that the service order corresponds to the path of ant colony, a single demand corresponds to a node on the path, and the total cost of parking based on different sorting of demands is the path cost of the ant colony. The ants of the current generation generate a set of path information after traversal to obtain the optimal path set of the current generation and update the pheromone concentration of the node transfer based on this. The genetic algorithm is nested in the ant colony algorithm, thus preventing the ant colony algorithm from falling into the local optimum. The path information corresponds to the gene sequence, and the nodes on the path correspond to single genes. Each time the ant colony algorithm forms a set of path information, the path information is mutated and optimized, and the optimal path is retained. The algorithm flow can be expressed as follows:Step 1 is initialization. Set the number and initial position of the ant colony, pheromone and related update parameters, genetic variation parameters, the maximum number of iterations, etc.Step 2: generate ant colony traversal path (demand distribution order). The ant determines the initial position and transfer direction according to the pheromone, and continuously searches for the unreached position to traverse all the demands.Step 3: determine both parents of the ant colony (calculate the cost of the distribution plan). According to the cost of each ant (allocation plan), determine the current optimal plan as parent I, and all plans in this generation as parent II.Step 4: ant colony cross-mutation and optimization (find the optimal allocation plan). The genes of both parents cross and mutate. Part of the gene sequence of parent I ants is extracted and combined with each ant gene of parent II, and the offspring ant colony equivalent to the parent II in number is generated by mutation. The ant colonies of the parent-child generations are optimized to update the pheromone.Step 5: repeat steps 1 to 4 until the maximum number of iterations is reached.The search behavior of ants is based on pheromone, and the pheromone update Eq. adopts the ant cycle model. Suppose the number of ants isM, and denote the pheromone matrix with τN×N. τi,q represents the pheromone concentration for arranging the travel demand q after the travel demand i is arranged, then(40)τi,qt+1=1−ρτi,qt+Δτi,q,i≠q,(41)Δτi,q=∑KΔτi,qk,(42)Δτi,qk=Qlm.In equations (40)–(42), t is the number of stages, ρ is the evaporation rate of pheromone, Q is the fixed parameter of pheromone update, and lm is the total cost of each parking demand after the m th ant traverses.The choice of them th ant’s search behavior at each step is determined by the transition probability pijk.(43)piqm=τi,qγ∑Sτi,sγ,S⊂allowedm,0else.In equation (43), allowedm is the set of locations currently searchable by the ant m, and γ is the parameter. Since the distance between adjacent points is the same, the influence of ant visibility in the traditional model is ignored.After the ant colony completes the node traversal, it reproduces and optimizes once. Suppose the optimal solutionGt until the stage t is the parent side; the solution FMt (M in number) searched by the ant colony in stage t is the other parent. The genes of both parents can be expressed as follows:Parent I:(44)Gt=g1t,g2t,…git,…,gNt,i∈N.Parent II:(45)FMt=f11tf12t…f1it…f1Ntf21tf22t…f2it…f2Nt…⋅⋅⋅…⋅⋅⋅……fm1tfm2t…fmit…f1Nt………………fM1tfM2t…fMit…fMNt,m∈M;i∈N.Both parental generations produceM offspring OMt through the following cross-mutation process. The crossover part is randomly generated from the parental generation Gt. M arrays X,Y are randomly generated as the starting point and ending point of the crossover, which are expressed as follows:(46)X=x1,x2,…,xM,Y=y1,y2,…,yM,∀xm≤N,∀ym≤N,∀xm≤ym,m∈M.The gene sequence in the parental generationGt of the m cross-selection in stage t can be expressed as gxmt,gxm+1t,…,gymt.The gene sequence selected by the parentGt is combined with the parent FMt. Find and delete the same elements as sequence Gmt=gxmt,gxm+1t,…,gymt in the sequence Fmt=fm1t,fm2t,…,fmNt, and the relative positions of the remaining elements remain unchanged. Insert the sequence Gmt into the xm position of the original Fmt to form the original offspring. Figure 5 shows the gene sequences of both parents.Figure 5
The gene sequence of both parents in the ant colony algorithm.Assume that the gene sequence of the parental generationG contains only two adjacent elements gxmt and gymt, which are, respectively, equal to the element fm2t and fmN−2t in the parental generation F. After crossover, the gene sequence composition of the offspring O is shown in Figure 6. The genes of the offspring O are composed of genes G and F. Where the relative positions of other elements in F do not change, the gene sequence in G is inserted into position xm to ym.Figure 6
The offspring gene sequence in the ant colony algorithm.The offspring will mutate with a lower probabilityη. Let the mutation behavior be the inversion of the access point of the gene sequence; that is, the gene sequence Γmt=gymt,gym−1t,…,gxmt inserted at the xm position. The original offspring forms the final offspring after the mutation process. Figure 7 shows the gene sequence after mutation (if any) in the offspring of Figure 6. Compared with the original offspring, the order of genes at positions xm and ym is reversed.Figure 7
The offspring gene sequence containing the variant gene.


### 4.2.1. Optimization

After the genetic algorithm cross-mutation in staget, the parent F and the offspring O have a total of 2M solutions. In order to update the pheromone efficiently, the ant colony conducts internal optimization, selects the first M solutions according to the pros and cons of the solution, and updates the pheromone according to the cost. Compare the optimal solution at this stage with that before the stage t and select the best to generate a new parent Gt+1.


## 4.2.1. Optimization

After the genetic algorithm cross-mutation in staget, the parent F and the offspring O have a total of 2M solutions. In order to update the pheromone efficiently, the ant colony conducts internal optimization, selects the first M solutions according to the pros and cons of the solution, and updates the pheromone according to the cost. Compare the optimal solution at this stage with that before the stage t and select the best to generate a new parent Gt+1.


## 5. Numerical Examples

To compare the effects of the three parking management modes of “arrival priority,” “reservation priority,” and “service order optimization,” this section designs a numerical example to simulate the performance of three modes in parking costs, parking lot utilization rate, and the number of vehicles in parking lot 1 under different parking supply-demand level.The opening time of the parking lot includes the number of time panesW=12. Travel demand N=50, and traveler’s arrival time and parking duration are shown in Table 2. The number of parking spaces takes K=1∼25 separately. Considering the possibility of multiple people in one vehicle, we suppose the walking cost is 90 per vehicle and the vehicle travel cost is 10 per vehicle (α=1/9). In the parking lot, the search cost of a unit parking space without a parking target is λ=0.5, and the search cost of unit parking space with a parking target is 0.2 (ε=0.4).Table 2
Travelers’ parking demand under the “reservation priority” mode.
Arrival orderArrival timeDurationArrival orderArrival timeDurationArrival orderArrival timeDuration13518343534293193336813832023373341122162389152222933944693233540227332410341228152593424292426103439310632744443211322843459212121294446841312303347131474313448341533325449101161033383506317333432The parameters of the ant colony and genetic combination algorithm are set as follows: the number of antsM=20, the maximum number of iterations NC=1000, the importance of pheromone γ=3, the pheromone evaporation factor ρ=0.2, the pheromone update parameter Q=150, and the mutation rate of the offspring ants η=0.01.In Table2, travel demand is sorted in a reserved order, which is applicable to modes r and r∗. In the mode n, the arrival sequence of travelers is determined according to the sequence of the expected arrival time, as shown in Table 3. The parking demand contained in Tables 2 and 3 is equal, but the sorting order is different.Table 3
Parking demand of travelers under the “arrival priority” mode.
Arrival orderArrival timeDurationArrival orderArrival timeDurationArrival orderArrival timeDuration11518333563212193536743132033378342221343883524223339816232391408472224934193822259242939322634439310342744449311322843451031235294446103133330444710314323142481011533325449112163333635012117343462Figures8 and 9, respectively, show the number of travel demands under different arrival time and different parking durations. Suppose that there are two peaks in parking demand, in time period 3 and time period 9, respectively, while the demand in the remaining period is small; in terms of parking duration, parking demands with medium duration are the most, and demand for longer or shorter travel decreases in turn.Figure 8
Parking demand distribution.Figure 9
Parking duration distribution.According to the previous assumptions on parking behavior and cost, under differentK values (representing different supply-demand level), the number of vehicles parked in the parking lot 1 and the utilization rate of the parking lot in the three modes, namely, the number of parked vehicles ∗ parking duration/(number of parking spaces ∗ parking lot opening hours) are shown in Figures 10 and 11.Figure 10
Parking number in lot 1 of the three modes.Figure 11
Utilization rate of lot 1 of the three modes.By observing Figures10 and 11, we draw the following conclusions:(1)
The order of service determines the number of parked vehicles in the parking lot and the parking lot utilization rate. In this example, the minimum number of parking spaces required for all travelers to complete parking in parking lot 1 is 23. When the number of parking spaces is less than 23, in comparison with moden and mode r, the parking lot utilization rate and the parking number in mode n are higher than mode r in most cases. This phenomenon is consistent with the discussion in Section 3. The mode n has better parking service order than the mode r in overall. When the number of parking spaces exceeds 23, there is no difference between the two modes, and 50 travelers can complete parking in parking lot 1.(2)
Moder∗ is superior to the mode n and mode r in the two indicators of parking number and the utilization rate of parking lot 1. Since the mode r∗ optimizes the service order, more parking needs can be met under the same number of parking spaces. When the parking lot contains only 1 parking space, the parking lot utilization rate in all the three modes is 1, but the mode r∗ can meet 6 demands, while the modes n and r can only meet 4 and 5 demands, respectively. When the number of parking spaces is between 1 and 23, the two indicators of the mode r∗ are also higher in varying degrees.Figure12 reflects the per capita parking cost under the three modes.Figure 12
Per capita parking cost of travelers in the three modes.According to the change trend of the graph, the parking lot availability can be divided into 4 stages based on the supply status, which are low (less than 4 parking spaces), relatively low (5 to 13 parking spaces), relatively high (14–21 parking spaces), and high (more than 22 parking spaces). By observing Figure12, the following conclusions can be drawn:(1)
In different parking space numbers, the per capita cost of the parking reservation management mode (r, r∗) is lower than the per capita cost of the “arrival priority” mode (n) to varying degrees. It reflects that the parking reservation mode has a good effect in lowering search cost and parking uncertainty.(2)
As the number of parking spaces increases from small to large, more travelers can park their vehicles in parking lot 1. The uncertainty of travelers moving between two parking lots in parking is reduced, and the search cost has weakened impact on the total cost, which is reflected in the continuous reduction of the per capita cost difference in the graph between the “arrival priority” mode and the “reservation priority” mode.(3)
As the number of parking spaces increases, the impact of the cost affected by the order of demand on the total cost shows a trend of “strengthening first, then weakening.” When the number of parking spaces is “small,” the parking lot is saturated in any order of demand, and the difference in the order of demand creates little effect on parking costs. For its reflection, although the order of demand is different between moder∗ and mode r, the difference from per capita cost in mode n is relatively fixed. When the number of parking spaces changes to “relatively small,” the order of demand gradually affects the cost (in this example, mode n has superior parking order than the mode r, so the difference in per capita cost between the two tends to shrink at this stage. In practice, this situation is much likely to occur). When the number of parking spaces increases to “relatively high” and most needs can be met in the parking lot, the influence of the order of demand shows a weakening trend, and there is savings in search cost under the parking permit management mode. Finally, when the number of parking spaces increases to “high,” the cost difference between three modes returns to a relatively fixed state; that is, the search cost of the two permit modes in the parking lot 1 is reduced.(4)
When the number of parking spaces is “large,” further increase in the number of parking spaces will no longer reduce the total cost. It can be seen from the graph that after the number of parking spaces exceeds 23, the total cost will no longer decrease.(5)
There is little difference between the moder∗ and the mode r when the number of parking spaces is “small” and “high,” and the difference is obvious when the number of parking spaces is “relatively small” and “relatively high,” indicating that the two parking permit modes have similar advantages in reducing search costs, and the mode r∗ has a more obvious advantage in reducing the travel cost generated by the service order.Figures13 and 14 reflect the usage status of the parking lot within a day (the number of time interval is 12) under the management modes r and r∗ when the number of parking spaces is sufficient (the number of parking spaces is 23).Figure 13
Usage of parking lot 1 in moder.Figure 14
Usage of parking lot in moder∗.When the number of parking spaces is 23, all travelers in moder and mode r∗ will complete their parking in parking lot 1. The total travel cost of the mode r is 590.2, and the total parking cost of the mode r∗ is 584.2, indicating that the mode r∗ is still superior to mode r if the parking demand can be fully guaranteed. It can be seen from the figure that the parking space with a smaller number in Figure 14 (indicating that the search cost in parking lot 1 is smaller) meets more parking needs in a day than the parking space with a smaller number in Figure 13. This conclusion shows that mode r∗ can achieve the goal of reducing parking costs by increasing the utilization rate and turnover rate of convenient parking spaces in the parking lot.


## 6. Conclusions and Prospects

Insufficient parking supply in central urban areas makes travelers spend more time searching for parking spaces or face the risk of being unable to park in the target parking lot. The existing research mostly considered the universal parking permit and reservation mode. The former has deficiencies in the internal search cost and the utilization rate of the parking lot, while the latter has deficiencies in the parking service number. Focusing on the above factors, this paper analyzes parking cruising in (search cost) and between (additional travel cost) of the parking lots, and proposes an improved permit mode to further optimize the parking service.This paper defines three parking management modes. The first is “arrival priority” mode, and the parking lot at the destination provides service according to the traveler’s arrival time. If the parking lot is fully occupied when the traveler arrives at the destination, then he returns to a farther parking lot (parking lot 2). The second is “reservation priority” mode, and travelers reserve parking permits in advance and complete parking at designated parking spaces. If one fails to obtain parking permit through application, they choose other parking lots. The third is “service order optimization” service mode. Managers selectively allocate parking permits by combining parking needs under the goal of system optimization. After theoretical derivation and analysis of calculation examples, the following conclusions are drawn:(1)
The advantage of the “arrival priority” mode is that the system service order is closer to the optimal service order without the intervention of the manager; the disadvantage is that the traveler cannot access the information about other travelers’ plan and parking lot usage information, thus unable to improve parking efficiency by adjusting his behavior. Travelers may take a long time to search or fail to find a vacant parking space in the target parking lot.(2)
The advantage of the “reservation priority” mode is that travelers can identify parking spaces in advance, search fast, and avoid round-trips between parking lots. The disadvantage is that the system’s service order is inferior, which affects the service capacity of the parking lot. In some cases, travelers may experience a higher total cost compared to the “arrival priority” mode.(3)
Solving the service order problem of the permit mode is the key to further reducing the system cost. This problem is equivalent to the optimal allocation of permits. This paper applies the combination of ant colony and genetic algorithms with strong local and global optimization capabilities to find a satisfactory solution to the optimal service order, and verifies that the parking permit mode of “service order optimization” has better results in terms of the number of served parking demand, parking lot utilization rate at the destination, and per capita parking cost of travelers.With the development of information technology, the permit mode can be applied to parking management more conveniently and economically. On the one hand, it will effectively improve the utilization efficiency of existing parking resources because of its advantages in precisely matching supply and demand and providing guidance information for parking lots. On the other hand, the permits mode optimizes the service order of demands and sets different priorities for requirements. It can be applied to the shared management of private parking spaces (prioritizing the parking needs of space owners), thus integrating more types of parking supply. Future research can continue to focus on the dynamics of parking management, evaluate real-time parking demand based on historical data, and set service priorities to achieve optimal matching between parking supply and demand.



---

*Source: 8364988-2022-06-09.xml*