Marriage Matching-based Instant Parking Spot Sharing in Internet of Vehicles

Zhonghai Zhao1, Student Member, IEEE, Yang Xu1, Member, IEEE, Jia Liu2, Member, IEEE,
Zhao Li1, Member, IEEE, Yulong Shen1, Member, IEEE, and Norio Shiratori3, Life Fellow, IEEE 1School of Computer Science and Technology, Xidian University, Xi’an, China
2Center for Strategic Cyber Resilience Research and Development, National Institute of Informatics, Tokyo, Japan
3Research and Development Initiative, Chuo University, Tokyo, Japan
Email: [email protected], [email protected], [email protected],
[email protected], [email protected], [email protected]

Abstract

The rapid development and integration of automotive manufacturing, sensor, and communication technologies have facilitated the emergence of the Internet of Vehicles (IoV). However, the explosive growing demand for parking spots has become a challenging issue to be addressed in IoV. In this paper, we propose a novel Smart Parking System (SPS) for IoV by applying the matching game approach. Specifically, the proposed SPS consists of three types of entities: drivers, parking spot owners (PSOs), and a certificate authority (CA). Drivers and PSOs send parking requests and parking spot information to the CA, respectively. The CA is responsible for identifying legitimate system users, matching drivers with PSOs, and recording their transaction information. We first design rational utility functions for drivers and PSOs, and then establish preference lists for them based on real-time conditions. With these information, we further develop an improved marriage matching (MM) algorithm to achieve stable matching results for drivers’ requests and parking spot allocation. Simulation results demonstrate that the proposed MM-based SPS not only ensures stable matching results with the objective of distance minimization but also achieves an overall utility close to that of the optimal algorithm.

Index Terms:

Parking spot sharing, Internet of vehicles, marriage matching, matching game, stability.

I Introduction

The rapid development and integration of automotive manufacturing, sensor, and communication technologies have empowered the intelligence and interconnection of vehicles, leading to the emergence of Internet of Vehicles (IoV) as a new paradigm for intelligent transportation systems. However, in the context of urban development, the escalating disparity between the growing number of vehicles and the limited expansion of parking infrastructure has become a significant contributor to urban traffic congestion. Therefore, how to effectively manage urban resources to alleviate the scarcity of parking spots has become an imperative challenge that must to be addressed in IoV [1].

The parking space-sharing methodology holds great potential in improving the utilization of urban parking spots and alleviating traffic congestion in IoV. The fundamental idea is that parking spot owners (PSOs) have the opportunity to share their parking spots during idle periods to earn some profits, while drivers can achieve quick parking based on the instructions provided by the available leased parking space information [2]. The establishment of a parking information platform and the design of parking spot allocation and transaction mechanisms are crucial for implementing rational and efficient parking spot sharing. Consequently, they have received growing attention from both industry and academic communities.

By now, there have been some preliminary research works in the design of parking spot sharing systems [3, 4, 5, 6, 7]. Specifically, Griggs et al.[3] designed a time allocation system for parking spots, taking into account customers’ personal preferences during the matching process. Kim et al.[4] proposed a distributed algorithm to minimize parking costs and balance multiple parking demands. Huang et al.[5] applied federated learning and reinforcement learning to parking spot selection, allowing for rapid sharing and prediction of parking spot information. Wu et al.[6] presented an efficient parking spot search system based on mobile crowdsensing, enabling fast and efficient intelligent parking. More recently, Karaliopoulos et al.[7] developed a temporary parking spot leasing transaction scheme on an online parking reservation platform.

Although the aforementioned studies represent significant advancements in the design of shared parking systems, they either fail to consider the stability of the matching outcomes or overlook the heterogeneity of user preferences. However, in practical applications, stability is an important characteristic for evaluating the matching results, as it ensures the absence of cases where both parties have mutual preferences but are not matched. Moreover, addressing the heterogeneous requirements of different users (e.g., time conflict) is crucial for achieving the subdivision of parking resources and facilitating reasonable allocation, so as to improve social welfare.

Inspired by the above observations, in this paper, we aim to develop a novel smart parking system comprised of drivers, parking spot owners (PSOs), and a certificate authority (CA), leveraging matching game theory to facilitate the efficient sharing of available parking spots. We first design personalized utility functions for drivers and PSOs, and then construct preference lists taking into account the heterogeneity of both the customers’ time requirements and the expected prices. Furthermore, we improve upon the traditional marriage matching algorithm to accommodate scenarios with incomplete preference lists, enabling stable matches between drivers and PSOs. The main contributions of this paper are summarized as follows:

•

We develop a smart parking system utilizing the principles of matching game theory. This system empowers drivers to accurately and reliably match with parking spots that best suit their specific needs and preferences, while enabling PSOs to profitably rent out their available parking spots through this system.
•

We design personalized utility functions for drivers and PSOs, which can accurately characterize their interactions. Based on this, we create tailored preference lists for drivers and PSOs, allowing customers to dynamically adjust their preference vectors to achieve optimal parking spot matches based on their real-time conditions.
•

We improve the traditional marriage matching (MM) algorithm and apply it to the driver-parking spot matching scenario. Simulation results show that the proposed MM-based smart parking system not only guarantees the stability of matching results but also achieves overall utility close to the optimal algorithm.

The remainder of this paper is organized as follows. Section II introduces the system overview and problem formulation. We elaborate on the marriage matching-based parking spot sharing algorithm design in Section III. Section IV presents the simulation results, followed by the conclusion in Section V.

II System Overview and Problem Formulation

We consider a smart parking system (SPS) in a vast urban area with multiple drivers and PSOs who can provide available parking spots. PSOs aim to earn profits during their free time by renting out their parking spots, while drivers seek to find available spots for parking their vehicles. In addition, we deploy a CA in the cloud to provide identity authentication and recognition services, as shown in Fig. 1.

II-A System Overview

Refer to caption — Figure 1: System Model.

1) System Initialization: The drivers and PSOs become legitimate entities after registering with CA in the SPS, and the CA initializes the basic information of drivers and PSOs. Let $D_{i}\in\mathcal{D}$ represent the $i$ -th driver and $\mathcal{D}$ is the set of drivers. Let $P_{j}\in\mathcal{P}$ represent the $j$ -th parking spot and $\mathcal{P}$ is the set of parking spots. The locations of driver $D_{i}$ and parking spot $P_{j}$ are denoted as $C_{D_{i}}$ and $C_{P_{j}}$ , respectively. The expected parking time vector for driver $D_{i}$ is denoted as $\alpha_{D_{i}}=\left[a_{1},a_{2},\cdots,a_{H}\right]$ , where each element represents a time interval of $24/H$ hours. For example, when $H=48$ , $a_{1}$ corresponds to the time interval 00:00-00:30, $a_{2}$ corresponds to the time interval 00:30 $-$ 01:00, and so on. Each element of $\alpha_{D_{i}}$ takes value $0$ or $1$ , i.e., when $a_{h}=1$ , driver $D_{i}$ needs parking, and when $a_{h}=0$ , there is no parking demand. Similarly, the sharable time of parking spot $P_{j}$ is denoted as a vector $\beta_{P_{j}}=\left[b_{1},b_{2},\cdots,b_{H}\right]$ . If $b_{h}=1$ , it indicates that the parking spot will not be rented out at this interval, and if $b_{h}=0$ , it indicates that the parking spot is available at this interval.

2) Send Parking Request Message: Once accomplishing the system initialization, a driver will send the following message to CA:

Message_{D_{i}}=D_{i}||W_{D_{i}}(M_{\mathcal{P}})||W_{D_{i}}(R_{\mathcal{P}})||C_{D_{i}}||\alpha_{D_{i}},

(1)

where $W_{D_{i}}(M_{\mathcal{P}})$ represents the maximum price per unit of time that driver $D_{i}$ is willing to pay for a parking spot in $\mathcal{P}$ , and $W_{D_{i}}(R_{\mathcal{P}})$ represents the minimum reputation requirement that driver $D_{i}$ has for a parking spot in $\mathcal{P}$ .

3) Send parking spot sharing message: Each PSO submits the following message to CA:

Message_{P_{j}}=P_{j}||M_{P_{j}}||W_{P_{i}}(R_{\mathcal{D}})||C_{P_{j}}||\beta_{P_{j}},

(2)

where $M_{P_{j}}$ is the rental fee for a unit time specified by the PSO, and $W_{P_{i}}(R_{\mathcal{D}})$ refers to the minimum reputation requirement that parking spot $P_{j}$ imposes on a driver in $\mathcal{D}$ .

4) Generate Preference Lists: After both parties submit their information, the CA will generate corresponding preference lists for them according to their heterogeneous preferences.

5) Matching Result Output and Data Update: The SPS applies a matching game approach (shown in the next section) to match the set of drivers with the set of parking spots, generating a matching result. Both parties conduct transactions according to the agreed-upon result. After the transaction is completed, they score each other, and the system updates their reputation values $R_{D_{i}}$ and $R_{P_{i}}$ based on the scores for the next round of matching reference. Specifically, the reputation value $R_{D_{i}}$ is updated by

R_{D_{i}}=(1-\gamma)R^{\prime}_{D_{i}}+\gamma\cdot r_{i,j},

(3)

where $\gamma$ is a constant that satisfies $0\leq\gamma\leq 1$ , $r_{i,j}$ is the evaluation score assigned by $P_{j}$ to $D_{i}$ in the current transaction, and $R^{\prime}_{D_{i}}$ is the last reputation value of $D_{i}$ . Similarly, the reputation value $R_{P_{j}}$ for a parking spot is updated by

R_{P_{j}}=(1-\delta)R^{\prime}_{P_{j}}+\delta\cdot r_{j,i},

(4)

where $\delta\in(0,1)$ is a constant parameter, $r_{j,i}$ is the evaluation score assigned by $D_{i}$ to $P_{j}$ in the current transaction, and $R^{\prime}_{P_{j}}$ is the last reputation value of $P_{j}$ .

II-B Problem Formulation

We consider that in IoV, drivers are more inclined to look for parking spots that are closer. Likewise, PSOs are also more inclined to rent out vacant parking spots to drivers who are closer in proximity (this helps to reduce the idle time of parking spots). We use $\mathcal{F}_{D_{i},P_{j}}$ to denote the path length between the coordinate points of $D_{i}$ and $P_{j}$ , i.e., $\mathcal{F}_{D_{i},P_{j}}=F(C_{D_{i}},C_{P_{j}})$ , where the function $F(\cdot)$ calculates the distance between two coordinates. Therefore, the matching problem between drivers and PSOs in our smart parking system can be formulated as the following optimization problem:

\begin{split}\min\,\,&\sum_{D_{i}\in\mathcal{D},P_{j}\in\mathcal{P}}\mathcal{F}_{D_{i},P_{j}}.\\ {\rm s.t.}\,\,&W_{D_{i}}(M_{\mathcal{P}})\geqslant M_{P_{j}},\forall_{D_{i}\in\mathcal{D}},\forall_{P_{j}\in\mathcal{P}}\\ &W_{D_{i}}(R_{\mathcal{P}})\leqslant R_{P_{j}},\forall_{D_{i}\in\mathcal{D}},\forall_{P_{j}\in\mathcal{P}}\\ &W_{P_{i}}(R_{\mathcal{D}})\leqslant R_{D_{i}},\forall_{D_{i}\in\mathcal{D}},\forall_{P_{j}\in\mathcal{P}}\\ &\alpha_{D_{i}}\cdot\beta_{P_{j}}=0,\forall_{D_{i}\in\mathcal{D}},\forall_{P_{j}\in\mathcal{P}}\end{split}

(5)

III Marriage Matching-based Algorithm Design

In this section, we first introduce the main concept of matching game theory. Then, we define the preference functions for drivers and PSOs and explain the details of creating preference lists for both entities in practice. Furthermore, we propose a stable driver-PSO matching scheme based on the improved marriage matching approach.

III-A Matching Game Concept

Definition 1: The outcome of the driver-PSO scheduling is a matching relation $\mu$ , which is a function such that $\mathcal{D}\cup\mathcal{P}\rightarrow 2^{\mathcal{D}\cup\mathcal{P}}$ satisfies the following conditions:

•

$\mu(D_{i})\subseteq\mathcal{P}$ such that $W_{D_{i}}(M_{\mathcal{P}})\geqslant M_{P_{j}}$ , $W_{D_{i}}(R_{\mathcal{P}})\leqslant R_{P_{j}}$ , and $\alpha_{D_{i}}\cdot\beta_{P_{j}}=0$ for $\forall D_{i}\in\mathcal{D}$ and $\forall P_{j}\in\mathcal{P}$ .
•

$\mu(P_{j})\subseteq\mathcal{D}$ such that $W_{P_{i}}(R_{\mathcal{D}})\leqslant R_{D_{i}}$ and $\alpha_{D_{i}}\cdot\beta_{P_{j}}=0$ for $\forall D_{i}\in\mathcal{D}$ and $\forall P_{j}\in\mathcal{P}$ .
•

$D_{i}\in\mu(P_{j})\Longleftrightarrow\mu(D_{i})=P_{j}$ for $\forall D_{i}\in\mathcal{D}$ and $\forall P_{j}\in\mathcal{P}$ .

Definition 2: Let $\mathcal{M}$ denote a matching result in SPS, which is a subset of $\mu$ . We say that $D_{1}$ is assigned to $P_{2}$ or $P_{2}$ is assigned to $D_{2}$ if the pair $(D_{1},P_{2})\in\mathcal{M}$ . Let $\mathcal{H}=\mathcal{D}\times\mathcal{P}$ , a pair $(D_{i},P_{j})\in\mathcal{H}\setminus\mathcal{M}$ blocks $\mathcal{M}$ , or $(D_{i},P_{j})$ is a blocking pair for $\mathcal{M}$ , if the following conditions are satisfied:

•

$D_{i}$ is unassigned or prefers $P_{j}$ to $\mathcal{M}(D_{i})$ .
•

$P_{j}$ is unassigned or prefers $D_{i}$ to $\mathcal{M}(P_{j})$ .

Definition 3: The matching relation $\mu$ is considered stable if (1) there are no blocking pairs, and (2) except for a few unmatched drivers, the majority of drivers in set $\mathcal{D}$ are assigned to parking spaces in set $\mathcal{P}$ .

III-B Preference Functions of Drivers and PSOs

In the smart parking system, we consider that drivers in need of parking have a preference for the nearest available parking spot, which allows them to minimize both the time and fuel costs associated with finding a suitable parking spot. Therefore, for each driver $D_{i}\in\mathcal{D}$ , there is a strict transitive preference relation $L_{D_{i}}(\mathcal{P})$ on the set of $\mathcal{P}$ regarding parking spots. The preference relation $P_{j}\succ_{D_{i}}P_{k}$ means that driver $D_{i}$ prefers parking spot $P_{j}$ over parking spot $P_{k}$ . Based on the above definition, we can define the driver’s preference function as follows:

P_{j}\succ_{D_{i}}P_{k}\Leftrightarrow L_{D_{i}}(P_{j})<L_{D_{i}}(P_{k}),

(6)

where

L_{D_{i}}(P_{j})=\mathcal{F}_{D_{i},P_{j}}.

(7)

The preference list for each parking spots $P_{j}\in\mathcal{P}$ is also based on distance because the shorter the distance, the faster the parking spot can execute transactions, reducing idle time and increasing profits. Similarly, the preference function for parking spots can be expressed as follows:

D_{i}\succ_{P_{j}}D_{k}\Leftrightarrow L_{P_{j}}(D_{i})<L_{P_{j}}(D_{k}),

(8)

where

L_{P_{j}}(D_{i})=\mathcal{F}_{P_{j},D_{i}}.

(9)

III-C Preference List Generation

We summarized in Algorithm 1 how to create a preference list for each driver based on the real-time system conditions. The algorithm takes all registered parking spots in the city as input and outputs a preference list $L(D_{i})$ for each driver $D_{i}$ . Algorithm 1 first iterates through each parking spot (line 1) and then checks whether the parking spot and driver $D_{i}$ satisfy the constraints in the optimization problem (5) (line 3). Parking spaces that meet the constraints are added to the list $L(D_{i})$ . Finally, the $L(D_{i})$ list is sorted in ascending order according to expression (7) (line 8).

Algorithm 1 Driver Preference List Generation.

1:Registered parking spot set

\mathcal{P}

2:Preference list

L(D_{i})

of driver

D_{i}

;

3:while there are non-visited parking spots in

\mathcal{P}

4: Select a non-visited

P_{j}

and mark it as visited;

5: if

D_{i}

and

P_{j}

meet the constraints specified in (5) then

6: Record the distance

\mathcal{F}_{D_{i},P_{j}}

between

D_{i}

and

P_{j}

;

7: end if

8:end while

9:Use expression (7) to rank the parking spots and store the results in

L(D_{i})

;

10:return

L(D_{i})

;

Similarly, we can generate a preference list $L(P_{j})$ for each PSO, as summarized in Algorithm 2.

Algorithm 2 PSO Preference List Generation.

1:Registered driver set

\mathcal{D}

2:Preference list

L(P_{j})

of parking spot

P_{j}

;

3:while there are non-visited drivers in

\mathcal{D}

4: Select a non-visited driver

D_{i}

and mark it as visited;

5: if

P_{j}

and

D_{i}

meet the constraints specified in (5) then

6: Record the distance

\mathcal{F}_{P_{j},D_{i}}

between

P_{j}

and

D_{i}

;

7: end if

8:end while

9:Use expression (9) to rank the drivers and store the results in

L(P_{j})

;

10:return

L(P_{j})

;

III-D Improved Marriage Matching Algorithm

Note that from the process of constructing the preference list, it can be observed that the generated preference list is incomplete. In other words, for different drivers, the set of parking spots that can be matched may vary, and vice versa. To address this issue, we will design a solution based on the Gale-Shapley stable marriage matching algorithm [8], which can accommodate incomplete preference lists.

We consider the driver as the party initiating the request and prioritize the driver’s interest. Therefore, we iterate through the set of drivers $\mathcal{D}$ and send matching requests to parking spots in order of decreasing preference within each driver’s preference list.

In Fig 2, we observe that without loss of generality, $D_{1}$ is chosen as the first driver. According to $D_{1}$ ’s preference list, a request is made for the second parking spot $P_{2}$ . Since $P_{2}$ has not been matched yet, a temporary pairing is made between $D_{1}$ and $P_{2}$ . Next, when driver $D_{2}$ is selected, he sends a request to the parking lot set based on his preference list. Similar to the request made by $D_{1}$ , $D_{2}$ is temporarily paired with the first parking spot $P_{1}$ . When $D_{3}$ is selected, it is found that the first parking spot $P_{2}$ in $D_{3}$ ’s preference list has already been assigned to $D_{1}$ . However, in $P_{2}$ ’s preference list, $D_{3}$ has a higher priority than $D_{1}$ . According to Definition 2, $(D_{3},P_{2})$ forms a blocking pair. Therefore, to eliminate the blocking pair, $D_{1}$ is unpaired from $P_{2}$ (and will continue requesting the next parking spot $P_{1}$ in the next round), while $P_{2}$ is temporarily paired with $D_{3}$ . Similarly, in $D_{4}$ ’s turn, it is found that $D_{2}$ and $P_{1}$ have already been paired. Upon checking $P_{1}$ ’s preference list, it is discovered that $D_{2}$ has a higher priority than $D_{4}$ , and thus $D_{4}$ ’s request fails, and he continues to request a parking spot in the next round. If a driver’s preference list has been fully traversed and no parking spot has been found for a pairing, it is considered a failure. Algorithm 3 provides specific implementation details. The variables $\left|\mathcal{D}\right|$ and $\left|\mathcal{P}\right|$ represent the number of drivers and the number of parking spots in the same area, respectively.

Algorithm 3 PSO Preference List Generation.

\mathcal{D}

\mathcal{P}

2:matching result set

\mathcal{M}

3:Initial Phase: An empty circular queue

que

is initialized with all elements of set

\mathcal{D}

, matching result set

\mathcal{M}

initialized as empty, the variable

n

is initialized to 0;

4:for i = 1:

|\mathcal{D}|

5: Build the preference list

L(D_{i})

through algorithm 1

6:end for

7:for j = 1:

|\mathcal{P}|

8: Build the preference list

L(P_{j})

through algorithm 2

9:end for

10:while

n\neq

|\mathcal{D}|

11: Pop a driver from

que

D_{i}

;

12: Look the next parking lot

P_{j}

in the

D_{i}

’s preference list;

13: if

\exists P_{j}

then

14: if

\exists\mathcal{M}(P_{j})

then

15: if

D_{i}

is more preferences than the old matched driver

\mathcal{M}(P_{j})

P_{j}

’s preference list

L_{(}P_{j})

then

16: Remove the old pair

(\mathcal{M}(P_{j}),P_{j})

from

\mathcal{M}

, a new pair

(D_{i},P_{j})

add to

\mathcal{M}

. The old driver is pushed into the

que

;

17: else

18: Request failed,

D_{i}

is pushed into the

que

19: end if

20: else

21: A new pair

(D_{i},P_{j})

add to

\mathcal{M}

22:

n++

23: end if

24: else

25:

n++

26: end if

27:end while

28:return

\mathcal{M}

;

After several rounds of matching, we will get the final matching result for the specific example above $(D_{1},P_{1}),(D_{2},P_{3}),(D_{3},P_{2}),(D_{5},P_{4})$ , and $D_{4}$ fails to match.

Proposition 1

For algorithm 3, the proposed method based on a stable marriage matching algorithm can converge and obtain stable matching results. Besides, as for the performance, the running time of the implementation can achieve $\mathcal{O}(\left|\mathcal{D}\right|\times\left|\mathcal{P}\right|)$ , where $(\left|\mathcal{D}\right|\times\left|\mathcal{P}\right|)$ denotes all the possible matching pairs.

Proof:

Let $\mathcal{M}$ be an instance of SPS matching. The stable pairs in $\mathcal{M}$ can be found in $\mathcal{O}(\left|\mathcal{D}\right|)$ time. The stable matchings in $\mathcal{M}$ can be listed in $\mathcal{O}(\left|\mathcal{P}\right|)$ time per matching, after $\mathcal{O}(\left|\mathcal{D}\right|)$ preprocessing time. Therefore, the overall running time can achieve $\mathcal{O}(\left|\mathcal{D}\right|\times\left|\mathcal{P}\right|)$ . The corresponding proof can be found in [9] and [10] in detail. ∎

IV Simulation Results

In this section, we evaluated the efficiency of our proposed matching algorithm. We compared its performance with that of greedy matching and random matching and also compared our proposed matching method with the theoretically optimal algorithm.

Random matching means that for a selected driver, a parking spot is randomly selected from his preference list for matching. If the parking spot is unmatched, the driver is matched with it; if the parking spot is matched and is greater than the maximum random count then the driver fails the match and continues to select the next driver, otherwise, the parking spot is re-randomized and matched again. Since preference lists vary in length and the matching result depends on the order of the selected drivers, to have as many pairs of matches as possible, we first sort the list of drivers in ascending order of preference lists and allow the maximum number of randoms for the same driver to equal its list length.

Greedy matching algorithm is based on the random matching algorithm sorting, front to back to select the driver, for this driver and then priority from the preference list of the first to take out the parking lot, if the parking lot has not yet matched, the driver and parking spot to match, if the parking spot has been matched, the driver give up this parking spot, continue to query the second parking spot in the preference list, cycle and repeat, if the final still can not find a parking spot, then the driver match failed.

To achieve the theoretical maximum utility, we use the Hungarian algorithm[11], which aims to find the sum of the weights on the edges that maximize while making as many points match as possible in a bipartite graph with weighted edges. In this article, we need to process distances. We subtract the actual distance from the distance upper bound and then perform the optimal bipartite matching on the result, and the resulting matching is the one that minimizes the total distance.

We randomly generate the distance $\mathcal{F}_{D_{i},P_{j}}$ between parking spots and drivers between $\left[0,5\right]$ km, and the edges between drivers and parking spots are randomly generated based on the percentage of their relationship $\eta_{\mathcal{E}}=\frac{\left|\mathcal{E}\right|}{\left|\mathcal{E}_{max}\right|}$ , where $\left|\mathcal{E}\right|$ is the number of actual relationships in a match and the maximum theoretical number of relationships $\left|\mathcal{E}_{max}\right|$ is equal to $\left|\mathcal{D}\right|\cdot\left|\mathcal{P}\right|$ . The edge weight is the distance between the driver and the parking spot. Based on this, we generate preference lists for both drivers and parking spots.

First, we discuss the impact of increasing the data scale on the total distance under the condition of an equal number of drivers and parking spots. Here we set the $\eta_{\mathcal{E}}=20\%$ , and the results are shown in Fig. 3. We enumerate cases where the number of drivers or parking spots increased from 50 to 500. As the data size increased, the random algorithm’s total distance grew much faster than that of the greedy algorithm, MM algorithm, and KM algorithm. The next fastest growth rate was the greedy algorithm. Our algorithm’s final total distance was second only to the optimal algorithm.

In Fig. 4, we set the number of drivers and parking spots to be 250 each and obtained trend lines for the number of blocking pairs as the $\eta_{\mathcal{E}}$ increases from 5% to 100% using four different algorithms.

In MM algorithm, it can be seen that the number of blocking pairs is always zero, while in the KM algorithm, there are blocking pairs between 100 and 150. It can be seen that the optimal matching algorithm for bipartite graphs is not stable. However, satisfying the matching between drivers and parking spots is an important means to improve social well-being. Therefore, the MM algorithm makes certain sacrifices in achieving matching stability to minimize distance.

During the simulation process, we found that the matching algorithm in this paper is less sensitive to the $\eta_{\mathcal{E}}$ . Therefore, by designing experiment Figure 5, we discuss the trend of the total distance of four matching algorithms as the $\eta_{\mathcal{E}}$ increases from 5% to 100% when the number of drivers is 250, the ratio of drivers to parking spots remains at $1:1$ , and the distance between drivers and parking spots is initialized between [0,100] km.

From the Fig. 5, it can be seen that the algorithm in this paper and the greedy algorithm are both very close to the optimal algorithm in terms of matching results. The random matching algorithm performs the worst, with a total distance much larger than the other algorithms. By observing the distance curve of the algorithm in this paper, it can be found that when the $\eta_{\mathcal{E}}$ is higher than 20%, the total distance of the matching result tends to be horizontal but decreases slowly. This is because when there are more contacts, there are more matching objects for both drivers and parking spots with shorter distances. However, for the part below 20%, the total distance will increase but still be smaller than that of the random algorithm. Therefore, even when there are relatively few available parking spots (low relationship percentage), this algorithm can still achieve a relatively low overall total distance.

TABLE I: Algorithm Running Time Comparison

Algorithm	Data Scale
Algorithm	100	200	300	400	500
random	0.0012	0.0026	0.0037	0.0053	0.0070
greedy	0.0016	0.0040	0.0050	0.0072	0.0094
MM	0.0061	0.0209	0.0460	0.0908	0.1643
KM	1.0984	1.6678	11.2773	16.5195	44.1794
The unit of time is second.

In TABLE I, we simulated the running time of four algorithms. We set the number of drivers from 100 to 500, with the same number of parking spots as drivers and $\eta_{\mathcal{E}}$ set to 20%. The data in Table 1 was obtained accordingly. It is worth noting that when the number of drivers reaches 500 (the total number of parking spots and drivers is 1000), the MM algorithm matching time reaches about 0.2s. However, the KM algorithm, which can achieve the shortest distance, requires approximately 44.2s to complete the matching. In a system that requires real-time matching, the system’s response time directly affects user experience. Although the KM algorithm can obtain the optimal matching result, it spends a lot of time, which is not worthwhile.

V Conclusion

In this paper, we design SPS to provide an idea for the rational allocation of shared parking spot resources. First, we analyzed the urgent demand for resource sharing in the current social environment and proposed a smart parking system model, then designed the utility functions of drivers and parking spots according to the actual situation. And then optimized our driver parking spot matching algorithm based on the original marriage matching algorithm. Finally, the performance of the modified algorithm is verified by experimental simulation.

References

[1] M. Zhu, X.-Y. Liu, F. Tang, M. Qiu, R. Shen, W. Shu, and M.-Y. Wu, “Public vehicles for future urban transportation,” IEEE Trans. Intell. Transp. Syst., vol. 17, no. 12, pp. 3344–3353, 2016.
[2] L. Sun, S. Sun, and X. Yu, “Paa: A blockchain-based parking assistance alliance with user preference,” IEEE Trans. Intell. Transp. Syst., 2022.
[3] W. Griggs, J. Y. Yu, F. Wirth, F. Häusler, and R. Shorten, “On the design of campus parking systems with qos guarantees,” IEEE Trans. Intell. Transp. Syst., vol. 17, no. 5, pp. 1428–1437, 2015.
[4] O. T. T. Kim, N. H. Tran, C. Pham, T. LeAnh, M. T. Thai, and C. S. Hong, “Parking assignment: Minimizing parking expenses and balancing parking demand among multiple parking lots,” IEEE Trans. Autom. Sci. Eng., vol. 17, no. 3, pp. 1320–1331, 2019.
[5] X. Huang, P. Li, R. Yu, Y. Wu, K. Xie, and S. Xie, “Fedparking: A federated learning based parking space estimation with parked vehicle assisted edge computing,” IEEE Trans. Veh. Technol., vol. 70, no. 9, pp. 9355–9368, 2021.
[6] D. Wu, Z. Zeng, F. Shi, W. Yu, T. Wu, and Q. Liu, “Human as a service: Towards resilient parking search system with sensorless sensing,” IEEE Trans. Intell. Transp. Syst., vol. 23, no. 8, pp. 13 863–13 877, 2022.
[7] M. Karaliopoulos, O. Mastakas, and W. K. Chai, “Matching supply and demand in online parking reservation platforms,” IEEE Trans. Intell. Transp. Syst., vol. 24, no. 3, pp. 3182–3193, 2023.
[8] D. Gale and L. S. Shapley, “College admissions and the stability of marriage,” Amer. Math. Monthly, vol. 120, no. 5, pp. 386–391, 2013.
[9] I. P. Gent and P. Prosser, “An empirical study of the stable marriage problem with ties and incomplete lists,” in Proc. 15th Eur. Conf. Artif. Intell., 2002, pp. 141–145.
[10] K. Iwama and S. Miyazaki, “A survey of the stable marriage problem and its variants,” in Proc. Int. Conf. Informat. Educ. Res. Knowl. Circulating Soc. (ICKS), 2008, pp. 131–136.
[11] H. W. Kuhn, “The hungarian method for the assignment problem,” Nav. Res. Logistics Quart., vol. 2, no. 1-2, pp. 83–97, 1955.