# CARSP: A Smart Parking System Based on Doubly Periodic Rolling Horizon Allocation Approach

Authors: Shangbin Ning; Zhenyu Han; Yang Yang; Zhenzhou Yuan; Xianyu Wu
Journal: Journal of Advanced Transportation
 (2022)

---

## Abstract

Blind search for available parking space is accountable for most traffic congestion, accident, and pollution in cities, which severely impact people’s life. Parking management based on an online smart parking system is practical to alleviate parking problems in which parking allocation is the core. However, existing researches are weak at satisfying allocation effect and speed simultaneously when solving large-scale dynamic parking allocation problem. To address this problem, we firstly construct an online “Collection-Allocation-Response” smart parking system (CARSP) to offer parking services to users and rent parking spaces from owners so as to obtain revenue for system managers. We then propose a novel Doubly Periodic Rolling Horizon allocation approach (DPRH) that circularly conduct allocation within a short period and reallocation within a long period. We formulate a narrow allocation model (without reallocation) and broad allocation model (with reallocation), both of which are binary integer programming models with the objective of maximizing system integrated benefit. We design seven performance metrics to evaluate the overall allocation effect and speed of CARSP based on DPRH. According to the three-day district-level instance in Beijing, CARSP based on DPRH performs excellently in balancing allocation effect and speed. This study is meaningful for constructing and optimizing an online smart parking system.


---

## Body

## 1. Introduction

With the swift development in urbanization and the great growth in living standards, the conflict between the increasing parking demands and scarce parking resources is becoming severer [1]. Besides parking resource shortage, inefficient parking resource usage also leads to parking difficulties, especially the increasing amounts of the blind search for available parking. Constrained by the limited land space in the urban area, it is difficult to solve the parking problem solely by constructing more parking resources. Therefore, how to efficiently utilize the limited parking resources has become a significant issue.In practice, more and more commercial companies worldwide have built online smart parking systems with the progress in Internet and communication technology, such as Airparking (China), Pavemint (the United States), and Nokisaki Parking (Japan). Applications of the above smart parking systems indicate that appropriate dynamic allocation approaches are the key to effectively maximizing system integrated benefit and maintaining allocation speed.Most online smart parking systems adopt First-Book-First-Serve (FBFS), and some studies proposed event-driven allocation approaches based on FBFS. In FBFS, each unallocated demand has a unique allocation priority, and each allocation process uses all unallocated resources to match one unallocated demand at demand submission time. Obviously, FBFS has an extremely high allocation speed since each demand is allocated immediately. However, FBFS sacrifices the allocation effect since each demand is allocated independently and myopically without any overall planning.As the research scale expands, researchers recognize that a large number of demands will be submitted to the system concurrently, while FBFS will result in unnecessary waiting of users. To improve the allocation effect, researchers proposed time-driven allocation approaches based on Rolling Horizon (RH). Based on Rolling Horizon allocation approaches, parking system collects demands in each allocation interval and allocates them simultaneously at the end time point of the interval. Demands participating in each allocation have the same priority. Naturally, unallocated demands could collectively participate in each allocation time point to achieve a better allocation effect. The unallocated demands refer to both newly submitted and previously submitted but unallocated demands.On this basis, some researchers noticed that users have different demand submission preferences: some prefer submitting demands a long time in advance before the trip, while some prefer submitting demands a short time in advance during the trip. Since the parking demands and resources are submitted to the system dynamically as time rolls on, the system managers can reallocate the allocated but unoccupied demands and meanwhile allocate the unallocated demands at each allocation time point to improve the resource utilization so as to improve the system's integrated benefit. The allocated but unoccupied demands and unallocated demands are collectively regarded as unoccupied demands.The allocation is called narrow allocation (NA for short) when only unallocated demands and resources participate, while the allocation is called broad allocation (BA for short) when unoccupied demands and resources participate. In other words, NA is allocation, while BA is the combination of allocation and reallocation. BA is practical and able to optimize the allocation effect as long as the system promises that these allocated but unoccupied demands can be successfully reallocated in each BA. Therefore, a rolling horizon allocation approach conducting NA at each allocation time point is Rolling Horizon Narrow Allocation (RHN), and a rolling horizon allocation approach conducting BA at each allocation time point is Rolling Horizon Broad Allocation (RHB).Under the same condition, i.e., the same overall time horizon, allocation period, demands and resources, RHN and RHB have different allocation effects and allocation speeds. In each allocation, the scales of demands and resources in RHN are smaller than that in RHB. Thus, RHN leads to higher allocation speed, while RHB leads to a better allocation effect. Especially, the larger the research scale is, the longer the allocation period is, and the closer the parking peak is, the larger the demand and service scale difference is, hence leading to the greater allocation effect gap and allocation speed gap between RHN and RHB. In this way, both RHN and RHB have unique drawbacks.In this paper, we firstly present an online smart parking system named CARSP to imply demands and resources collection, allocation, and response in the dynamic parking environment. CARSP not only fully considers the heterogeneity of demands and resources but also achieves accurate allocation to parking spaces rather than parking facilities, which are different from most existing smart parking systems.To mitigate the drawbacks of FBFS, RHN, and RHB, we creatively propose the Doubly Periodic Rolling Horizon allocation approach that circularly conduct NA within a short period and BA within a long period. DPRH is a brand new attempt at a dynamic allocation approach since it combines the superiorities of RHN and RHB, i.e., optimizing allocation effect and guaranteeing allocation speed. NA and BA models are formulated to optimize the integrated benefit for both system managers and CPLEX solvers are applied to solve the model at each allocation time point to obtain the optimal solution.The rest of this study is structured as follows. Section2 reviews the relevant studies. In Section 3, the structure and reaction scheme of “Collection-Allocation-Response” smart parking system are presented. In Section 4, the novel Doubly Periodic Rolling Horizon allocation approach is described. Meanwhile, the narrow and broad allocation models are formulated. In Section 5, seven performance metrics are designed to evaluate the allocation effect and speed. Meanwhile, a three-day district-level instance in Beijing, China, is studied. Section 6 gives the conclusions.


## 2. Literature Review

In existing studies on dynamic parking allocation problems, some focused on proposing event-driven allocation approaches. Raichura and Padhariya [2] proposed a smart parking allocation system containing a static allocation process and a dynamic allocation process. The dynamic allocation process was event-driven, which meant only when a user arrived at the allocated parking facility earlier would the user be reallocated to a more suitable parking facility. Nugraha and Tanamas [3] proposed a dynamic allocation subsystem based on an event-driven approach to reallocate FBFS results when trigger events happen. To maximize the user’s comfort level and the owner’s revenue simultaneously, Hassija et al. [4] proposed an event-driven parking space allocation framework based on the Virtual Voting and Adaptive Pricing Algorithm.To obtain better allocation effects, some studies focused on proposing time-driven allocation approaches to allocate parking demands and parking services group-by-group at each allocation time point, in which RHN, RHB, and static allocation models are improved.


### 2.1. Developments on Rolling Horizon Narrow Allocation

In the studies on time-driven allocation approaches based on RH, some focused on Narrow Allocation and proposed a rolling horizon narrow allocation approach.Zou et al. [5] firstly formulated a static allocation model from the perspective of society. Afterward, a dynamic model with the objective of maximizing social welfare was formulated and solved at each decision time interval as time rolled on. Both static and dynamic models were improved with a payment scheme to align users’ selfish intents with the system managers’ intents. Lei and Ouyang [6] regarded the problem as a Stackelberg leader-follower game and formulated a multiperiod bilevel model. The upper level decided the dynamic parking price of each parking facility and aimed at maximizing system profits, while the lower level decided the dynamic allocation and aimed at minimizing users’ disutility. An approximate dynamic programming approach was proposed to solve the model at each decision time point. He et al. [7] proposed an RHN to solve the dynamic parking allocation problem. A binary integer programming model with the objective of minimizing users’ costs was formulated. At each decision time point, the static model was solved by ILOG CPLEX. Yan et al. [8] focused on the dynamic parking allocation problem under uncertain demand and supply. Based on RHN, a mixed-integer programming model with the objective of minimizing users’ costs was formulated and solved by an iterative two-stage heuristic algorithm.


### 2.2. Developments on Rolling Horizon Broad Allocation

In the studies on time-driven allocation approaches based on RH, some focused on Broad Allocation and proposed a rolling horizon broad allocation approach (RHB for short).Geng and Cassandras [9] and Geng and Cassandras [10] firstly defined users’ costs function as the weighted sum of the total monetary costs and walking distance between the parking space and actual destination. Then mixed-integer linear programming models with the objective of minimizing users’ costs were formulated. Afterward, the RHB was proposed to allocate users including unallocated users and allocated users at each decision time point. However, users who were away from their destination were kept in a waiting queue and forbidden to be allocated, which not only increased users’ waiting costs but also failed to respond timely to users on providing parking guarantees. Based on the above studies, Kotb et al. [11] combined dynamic and static parking space allocation. A mixed-integer programming model aiming at minimizing users’ costs was formulated, in which users’ costs function was similar to the above studies. Under RHB, users in the dynamic reservation would participate in BA at each decision time point until they reached destination zones, while users in static reservation would not participate in subsequent allocation once they were successfully allocated. Mladenović et al. [12] proposed a four-layer RH framework to tackle the real-time updates of parking demands and parking spaces. During each time interval, users that had not arrived at their parking will be reallocated. A binary integer programming model aiming to minimize users’ costs was formulated. A heuristic algorithm and an exact algorithm were implied to solve the allocation model at each decision time point. Zhao et al. [13] researched the large-scale parking allocation problem in a dynamic parking environment of mixed automated and human-driven vehicles. A mixed-integer programming model aiming at minimizing users’ costs was formulated and solved by Monte Carlo Tree Search at each decision time point.


### 2.3. Improvements in Static Allocation Models

Studies focused on improving static allocation models are from the perspectives of system managers, users, and society.From the perspective of system managers, the objective of allocation models was generally maximizing system profits. Xu et al. [14] researched the private parking space sharing problem with the market design theory and extended the parking space allocation mechanism with money flow. Static allocation mechanisms named TTCD and PC-TTCC for lessor-like agents and lessee-like agents, respectively, were proposed. Yang et al. [15] supposed the system received parking supply and demand before a certain time and formulated a binary integer programming model aiming at maximizing system profits. User costs containing walking time cost and rejection cost were also considered and transferred into penalties for the system managers in the objective function. Han et al. [16] focused on the sharing of residential parking spaces and the improvements in parking resource utilization. A binary integer programming model with the objective of maximizing system profits was formulated. Ning et al. [17] focused on the private shared parking spaces allocation and formulated a binary integer programming model aiming at maximizing system profits, in which costs for failing allocating demands were also considered in the objective function as the penalty for the system managers. Jiang and Fan [18] focused on the users’ parking unpunctually and formulated a binary stochastic linear programming model with the objective of maximizing system profits. The stochastic programming model was then transformed into an expectation model by formulating the parking probability function of users and owners.From the perspective of users, the objective of allocation models was generally minimizing user costs. When constructing user cost functions, traveling time for parking, walking distance or walking time from parking facilities to destinations, and parking price were major considerations. Arellano-Verdejo and Alba [19] focused on the available parking space allocation in a city according to users’ preferences. The user costs function was formulated by combining the driving distance with the preference deviation distance. The driving distance was the distance between users’ current positions and the allocated parking spaces, and the preference deviation distance was the distance between the allocated parking spaces and the parking spaces desired by users. Meanwhile, an evolutionary algorithm based on Steady-State Evolutionary Algorithm was designed to solve the problem. To solve the problem brought by unpunctuality, Li et al. [20] formulated a shared parking allocation optimization model considering user's default, which possibilities were measured by credit value. The objective was to maximize the shared parking rate for all users. The problem was transformed into a vertex coloring problem and solved by an improved ant colony algorithm.From the perspective of society, the objective of allocation models was generally maximizing shared parking resource utilization. Shao et al. [21] formulated an allocation model to embrace private residential parking space sharing between residents and public users. The objective of the model was to maximize resource utilization under given demand and supply time windows and preset parking prices.Some researchers considered all three perspectives, and therefore, formulated allocation models with multiple objectives. Jiang et al. [22] constructed a two-stage method to allocate private parking spaces. The first stage screened the available parking spaces according to demand walking distance and parking price. The second stage allocated spaces to demands by a formulated multiobjective allocation model aiming to maximize users’ satisfaction, private idle parking space owners’ satisfaction, and the system profits. The model was solved by an improved nondominated sorting genetic algorithm II (INSGA II).Table1 shows the summary of the studies on rolling horizon allocation approaches in smart parking systems, in which this study is included.Table 1
Summary of the studies on rolling horizon allocation approach in the online smart parking system.
StudyParticipantsAllocation approachCase studyScale (total demands-total spaces)Time horizonAllocation periodZou et al. [5]U-SRHN200-10020 periodsNMLei and ouyang [6]U-SRHNNM-295360 min30 minHe et al. [7]U-SRHN1500-10001080 min3 minYan et al. [8]U-S-ORHN300-200720 min10 minGeng and cassandras [9]U-SRHBNM-30300 min10/15/20/25/30 sGeng and cassandras [10]U-SRHBNM-26113000 min1 minKotb et al. [11]U-SRHBNM-112720 minNMMladenović et al. [12]U-SRHB1000-4801440 min1 minZhao et al. [13]U-SRHB6944-NM1667 min10 sThis studyU-S-ODPRH31494-18004320 min0.5/1/5/10/15 minNote. U: users; S: system managers; O: owners; RHN: rolling horizon narrow allocation approach; RHB: rolling horizon broad allocation approach; DPRH: doubly periodic rolling horizon allocation approach; NM: not mentioned.Apparently, existing studies on rolling horizon allocation approaches were either RHN or RHB. Few had proposed a rolling horizon allocation approach that integrated the superiorities of RHN and RHB.


## 2.1. Developments on Rolling Horizon Narrow Allocation

In the studies on time-driven allocation approaches based on RH, some focused on Narrow Allocation and proposed a rolling horizon narrow allocation approach.Zou et al. [5] firstly formulated a static allocation model from the perspective of society. Afterward, a dynamic model with the objective of maximizing social welfare was formulated and solved at each decision time interval as time rolled on. Both static and dynamic models were improved with a payment scheme to align users’ selfish intents with the system managers’ intents. Lei and Ouyang [6] regarded the problem as a Stackelberg leader-follower game and formulated a multiperiod bilevel model. The upper level decided the dynamic parking price of each parking facility and aimed at maximizing system profits, while the lower level decided the dynamic allocation and aimed at minimizing users’ disutility. An approximate dynamic programming approach was proposed to solve the model at each decision time point. He et al. [7] proposed an RHN to solve the dynamic parking allocation problem. A binary integer programming model with the objective of minimizing users’ costs was formulated. At each decision time point, the static model was solved by ILOG CPLEX. Yan et al. [8] focused on the dynamic parking allocation problem under uncertain demand and supply. Based on RHN, a mixed-integer programming model with the objective of minimizing users’ costs was formulated and solved by an iterative two-stage heuristic algorithm.


## 2.2. Developments on Rolling Horizon Broad Allocation

In the studies on time-driven allocation approaches based on RH, some focused on Broad Allocation and proposed a rolling horizon broad allocation approach (RHB for short).Geng and Cassandras [9] and Geng and Cassandras [10] firstly defined users’ costs function as the weighted sum of the total monetary costs and walking distance between the parking space and actual destination. Then mixed-integer linear programming models with the objective of minimizing users’ costs were formulated. Afterward, the RHB was proposed to allocate users including unallocated users and allocated users at each decision time point. However, users who were away from their destination were kept in a waiting queue and forbidden to be allocated, which not only increased users’ waiting costs but also failed to respond timely to users on providing parking guarantees. Based on the above studies, Kotb et al. [11] combined dynamic and static parking space allocation. A mixed-integer programming model aiming at minimizing users’ costs was formulated, in which users’ costs function was similar to the above studies. Under RHB, users in the dynamic reservation would participate in BA at each decision time point until they reached destination zones, while users in static reservation would not participate in subsequent allocation once they were successfully allocated. Mladenović et al. [12] proposed a four-layer RH framework to tackle the real-time updates of parking demands and parking spaces. During each time interval, users that had not arrived at their parking will be reallocated. A binary integer programming model aiming to minimize users’ costs was formulated. A heuristic algorithm and an exact algorithm were implied to solve the allocation model at each decision time point. Zhao et al. [13] researched the large-scale parking allocation problem in a dynamic parking environment of mixed automated and human-driven vehicles. A mixed-integer programming model aiming at minimizing users’ costs was formulated and solved by Monte Carlo Tree Search at each decision time point.


## 2.3. Improvements in Static Allocation Models

Studies focused on improving static allocation models are from the perspectives of system managers, users, and society.From the perspective of system managers, the objective of allocation models was generally maximizing system profits. Xu et al. [14] researched the private parking space sharing problem with the market design theory and extended the parking space allocation mechanism with money flow. Static allocation mechanisms named TTCD and PC-TTCC for lessor-like agents and lessee-like agents, respectively, were proposed. Yang et al. [15] supposed the system received parking supply and demand before a certain time and formulated a binary integer programming model aiming at maximizing system profits. User costs containing walking time cost and rejection cost were also considered and transferred into penalties for the system managers in the objective function. Han et al. [16] focused on the sharing of residential parking spaces and the improvements in parking resource utilization. A binary integer programming model with the objective of maximizing system profits was formulated. Ning et al. [17] focused on the private shared parking spaces allocation and formulated a binary integer programming model aiming at maximizing system profits, in which costs for failing allocating demands were also considered in the objective function as the penalty for the system managers. Jiang and Fan [18] focused on the users’ parking unpunctually and formulated a binary stochastic linear programming model with the objective of maximizing system profits. The stochastic programming model was then transformed into an expectation model by formulating the parking probability function of users and owners.From the perspective of users, the objective of allocation models was generally minimizing user costs. When constructing user cost functions, traveling time for parking, walking distance or walking time from parking facilities to destinations, and parking price were major considerations. Arellano-Verdejo and Alba [19] focused on the available parking space allocation in a city according to users’ preferences. The user costs function was formulated by combining the driving distance with the preference deviation distance. The driving distance was the distance between users’ current positions and the allocated parking spaces, and the preference deviation distance was the distance between the allocated parking spaces and the parking spaces desired by users. Meanwhile, an evolutionary algorithm based on Steady-State Evolutionary Algorithm was designed to solve the problem. To solve the problem brought by unpunctuality, Li et al. [20] formulated a shared parking allocation optimization model considering user's default, which possibilities were measured by credit value. The objective was to maximize the shared parking rate for all users. The problem was transformed into a vertex coloring problem and solved by an improved ant colony algorithm.From the perspective of society, the objective of allocation models was generally maximizing shared parking resource utilization. Shao et al. [21] formulated an allocation model to embrace private residential parking space sharing between residents and public users. The objective of the model was to maximize resource utilization under given demand and supply time windows and preset parking prices.Some researchers considered all three perspectives, and therefore, formulated allocation models with multiple objectives. Jiang et al. [22] constructed a two-stage method to allocate private parking spaces. The first stage screened the available parking spaces according to demand walking distance and parking price. The second stage allocated spaces to demands by a formulated multiobjective allocation model aiming to maximize users’ satisfaction, private idle parking space owners’ satisfaction, and the system profits. The model was solved by an improved nondominated sorting genetic algorithm II (INSGA II).Table1 shows the summary of the studies on rolling horizon allocation approaches in smart parking systems, in which this study is included.Table 1
Summary of the studies on rolling horizon allocation approach in the online smart parking system.
StudyParticipantsAllocation approachCase studyScale (total demands-total spaces)Time horizonAllocation periodZou et al. [5]U-SRHN200-10020 periodsNMLei and ouyang [6]U-SRHNNM-295360 min30 minHe et al. [7]U-SRHN1500-10001080 min3 minYan et al. [8]U-S-ORHN300-200720 min10 minGeng and cassandras [9]U-SRHBNM-30300 min10/15/20/25/30 sGeng and cassandras [10]U-SRHBNM-26113000 min1 minKotb et al. [11]U-SRHBNM-112720 minNMMladenović et al. [12]U-SRHB1000-4801440 min1 minZhao et al. [13]U-SRHB6944-NM1667 min10 sThis studyU-S-ODPRH31494-18004320 min0.5/1/5/10/15 minNote. U: users; S: system managers; O: owners; RHN: rolling horizon narrow allocation approach; RHB: rolling horizon broad allocation approach; DPRH: doubly periodic rolling horizon allocation approach; NM: not mentioned.Apparently, existing studies on rolling horizon allocation approaches were either RHN or RHB. Few had proposed a rolling horizon allocation approach that integrated the superiorities of RHN and RHB.


## 3. “Collection-Allocation-Response” Smart Parking System

In the dynamic parking environment, “Collection-Allocation-Response” smart parking system (CARSP for short) collects enough demand and service data at one time, allocates demands and services without unnecessary interaction processes, and responds to users and owners with necessary notifications. Under this consideration, CARSP is composed of a collection center (CC for short), allocation center (AC for short), and response center (RC for short). CC and RC are responsible for data transmission through human-machine interaction in the front end, while AC is accountable for data storing, allocating, and updating in the back end. The framework of CARSP is shown in Figure1. All notations of this paper are summarized in Table 2.Figure 1
Framework of CARSP.Table 2
Notations of this paper.
SetDescriptionSt1,2,…,TThe overall time horizonStATA1,TA2,…,TAThe set of allocation time pointsStBTB1,TB2,…,TBThe subset of BA time pointsStNTN1,TN2,…,TNThe subset of NA time pointsSi1,2,…,IThe set of total parking demandsSj1,2,…,JThe set of total parking servicesSf1,2,…,FThe set of parking facilitiesSiUtThe unallocated parking demand set at time pointtSiUNtThe newly submitted parking demand set at time pointtSiUPtThe previously submitted (but unallocated) parking demand set at time pointtSiAtThe allocated (but not occupied) parking demand set at time pointtSiARtThe arriving parking demand set at time pointtSiARNtThe allocated but not arriving parking demand set at time pointtSiAPtThe approaching parking demand set at time pointtSiAPNtThe allocated but not approaching parking demand set at time pointtSiOtThe occupied (but not terminated) parking demand set at time pointtSiTtThe terminated parking demand set at time pointtSiFtThe failed parking demand set at time pointtSiNtThe NA parking demand set at time pointtSiBtThe BA parking demand set at time pointtSiBtThe unallocated parking service set at time pointtSjAtThe allocated (but not occupied) parking service set at time pointtSjARtThe arriving parking service set at time pointtSjARNtThe allocated but not arriving parking service set at time pointtSjAPtThe approaching parking service set at time pointtSjAPNtThe allocated but not approaching parking service set at time pointtSjOtThe occupied (but not terminated) parking service set at time pointtSjTtThe terminated parking service set at time pointtSjNtThe NA parking service set at time pointtSjBtThe BA parking service set at time pointtParameter descriptiontiPThe submission time of parking demanditiRThe response time of parking demanditiS,tiEThe time window of parking demandilongi,latiThe destination location of parking demandidimaxThe maximum acceptable walking distance of parking demandipimaxThe maximum acceptable parking price of parking demandiwimaxThe maximum acceptable waiting time of parking demanditjStjEThe time window of parking servicejlongj,latjThe parking space location of parking servicejpjThe parking price of parking servicejrjThe short-term renting price of parking servicej 0 - if parking service j is long-term rentingrj′The long-term renting price of parking servicej 0 - if parking service j is short-term rentingqThe compensation priceτ0The length of parking time intervalτThe allocation periodτ′The BA periodTARThe time threshold to determine whether demands and services are arrivingTAPThe time threshold to determine whether demands and services are approachingINtThe size of NA parking demand set at time pointtIBtThe size of BA parking demand set at time pointtIjThe number of parking demands served by parking spacejdijThe walking distance between parking space location of parking servicej and destination location of parking demand icijThe time window relationship between parking demandi and parking service j 1 - if the time window of parking demand i is within that of parking service j 0 - otherwisecii′The time window relationship between parking demandi and parking demand i′ 1 - if the time window of parking demand i is not in conflict with that of parking demand i′ 0 - otherwisebjfThe belonging relationship between parking servicej and parking facility f 1 - if parking service j belongs to parking facility f 0 - otherwiseaiThe current status of passenger demandi 1 - if passenger demand i is arriving 0 - otherwisex˜ijThe last allocation result between parking demandi and parking service j 1 - if parking service j was allocated to parking demand i 0 - otherwiseVariable descriptionxijThe allocation result between parking de mandi and parking service j 1 - if parking service j is allocated to parking demand i 0 - otherwise.


### 3.1. Collection Center

#### 3.1.1. Demand Collection

CC collects parking demands from either leisure or urgent users. Leisure users refer to users with a long planning time. Urgent users refer to users with a short planning time. Planning time is the duration between demand submission time and demand start time.The overall time horizon is discretized into a set of parking time intervals with lengthτ0. Each user can submit several parking demands. Each parking demand corresponds to a unique demand time window composed of continuous parking time intervals.Each parking demandi∈Si1,2,…,I contains the following information: submission time tiP, time window tiS,tiE, destination location longi,lati, the maximum acceptable walking distance dimax, the maximum acceptable parking price pimax , and the maximum acceptable waiting time wimax.


#### 3.1.2. Service Collection

CC collects parking spaces in either public or private parking facilities from owners. Public parking facilities refer to the parking facilities that are fully open to the public, such as the public parking garages and the curbside parking spaces. Private parking facilities refer to the parking facilities that are personal belongings, such as the residential parking garages. In a certain area, both public and private parking facilities compose the set of parking facilitiesSf1,2,…,F.Based on the renting schemes, parking spaces are classified into short-term renting and long-term renting parking spaces. Owners can choose either renting scheme according to their situations. Though system managers totally decide the parking prices, owners can mainly decide the renting prices.For each short-term renting parking space, the owner provides short-term usage authority to CARSP according to real-time parking arrangements. For example, commuters can provide their own parking spaces to CARSP for nine-to-five sharing on weekdays. Under the short-term renting price, the rent will be paid once the parking space is occupied for a specific period.For each long-term renting parking space, the owner provides long-term usage authority to CARSP according to historical parking characteristics. For example, shopping mall managers can provide long-term idle parking spaces to CARSP for twenty-four-hour sharing. Under the long-term renting price, the rent will be paid in advance whether the parking space is occupied or not.Each owner can submit several parking spaces, and each parking space can provide several parking services. Each parking service corresponds to a unique service time window composed of continuous parking time intervals.Figure2 shows a typical example of one parking space providing two parking services. The Time window of parking space 10:30,12:00 is divided into eighteen parking time intervals with a length of 5 minutes. Time window of parking service j is 10:30,11:00, and the time window of parking service j′ is 11:30,12:00. The parking space is not for sharing in the time window 11:00,11:30.Figure 2
Example of one parking space providing two parking services.Each parking servicej∈Sj1,2,…,J contains the following information: time window tjS,tjE, parking space location longj,latj, parking price pj, short-term renting price rj , and long-term renting price rj′.


### 3.2. Allocation Center

#### 3.2.1. Demand and Service Storing

Once CC collects a parking space or a parking demand, AC receives the data from CC immediately. All data is stored in AC by category.At time pointt, the demand data stored in AC includes the unallocated parking demand set SiUt, the allocated (but not occupied) parking demand set SiAt, the occupied (but not terminated) parking demand set SiOt, the terminated parking demand set SiTt , and the failed parking demand set SiFt. Furthermore, the unallocated parking demand set SiUt includes both the newly submitted parking demand set SiUNt and the previously submitted (but unallocated) parking demand set SiUPt. Meanwhile, the allocated (but not occupied) parking demand set SiAt includes both the arriving parking demand set SiARt and the allocated but not arriving parking demand set SiARNt. Given an appropriate time threshold TAR, parking demand i in SiAt belongs to the arriving parking demand set SiARt if tiS≤t+TAR, while it belongs to the allocated but not arriving parking demand set SiARNt otherwise.Simultaneously, the service data stored in AC includes the unallocated parking service setSjUt, the allocated (but not occupied) parking service set SjAt, the occupied (but not terminated) parking service set SjOt, and the terminated parking service set SjTt. Moreover, the allocated (but not occupied) parking service set SjAt includes both the arriving parking service set SjARt and the allocated but not arriving parking service set SjARNt. Given the same time threshold TAR, parking service j in SjAt belongs to the arriving parking service set SjARt if tjS≤t+TAR and the allocated but not arriving parking service set SjARNt otherwise.Inspired by Spectrum, a parking spectrum graph is introduced to demonstrate the transition of all demand and service sets. In Figure3, except for the failed parking demand set SiFt, the further to the left, the more necessary demands and services are to be allocated. Conversely, the further to the right, the more parking details are required by relevant users and owners.Figure 3
Smart parking spectrum graph.


#### 3.2.2. Demand and Service Allocating

At each allocation time point, AC selects specific demand and service to participate in the allocation process.Parking servicej can serve parking demand i if the following three criteria are achieved. Firstly, parking price pj is within the maximum acceptable parking price pimax. Secondly, walking distance dij (calculated by destination location longi,lati and parking space location longj,latj) is within the maximum acceptable walking distance dimax. Thirdly, time window tiS,tiE is within the time window tjS,tjE. On this basis, parking service j can serve parking demand i′ at the same time if time window ti′S,ti′E is not in conflict with time window tiS,tiE.Figure4 shows a typical example of one parking service serving two parking demands. Time window of parking service j10:00,11:00 is divided into twelve parking time intervals with length of 5 minutes. Time window of parking demand i is 10:00,10:30, and time window of parking demand i′ is 10:45,11:00. Parking demand i has no time conflicts with parking demand i′ so that they can be allocated to parking service j simultaneously.Figure 4
Example of one parking service serving two parking demands.It is preset that users cannot cancel or modify parking demands and owners cannot cancel or modify parking services. That is, users will accept the parking services allocated by CARSP, and owners will accept the parking demand allocated by CARSP.


#### 3.2.3. Demand and Service Updating

Once the allocation process is complete, AC updates demand and service immediately according to the allocation results.Unallocated parking demandi will be moved to SiUPt to wait for the next allocation process if waiting time t−tiP is within the maximum acceptable waiting time wimax. Unallocated parking demand i will be moved to SiFt and added to failed demand list if waiting time t−tiP exceeds the maximum acceptable waiting time wimax. Allocated parking demand i will be moved to SiARt (if tiS≤t+TAR) or SiARNt (otherwise) and added to the allocated demand list.Unallocated parking servicej will be moved to SjUt to wait for the next allocation process. Allocated parking service j will produce Ij totally allocated parking services and at most Ij+1 totally unallocated parking services. All totally allocated parking services will be moved to SjARt (if tjS≤t+TAR) or SjARNt (otherwise). All totally unallocated parking services will be moved to SjUt to wait for the next allocation process.Figure5 shows a typical example of one parking service producing several parking services. Since parking service j serves parking demand i and parking demand i′, it produces two totally allocated parking services and, at most, three totally unallocated parking services. There are eight cases due to the different relationships of time windows tjS,tjE, tiS,tiE, and ti′S,ti′E. Parking service j produces two parking services in Case 1. Parking service j produces three parking services in Cases 2, 3, and 4. Parking service j produces four parking services in Cases 5, 6, and 7. Parking service j produces five parking services in Case 8.Figure 5
Example of one parking service producing several parking services.The overall time horizon is discretized into a set of time unitsSt1,2,…,T. Each time unit corresponds to its end time point, so that St is also a set of time points. At each time point, AC also updates demand and service periodically.Parking demandi in SiARNt will be moved to SiARt and added to arriving demand list if tiS=t+TAR. Parking demand i in SiARt will be moved to SiOt and added to the occupied demand list if tiS=t. Parking demand i in SiOt will be added to leaving demand list if tiE=t+TAR. Parking demand i in SiOt will be moved to SiTt and added to terminated demand list if tiE=t.Parking servicej in SjARNt will be moved to SjARt if tjS=t+TAR. Parking service j in SjARt will be moved to SjOt and added to occupied service list if tjS=t. Parking service j in SjOt will be moved to SjTt and added to terminated service list if tjE=t.Figures6 and 7 show the state transitions of demands and services, respectively.Figure 6
State transitions of demands.Figure 7
State transitions of services. After each update, AC sends the demand and service lists to RC.


### 3.3. Response Center

Once receiving the demand and service lists from AC, RC sends specific notifications to relevant users and owners.After each allocation process, RC will send “allocation success” notifications to users in the allocated demand list and send “allocation failure” notifications to users in failed demand list. “Allocation success” notification is the parking promise, but it does not contain a specific number and location of the parking facility and parking space. Specific number and location of parking facilities will be sent to users whose demands are inSiARt and the details of parking spaces will be sent to users in the occupied demand list. This kind of notification scheme provides a possibility for integrating all available parking services.At each time point, RC will send “parking start” notifications to users in the occupied demand list and owners in the occupied service list and send “parking end” notifications to users in terminated demand list and owners in the terminated service list. [23] “Parking start” notifications should contain accurate information of parking facility and parking space to users and owners, and “parking end” notifications should contain bill information to users and owners.Besides, RC will send “arriving reminder” notifications to users in arriving demand list and send “leaving reminder” notifications to users in leaving demand list. “Arriving reminder” notifications should prompt users to drive to the allocated parking facility on time, and “leaving reminder” notifications should prompt users to leave the parking facility on time.It is assumed that users and owners are punctual. That is, users will arrive at and leave parking spaces on time, and owners will guarantee that parking services are available.


## 3.1. Collection Center

### 3.1.1. Demand Collection

CC collects parking demands from either leisure or urgent users. Leisure users refer to users with a long planning time. Urgent users refer to users with a short planning time. Planning time is the duration between demand submission time and demand start time.The overall time horizon is discretized into a set of parking time intervals with lengthτ0. Each user can submit several parking demands. Each parking demand corresponds to a unique demand time window composed of continuous parking time intervals.Each parking demandi∈Si1,2,…,I contains the following information: submission time tiP, time window tiS,tiE, destination location longi,lati, the maximum acceptable walking distance dimax, the maximum acceptable parking price pimax , and the maximum acceptable waiting time wimax.


### 3.1.2. Service Collection

CC collects parking spaces in either public or private parking facilities from owners. Public parking facilities refer to the parking facilities that are fully open to the public, such as the public parking garages and the curbside parking spaces. Private parking facilities refer to the parking facilities that are personal belongings, such as the residential parking garages. In a certain area, both public and private parking facilities compose the set of parking facilitiesSf1,2,…,F.Based on the renting schemes, parking spaces are classified into short-term renting and long-term renting parking spaces. Owners can choose either renting scheme according to their situations. Though system managers totally decide the parking prices, owners can mainly decide the renting prices.For each short-term renting parking space, the owner provides short-term usage authority to CARSP according to real-time parking arrangements. For example, commuters can provide their own parking spaces to CARSP for nine-to-five sharing on weekdays. Under the short-term renting price, the rent will be paid once the parking space is occupied for a specific period.For each long-term renting parking space, the owner provides long-term usage authority to CARSP according to historical parking characteristics. For example, shopping mall managers can provide long-term idle parking spaces to CARSP for twenty-four-hour sharing. Under the long-term renting price, the rent will be paid in advance whether the parking space is occupied or not.Each owner can submit several parking spaces, and each parking space can provide several parking services. Each parking service corresponds to a unique service time window composed of continuous parking time intervals.Figure2 shows a typical example of one parking space providing two parking services. The Time window of parking space 10:30,12:00 is divided into eighteen parking time intervals with a length of 5 minutes. Time window of parking service j is 10:30,11:00, and the time window of parking service j′ is 11:30,12:00. The parking space is not for sharing in the time window 11:00,11:30.Figure 2
Example of one parking space providing two parking services.Each parking servicej∈Sj1,2,…,J contains the following information: time window tjS,tjE, parking space location longj,latj, parking price pj, short-term renting price rj , and long-term renting price rj′.


## 3.1.1. Demand Collection

CC collects parking demands from either leisure or urgent users. Leisure users refer to users with a long planning time. Urgent users refer to users with a short planning time. Planning time is the duration between demand submission time and demand start time.The overall time horizon is discretized into a set of parking time intervals with lengthτ0. Each user can submit several parking demands. Each parking demand corresponds to a unique demand time window composed of continuous parking time intervals.Each parking demandi∈Si1,2,…,I contains the following information: submission time tiP, time window tiS,tiE, destination location longi,lati, the maximum acceptable walking distance dimax, the maximum acceptable parking price pimax , and the maximum acceptable waiting time wimax.


## 3.1.2. Service Collection

CC collects parking spaces in either public or private parking facilities from owners. Public parking facilities refer to the parking facilities that are fully open to the public, such as the public parking garages and the curbside parking spaces. Private parking facilities refer to the parking facilities that are personal belongings, such as the residential parking garages. In a certain area, both public and private parking facilities compose the set of parking facilitiesSf1,2,…,F.Based on the renting schemes, parking spaces are classified into short-term renting and long-term renting parking spaces. Owners can choose either renting scheme according to their situations. Though system managers totally decide the parking prices, owners can mainly decide the renting prices.For each short-term renting parking space, the owner provides short-term usage authority to CARSP according to real-time parking arrangements. For example, commuters can provide their own parking spaces to CARSP for nine-to-five sharing on weekdays. Under the short-term renting price, the rent will be paid once the parking space is occupied for a specific period.For each long-term renting parking space, the owner provides long-term usage authority to CARSP according to historical parking characteristics. For example, shopping mall managers can provide long-term idle parking spaces to CARSP for twenty-four-hour sharing. Under the long-term renting price, the rent will be paid in advance whether the parking space is occupied or not.Each owner can submit several parking spaces, and each parking space can provide several parking services. Each parking service corresponds to a unique service time window composed of continuous parking time intervals.Figure2 shows a typical example of one parking space providing two parking services. The Time window of parking space 10:30,12:00 is divided into eighteen parking time intervals with a length of 5 minutes. Time window of parking service j is 10:30,11:00, and the time window of parking service j′ is 11:30,12:00. The parking space is not for sharing in the time window 11:00,11:30.Figure 2
Example of one parking space providing two parking services.Each parking servicej∈Sj1,2,…,J contains the following information: time window tjS,tjE, parking space location longj,latj, parking price pj, short-term renting price rj , and long-term renting price rj′.


## 3.2. Allocation Center

### 3.2.1. Demand and Service Storing

Once CC collects a parking space or a parking demand, AC receives the data from CC immediately. All data is stored in AC by category.At time pointt, the demand data stored in AC includes the unallocated parking demand set SiUt, the allocated (but not occupied) parking demand set SiAt, the occupied (but not terminated) parking demand set SiOt, the terminated parking demand set SiTt , and the failed parking demand set SiFt. Furthermore, the unallocated parking demand set SiUt includes both the newly submitted parking demand set SiUNt and the previously submitted (but unallocated) parking demand set SiUPt. Meanwhile, the allocated (but not occupied) parking demand set SiAt includes both the arriving parking demand set SiARt and the allocated but not arriving parking demand set SiARNt. Given an appropriate time threshold TAR, parking demand i in SiAt belongs to the arriving parking demand set SiARt if tiS≤t+TAR, while it belongs to the allocated but not arriving parking demand set SiARNt otherwise.Simultaneously, the service data stored in AC includes the unallocated parking service setSjUt, the allocated (but not occupied) parking service set SjAt, the occupied (but not terminated) parking service set SjOt, and the terminated parking service set SjTt. Moreover, the allocated (but not occupied) parking service set SjAt includes both the arriving parking service set SjARt and the allocated but not arriving parking service set SjARNt. Given the same time threshold TAR, parking service j in SjAt belongs to the arriving parking service set SjARt if tjS≤t+TAR and the allocated but not arriving parking service set SjARNt otherwise.Inspired by Spectrum, a parking spectrum graph is introduced to demonstrate the transition of all demand and service sets. In Figure3, except for the failed parking demand set SiFt, the further to the left, the more necessary demands and services are to be allocated. Conversely, the further to the right, the more parking details are required by relevant users and owners.Figure 3
Smart parking spectrum graph.


### 3.2.2. Demand and Service Allocating

At each allocation time point, AC selects specific demand and service to participate in the allocation process.Parking servicej can serve parking demand i if the following three criteria are achieved. Firstly, parking price pj is within the maximum acceptable parking price pimax. Secondly, walking distance dij (calculated by destination location longi,lati and parking space location longj,latj) is within the maximum acceptable walking distance dimax. Thirdly, time window tiS,tiE is within the time window tjS,tjE. On this basis, parking service j can serve parking demand i′ at the same time if time window ti′S,ti′E is not in conflict with time window tiS,tiE.Figure4 shows a typical example of one parking service serving two parking demands. Time window of parking service j10:00,11:00 is divided into twelve parking time intervals with length of 5 minutes. Time window of parking demand i is 10:00,10:30, and time window of parking demand i′ is 10:45,11:00. Parking demand i has no time conflicts with parking demand i′ so that they can be allocated to parking service j simultaneously.Figure 4
Example of one parking service serving two parking demands.It is preset that users cannot cancel or modify parking demands and owners cannot cancel or modify parking services. That is, users will accept the parking services allocated by CARSP, and owners will accept the parking demand allocated by CARSP.


### 3.2.3. Demand and Service Updating

Once the allocation process is complete, AC updates demand and service immediately according to the allocation results.Unallocated parking demandi will be moved to SiUPt to wait for the next allocation process if waiting time t−tiP is within the maximum acceptable waiting time wimax. Unallocated parking demand i will be moved to SiFt and added to failed demand list if waiting time t−tiP exceeds the maximum acceptable waiting time wimax. Allocated parking demand i will be moved to SiARt (if tiS≤t+TAR) or SiARNt (otherwise) and added to the allocated demand list.Unallocated parking servicej will be moved to SjUt to wait for the next allocation process. Allocated parking service j will produce Ij totally allocated parking services and at most Ij+1 totally unallocated parking services. All totally allocated parking services will be moved to SjARt (if tjS≤t+TAR) or SjARNt (otherwise). All totally unallocated parking services will be moved to SjUt to wait for the next allocation process.Figure5 shows a typical example of one parking service producing several parking services. Since parking service j serves parking demand i and parking demand i′, it produces two totally allocated parking services and, at most, three totally unallocated parking services. There are eight cases due to the different relationships of time windows tjS,tjE, tiS,tiE, and ti′S,ti′E. Parking service j produces two parking services in Case 1. Parking service j produces three parking services in Cases 2, 3, and 4. Parking service j produces four parking services in Cases 5, 6, and 7. Parking service j produces five parking services in Case 8.Figure 5
Example of one parking service producing several parking services.The overall time horizon is discretized into a set of time unitsSt1,2,…,T. Each time unit corresponds to its end time point, so that St is also a set of time points. At each time point, AC also updates demand and service periodically.Parking demandi in SiARNt will be moved to SiARt and added to arriving demand list if tiS=t+TAR. Parking demand i in SiARt will be moved to SiOt and added to the occupied demand list if tiS=t. Parking demand i in SiOt will be added to leaving demand list if tiE=t+TAR. Parking demand i in SiOt will be moved to SiTt and added to terminated demand list if tiE=t.Parking servicej in SjARNt will be moved to SjARt if tjS=t+TAR. Parking service j in SjARt will be moved to SjOt and added to occupied service list if tjS=t. Parking service j in SjOt will be moved to SjTt and added to terminated service list if tjE=t.Figures6 and 7 show the state transitions of demands and services, respectively.Figure 6
State transitions of demands.Figure 7
State transitions of services. After each update, AC sends the demand and service lists to RC.


## 3.2.1. Demand and Service Storing

Once CC collects a parking space or a parking demand, AC receives the data from CC immediately. All data is stored in AC by category.At time pointt, the demand data stored in AC includes the unallocated parking demand set SiUt, the allocated (but not occupied) parking demand set SiAt, the occupied (but not terminated) parking demand set SiOt, the terminated parking demand set SiTt , and the failed parking demand set SiFt. Furthermore, the unallocated parking demand set SiUt includes both the newly submitted parking demand set SiUNt and the previously submitted (but unallocated) parking demand set SiUPt. Meanwhile, the allocated (but not occupied) parking demand set SiAt includes both the arriving parking demand set SiARt and the allocated but not arriving parking demand set SiARNt. Given an appropriate time threshold TAR, parking demand i in SiAt belongs to the arriving parking demand set SiARt if tiS≤t+TAR, while it belongs to the allocated but not arriving parking demand set SiARNt otherwise.Simultaneously, the service data stored in AC includes the unallocated parking service setSjUt, the allocated (but not occupied) parking service set SjAt, the occupied (but not terminated) parking service set SjOt, and the terminated parking service set SjTt. Moreover, the allocated (but not occupied) parking service set SjAt includes both the arriving parking service set SjARt and the allocated but not arriving parking service set SjARNt. Given the same time threshold TAR, parking service j in SjAt belongs to the arriving parking service set SjARt if tjS≤t+TAR and the allocated but not arriving parking service set SjARNt otherwise.Inspired by Spectrum, a parking spectrum graph is introduced to demonstrate the transition of all demand and service sets. In Figure3, except for the failed parking demand set SiFt, the further to the left, the more necessary demands and services are to be allocated. Conversely, the further to the right, the more parking details are required by relevant users and owners.Figure 3
Smart parking spectrum graph.


## 3.2.2. Demand and Service Allocating

At each allocation time point, AC selects specific demand and service to participate in the allocation process.Parking servicej can serve parking demand i if the following three criteria are achieved. Firstly, parking price pj is within the maximum acceptable parking price pimax. Secondly, walking distance dij (calculated by destination location longi,lati and parking space location longj,latj) is within the maximum acceptable walking distance dimax. Thirdly, time window tiS,tiE is within the time window tjS,tjE. On this basis, parking service j can serve parking demand i′ at the same time if time window ti′S,ti′E is not in conflict with time window tiS,tiE.Figure4 shows a typical example of one parking service serving two parking demands. Time window of parking service j10:00,11:00 is divided into twelve parking time intervals with length of 5 minutes. Time window of parking demand i is 10:00,10:30, and time window of parking demand i′ is 10:45,11:00. Parking demand i has no time conflicts with parking demand i′ so that they can be allocated to parking service j simultaneously.Figure 4
Example of one parking service serving two parking demands.It is preset that users cannot cancel or modify parking demands and owners cannot cancel or modify parking services. That is, users will accept the parking services allocated by CARSP, and owners will accept the parking demand allocated by CARSP.


## 3.2.3. Demand and Service Updating

Once the allocation process is complete, AC updates demand and service immediately according to the allocation results.Unallocated parking demandi will be moved to SiUPt to wait for the next allocation process if waiting time t−tiP is within the maximum acceptable waiting time wimax. Unallocated parking demand i will be moved to SiFt and added to failed demand list if waiting time t−tiP exceeds the maximum acceptable waiting time wimax. Allocated parking demand i will be moved to SiARt (if tiS≤t+TAR) or SiARNt (otherwise) and added to the allocated demand list.Unallocated parking servicej will be moved to SjUt to wait for the next allocation process. Allocated parking service j will produce Ij totally allocated parking services and at most Ij+1 totally unallocated parking services. All totally allocated parking services will be moved to SjARt (if tjS≤t+TAR) or SjARNt (otherwise). All totally unallocated parking services will be moved to SjUt to wait for the next allocation process.Figure5 shows a typical example of one parking service producing several parking services. Since parking service j serves parking demand i and parking demand i′, it produces two totally allocated parking services and, at most, three totally unallocated parking services. There are eight cases due to the different relationships of time windows tjS,tjE, tiS,tiE, and ti′S,ti′E. Parking service j produces two parking services in Case 1. Parking service j produces three parking services in Cases 2, 3, and 4. Parking service j produces four parking services in Cases 5, 6, and 7. Parking service j produces five parking services in Case 8.Figure 5
Example of one parking service producing several parking services.The overall time horizon is discretized into a set of time unitsSt1,2,…,T. Each time unit corresponds to its end time point, so that St is also a set of time points. At each time point, AC also updates demand and service periodically.Parking demandi in SiARNt will be moved to SiARt and added to arriving demand list if tiS=t+TAR. Parking demand i in SiARt will be moved to SiOt and added to the occupied demand list if tiS=t. Parking demand i in SiOt will be added to leaving demand list if tiE=t+TAR. Parking demand i in SiOt will be moved to SiTt and added to terminated demand list if tiE=t.Parking servicej in SjARNt will be moved to SjARt if tjS=t+TAR. Parking service j in SjARt will be moved to SjOt and added to occupied service list if tjS=t. Parking service j in SjOt will be moved to SjTt and added to terminated service list if tjE=t.Figures6 and 7 show the state transitions of demands and services, respectively.Figure 6
State transitions of demands.Figure 7
State transitions of services. After each update, AC sends the demand and service lists to RC.


## 3.3. Response Center

Once receiving the demand and service lists from AC, RC sends specific notifications to relevant users and owners.After each allocation process, RC will send “allocation success” notifications to users in the allocated demand list and send “allocation failure” notifications to users in failed demand list. “Allocation success” notification is the parking promise, but it does not contain a specific number and location of the parking facility and parking space. Specific number and location of parking facilities will be sent to users whose demands are inSiARt and the details of parking spaces will be sent to users in the occupied demand list. This kind of notification scheme provides a possibility for integrating all available parking services.At each time point, RC will send “parking start” notifications to users in the occupied demand list and owners in the occupied service list and send “parking end” notifications to users in terminated demand list and owners in the terminated service list. [23] “Parking start” notifications should contain accurate information of parking facility and parking space to users and owners, and “parking end” notifications should contain bill information to users and owners.Besides, RC will send “arriving reminder” notifications to users in arriving demand list and send “leaving reminder” notifications to users in leaving demand list. “Arriving reminder” notifications should prompt users to drive to the allocated parking facility on time, and “leaving reminder” notifications should prompt users to leave the parking facility on time.It is assumed that users and owners are punctual. That is, users will arrive at and leave parking spaces on time, and owners will guarantee that parking services are available.


## 4. Doubly Periodic Rolling Horizon Allocation Approach

### 4.1. Allocation Approach Description

As a classical theory, the rolling horizon has been widely used in optimization, estimation, control, and other fields [24, 25]. Referring to the relevant studies, time-driven rolling horizon allocation (RH for short) is introduced to replace event-driven First-Book-First-Serve (FBFS for short). In a large-scale dynamic parking allocation problem, RH aims at realizing the overall optimization in each period but not the overall optimization throughout the entire time horizon.As mentioned before, CARSP executes either NA or BA at each allocation time point. Thus, CARSP is based on Rolling Horizon Narrow Allocation if it conducts NA at each allocation time point, while CARSP is based on Rolling Horizon Broad Allocation if it conducts BA at each allocation time point. Under the same condition, RHN shows superiority in allocation speed while RHB shows superiority in allocation effect and both RHN and RHB have unique advantages and cannot be replaced.In this way, we propose a Doubly Periodic Rolling Horizon allocation approach in CARSP to combine the superiorities of RNA and RHB.Three principles are clarified to ensure allocation effect and allocation speed in CARSP based on DPRH.Firstly, the unallocated parking service setSjU and the allocated parking service set SjA cannot be simply merged but should be deeply integrated before each BA process. Referring to Figure 5, the parking service is split into several parking services. Then, the several parking services will be integrated into one parking service to participate in the BA process.Secondly, the parking guarantee for each parking demandi∈SiA cannot be broken, which means that each allocated parking demand must be reallocated to one parking space in each BA process.Thirdly, the parking facility for each parking demandi∈SiAR cannot be changed, which means that each arriving parking demand must be reallocated to one parking space within the parking facility in each BA process. Given this, parking facility information will be sent in “Arriving reminder” notifications, and parking service information will be sent in “Parking start” notifications.The overall time horizon is discretized into a set of allocation time pointsStATA1,TA2,…,TAn with period τ. StATA1,TA2,…,TAn can be divided into a subset of BA time points StBTB1,TB2,…,TBn with period τ′ and a subset of NA time points StNTN1,TN2,…,TNn. In RHN, StN=StA, StB=∅. In RHB, τ′=τ,StB=StA,StN=∅. Thus, in DPRH, we describe the relation of τ′ and τ as τ′=m∗τm>1 and StB⊊StA,StN⊊StA, StB∪StN=StA.Figure8 shows the process of DPRH, in which the black arrow points to the direction of time rolling, demands and services participating in NA are indicated by green rectangles, and the demands and services participating in BA are denoted by orange rectangles. The green and orange rectangles are also marked in Figures 6 and 7.Figure 8
Process of DPRH.At each NA time pointt∈StN, the unallocated parking demand set SiUt is the NA parking demand set SiNt, and the unallocated parking service set SjUt is the NA parking service set SjNt. The NA model allocates parking demands in SiNt and parking services in SjNt.At each BA time pointt∈StB, the unallocated parking demand set SiUt and the allocated parking demand set SiAt are simply merged into the BA parking demand set SiBt, and the unallocated parking service set SjUt and the allocated parking service set SjAt are deeply integrated into the BA parking service set SjBt. The BA model allocates parking demands in SiBt and parking services in SjBt.DPRH can theoretically reach the ideal allocation effect and speed. However, in practice, especially in a large city, BA demand and service setsSiBt and SjBt should be controlled within reasonable scales due to the limitation of computing power. Considering the differences in allocation urgency, the unallocated demand and service sets SiUt and SjUt should be totally reserved in BA, while the allocated demand and service sets SiAt and SjAt should be partly erased from BA. Given an appropriate time threshold TAP (TAP>TAR), parking demand i in SiAt belongs to the approaching parking demand set SiAPt if t+TAR<tiS≤t+TAP, while it belongs to the allocated but not approaching parking demand set SiAPNt if tiS>t+TAP. Simultaneously, parking service j in SjAt belongs to the approaching parking service set SjAPt if t+TAR<tjS≤t+TAP and the allocated but not approaching parking service set SjAPNt if tjS>t+TAP. Obviously, the approaching demand and service sets SiAPt and SjAPt should be reserved to participate in BA.


### 4.2. Allocation Models

In DPRH, NA and BA are conducted at specific allocation time points. Both models are formulated to maximize revenue for system managers and minimize waiting time for users. We integrate user waiting time into system cost so that the objectives of both models are maximizing integrated benefit for system. The integrated benefit consists of system revenue and system cost. System revenue comes from the parking fees paid by allocated users. Under parking pricepj, parking fees are positively correlated with occupancy time of parking demands. System cost refers to not only the renting cost paid to owners but also the compensation cost paid to users waiting to be allocated. Under short-term renting price rj, renting cost is positively correlated with occupancy time of parking demands. Under long-term renting price rj′, renting cost is not correlated with occupancy time of parking demands. Under compensation price q, compensation cost is positively correlated with waiting time of parking demands.Five binary parameters are designed in NA and BA models: (1)cij expresses the time window relationship between parking demand i and parking service j. cij=1 if time window of parking demand i is within that of parking service j, while cij=0 otherwise. (2) cii′ expresses the time window relationship between parking demand i and parking demand i′. cii′=1 if time window of parking demand i is not in conflict with that of parking demand i′, while cii′=0 otherwise. (3) bjf indicates the belonging relationship between parking service j and parking facility f. bjf=1 if parking service j belongs to parking facility f, while bjf=0 otherwise. (4) ai denotes the current status of passenger demand i. ai=1 if passenger demand i is arriving, while ai=0 otherwise. (5) x˜ij represents the last allocation result between parking demand i and parking service j. x˜ij=1 if parking service j was allocated to parking demand i in the last allocation, while x˜ij=0 otherwise.Besides, a binary variablexij is introduced to represent the allocation result between parking demand i and parking service j. xij=1 if parking service j is allocated to parking demand i, while xij=0 otherwise.


#### 4.2.1. Narrow Allocation Model

Narrow allocation model is formulated as a binary integer programming model with the objective of maximizing system integrated benefit at each NA time pointt∈StN, as formula (1) shows and it is subject to constraints (2)-(7).(1)maxZNt=∑i∈SiNt∑j∈SjNtpj−rj⋅tiE−tiS⋅xij−q⋅τ⋅∑i∈SiNt1−∑j∈SjNtxij,(2)∑j∈SjNtxij≤1,∀i∈SiNt,(3)xij≤cij,∀i∈SiNt,∀j∈SjNt,(4)xij+xi′j≤cii′+1,∀i,i′∈SiNt,i≠i′,∀j∈SjNt,(5)dij⋅xij≤dimax,∀i∈SiNt,∀j∈SjNt,(6)pj⋅xij≤pimax,∀i∈SiNt,∀j∈SjNt,(7)xij∈0,1,∀i∈SiNt,∀j∈SjNt.Constraint (2) restricts that each parking demand cannot be allocated to more than one parking service. Constraint (3) claims that each parking demand cannot be allocated to the conflicting parking service. Constraint (4) implies that every two conflicting parking demands cannot be allocated to the same parking service. Constraint (5) ensures that each parking demand cannot be allocated to parking services with too long walking distances. Constraint (6) assures that each parking demand cannot be allocated to parking services with too high parking prices. Constraint (7) defines variable xij.


#### 4.2.2. Broad Allocation Model

Broad allocation model is formulated as a binary integer programming model with the objective of maximizing system integrated benefit at each BA time pointt∈StB, as formula (8) shows.To ensure allocation effect, different from NA model, BA model must guarantee that all unoccupied demands participating in BA are successfully allocated. Meanwhile, BA must guarantee that all approaching demands will not be reallocated to another parking facility. Constraints are shown in (9)-(16).(8)maxZBt=∑i∈SiBt∑j∈SjBtpj−rj⋅tiE−tiS⋅xij−q⋅τ⋅∑i∈SiBt1−∑j∈SjBtxij,(9)∑j∈SjBtxij≤1,∀i∈SiBt,(10)xij≤cij,∀i∈SiBt,∀j∈SjBt,(11)xij+xi′j≤cii′+1,∀i,i′∈SiBt,i≠i′,∀j∈SjBt,(12)dij⋅xij≤dimax,∀i∈SiBt,∀j∈SjBt,(13)pj⋅xij≤pimax,∀i∈SiBt,∀j∈SjBt,(14)∑j∈SjBtxij≥∑j∈SjBtx˜ij,∀i∈SiBt,(15)∑j∈SjBtbjf⋅xij≥∑j∈SjBtai⋅bjf⋅x˜ij,∀i∈SiBt,∀f∈Sf,(16)xij∈0,1,∀i∈SiBt,∀j∈SjBt.Constraints (9)-(14) are derived from constraints (2)-(7), respectively. Constraint (15) specifies that each allocated parking demand must be allocated to one parking space. Constraint (16) stipulates that each arriving parking demand can only be reallocated to another parking space within the same parking facility.


### 4.3. Performance Metrics

RHN, RHB, and DPRH are all based on RH and it is meaningless to compare the total value of the objective function or the value of the objective in each allocation. Therefore, we set seven performance metrics to assess the actual allocation performances throughout the overall time horizon rather than simply comparing the values of the objective [26]. Performance metrics (1) to (5) describe allocation effect, in which (1) represents system integrated benefit throughout the overall time horizon, (2) and (3) indicate resource utilization, (4) and (5) denote user satisfaction. Performance metric (6) expresses allocation speed. Performance metric (7) shows total computing time.


#### 4.3.1. Total Integrated Benefit (TIB for Short)

TIB refers to total integrated benefit throughout the overall time horizon, which is calculated in (3). A higher TIB means that system managers can guarantee more sustainable operation.(17)TIB=∑i∈Si∑j∈Sjpj−rj⋅tiE−tiS⋅xij−T⋅∑j∈Sjrj′−q⋅∑i∈SitiR−tiP.


#### 4.3.2. Service Temporal Utilization (STU for Short)

STU refers to the ratio of total occupancy time to total available parking time, which is calculated in (4). A higher STU means that system managers can utilize parking services more adequately.(18)STU=∑i∈SitiE−tiS⋅xij∑j∈SjtjE−tjS.


#### 4.3.3. Effective Service Temporal Utilization (ESTU for Short)

ESTU refers to the ratio of total occupancy time to total effective parking time, which is calculated in (5). Effective parking time is the time of the parking service that has been allocated to at least one parking demand. A higher ESTU means that system managers can utilize the allocated parking services more efficiently.(19)ESTU=∑i∈SitiE−tiS⋅xij∑j∈SjtjE−tjS⋅yj.


#### 4.3.4. Allocation Success Probability (ASP for Short)

ASP refers to the ratio of allocated parking demands to total parking demands, which is calculated in (6). A higher ASP means that users can obtain parking services more easily.(20)ASP=∑i∈Si∑j∈SjxijI.


#### 4.3.5. Average Planning Time (APT for Short)

APT refers to the average duration between demand submission time and demand start time, which is calculated in (7). A shorter APT means that urgent users can obtain parking services more easily.(21)APT=∑i∈Si∑j∈SjtiS−tiP⋅xij∑i∈Si∑j∈Sjxij.


#### 4.3.6. Average Waiting Time (AWT for Short)

AWT refers to the average duration between demand submission time and response time, which is calculated in (8). A longer AWT means that users can obtain responses faster.(22)AWT=∑i∈SitiR−tiPI.


#### 4.3.7. Total Computing Time (TCT for Short)

TCT refers to the total computing time throughout the overall time horizon. Under the same computing environment, a shorter TCT means that the approach is more efficient and more practical.


## 4.1. Allocation Approach Description

As a classical theory, the rolling horizon has been widely used in optimization, estimation, control, and other fields [24, 25]. Referring to the relevant studies, time-driven rolling horizon allocation (RH for short) is introduced to replace event-driven First-Book-First-Serve (FBFS for short). In a large-scale dynamic parking allocation problem, RH aims at realizing the overall optimization in each period but not the overall optimization throughout the entire time horizon.As mentioned before, CARSP executes either NA or BA at each allocation time point. Thus, CARSP is based on Rolling Horizon Narrow Allocation if it conducts NA at each allocation time point, while CARSP is based on Rolling Horizon Broad Allocation if it conducts BA at each allocation time point. Under the same condition, RHN shows superiority in allocation speed while RHB shows superiority in allocation effect and both RHN and RHB have unique advantages and cannot be replaced.In this way, we propose a Doubly Periodic Rolling Horizon allocation approach in CARSP to combine the superiorities of RNA and RHB.Three principles are clarified to ensure allocation effect and allocation speed in CARSP based on DPRH.Firstly, the unallocated parking service setSjU and the allocated parking service set SjA cannot be simply merged but should be deeply integrated before each BA process. Referring to Figure 5, the parking service is split into several parking services. Then, the several parking services will be integrated into one parking service to participate in the BA process.Secondly, the parking guarantee for each parking demandi∈SiA cannot be broken, which means that each allocated parking demand must be reallocated to one parking space in each BA process.Thirdly, the parking facility for each parking demandi∈SiAR cannot be changed, which means that each arriving parking demand must be reallocated to one parking space within the parking facility in each BA process. Given this, parking facility information will be sent in “Arriving reminder” notifications, and parking service information will be sent in “Parking start” notifications.The overall time horizon is discretized into a set of allocation time pointsStATA1,TA2,…,TAn with period τ. StATA1,TA2,…,TAn can be divided into a subset of BA time points StBTB1,TB2,…,TBn with period τ′ and a subset of NA time points StNTN1,TN2,…,TNn. In RHN, StN=StA, StB=∅. In RHB, τ′=τ,StB=StA,StN=∅. Thus, in DPRH, we describe the relation of τ′ and τ as τ′=m∗τm>1 and StB⊊StA,StN⊊StA, StB∪StN=StA.Figure8 shows the process of DPRH, in which the black arrow points to the direction of time rolling, demands and services participating in NA are indicated by green rectangles, and the demands and services participating in BA are denoted by orange rectangles. The green and orange rectangles are also marked in Figures 6 and 7.Figure 8
Process of DPRH.At each NA time pointt∈StN, the unallocated parking demand set SiUt is the NA parking demand set SiNt, and the unallocated parking service set SjUt is the NA parking service set SjNt. The NA model allocates parking demands in SiNt and parking services in SjNt.At each BA time pointt∈StB, the unallocated parking demand set SiUt and the allocated parking demand set SiAt are simply merged into the BA parking demand set SiBt, and the unallocated parking service set SjUt and the allocated parking service set SjAt are deeply integrated into the BA parking service set SjBt. The BA model allocates parking demands in SiBt and parking services in SjBt.DPRH can theoretically reach the ideal allocation effect and speed. However, in practice, especially in a large city, BA demand and service setsSiBt and SjBt should be controlled within reasonable scales due to the limitation of computing power. Considering the differences in allocation urgency, the unallocated demand and service sets SiUt and SjUt should be totally reserved in BA, while the allocated demand and service sets SiAt and SjAt should be partly erased from BA. Given an appropriate time threshold TAP (TAP>TAR), parking demand i in SiAt belongs to the approaching parking demand set SiAPt if t+TAR<tiS≤t+TAP, while it belongs to the allocated but not approaching parking demand set SiAPNt if tiS>t+TAP. Simultaneously, parking service j in SjAt belongs to the approaching parking service set SjAPt if t+TAR<tjS≤t+TAP and the allocated but not approaching parking service set SjAPNt if tjS>t+TAP. Obviously, the approaching demand and service sets SiAPt and SjAPt should be reserved to participate in BA.


## 4.2. Allocation Models

In DPRH, NA and BA are conducted at specific allocation time points. Both models are formulated to maximize revenue for system managers and minimize waiting time for users. We integrate user waiting time into system cost so that the objectives of both models are maximizing integrated benefit for system. The integrated benefit consists of system revenue and system cost. System revenue comes from the parking fees paid by allocated users. Under parking pricepj, parking fees are positively correlated with occupancy time of parking demands. System cost refers to not only the renting cost paid to owners but also the compensation cost paid to users waiting to be allocated. Under short-term renting price rj, renting cost is positively correlated with occupancy time of parking demands. Under long-term renting price rj′, renting cost is not correlated with occupancy time of parking demands. Under compensation price q, compensation cost is positively correlated with waiting time of parking demands.Five binary parameters are designed in NA and BA models: (1)cij expresses the time window relationship between parking demand i and parking service j. cij=1 if time window of parking demand i is within that of parking service j, while cij=0 otherwise. (2) cii′ expresses the time window relationship between parking demand i and parking demand i′. cii′=1 if time window of parking demand i is not in conflict with that of parking demand i′, while cii′=0 otherwise. (3) bjf indicates the belonging relationship between parking service j and parking facility f. bjf=1 if parking service j belongs to parking facility f, while bjf=0 otherwise. (4) ai denotes the current status of passenger demand i. ai=1 if passenger demand i is arriving, while ai=0 otherwise. (5) x˜ij represents the last allocation result between parking demand i and parking service j. x˜ij=1 if parking service j was allocated to parking demand i in the last allocation, while x˜ij=0 otherwise.Besides, a binary variablexij is introduced to represent the allocation result between parking demand i and parking service j. xij=1 if parking service j is allocated to parking demand i, while xij=0 otherwise.


### 4.2.1. Narrow Allocation Model

Narrow allocation model is formulated as a binary integer programming model with the objective of maximizing system integrated benefit at each NA time pointt∈StN, as formula (1) shows and it is subject to constraints (2)-(7).(1)maxZNt=∑i∈SiNt∑j∈SjNtpj−rj⋅tiE−tiS⋅xij−q⋅τ⋅∑i∈SiNt1−∑j∈SjNtxij,(2)∑j∈SjNtxij≤1,∀i∈SiNt,(3)xij≤cij,∀i∈SiNt,∀j∈SjNt,(4)xij+xi′j≤cii′+1,∀i,i′∈SiNt,i≠i′,∀j∈SjNt,(5)dij⋅xij≤dimax,∀i∈SiNt,∀j∈SjNt,(6)pj⋅xij≤pimax,∀i∈SiNt,∀j∈SjNt,(7)xij∈0,1,∀i∈SiNt,∀j∈SjNt.Constraint (2) restricts that each parking demand cannot be allocated to more than one parking service. Constraint (3) claims that each parking demand cannot be allocated to the conflicting parking service. Constraint (4) implies that every two conflicting parking demands cannot be allocated to the same parking service. Constraint (5) ensures that each parking demand cannot be allocated to parking services with too long walking distances. Constraint (6) assures that each parking demand cannot be allocated to parking services with too high parking prices. Constraint (7) defines variable xij.


### 4.2.2. Broad Allocation Model

Broad allocation model is formulated as a binary integer programming model with the objective of maximizing system integrated benefit at each BA time pointt∈StB, as formula (8) shows.To ensure allocation effect, different from NA model, BA model must guarantee that all unoccupied demands participating in BA are successfully allocated. Meanwhile, BA must guarantee that all approaching demands will not be reallocated to another parking facility. Constraints are shown in (9)-(16).(8)maxZBt=∑i∈SiBt∑j∈SjBtpj−rj⋅tiE−tiS⋅xij−q⋅τ⋅∑i∈SiBt1−∑j∈SjBtxij,(9)∑j∈SjBtxij≤1,∀i∈SiBt,(10)xij≤cij,∀i∈SiBt,∀j∈SjBt,(11)xij+xi′j≤cii′+1,∀i,i′∈SiBt,i≠i′,∀j∈SjBt,(12)dij⋅xij≤dimax,∀i∈SiBt,∀j∈SjBt,(13)pj⋅xij≤pimax,∀i∈SiBt,∀j∈SjBt,(14)∑j∈SjBtxij≥∑j∈SjBtx˜ij,∀i∈SiBt,(15)∑j∈SjBtbjf⋅xij≥∑j∈SjBtai⋅bjf⋅x˜ij,∀i∈SiBt,∀f∈Sf,(16)xij∈0,1,∀i∈SiBt,∀j∈SjBt.Constraints (9)-(14) are derived from constraints (2)-(7), respectively. Constraint (15) specifies that each allocated parking demand must be allocated to one parking space. Constraint (16) stipulates that each arriving parking demand can only be reallocated to another parking space within the same parking facility.


## 4.2.1. Narrow Allocation Model

Narrow allocation model is formulated as a binary integer programming model with the objective of maximizing system integrated benefit at each NA time pointt∈StN, as formula (1) shows and it is subject to constraints (2)-(7).(1)maxZNt=∑i∈SiNt∑j∈SjNtpj−rj⋅tiE−tiS⋅xij−q⋅τ⋅∑i∈SiNt1−∑j∈SjNtxij,(2)∑j∈SjNtxij≤1,∀i∈SiNt,(3)xij≤cij,∀i∈SiNt,∀j∈SjNt,(4)xij+xi′j≤cii′+1,∀i,i′∈SiNt,i≠i′,∀j∈SjNt,(5)dij⋅xij≤dimax,∀i∈SiNt,∀j∈SjNt,(6)pj⋅xij≤pimax,∀i∈SiNt,∀j∈SjNt,(7)xij∈0,1,∀i∈SiNt,∀j∈SjNt.Constraint (2) restricts that each parking demand cannot be allocated to more than one parking service. Constraint (3) claims that each parking demand cannot be allocated to the conflicting parking service. Constraint (4) implies that every two conflicting parking demands cannot be allocated to the same parking service. Constraint (5) ensures that each parking demand cannot be allocated to parking services with too long walking distances. Constraint (6) assures that each parking demand cannot be allocated to parking services with too high parking prices. Constraint (7) defines variable xij.


## 4.2.2. Broad Allocation Model

Broad allocation model is formulated as a binary integer programming model with the objective of maximizing system integrated benefit at each BA time pointt∈StB, as formula (8) shows.To ensure allocation effect, different from NA model, BA model must guarantee that all unoccupied demands participating in BA are successfully allocated. Meanwhile, BA must guarantee that all approaching demands will not be reallocated to another parking facility. Constraints are shown in (9)-(16).(8)maxZBt=∑i∈SiBt∑j∈SjBtpj−rj⋅tiE−tiS⋅xij−q⋅τ⋅∑i∈SiBt1−∑j∈SjBtxij,(9)∑j∈SjBtxij≤1,∀i∈SiBt,(10)xij≤cij,∀i∈SiBt,∀j∈SjBt,(11)xij+xi′j≤cii′+1,∀i,i′∈SiBt,i≠i′,∀j∈SjBt,(12)dij⋅xij≤dimax,∀i∈SiBt,∀j∈SjBt,(13)pj⋅xij≤pimax,∀i∈SiBt,∀j∈SjBt,(14)∑j∈SjBtxij≥∑j∈SjBtx˜ij,∀i∈SiBt,(15)∑j∈SjBtbjf⋅xij≥∑j∈SjBtai⋅bjf⋅x˜ij,∀i∈SiBt,∀f∈Sf,(16)xij∈0,1,∀i∈SiBt,∀j∈SjBt.Constraints (9)-(14) are derived from constraints (2)-(7), respectively. Constraint (15) specifies that each allocated parking demand must be allocated to one parking space. Constraint (16) stipulates that each arriving parking demand can only be reallocated to another parking space within the same parking facility.


## 4.3. Performance Metrics

RHN, RHB, and DPRH are all based on RH and it is meaningless to compare the total value of the objective function or the value of the objective in each allocation. Therefore, we set seven performance metrics to assess the actual allocation performances throughout the overall time horizon rather than simply comparing the values of the objective [26]. Performance metrics (1) to (5) describe allocation effect, in which (1) represents system integrated benefit throughout the overall time horizon, (2) and (3) indicate resource utilization, (4) and (5) denote user satisfaction. Performance metric (6) expresses allocation speed. Performance metric (7) shows total computing time.


### 4.3.1. Total Integrated Benefit (TIB for Short)

TIB refers to total integrated benefit throughout the overall time horizon, which is calculated in (3). A higher TIB means that system managers can guarantee more sustainable operation.(17)TIB=∑i∈Si∑j∈Sjpj−rj⋅tiE−tiS⋅xij−T⋅∑j∈Sjrj′−q⋅∑i∈SitiR−tiP.


### 4.3.2. Service Temporal Utilization (STU for Short)

STU refers to the ratio of total occupancy time to total available parking time, which is calculated in (4). A higher STU means that system managers can utilize parking services more adequately.(18)STU=∑i∈SitiE−tiS⋅xij∑j∈SjtjE−tjS.


### 4.3.3. Effective Service Temporal Utilization (ESTU for Short)

ESTU refers to the ratio of total occupancy time to total effective parking time, which is calculated in (5). Effective parking time is the time of the parking service that has been allocated to at least one parking demand. A higher ESTU means that system managers can utilize the allocated parking services more efficiently.(19)ESTU=∑i∈SitiE−tiS⋅xij∑j∈SjtjE−tjS⋅yj.


### 4.3.4. Allocation Success Probability (ASP for Short)

ASP refers to the ratio of allocated parking demands to total parking demands, which is calculated in (6). A higher ASP means that users can obtain parking services more easily.(20)ASP=∑i∈Si∑j∈SjxijI.


### 4.3.5. Average Planning Time (APT for Short)

APT refers to the average duration between demand submission time and demand start time, which is calculated in (7). A shorter APT means that urgent users can obtain parking services more easily.(21)APT=∑i∈Si∑j∈SjtiS−tiP⋅xij∑i∈Si∑j∈Sjxij.


### 4.3.6. Average Waiting Time (AWT for Short)

AWT refers to the average duration between demand submission time and response time, which is calculated in (8). A longer AWT means that users can obtain responses faster.(22)AWT=∑i∈SitiR−tiPI.


### 4.3.7. Total Computing Time (TCT for Short)

TCT refers to the total computing time throughout the overall time horizon. Under the same computing environment, a shorter TCT means that the approach is more efficient and more practical.


## 4.3.1. Total Integrated Benefit (TIB for Short)

TIB refers to total integrated benefit throughout the overall time horizon, which is calculated in (3). A higher TIB means that system managers can guarantee more sustainable operation.(17)TIB=∑i∈Si∑j∈Sjpj−rj⋅tiE−tiS⋅xij−T⋅∑j∈Sjrj′−q⋅∑i∈SitiR−tiP.


## 4.3.2. Service Temporal Utilization (STU for Short)

STU refers to the ratio of total occupancy time to total available parking time, which is calculated in (4). A higher STU means that system managers can utilize parking services more adequately.(18)STU=∑i∈SitiE−tiS⋅xij∑j∈SjtjE−tjS.


## 4.3.3. Effective Service Temporal Utilization (ESTU for Short)

ESTU refers to the ratio of total occupancy time to total effective parking time, which is calculated in (5). Effective parking time is the time of the parking service that has been allocated to at least one parking demand. A higher ESTU means that system managers can utilize the allocated parking services more efficiently.(19)ESTU=∑i∈SitiE−tiS⋅xij∑j∈SjtjE−tjS⋅yj.


## 4.3.4. Allocation Success Probability (ASP for Short)

ASP refers to the ratio of allocated parking demands to total parking demands, which is calculated in (6). A higher ASP means that users can obtain parking services more easily.(20)ASP=∑i∈Si∑j∈SjxijI.


## 4.3.5. Average Planning Time (APT for Short)

APT refers to the average duration between demand submission time and demand start time, which is calculated in (7). A shorter APT means that urgent users can obtain parking services more easily.(21)APT=∑i∈Si∑j∈SjtiS−tiP⋅xij∑i∈Si∑j∈Sjxij.


## 4.3.6. Average Waiting Time (AWT for Short)

AWT refers to the average duration between demand submission time and response time, which is calculated in (8). A longer AWT means that users can obtain responses faster.(22)AWT=∑i∈SitiR−tiPI.


## 4.3.7. Total Computing Time (TCT for Short)

TCT refers to the total computing time throughout the overall time horizon. Under the same computing environment, a shorter TCT means that the approach is more efficient and more practical.


## 5. Large-Scale Real-World Instance

### 5.1. Instance Setup

Figure9(a) shows the district in Chaoyang District, Beijing, China, where the historical parking data come from. Figure 9(b) shows the normalized district, of which the length and width are both 1 km. There are five adjacent blocks in the district. Blocks with the same color have the same land use. The green block is for business, the yellow block is for commercial, and the orange block is for residential. The solid circle in each block represents a parking facility. The numbers beneath each solid circle represent the coordinates of each parking facility. The five parking facilities rent parking spaces to CARSP for sharing. The sizes of blocks are also set as Figure 9(b) shows. Table 3 shows the parameters of the instance.Figure 9
District of the instance.
(a)(b)Table 3
Parameters of the instance.
ParametersDescriptionsValueTThe number of time units4320IThe number of parking demands31494JThe number of parking services1800FThe number of parking facilities5dimaxThe maximum acceptable walking distance of parking demandi (m)[100, 700]pimaxThe maximum acceptable parking price of parking demandi (CNY/5 min)[0.5, 1.2]wimaxThe maximum acceptable waiting time of parking demandi (min)[1, 10]pjThe parking price of parking servicej (CNY/5 min)[0.5, 1.2]rjThe short-term renting price of parking servicej (CNY/5 min)0.5rj′The long-term renting price of parking servicej (CNY/5 min)0.1qThe compensation price (CNY/min)0.025ρThe split penalty coefficient (CNY/min)0.001τ0The length of parking time interval (min)5TARThe time threshold to determine whether demands and services are arriving (min)15TAPThe time threshold to determine whether demands and services are approaching (min)30The instance selects historical parking data from 00 : 00 on April 20th, 2018, to 00 : 00 on April 23rd, 2018, so that the overall time horizon is 3 days. The overall time horizon is divided into 4320 time units with length of 1 minute. The parking time interval is set to be 5 minutes.The total number of historical parking demands is 31494. Figures10 and 11 show the start time and end time distribution of parking demands [27]. For each parking demand, the submission time varies within [5, 1440] minutes before its start time. The maximum acceptable walking distance varies within [100, 700] meters. The maximum acceptable parking price varies within [0.5, 1.2] CNY per 5 minutes according to Beijing Parking Charge Standard. The maximum acceptable waiting time varies within [1, 10] minutes.Figure 10
Start time distribution of parking demand.Figure 11
End time distribution of parking demand.The total number of parking services is 1800. Table4 shows the details of parking services. According to land use, parking facilities 1, 2, and 3 provide long-term renting parking services, while parking facilities 4 and 5 provide short-term renting parking services. For each short-term renting parking service, the time window varies within [1, 4320]. The renting price is 0.5 CNY per 5 minutes. The parking price varies within [0.6, 1.2] CNY per 5 minutes. For each long-term renting parking service, the time window is [1, 4320]. The renting price is 0.1 CNY per 5 minutes. The parking price is 0.5 or 0.7 CNY per 5 minutes.Table 4
Details of parking services.
Parking facilityNumber of parking servicesRenting typeRenting price (CNY/5 min)Parking price (CNY/5 min)1400Long-term0.10.52600Long-term0.10.73400Long-term0.10.74200Short-term0.5[0.6, 1.2]5200Short-term0.5[0.6, 1.2]Besides, the compensation price is set to be 0.025 CNY per minute. The arrival time threshold is 15 minutes. The approaching time threshold is 30 minutes.The instance sets thirteen groups to test the performances of different allocation approaches with different allocation models under different allocation periods. Table5 shows the details of the test groups. Group 1 is the FBFS group. Groups 2 to 5 are the RHN groups, in which τ∈0.5,1,5,10 and τ′=0. Groups 6 to 9 are the RHB groups, in which τ∈0.5,1,5,10 and τ′=τ. Groups 10 to 13 are the DPRH groups, in which τ∈0.5,1 and τ′∈5,10.Table 5
Details of the test groups.
Group indexGroup codeAllocation approachAllocation modelsτ (min)τ' (min)1FBFSFBFS———2RHN-0.5RHNNA model0.503RHN-1104RHN-5505RHN-101006RHB-0.5RHBBA model0.50.57RHB-1118RHB-5559RHB-10101010DPRH-0.5-5DPRHNA modelBA model0.5511DPRH-0.5-100.51012DPRH-1-51513DPRH-1-10110The CARSP programs based on FBFS, RHN, RHB, DPRH allocation approaches are all encoded in Visual Studio 2017 using C# language. The software used to solve the allocation problem at each allocation time point is IBM ILOG CPLEX Solver 12.6.3. All computations were performed on a personal computer with Intel Core i5-7200U CPU, 8G RAM, and a 64 bit Windows 10 Operating System.


### 5.2. Instance Results

We set two tests to study the performance of CARSP based on FBFS, RHN, RHB, and DPRH when applying to large-scale real-world instance. Test 1 aims to explore the effects of different allocation approaches. Test 2 aims to explore the effects of different allocation periods.The performances of different groups over three days are shown in Table6.Table 6
Performances of different groups over three days.
Group codeTIB (CNY)STUESTUASPAPT (min)AWT (s)TCT (h)FBFS276239.400.4500.5290.580801.050.060.29RHN-0.5277690.720.4520.5320.573805.2815.150.47RHN-1277370.120.4520.5310.571806.5830.370.42RHN-5278382.680.4540.5330.566808.52158.741.11RHN-10276771.090.4520.5310.566809.70317.210.99RHB-0.5283237.340.4580.5380.583790.8224.8526.84RHB-1284196.220.4590.5390.582792.1541.1812.75RHB-5285339.140.4600.5410.581791.09172.574.89RHB-10284600.370.4590.5400.582790.15337.123.66DPRH-0.5-5282422.160.4570.5370.581791.8216.613.85DPRH-0.5-10280797.810.4550.5360.577795.1015.282.10DPRH-1-5283141.950.4580.5380.582790.3432.953.73DPRH-1-10282115.440.4570.5380.578792.6931.652.04


#### 5.2.1. Test 1: Performance of Different Allocation Approaches

Test 1 aims to seek the effects of different allocation approaches. Min-Max normalization is applied to normalize the performance metric values of thirteen groups. In this way, under each performance metric, the strengths and weaknesses of each allocation approach can be demonstrated more clearly. The allocation approach is better if TIB, STU, ESTU, and ASP are higher while APT, AWT, and TCT are lower. Therefore, the normalization equation for the former kind of performance metrics is shown as (23). The normalization equation for the latter kind of performance metrics is shown as (24). Under each performance metric,Max is the maximum of thirteen performance metric values while Min is the minimum. Current is the performance metric value of the current allocation approach, while Current∗ is the normalized performance metric value. Therefore, the allocation approach is better if the normalized performance metric value is higher.(23)Current∗=Current−MinMax−Min,(24)Current∗=Max−CurrentMax−Min.Figure12. Comparisons of FBFS, RHN, RHB, and DPRH.Figure 12
Shows the comparisons of FBFS, RHN, RHB, and DPRH.
(a)(b)(c)(d)(e)For FBFS, the lowest AWT indicates excellent allocation speed. However, the lowest TIB reflects dreadful integrated benefit, the lowest STU and ESTU reflects dreadful resource utilization, and the moderate ASP and APT reflect poor user satisfaction. Meanwhile, FBFS requires the shortest computing time.For RHN, the normalized TIB of all RHN Groups ranges widely, but on the whole, RHN leads to poorly integrated benefit. Similarly, the normalized STU and normalized ESTU of all RHN Groups range widely, but on the whole, RHN results in poor resource utilization. The normalized ASP and normalized APT of all RHN Groups are centralized in the lower half, thus, RHN leads to dreadful user satisfaction. The normalized AWT of all RHN Groups ranges widely, but on the whole, RHN results in good allocation speed. Meanwhile, RHN requires the second shortest computing time.For RHB, the normalized TIB of all RHB Groups are centralized in the upper half, which indicates that RHB results in well integrated benefit. Similarly, the normalized STU and normalized ESTU of all RHB Groups are centralized in the upper half, which indicates that RHB results in good resource utilization. The normalized ASP and normalized APT of all RHB Groups are centralized in the upper half. Meanwhile, RHB results in the highest ASP and APT. Thus RHB results in excellent user satisfaction. The normalized AWT of all RHB Groups ranges widely, but on the whole, RHB leads to dreadful allocation speed. Meanwhile, RHB requires the longest computing time.For DPRH, all normalized performance metrics values are centralized in the upper half. Comparing the thirteen Groups, DPRH results in the highest TIB, STU, and ESTU. Compared with FBFS, DPRH raises TIB by 3.83%, raises STU by 2.65%, and raises ESTU by 2.72%. Therefore, DPRH results in excellent integrated benefits, excellent resource utilization, good user satisfaction, and good allocation speed. Meanwhile, DPRH requires the second-longest computing time.


#### 5.2.2. Test 2: Effects of Different Allocation Periods

Test 2 aims to seek the effects of different allocation periods in the same allocation approach and the same allocation model. Allocation periodsτ∈0.5,1,5,10. The normalization (9) and (10) are also applied to demonstrate the strengths and weaknesses of each allocation period more clearly.Figure13 shows the comparisons of different allocation periods in RHN. Figure 14 shows the comparisons of different allocation periods in RHB. Figure 15 shows the comparisons of different allocation periods in DPRH.Figure 13
Comparisons of RHN with different allocation periods.Figure 14
Comparisons of RHB with different allocation periods.Figure 15
Comparisons of DPRH with different allocation periods.In the light of Figure13, in RHN, when allocation period τ=0.5 (i.e., RHN-0.5), TIB, STU, and ESTU are good. Meanwhile, ASP and APT are the best. AWT is the best and TCT is good. When allocation period τ=1 (i.e., RHN-S-1), TIB, STU, and ESTU are poor. ASP and APT are good. AWT is good and TCT is the best. When allocation period τ=5 (i.e., RHN-5), TIB, STU, and ESTU are the best. ASP and APT are poor. AWT is poor and TCT is the worst. When allocation period τ=10 (i.e., RHN-10), TIB, STU, ESTU, ASP, APT, and AWT are the worst while TCT is poor. Clearly, RHN-0.5 performs the best in user satisfaction and allocation speed, while RHN-5 performs the best in integrated benefit and resource utilization. From the perspective of system managers, the integrated benefit is the most concern. However, allocation speed is also vital since it is the representation of system service quality. In light of Table 6, the TIB of RHN-5 is raised by 0.25%, while the AWT of RHN-5 is ten times that of RHN-0.5.In the light of Figure14, in RHB, when allocation period τ=0.5 (i.e., RHB-0.5), TIB, STU, and ESTU are the worst. ASP is the best and APT is good. AWT is the best, but TCT is the worst. When allocation period τ=1 (i.e., RHB-1), TIB, STU, and ESTU are poor. ASP is good but APT is the worst. AWT is good but TCT is poor. When allocation period τ=5 (i.e., RHB-5), TIB, STU, and ESTU are the best. ASP is the worst and APT is poor. AWT is poor while TCT is good. When allocation period τ=10 (i.e., RHB-10), TIB, STU, and ESTU are good. ASP is good, while APT is poor. AWT is poor while TCT is good. Though RHB-5 and RHB-10 perform better than RHN; AWT is a defect that cannot be ignored.In the light of Figure15, in DPRH, when allocation period τ=0.5 and τ′=5 (i.e., DPRH-0.5-5), TIB is good, STU and ESTU are poor. ASP and APT are good. AWT is good while TCT is the worst. When allocation period τ=0.5 and τ′=10 (i.e., DPRH-0.5-10), TIB, STU, ESTU, ASP, and APT are the worst. AWT is the best and TCT is good. When allocation period τ=1 and τ′=5 (i.e., DPRH-1-5), TIB, STU, ESTU, ASP, and APT are the best. AWT is the worst and TCT is poor. When allocation period τ=1 and τ′=10 (i.e., DPRH-1-10), TIB is poor. STU and ESTU are good. ASP and APT are poor. AWT is poor while TCT is the best. In summary, it is clear that when τ is the same, DPRH with τ′=0.5 achieves higher integrated benefit, higher resource utilization, and higher user satisfaction but a lower allocation speed than DPRH with τ′=1. When τ′ is the same, DPRH with τ=1 achieves higher integrated benefit, higher resource utilization, and higher user satisfaction but lower allocation speed than DPRH with τ=0.5.


## 5.1. Instance Setup

Figure9(a) shows the district in Chaoyang District, Beijing, China, where the historical parking data come from. Figure 9(b) shows the normalized district, of which the length and width are both 1 km. There are five adjacent blocks in the district. Blocks with the same color have the same land use. The green block is for business, the yellow block is for commercial, and the orange block is for residential. The solid circle in each block represents a parking facility. The numbers beneath each solid circle represent the coordinates of each parking facility. The five parking facilities rent parking spaces to CARSP for sharing. The sizes of blocks are also set as Figure 9(b) shows. Table 3 shows the parameters of the instance.Figure 9
District of the instance.
(a)(b)Table 3
Parameters of the instance.
ParametersDescriptionsValueTThe number of time units4320IThe number of parking demands31494JThe number of parking services1800FThe number of parking facilities5dimaxThe maximum acceptable walking distance of parking demandi (m)[100, 700]pimaxThe maximum acceptable parking price of parking demandi (CNY/5 min)[0.5, 1.2]wimaxThe maximum acceptable waiting time of parking demandi (min)[1, 10]pjThe parking price of parking servicej (CNY/5 min)[0.5, 1.2]rjThe short-term renting price of parking servicej (CNY/5 min)0.5rj′The long-term renting price of parking servicej (CNY/5 min)0.1qThe compensation price (CNY/min)0.025ρThe split penalty coefficient (CNY/min)0.001τ0The length of parking time interval (min)5TARThe time threshold to determine whether demands and services are arriving (min)15TAPThe time threshold to determine whether demands and services are approaching (min)30The instance selects historical parking data from 00 : 00 on April 20th, 2018, to 00 : 00 on April 23rd, 2018, so that the overall time horizon is 3 days. The overall time horizon is divided into 4320 time units with length of 1 minute. The parking time interval is set to be 5 minutes.The total number of historical parking demands is 31494. Figures10 and 11 show the start time and end time distribution of parking demands [27]. For each parking demand, the submission time varies within [5, 1440] minutes before its start time. The maximum acceptable walking distance varies within [100, 700] meters. The maximum acceptable parking price varies within [0.5, 1.2] CNY per 5 minutes according to Beijing Parking Charge Standard. The maximum acceptable waiting time varies within [1, 10] minutes.Figure 10
Start time distribution of parking demand.Figure 11
End time distribution of parking demand.The total number of parking services is 1800. Table4 shows the details of parking services. According to land use, parking facilities 1, 2, and 3 provide long-term renting parking services, while parking facilities 4 and 5 provide short-term renting parking services. For each short-term renting parking service, the time window varies within [1, 4320]. The renting price is 0.5 CNY per 5 minutes. The parking price varies within [0.6, 1.2] CNY per 5 minutes. For each long-term renting parking service, the time window is [1, 4320]. The renting price is 0.1 CNY per 5 minutes. The parking price is 0.5 or 0.7 CNY per 5 minutes.Table 4
Details of parking services.
Parking facilityNumber of parking servicesRenting typeRenting price (CNY/5 min)Parking price (CNY/5 min)1400Long-term0.10.52600Long-term0.10.73400Long-term0.10.74200Short-term0.5[0.6, 1.2]5200Short-term0.5[0.6, 1.2]Besides, the compensation price is set to be 0.025 CNY per minute. The arrival time threshold is 15 minutes. The approaching time threshold is 30 minutes.The instance sets thirteen groups to test the performances of different allocation approaches with different allocation models under different allocation periods. Table5 shows the details of the test groups. Group 1 is the FBFS group. Groups 2 to 5 are the RHN groups, in which τ∈0.5,1,5,10 and τ′=0. Groups 6 to 9 are the RHB groups, in which τ∈0.5,1,5,10 and τ′=τ. Groups 10 to 13 are the DPRH groups, in which τ∈0.5,1 and τ′∈5,10.Table 5
Details of the test groups.
Group indexGroup codeAllocation approachAllocation modelsτ (min)τ' (min)1FBFSFBFS———2RHN-0.5RHNNA model0.503RHN-1104RHN-5505RHN-101006RHB-0.5RHBBA model0.50.57RHB-1118RHB-5559RHB-10101010DPRH-0.5-5DPRHNA modelBA model0.5511DPRH-0.5-100.51012DPRH-1-51513DPRH-1-10110The CARSP programs based on FBFS, RHN, RHB, DPRH allocation approaches are all encoded in Visual Studio 2017 using C# language. The software used to solve the allocation problem at each allocation time point is IBM ILOG CPLEX Solver 12.6.3. All computations were performed on a personal computer with Intel Core i5-7200U CPU, 8G RAM, and a 64 bit Windows 10 Operating System.


## 5.2. Instance Results

We set two tests to study the performance of CARSP based on FBFS, RHN, RHB, and DPRH when applying to large-scale real-world instance. Test 1 aims to explore the effects of different allocation approaches. Test 2 aims to explore the effects of different allocation periods.The performances of different groups over three days are shown in Table6.Table 6
Performances of different groups over three days.
Group codeTIB (CNY)STUESTUASPAPT (min)AWT (s)TCT (h)FBFS276239.400.4500.5290.580801.050.060.29RHN-0.5277690.720.4520.5320.573805.2815.150.47RHN-1277370.120.4520.5310.571806.5830.370.42RHN-5278382.680.4540.5330.566808.52158.741.11RHN-10276771.090.4520.5310.566809.70317.210.99RHB-0.5283237.340.4580.5380.583790.8224.8526.84RHB-1284196.220.4590.5390.582792.1541.1812.75RHB-5285339.140.4600.5410.581791.09172.574.89RHB-10284600.370.4590.5400.582790.15337.123.66DPRH-0.5-5282422.160.4570.5370.581791.8216.613.85DPRH-0.5-10280797.810.4550.5360.577795.1015.282.10DPRH-1-5283141.950.4580.5380.582790.3432.953.73DPRH-1-10282115.440.4570.5380.578792.6931.652.04


### 5.2.1. Test 1: Performance of Different Allocation Approaches

Test 1 aims to seek the effects of different allocation approaches. Min-Max normalization is applied to normalize the performance metric values of thirteen groups. In this way, under each performance metric, the strengths and weaknesses of each allocation approach can be demonstrated more clearly. The allocation approach is better if TIB, STU, ESTU, and ASP are higher while APT, AWT, and TCT are lower. Therefore, the normalization equation for the former kind of performance metrics is shown as (23). The normalization equation for the latter kind of performance metrics is shown as (24). Under each performance metric,Max is the maximum of thirteen performance metric values while Min is the minimum. Current is the performance metric value of the current allocation approach, while Current∗ is the normalized performance metric value. Therefore, the allocation approach is better if the normalized performance metric value is higher.(23)Current∗=Current−MinMax−Min,(24)Current∗=Max−CurrentMax−Min.Figure12. Comparisons of FBFS, RHN, RHB, and DPRH.Figure 12
Shows the comparisons of FBFS, RHN, RHB, and DPRH.
(a)(b)(c)(d)(e)For FBFS, the lowest AWT indicates excellent allocation speed. However, the lowest TIB reflects dreadful integrated benefit, the lowest STU and ESTU reflects dreadful resource utilization, and the moderate ASP and APT reflect poor user satisfaction. Meanwhile, FBFS requires the shortest computing time.For RHN, the normalized TIB of all RHN Groups ranges widely, but on the whole, RHN leads to poorly integrated benefit. Similarly, the normalized STU and normalized ESTU of all RHN Groups range widely, but on the whole, RHN results in poor resource utilization. The normalized ASP and normalized APT of all RHN Groups are centralized in the lower half, thus, RHN leads to dreadful user satisfaction. The normalized AWT of all RHN Groups ranges widely, but on the whole, RHN results in good allocation speed. Meanwhile, RHN requires the second shortest computing time.For RHB, the normalized TIB of all RHB Groups are centralized in the upper half, which indicates that RHB results in well integrated benefit. Similarly, the normalized STU and normalized ESTU of all RHB Groups are centralized in the upper half, which indicates that RHB results in good resource utilization. The normalized ASP and normalized APT of all RHB Groups are centralized in the upper half. Meanwhile, RHB results in the highest ASP and APT. Thus RHB results in excellent user satisfaction. The normalized AWT of all RHB Groups ranges widely, but on the whole, RHB leads to dreadful allocation speed. Meanwhile, RHB requires the longest computing time.For DPRH, all normalized performance metrics values are centralized in the upper half. Comparing the thirteen Groups, DPRH results in the highest TIB, STU, and ESTU. Compared with FBFS, DPRH raises TIB by 3.83%, raises STU by 2.65%, and raises ESTU by 2.72%. Therefore, DPRH results in excellent integrated benefits, excellent resource utilization, good user satisfaction, and good allocation speed. Meanwhile, DPRH requires the second-longest computing time.


### 5.2.2. Test 2: Effects of Different Allocation Periods

Test 2 aims to seek the effects of different allocation periods in the same allocation approach and the same allocation model. Allocation periodsτ∈0.5,1,5,10. The normalization (9) and (10) are also applied to demonstrate the strengths and weaknesses of each allocation period more clearly.Figure13 shows the comparisons of different allocation periods in RHN. Figure 14 shows the comparisons of different allocation periods in RHB. Figure 15 shows the comparisons of different allocation periods in DPRH.Figure 13
Comparisons of RHN with different allocation periods.Figure 14
Comparisons of RHB with different allocation periods.Figure 15
Comparisons of DPRH with different allocation periods.In the light of Figure13, in RHN, when allocation period τ=0.5 (i.e., RHN-0.5), TIB, STU, and ESTU are good. Meanwhile, ASP and APT are the best. AWT is the best and TCT is good. When allocation period τ=1 (i.e., RHN-S-1), TIB, STU, and ESTU are poor. ASP and APT are good. AWT is good and TCT is the best. When allocation period τ=5 (i.e., RHN-5), TIB, STU, and ESTU are the best. ASP and APT are poor. AWT is poor and TCT is the worst. When allocation period τ=10 (i.e., RHN-10), TIB, STU, ESTU, ASP, APT, and AWT are the worst while TCT is poor. Clearly, RHN-0.5 performs the best in user satisfaction and allocation speed, while RHN-5 performs the best in integrated benefit and resource utilization. From the perspective of system managers, the integrated benefit is the most concern. However, allocation speed is also vital since it is the representation of system service quality. In light of Table 6, the TIB of RHN-5 is raised by 0.25%, while the AWT of RHN-5 is ten times that of RHN-0.5.In the light of Figure14, in RHB, when allocation period τ=0.5 (i.e., RHB-0.5), TIB, STU, and ESTU are the worst. ASP is the best and APT is good. AWT is the best, but TCT is the worst. When allocation period τ=1 (i.e., RHB-1), TIB, STU, and ESTU are poor. ASP is good but APT is the worst. AWT is good but TCT is poor. When allocation period τ=5 (i.e., RHB-5), TIB, STU, and ESTU are the best. ASP is the worst and APT is poor. AWT is poor while TCT is good. When allocation period τ=10 (i.e., RHB-10), TIB, STU, and ESTU are good. ASP is good, while APT is poor. AWT is poor while TCT is good. Though RHB-5 and RHB-10 perform better than RHN; AWT is a defect that cannot be ignored.In the light of Figure15, in DPRH, when allocation period τ=0.5 and τ′=5 (i.e., DPRH-0.5-5), TIB is good, STU and ESTU are poor. ASP and APT are good. AWT is good while TCT is the worst. When allocation period τ=0.5 and τ′=10 (i.e., DPRH-0.5-10), TIB, STU, ESTU, ASP, and APT are the worst. AWT is the best and TCT is good. When allocation period τ=1 and τ′=5 (i.e., DPRH-1-5), TIB, STU, ESTU, ASP, and APT are the best. AWT is the worst and TCT is poor. When allocation period τ=1 and τ′=10 (i.e., DPRH-1-10), TIB is poor. STU and ESTU are good. ASP and APT are poor. AWT is poor while TCT is the best. In summary, it is clear that when τ is the same, DPRH with τ′=0.5 achieves higher integrated benefit, higher resource utilization, and higher user satisfaction but a lower allocation speed than DPRH with τ′=1. When τ′ is the same, DPRH with τ=1 achieves higher integrated benefit, higher resource utilization, and higher user satisfaction but lower allocation speed than DPRH with τ=0.5.


## 5.2.1. Test 1: Performance of Different Allocation Approaches

Test 1 aims to seek the effects of different allocation approaches. Min-Max normalization is applied to normalize the performance metric values of thirteen groups. In this way, under each performance metric, the strengths and weaknesses of each allocation approach can be demonstrated more clearly. The allocation approach is better if TIB, STU, ESTU, and ASP are higher while APT, AWT, and TCT are lower. Therefore, the normalization equation for the former kind of performance metrics is shown as (23). The normalization equation for the latter kind of performance metrics is shown as (24). Under each performance metric,Max is the maximum of thirteen performance metric values while Min is the minimum. Current is the performance metric value of the current allocation approach, while Current∗ is the normalized performance metric value. Therefore, the allocation approach is better if the normalized performance metric value is higher.(23)Current∗=Current−MinMax−Min,(24)Current∗=Max−CurrentMax−Min.Figure12. Comparisons of FBFS, RHN, RHB, and DPRH.Figure 12
Shows the comparisons of FBFS, RHN, RHB, and DPRH.
(a)(b)(c)(d)(e)For FBFS, the lowest AWT indicates excellent allocation speed. However, the lowest TIB reflects dreadful integrated benefit, the lowest STU and ESTU reflects dreadful resource utilization, and the moderate ASP and APT reflect poor user satisfaction. Meanwhile, FBFS requires the shortest computing time.For RHN, the normalized TIB of all RHN Groups ranges widely, but on the whole, RHN leads to poorly integrated benefit. Similarly, the normalized STU and normalized ESTU of all RHN Groups range widely, but on the whole, RHN results in poor resource utilization. The normalized ASP and normalized APT of all RHN Groups are centralized in the lower half, thus, RHN leads to dreadful user satisfaction. The normalized AWT of all RHN Groups ranges widely, but on the whole, RHN results in good allocation speed. Meanwhile, RHN requires the second shortest computing time.For RHB, the normalized TIB of all RHB Groups are centralized in the upper half, which indicates that RHB results in well integrated benefit. Similarly, the normalized STU and normalized ESTU of all RHB Groups are centralized in the upper half, which indicates that RHB results in good resource utilization. The normalized ASP and normalized APT of all RHB Groups are centralized in the upper half. Meanwhile, RHB results in the highest ASP and APT. Thus RHB results in excellent user satisfaction. The normalized AWT of all RHB Groups ranges widely, but on the whole, RHB leads to dreadful allocation speed. Meanwhile, RHB requires the longest computing time.For DPRH, all normalized performance metrics values are centralized in the upper half. Comparing the thirteen Groups, DPRH results in the highest TIB, STU, and ESTU. Compared with FBFS, DPRH raises TIB by 3.83%, raises STU by 2.65%, and raises ESTU by 2.72%. Therefore, DPRH results in excellent integrated benefits, excellent resource utilization, good user satisfaction, and good allocation speed. Meanwhile, DPRH requires the second-longest computing time.


## 5.2.2. Test 2: Effects of Different Allocation Periods

Test 2 aims to seek the effects of different allocation periods in the same allocation approach and the same allocation model. Allocation periodsτ∈0.5,1,5,10. The normalization (9) and (10) are also applied to demonstrate the strengths and weaknesses of each allocation period more clearly.Figure13 shows the comparisons of different allocation periods in RHN. Figure 14 shows the comparisons of different allocation periods in RHB. Figure 15 shows the comparisons of different allocation periods in DPRH.Figure 13
Comparisons of RHN with different allocation periods.Figure 14
Comparisons of RHB with different allocation periods.Figure 15
Comparisons of DPRH with different allocation periods.In the light of Figure13, in RHN, when allocation period τ=0.5 (i.e., RHN-0.5), TIB, STU, and ESTU are good. Meanwhile, ASP and APT are the best. AWT is the best and TCT is good. When allocation period τ=1 (i.e., RHN-S-1), TIB, STU, and ESTU are poor. ASP and APT are good. AWT is good and TCT is the best. When allocation period τ=5 (i.e., RHN-5), TIB, STU, and ESTU are the best. ASP and APT are poor. AWT is poor and TCT is the worst. When allocation period τ=10 (i.e., RHN-10), TIB, STU, ESTU, ASP, APT, and AWT are the worst while TCT is poor. Clearly, RHN-0.5 performs the best in user satisfaction and allocation speed, while RHN-5 performs the best in integrated benefit and resource utilization. From the perspective of system managers, the integrated benefit is the most concern. However, allocation speed is also vital since it is the representation of system service quality. In light of Table 6, the TIB of RHN-5 is raised by 0.25%, while the AWT of RHN-5 is ten times that of RHN-0.5.In the light of Figure14, in RHB, when allocation period τ=0.5 (i.e., RHB-0.5), TIB, STU, and ESTU are the worst. ASP is the best and APT is good. AWT is the best, but TCT is the worst. When allocation period τ=1 (i.e., RHB-1), TIB, STU, and ESTU are poor. ASP is good but APT is the worst. AWT is good but TCT is poor. When allocation period τ=5 (i.e., RHB-5), TIB, STU, and ESTU are the best. ASP is the worst and APT is poor. AWT is poor while TCT is good. When allocation period τ=10 (i.e., RHB-10), TIB, STU, and ESTU are good. ASP is good, while APT is poor. AWT is poor while TCT is good. Though RHB-5 and RHB-10 perform better than RHN; AWT is a defect that cannot be ignored.In the light of Figure15, in DPRH, when allocation period τ=0.5 and τ′=5 (i.e., DPRH-0.5-5), TIB is good, STU and ESTU are poor. ASP and APT are good. AWT is good while TCT is the worst. When allocation period τ=0.5 and τ′=10 (i.e., DPRH-0.5-10), TIB, STU, ESTU, ASP, and APT are the worst. AWT is the best and TCT is good. When allocation period τ=1 and τ′=5 (i.e., DPRH-1-5), TIB, STU, ESTU, ASP, and APT are the best. AWT is the worst and TCT is poor. When allocation period τ=1 and τ′=10 (i.e., DPRH-1-10), TIB is poor. STU and ESTU are good. ASP and APT are poor. AWT is poor while TCT is the best. In summary, it is clear that when τ is the same, DPRH with τ′=0.5 achieves higher integrated benefit, higher resource utilization, and higher user satisfaction but a lower allocation speed than DPRH with τ′=1. When τ′ is the same, DPRH with τ=1 achieves higher integrated benefit, higher resource utilization, and higher user satisfaction but lower allocation speed than DPRH with τ=0.5.


## 6. Conclusion

This study researched the large-scale dynamic parking allocation problem by proposing a smart parking system CARSP based on a novel rolling horizon allocation DPRH.The “Collection-Allocation-Response” smart parking system (CARSP) is constructed to amply describe trilateral requirements, deeply portray trilateral relationships, and thoroughly realize trilateral data transmission in the dynamic smart parking environment. The Doubly Periodic Rolling Horizon allocation approach (DPRH) is proposed to combine the superiorities of RHN and RHB. The NA and BA models integrate the user’s waiting time and system revenue so as to maximize system integrated benefit from the perspective of both users and system managers.According to the large-scale real numerical instance study, DPRH is superior to FBFS, RHN, and RHB in balancing allocation effect and allocation speed: Though FBFS is unparalleled in allocation speed, DPRH achieves better allocation effect, i.e., the total integrated benefit is raised by 3.83%, resource utilization is raised by 2.7%, user satisfaction is raised by 1.53% with acceptable allocation speed. DPRH reaches nearly the same allocation speed as RHN but leads to a better allocation effect. DPRH achieves nearly the same allocation effect as RHB but improves allocation speed.Future research will focus on the following aspects. Firstly, the allocation approach can be improved to achieve nearly the same allocation speed as FBFS. Secondly, the allocation approach and allocation model can be improved to deal with the unpunctuality of users and owners in a realistic smart parking environment. Thirdly, dynamic pricing can be considered in the allocation models to further improve the allocation effects.



---

*Source: 1373391-2022-05-28.xml*