A many-to-many matching method considering priority for shared private idle parking spaces and demanders

Abstract

There has been widespread and growing concern about parking. This paper attempts to provide decision support for a shared parking system to reduce parking difficulty. We study a many-to-many matching problem between shared private idle parking spaces and their demanders. A novelty is that the demanders are allowed to use different parking spaces successively in parking relocation service support. This can further reintegrate the idle time of the parking spaces and improve their utilization rate. A multi-objective optimization model is constructed to maximize the number of matched demanders, the total priority of the parking spaces, and the total priority of the demanders. More importantly, the priorities of the parking spaces and the demanders are innovatively considered. Each of the parking spaces and the demanders is given a priority for the matching and the priority of a parking space or a demander will be increased if the parking space or demander rarely gets matched successfully. This helps reduce the withdrawal of parking spaces and the demanders from the parking platform. In addition, an NSGA-II algorithm is designed to solve the model efficiently. Finally, the feasibility of the proposed method is illustrated via an example.

Keywords

Sharing economy shared private idle parking space many-to-many matching parking priority improved NSGA-II algorithm

1 Introduction

Parking takes on growing importance in urban planning mainly as car ownership and car use keep growing while urban space for parking becomes scarcer [1].

On the whole, the supply of parking spaces is far from adequate to meet demand. For example, the peak and average parking saturation in the surveyed market areas are respectively 1.66 and 0.99, which demonstrates that the supply of parking spaces in the market areas is not sufficient to meet parking demands in central Shanghai [2]. According to statistics, the ratio of parking spaces to private cars is 0.8 : 1 in large cities and 0.5 : 1 in small and mid-sized cities, which are far lower than those in developed countries with 1.3 : 1 [3]. As such, if the balance between the supply and the demand of parking spaces cannot be redressed, problems such as long-term cruising for parking spaces, traffic congestion, and environmental pollution will arise in cities. [4] found that all the vehicles in Chicago need to travel an extra 63 million miles per year to search for parking spaces, which generates an extra 48000 tons of carbon dioxide. In addition, [5] showed that 30% of cars on the road are cruising to find parking spaces, which takes an average of 7.8 minutes per car.

Although parking spaces in China are in short supply, a lot of privately owned or long-term rental parking spaces often stand idle in cities [6]. For example, a private parking space will be idle after its owner drives to work. According to “2015 Internet Plus Urban Smart Parking Index Research Report (in Chinese)”, the idle parking spaces in big cities Beijing, Shanghai, Guangzhou, and Shenzhen account for 44.6% of the total parking spaces while the parking spaces in these cities have an average vacancy rate of 50%.

In the context of the sharing economy, the option of shared private idle parking spaces emerges. Shared private idle parking spaces mean using exiting gaps or spaces intended for parking vehicles when owners are not using them [7]. Using the idea of sharing to counteract the imbalance between the supply and the demand of parking spaces, we can integrate scattered parking spaces and improve their usage to ease the parking problem.

With the rapid development of the Internet, online sharing parking platforms provide a matching service for shared private idle parking spaces and demanders, enabling the sharing of private idle parking spaces. At present, there are two ways to match the parking spaces with their demanders. On the one hand, demanders should select parking spaces by themselves. On the other hand, platforms should assign parking spaces to demanders in a centralized manner. The former collects the scattered parking spaces and presents the information in the form of lists for demanders’ reference. For example, sharing platforms such as “PP Parking” and “Parking Master” purchase the rights to use parking spaces for a time, and rent them out to their demanders. Then, demanders choose the parking spaces by themselves to park. If the sharing platform adopts the former way to manage the parking spaces, it will be time-consuming for demanders to find acceptable parking spaces. For one thing, demanders have to take some seeking and comparing parking spaces by themselves. For another, demanders have to keep an eye out for available parking spaces to appear if no parking spaces are currently available. In addition, the platforms will find it difficult to attain a global optimal scheme over the whole planning horizon, which is not conducive to making the most of the parking spaces. In the latter way, the platforms allocate the parking spaces to the demanders uniformly according to their requirements such as parking location, and parking time. This method can save demanders’ time spent in choosing parking spaces, and improve the usage of the parking spaces as much as possible by attaining a global optimal scheme. Research on matching the parking spaces with the demanders via the latter way has attracted scholars’ attention. For example, [7] studied the problem of maximizing the sharing platform profit in the latter way. However, these studies are preliminary, and there are still some related problems worth studying. For example, providing the demanders with parking relocation service or giving the parking space owner and the demander priorities when matching are ignored.

Therefore, how to determine a matching scheme for the parking spaces and demanders in the latter way, according to the submitted information, to improve the utilization rate of the parking spaces and the matching rate of high-priority users, is a problem (hereinafter referred to as the parking space-demander matching problem) worthy of study. In this paper, priorities are considered to motivate frustrated demanders who have not gained parking spaces and wait for the next allocation rather than withdraw from the parking platform. Also, priorities are considered to encourage the owners of the parking spaces to keep sharing the parking spaces even if they have not been matched after waiting for a time. Therefore, we construct a many-to-many matching model between the parking spaces and their demanders. This model aims at improving the travel efficiency of demanders and the utilization rate of parking spaces.

This paper tries to provide model and algorithm support for the urban planning community and parking managers to establish powerful shared parking platforms, which widely collect private idle parking spaces and revitalize them. This can not only improve the operational efficiency and the service quality of shared parking but also help reduce the traveling distances, energy consumption, and carbon dioxide emissions involved in finding parking spaces to ease traffic congestion and protect the environment [1]. Further, it helps the urban planning community to achieve smart parking management in building a smart city.

This paper proceeds as follows: Section 2 reviews the related literature. Section 3 describes the problems examined. Section 4 constructs a multi-objective optimization model for matching the parking spaces with their demanders. The improved NSGA-II algorithm is investigated in Section 5 to solve the model and the matching scheme is determined. An illustrative example is presented to demonstrate the applicability of the proposed method in Section 6. Finally, Section 7 summarizes the applications of the proposed approach, and managerial insights for decision and outlines future research directions.

2 Literature review

With the development of the sharing economy, many scholars have begun to pay attention to the matching problems between parking spaces and their demanders. According to the type of parking spaces, this section reviews the existing research. Previous studies on shared private idle parking spaces are summarized in Table 1.

Table 1
Literature on shared private idle parking spaces’ matching

Author Known information Objective Tool/Model

Ding et al. (2016) [6] Demanders’ preference factors for shared private idle parking spaces Minimization of the cruise time and evaluation index Weighted TOPSIS model

Xu et al. (2016) [8] Demanders’ preference for shared private idle parking spaces and the acceptable prices; the locations and the free time of the parking spaces Pareto optimal matching scheme Top trading cycle mechanism

Xiao et al. (2018) [9] Demanders’ bidding prices, priority levels, and the required time; the bidding prices, priority levels, and the rental time of shared private idle parking spaces Maximization social welfare Bilateral auction

Shao et al. (2016) [7] The number and the rental time of shared private idle parking spaces; demanders’ requirement time; the prices paid to owners and the prices charged to demanders Maximization of sharing platform’s profit Binary integer linear programming

Guo et al. (2016) [10] Demanders’ arrival and departure behaviors Provide decision support for maximizing sharing platform profit Decision support system

Chou et al. (2018) [11] Demanders’ arrival behaviors Provide decision support for maximizing sharing platform profit Decision support system

Jiang et al. (2021) [12] Demanders’ walking distance and parking price Maximizing the satisfaction degree of demanders, the satisfaction degree of private idle parking slot owners, and the profits of the platform Binary integer linear programming

Tang et al. (2022) [13] Demanders’ parking time intervals, walking distances, and parking rates Maximizing utilization rate of shared parking slots Binary integer linear programming

Author	Known information	Objective	Tool/Model
Ding et al. (2016) [6]	Demanders’ preference factors for shared private idle parking spaces	Minimization of the cruise time and evaluation index	Weighted TOPSIS model
Xu et al. (2016) [8]	Demanders’ preference for shared private idle parking spaces and the acceptable prices; the locations and the free time of the parking spaces	Pareto optimal matching scheme	Top trading cycle mechanism
Xiao et al. (2018) [9]	Demanders’ bidding prices, priority levels, and the required time; the bidding prices, priority levels, and the rental time of shared private idle parking spaces	Maximization social welfare	Bilateral auction
Shao et al. (2016) [7]	The number and the rental time of shared private idle parking spaces; demanders’ requirement time; the prices paid to owners and the prices charged to demanders	Maximization of sharing platform’s profit	Binary integer linear programming
Guo et al. (2016) [10]	Demanders’ arrival and departure behaviors	Provide decision support for maximizing sharing platform profit	Decision support system
Chou et al. (2018) [11]	Demanders’ arrival behaviors	Provide decision support for maximizing sharing platform profit	Decision support system
Jiang et al. (2021) [12]	Demanders’ walking distance and parking price	Maximizing the satisfaction degree of demanders, the satisfaction degree of private idle parking slot owners, and the profits of the platform	Binary integer linear programming
Tang et al. (2022) [13]	Demanders’ parking time intervals, walking distances, and parking rates	Maximizing utilization rate of shared parking slots	Binary integer linear programming

[6] put forward an idea for meeting growing parking demand by maximizing the usage of the parking spaces. These authors calculated an evaluation index according to demanders’ preference factors and determined the best parking position by using a weighted TOPSIS model. [8] discussed the allocation of parking spaces during normal working hours in a large city and a Pareto optimal matching result can be obtained via the proposed PC-TTCC mechanism. [9] proposed two real double-auction mechanisms for the problem of parking slot sharing, which guaranteed fairness of the matching results. These authors also considered how to prevent participants from withdrawing from the sharing market. [7] proposed a binary integer linear programming model that enables external demanders to match with the parking spaces in a residential area during working hours and obtained a matching scheme that can maximize the profits of the sharing platform. In addition, [10] and [11] developed decision support systems to provide decision support for the parking-sharing platform. [12] proposed a two-stage method for matching the parking spaces with demanders. [13] proposed a Lagrangian relaxation method for matching shared parking slots with demanders to make the most use of the parking slots.

In addition, the literature on the allocation of public parking spaces is also important for the research content of this paper. Table 2 summarizes the study on the allocation of public parking spaces.

Table 2

Literature on the allocation of public parking spaces

Author	Known information	Objective	Tool/Model
Truong (2015) [14]	Demanders’ expected utility	Maximization of demanders’ expected utility	Linear programming model
Fu et al. (2014) [15]	Demanders’ types; parking fee; requirement time	Minimization of cruise time and costs	Two-stage model
Zou et al. (2015) [16]	The number of available parking spaces; the number of drivers; drivers requirement time; parking spaces valuation; parking fees	Maximization of social welfare	Integer programming model
Du et al. (2016) [17]	Number of demanders and their destinations; parking lots’ rental prices	Maximization of demanders’ expected utility	Stochastic Poisson game model
Abidi et al. (2017) [18]	Demanders’ location, requirement time, parking cost, and the weight between price and distance; parking spaces’ locations, available quantity, and rental time	Minimization of the total distance traveled by cars	Integer programming model
Cheng et al. (2018) [19]	Demanders’ locations and requirement time; parking spaces’ locations and rental time	Minimization of demanders’ walking time	Bilevel programming model
Kokolaki et al. (2014) [20]	Parking spaces’ rental prices; demanders’ rental prices	Minimization of parking cost	Auction theory
Mladenović et al. (2018) [21]	Demanders’ locations and destinations; parking lots’ locations and the number of available parking spaces	Minimization of demanders’ total travel time	0-1 integer programming model
Shin and Kim (2018) [22]	Driver’s destination and personal parking preferences; parking spaces’ locations and the traffic around them	Maximize drivers’ utility function value	Dynamic control theory
Xie et al., 2021 [23]	departure time, origins, and destinations	Minimize the total travel time of the system	Nonlinear integer programming model
Ayala et al. (2011) [4]	Location of cars and parking spaces; parking cost function	Maximization of social welfare	Game theory

[14] introduced a general parking utility function for street parking assignment and established a linear programming model to maximize the expected parking utility. [15] designed an optimal parking recommendation model considering reservation behavior for street parking problems and obtained the optimal parking space through the staged selection method. In a similar vein, [16] built an optimization model to maximize the total utility, considering that drivers have different perceptions of the utility of the same parking space. [17] proposed a decentralized online parking mechanism (DCPM) to guide the parking decision of a parking coordination group by establishing a random Poisson game model. Since different public parking areas have different parking time ranges, [18] established an optimization model with the goal of minimizing the total parking cost and obtained a parking space allocation scheme through an improved genetic algorithm. [19] designed a time-limited parking management scheme for large parking lots. They proposed a bilevel programming model and obtained the optimal parking duration by minimizing the average walking time of parking space demanders. Furthermore, since drivers can obtain public parking spaces through bidding, [20] proposed a parking space allocation system based on auction behavior and obtained a centralized parking space allocation scheme. Moreover, [21] obtained an optimal matching scheme to minimize the total cruise time of demanders by building a 0-1 integer programming model. Moreover, [22] proposed a predictive control method based on neural networks to improve the performance of an intelligent parking guidance system by dynamically selecting the best parking lot. [23] proposed a parking lot allocation model of system traffic optimal control and a particle swarm algorithm to solve it. [4] studied the public parking space allocation game under both complete and incomplete information using game theory.

Parking spaces belonging to buildings such as hotels, hospitals, and shopping malls are public but not open to personal use. At the same time, occupancy of these parking spaces has clear peak/valley characteristics, so these parking spaces are similar to private parking spaces. Therefore, the parking space-demander matching problem of these parking spaces differs from the private parking space matching or public parking space allocation situations described above. Table 3 summarizes the literature on the matching of shared parking spaces attached to buildings.

Table 3

Literature on the matching of shared parking spaces attached to buildings

Author	Known information	Objective	Tool/Model
Yu et al. (2018) [24]	Parking spaces’ available time and rental prices; Demanders’ demand time and rental prices	Maximization of parking lot’s profit	Integer linear programming model
Wu (2016) [25]	Historical data on parking space	Maximizing the number of shared parking spaces	Time series prediction model
Mejri et al. (2014) [26]	Demanders’ types and acceptable walking distances; parking spaces’ rental time	Minimization of the network cost	PC-aware game theory

In view of the difficulty of parking at night, [24] proposed an integer linear programming model of night-time shared parking spaces for large shopping malls with the objective of maximizing the profits of shared parking spaces. [25] constructed a control model for the affiliated berths of hotels, to provide as many shared berths as possible after guaranteeing the hotel’s demand. [26] proposed a network-level parking space allocation method (PSAM) to solve the problem of low utilization in the affiliated parking lots of public buildings.

Previous research results are important to solve the parking space-demander matching problem, but there are some limitations to existing research results: (1) Almost all the research results hold that each demander can match with one parking space at most. They do not consider that the sharing platform might provide the demanders with a parking relocation service to improve the utilization rate of parking spaces. (2) Almost all the research results consider only the prices and the time window submitted by shared private idle parking spaces and their demanders in the matching but do not consider their historical matching success rate which means the fraction or percentage of success among a number of attempts to match a parking space or demander. (3) Most of the research results assume that shared private idle parking space owners or the demanders never withdraw. Only a few research results consider the negative effect caused by the parking space owners’ or demanders’ withdrawal behavior and solve it by setting a fixed withdrawal rate for them. However, it is difficult to describe differentiated withdrawal behavior with a fixed withdrawal rate.

Therefore, aiming at the parking space-demander matching problem, we study a many-to-many matching problem for shared private idle parking spaces and their demanders, considering a situation in which every demander can park in the different parking spaces successively, every shared private idle parking space can be supplied to different demanders successively and the sharing platform is eager to keep the parking spaces and demanders in the sharing market. In addition, a multi-objective optimization model is constructed to maximize the following: the number of the demanders matched with a parking space; the total priority of the parking spaces that have successfully matched with demanders; and the total priority of demanders who have successfully matched with the parking spaces.

3 Problem description

3.1 Providing demanders with parking relocation service

Emerging technologies enable parking relocation services for parking demanders without their participation [9]. The online shared parking platform provides demanders with parking relocation services so that demanders can park in different shared private idle parking spaces successively in their demand time windows. Importantly, parking relocation service is conducive to improving the utilization rate of parking spaces [9].

Suppose that there are two demanders and two parking spaces denoted by D₁, D₂, S₁, S₂ respectively. Further, we suppose that S₁ and S₂ are acceptable to D₁, and only S₁ is acceptable to D₂ because the parking rate of S₂ exceeds D₂’s maximum acceptable parking rate and the distance between S₂ and D₂ exceeds D₂’s maximum acceptable distance. As shown in Fig. 1 and Fig. 2, demanders D₁ and D₂ have the demand time windows of 8 : 00–18 : 00 and 13 : 00–17 : 00 respectively; two parking spaces S₁ and S₂, have supply time windows of 8 : 00–18 : 00 and 13 : 00–18 : 00 respectively. We consider the following two cases:

Fig. 1

Sharing platform does not provide a parking relocation service.

Fig. 2

Sharing platform provides parking relocation service.

If parking relocation is not allowed, every demander can match with one parking space at most. Therefore, the matching result is D₁–S₁(8 : 00–18 : 00), but D₂ and S₂ match with nothing.

If the sharing platform provides parking relocation services, every demander can match with different parking spaces successively. Therefore, the matching result is D₁–S₁(8 : 00–13 : 00), D₁–S₂(13 : 00–18 : 00) and D₂–S₁(13 : 00–17 : 00).

By comparison, we can find that parking relocation makes one more demander get matched and brings an increase of 14 in the total usage time of the parking spaces. Thus, the platform can improve the utilization rate of parking spaces by providing demanders with a parking relocation service.

Figure 3 describes the problem studied in this paper. There are 4 parking spaces, S₁, S₂, S₃, S₄, and 6 demanders, D₁, D₂, D₃, D₄, D₅, D₆. Δ and ◎ represent the positions of the parking spaces and the destinations of the demanders respectively. ○ indicates the maximum acceptable walking distances of the demanders. [27] provided an example of user interface design to illustrate how demanders can set the destinations and the maximum acceptable walking distances. The parking platform can provide demanders with input interfaces to set the destinations and the maximum acceptable walking distances. As for the labels, we take some examples to illustrate their meanings: S₁ [8, 17] represents that the supply time window of parking space S₁ is from 8 : 00 to 17 : 00, D₃ [9, 17] represents that the demand time window of demander D₃ is from 9 : 00 to 17 : 00.

Fig. 3

Problem description.

Within the constraints of price and walking distance, the parking spaces within the dotted circles and with demanders’ destinations in the centers of the circles are acceptable for these demanders. Adding the constraints of time windows, the many-to-many matching result is shown in Fig. 3, where the red arrows point to the parking spaces matched with a demander. Facing a set of parking spaces with available time slots, each demander D_i can select a subset of time slots of parking spaces to park. If D_i’s requirements on the parking rate, the walking distance, and the parking time interval are met by these time slots, we call this subset a feasible choice for D_i. For example, in Fig 3, {S₁(8 : 00–13 : 00), S₂(13 : 00–17 : 00)} is a feasible choice for D₁ as S₁ and S₂ meet D₁’s requirements on parking rate and walking distance, and time slots (8 : 00–13 : 00) and (13 : 00–17 : 00) satisfy D₁’s requirement on parking time slot (8 : 00–17 : 00). Analogously, either {S₂(9 : 00–17 : 00)} or {S₂(9 : 00–13 : 00), S₄(13 : 00–17 : 00)} is a feasible choice for D₃. In a matching result (solution), each demander should be matched with a feasible choice or with nothing. For example, a matching result is D₁–S₃(8 : 00–13 : 00), D₁–S₂(13 : 00–17 : 00), D₂–S₄(9 : 00–12 : 00), D₃–S₂(9 : 00–13 : 00), D₃–S₄(13 : 00–17 : 00), D₄–S₁(9 : 00–15 : 00) and D₅, D₆, S₅ are matched with nothing.

3.2 Considering the priorities of shared private idle parking spaces and demanders

When solving the parking space-demander matching problem, it is necessary to consider the matching priorities of shared private idle parking spaces and their demanders because of the following factors:

If the demanders or the suppliers of parking spaces often put forward matching applications to an online shared parking platform many times but rarely get successfully matched, they might feel disappointed and exit from the platform. If more suppliers exit from the platform, their parking spaces will be more likely to remain idle. In addition, if more demanders exit from the platform, the demand for the parking spaces on the platform will decline, which will cause more parking spaces to remain idle. Therefore, if the parking spaces or the demanders withdraw from the platform, the risk of the parking spaces being idle will increase.

A matching scheme provided by the sharing platform may not be carried out due to the suppliers’ or demanders’ breach of contract, which will have a negative impact on the suppliers, the demanders, and the platform. For example, a demander may cancel the online order when they find a parking space that is more in line with their expectations. Demanders’ default will have a few bad impacts: first, the matched parking space will fail to rent out, which will reduce its suppliers’ profits. Second, other demanders who have failed to be matched will lose the chance to match with the parking spaces that some demanders refuse to match with. Third, not only may the platform’s revenue decline but the matching scheme may also be negatively affected. In addition, the sharing platform’s reputation may also be damaged.

Therefore, when solving the many-to-many matching problem between the parking spaces and their demanders, the platform should set the priorities for the parking spaces and the demanders according to their historical matching information. The probability of a parking space or a demander being matched successfully will be affected by the priority. The platform calculates the priorities of the parking spaces and the demanders so that their priorities will increase with the decrease in the matched or the defaulted rate. The platform can prevent the parking spaces or the demanders from withdrawing from the platform or defaulting by increasing the probability of successfully matching those whose priorities are high and decreasing the probability of matching those whose priorities are low, thus improving the performance of the matching scheme.

3.3 Notations

The earliest start time and the latest end time of all the time windows of shared private idle parking spaces and their demanders are respectively taken as the beginning and end of the planning horizon. The planning horizon is divided into K time slots. To describe the problem, we use the following notation:

k∈{1, 2, . . . ,K}: the k-th slot after the starting time of the planning.S = {S₁, S₂, . . . ,S_j, . . . ,S_N}: the set of all parking spaces.D = {D₁, D₂, . . . ,D_i, . . . ,D_M}: the set of all the demanders. $T_{jk}^{s} = {\begin{matrix} 1, S_{j} is shared in the k - th slot \\ 0, otherwise \end{matrix}$ $T_{ik}^{d} = {\begin{matrix} 1, D_{i} needs to park in the k - th slot \\ 0, otherwise \end{matrix}$

$(a_{j}^{d}, b_{i}^{d})$ : coordinates of D_i’s destination.

$(a_{j}^{s}, b_{j}^{s})$ : coordinates of S_j’s position.

$p_{j}^{s}$ : minimum parking rate of S_j.

$p_{i}^{d}$ : maximum acceptable parking rate of D_i.

Dist_i: maximum acceptable walking distance for D_i between i’s destination and i’s matched parking space.

n_i: maximum acceptable number of D_i’s parking relocations.

$A_{j}^{s}$ : the number of applications for S_j before a decision point.

$B_{j}^{s}$ : the number of times S_j has been successfully matched before a decision point.

$C_{j}^{s}$ : the number of S_j’s defaults before a decision point such that $C_{j}^{d} ⩽ B_{i}^{d} ⩽ A_{i}^{d}$ .

$A_{j}^{d}$ : the number of applications that D_i has submitted before a decision point.

$B_{i}^{d}$ : the number of times D_i has been successfully matched before a decision point.

$C_{i}^{d}$ : the number of D_i’s cancellations of the match before a decision point such that $C_{j}^{s} ⩽ B_{j}^{s} ⩽ A_{j}^{s}$ .

This paper addresses the problem of how a matching scheme can be determined based on the premise that online shared parking platforms provide the demanders with parking relocation service, according to the demanders’ information including maximum acceptable walking distances, maximum acceptable prices, demand time windows, maximum acceptable numbers of parking relocations and the priorities.

4 The parking space-demander matching model

To determine the matching scheme, we first calculate the priorities of shared private idle parking spaces and their demanders according to their historical matching information. Then, a multi-objective optimization model is constructed to maximize the number of the matched demanders, the total priority of the matched parking spaces, and the total priority of the matched demanders, based on the consideration that the platform can provide the demanders with parking relocation service and the effect of the priorities of the parking spaces and the demanders with respect to the matching scheme.

4.1 Priorities of shared private idle parking spaces and demanders

When calculating the priorities of the parking spaces and the demanders, we focus on the total number of matching applications, matched times, and defaulted times after matching successfully. Let $W_{j}^{s}$ and $W_{i}^{d}$ indicate S_j’s priority and D_i’s priority in this matching respectively. $W_{j}^{s}$ and $W_{i}^{d}$ are calculated as follows: $W_{j}^{s} = (1 - \frac{1 + B_{j}^{s}}{1 + A_{j}^{s}}) (1 - \frac{1 + C_{j}^{s}}{1 + C_{j}^{s}})$ (1) $W_{j}^{d} = (1 - \frac{1 + B_{i}^{d}}{1 + A_{i}^{d}}) (1 - \frac{1 + C_{i}^{d}}{1 + B_{i}^{d}})$ (2)

Note that $W_{j}^{d}, W_{j}^{s} \in {1, 0}$ . When $A_{i}^{d}$ is constant, $W_{i}^{d}$ decreases with the increase of $B_{i}^{d}$ or $C_{j}^{d}$ . Similarly, when $A_{j}^{s}$ is constant, $W_{j}^{s}$ decreases with the increase of $B_{j}^{s}$ or $C_{j}^{s}$ . In particular, taking the demand side as an example, $W_{i}^{d} = 1$ when $B_{i}^{d} ⪡ A_{i}^{d}$ and $C_{i}^{d} ⪡ B_{i}^{d}$ , which means that if a demander has applied for parking many times but was seldom successfully matched with any parking spaces and rarely defaulted after matching successfully, its priority should be the highest. $W_{i}^{d} = 0$ when $B_{i}^{d} \to A_{i}^{d}$ or $C_{i}^{d} \to B_{i}^{d}$ . It means that if a demander is matched with a parking space successfully almost every time after applying for a parking space, or if the demander cancels the order almost every time after being matched successfully, the demander’s priority should be lowest. The priorities for the parking spaces operate similarly.

4.2 Matching model

After the priorities are calculated, we determine a matching scheme in which the number of the demanders successfully matched with a parking space is the biggest; the total priority of the parking spaces that have successfully matched with a demander is highest; and the total priority of demanders who have matched with a parking space successfully is highest, according to the acceptable prices on both sides, demanders’ maximum acceptable walking distances and demanders’ maximum acceptable car movements.

Let x_kij be the binary variable. x_kij = 1 if D_i matches with S_j in time slot k and x_kij = 0 otherwise. Then, we build a multi-objective optimization model as follows: $\max Z_{1} = \sum_{i = 1}^{M} (\frac{\sum_{j = 1}^{N} \sum_{k = 1}^{K} x_{kij}}{\sum_{k = 1}^{K} T_{kij}^{d}})$ (3) $\max Z_{2} = \sum_{j = 1}^{N} (\frac{\sum_{i = 1}^{M} \sum_{k = 1}^{K} x_{kij}}{\sum_{k = 1}^{K} T_{jk}^{s}} W_{j}^{s})$ (4) $\max Z_{3} = \sum_{i = 1}^{M} (\frac{\sum_{j = 1}^{N} \sum_{k = 1}^{K} x_{kij}}{\sum_{k = 1}^{K} T_{ik}^{d}} W_{j}^{d})$ (5)

subject to $(p_{ki}^{d} - p_{kj}^{s}) x_{kij} ⩾ 0$ (6) $[(a_{i}^{d} - a_{j}^{s}) + (b_{i}^{d} - b_{j}^{s})] x_{kij} ⩽ {Dist}_{i}^{2}$ (7) $\sum_{j = 1}^{N} [\frac{\sum_{k = 1}^{K} x_{kij}}{\sum_{k = 1}^{K} T_{ik}^{d}}] ⩽ n_{i} + 1$ (8) $\sum_{i = 1}^{M} x_{kij} ⩽ 1$ (9) $\sum_{j = 1}^{N} x_{kij} ⩽ 1$ (10) $\sum_{k = 1}^{K} \sum_{j = 1}^{N} x_{kij} \in \sum_{k} T_{ik}^{d}, 0$ (11) $x_{kij} ⩽ T_{jk}^{s} T_{ik}^{d}$ (12)

$\begin{matrix} i = 1, 2, \dots, M; j = 1, 2, \dots, N; \\ k \in {k | T_{jk}^{s} T_{ik}^{d} = 1, k = 1, 2, \dots, K} \end{matrix}$ (13)

Objective function (3) maximizes the number of matched demanders. Objective function (4) maximizes the total priority of the matched parking spaces. Objective function (5) maximizes the total priority of the matched demanders. Constraints (6) ensure that D_i’s maximum acceptable parking rate is not lower than the parking rate of S_j if D_i matches with S_j. Constraints (7) indicate that the walking distance between D_i’s destination and the location of S_j should be within the acceptable range of D_i, if D_i matches with S_j. Constraints (8) indicate D_i’s car is moved no more than its maximum acceptable parking relocation times. Constraints (9) indicate that S_j can match with at most one demander in each time slot. Constraints (10) indicate that D_i can match with at most one parking space in each time slot. Constraints (11) indicate that D_i can match with no less than one parking space or nothing. Constraint (12) indicates that only if D_i wants to park within S_j’s supply time window can they match successfully.

5 NSGA-II algorithm

The parking space-demander matching problem is a many-to-many matching problem. For example, if each demander can match with at most one parking space, the problem would be a classic one-to-many matching problem, which is proven to be NP-hard [28]. Because each demander can match different parking spaces successively, our problem is also NP-hard and can be solved by a heuristic algorithm. Non-sort genetic algorithm II (NSGA-II) is a genetic algorithm proposed by [29] and is widely applied to multi-objective optimization problems. This algorithm greatly contributes to solving multi-objective problems and alleviates computational complexity, non-elitist method, and the specification of shared parameters, which are three difficulties of previous multi-objective evolutionary algorithms when using non-dominant ordering and sharing methods. In addition, the algorithm can search rapidly and has an excellent performance in speed and efficiency [30]. As there are three objective functions, we choose the NSGA-II algorithm to solve the model.

However, it is difficult to apply the traditional NSGA-II algorithm directly. According to the traditional NSGA-II algorithm, a solution (individual) is generated randomly, i.e., it is yielded by randomly selecting some time slots of the parking spaces for each demander. On account of the complex and tight constraints in our model, the solution space is sparse and feasible solutions are hard to find via random selection. Further, it is very slow in generating an initial population. Therefore, we propose a method for quickly generating feasible solutions to speed up the process of generating an initial population. The main steps of the NSGA-II algorithm are redesigned and described in detail in Fig. 4. First, L feasible solutions are quickly generated by our new method, which plays a crucial role in improving the computation efficiency of our algorithm. Then the crossover operator is carried out. Next is the mutation operator. Subsequently, feasible individuals are screened. Finally, the selection operator is carried out, that is to say, L individuals are selected to form a new generation according to the non-dominated sort.

Fig. 4

Algorithm flow chart.

5.1 Chromosome coding

Chromosome coding is the first problem in the optimization process. In the many-to-many parking space-demander matching problem, we need to match a supplier with a demander in each time slot, so we use binary coding to encode chromosomes. A gene can be represented by a two-dimensional array containing N rows and K columns coded with 0 or 1. A chromosome with M genes can be represented as a three-dimensional array containing M rows, N columns, and K layers. Let R = {r_m×n×k}, where m ∈ {1, 2, …, M} , n ∈ {1, 2, …, N} and k ∈ {1, 2, …, K}. Let L be the population size. Demander D_m is matched with parking space S_n in time slot k if r_m×n×k = 1 and otherwise r_m×n×k = 0. After analyzing the feasible solution of model [3 –13], we find that there is at most one code “1” in each column of a gene, which means that every demander can match with at most one parking space at each time slot. And there is at most one code “1” in each column of a chromosome’s layer, which means that every parking space can only match with at most one demander in each time slot. According to the predetermined population size, M, N, and K, L individuals of the initial population are randomly generated.

5.2 Fast generation of feasible solutions

Because the feasible solutions of this model are sparse, finding feasible solutions would be difficult if the method of random assignment is adopted. After both parties submit personal information, the number of feasible choices for a demander is limited. A feasible solution of optimization model [3 –13] can be obtained by randomly selecting and combining any feasible choices for each demander according to the constraints. To improve the speed of generating feasible solutions, the specific steps (step 1 to step 4) that yield a feasible solution are as follows:

Step 1: Find all the parking spaces that meet the requirements on walking distance and price for each demander.

Step 2: Find all the feasible choices that meet the requirement on the number of car movements and parking time for each demander.

Step 3: Choose one feasible choice for each demander randomly and merge them into a solution.

Step 4: Verify whether the solution satisfies equation [9]. If it does, output the feasible solution (i.e. individual); otherwise, proceed to step 3.

5.3 Crossover operator

Crossover is made in hope that new chromosomes will inherit good parts of old chromosomes and therefore the new chromosomes will be better [31].

Next, we take an example to illustrate crossover operator, let M = 5, N = 2, K = 3, f₁ = 1 and f₂ = 4, then the two parents generated randomly are represented as:

parent_1 =

$[(\begin{matrix} 0, 1, 1 \\ 1, 0, 0 \end{matrix}) | (\begin{matrix} 0, 1, 0 \\ 1, 0, 1 \end{matrix}) | (\begin{matrix} 0, 0, 1 \\ 1, 1, 1 \end{matrix}) | (\begin{matrix} 1, 1, 0 \\ 1, 0, 1 \end{matrix}) | (\begin{matrix} 0, 1, 1 \\ 1, 1, 1 \end{matrix})],$

parent_2 =

$[(\begin{matrix} 0, 1, 1 \\ 1, 0, 1 \end{matrix}) | (\begin{matrix} 0, 0, 0 \\ 1, 0, 1 \end{matrix}) | (\begin{matrix} 1, 0, 1 \\ 0, 1, 1 \end{matrix}) | (\begin{matrix} 0, 1, 0 \\ 1, 1, 1 \end{matrix}) | (\begin{matrix} 1, 1, 1 \\ 0, 1, 1 \end{matrix})],$

The process of generating two-hybrid progeny is expressed as:

parent_1 =

parent_2 =

The two generated offspring are represented as:

offspring_1 =

$[(\begin{matrix} 0, 1, 1 \\ 1, 0, 0 \end{matrix}) | (\begin{matrix} 0, 0, 0 \\ 1, 0, 1 \end{matrix}) | (\begin{matrix} 1, 0, 1 \\ 0, 1, 1 \end{matrix}) | (\begin{matrix} 0, 1, 0 \\ 1, 1, 1 \end{matrix}) | (\begin{matrix} 0, 1, 1 \\ 1, 1, 1 \end{matrix})],$

offspring_2 =

$[(\begin{matrix} 0, 1, 1 \\ 1, 0, 1 \end{matrix}) | (\begin{matrix} 0, 1, 0 \\ 1, 0, 1 \end{matrix}) | (\begin{matrix} 1, 0, 1 \\ 1, 1, 1 \end{matrix}) | (\begin{matrix} 1, 1, 0 \\ 1, 0, 1 \end{matrix}) | (\begin{matrix} 1, 1, 1 \\ 0, 1, 1 \end{matrix})],$

5.4 Mutation operator

Crossover is to use the current solutions to find better ones, while mutation helps for the exploration of the entire solution space to maintain the diversity of the population and to escape local optima [31]. In this paper, the gene on a chromosome represents a feasible choice. In Section 5.2, we have generated all feasible choices for each demander, so there are several alleles for each gene on the chromosome. First, a random individual is selected from the population composed of parents and hybrid individuals. Then, an integer f₃ is randomly generated in the range 1 to M. The f₃-th gene on the selected chromosome is replaced with any feasible choice of the f₃-th demander to complete the mutation operation.

5.5 Selection operator

The fast non-dominant sorting and crowding distance in NSGA-II are used to select the next generation of individuals. First, L individuals of the parent population and L individuals of the progeny population are combined to produce a population containing 2L individuals. Then, 2L individuals are sorted and stratified according to the Pareto dominance relation to obtain E₁, E₂ . . . E_l, total l layer non-dominant frontier, where the number of individuals in the i-th non-dominant frontier is H_i. Finally, if there are h < l making , it is unnecessary to calculate the crowding distances of individuals, and directly add L individuals from layer 1 to h to the next generation population, and the crowding distances of individuals in layer (h + 1) are calculated at the same time, and the previous individual arranged in descending order according to the crowding distances is selected to enter the next generation population.

6 Illustrative example

To illustrate the effectiveness and feasibility of the proposed method, an example is given below. Suppose that 30 parking spaces submit supply information, as shown in Table 4, and 40 demanders submit demand information, as shown in Table 5.

Table 4
The supply information for the parking spaces

S_j $(a_{j}^{s}, b_{j}^{s})$ $T_{jk}^{s}$ $P_{j}^{s}$ $A_{j}^{s}$ $B_{j}^{s}$ $C_{j}^{s}$

S ₁ (6,4) (0 0 0 0 1 1 1 1 1 1) 0.55 13 9 4

S ₂ (3,1) (0 0 1 1 1 1 1 0 0 0) 0.61 20 18 2

S ₃ (7,5) (0 1 1 1 1 1 0 0 0 0) 0.52 20 17 3

S ₄ (1,3) (0 0 1 1 1 1 1 0 0 0) 0.45 15 14 1

S ₅ (1,10) (0 1 1 1 1 1 1 0 0 0) 0.56 16 11 5

S ₆ (2,3) (0 1 1 1 1 1 1 1 1 0) 0.37 14 14 0

S ₇ (1,5) (0 0 0 0 0 1 1 1 1 1) 0.40 19 18 1

S ₈ (5,7) (0 0 0 0 1 1 1 1 1 1) 0.62 14 10 4

S ₉ (9,1) (1 1 1 1 1 1 1 0 0 0) 0.45 14 12 2

S ₁₀ (5,10) (0 0 0 0 0 0 0 1 1 1) 0.32 13 10 3

S ₁₁ (3,8) (0 0 0 0 0 1 1 1 1 1) 0.35 19 16 3

S ₁₂ (1,9) (0 0 0 0 0 1 1 1 1 0) 0.56 17 13 4

S ₁₃ (10,4) (0 0 0 0 0 0 1 1 1 1) 0.63 15 15 0

S ₁₄ (9,6) (0 0 0 0 1 1 1 1 1 1) 0.57 13 11 2

S ₁₅ (4,3) (0 0 0 0 1 1 1 1 1 0) 0.38 12 10 2

S ₁₆ (4,4) (0 0 0 0 1 1 1 1 1 1) 0.40 20 15 5

S ₁₇ (2,1) (1 1 1 1 1 1 1 1 1 1) 0.35 18 17 1

S ₁₈ (8,4) (0 0 1 1 1 1 1 1 0 0) 0.35 20 18 2

S ₁₉ (1,7) (0 0 1 1 1 1 0 0 0 0) 0.35 12 7 5

S ₂₀ (2,8) (0 0 0 0 0 1 1 1 1 1) 0.56 15 10 5

S ₂₁ (1,6) (0 0 0 0 0 0 1 1 1 1) 0.43 13 9 4

S ₂₂ (6,7) (1 1 1 1 1 1 0 0 0 0) 0.65 13 10 3

S ₂₃ (3,4) (0 0 0 0 0 1 1 1 1 0) 0.41 19 18 1

S ₂₄ (10,1) (0 1 1 1 1 1 1 1 0 0) 0.45 14 9 5

S ₂₅ (7,5) (0 0 0 0 0 1 1 1 1 1) 0.53 14 14 0

S ₂₆ (2,10) (1 1 1 1 1 1 1 1 1 0) 0.45 18 17 1

S ₂₇ (8,8) (0 0 0 0 0 1 1 1 1 1) 0.52 16 14 2

S ₂₈ (10,4) (0 0 0 0 0 0 1 1 1 1) 0.48 13 11 2

S ₂₉ (10,5) (1 1 1 1 1 1 1 0 0 0) 0.47 17 14 3

S ₃₀ (7,2) (0 0 0 1 1 1 1 1 1 0) 0.32 19 18 1

S_j	$(a_{j}^{s}, b_{j}^{s})$	$T_{jk}^{s}$	$P_{j}^{s}$	$A_{j}^{s}$	$B_{j}^{s}$	$C_{j}^{s}$
S ₁	(6,4)	(0 0 0 0 1 1 1 1 1 1)	0.55	13	9	4
S ₂	(3,1)	(0 0 1 1 1 1 1 0 0 0)	0.61	20	18	2
S ₃	(7,5)	(0 1 1 1 1 1 0 0 0 0)	0.52	20	17	3
S ₄	(1,3)	(0 0 1 1 1 1 1 0 0 0)	0.45	15	14	1
S ₅	(1,10)	(0 1 1 1 1 1 1 0 0 0)	0.56	16	11	5
S ₆	(2,3)	(0 1 1 1 1 1 1 1 1 0)	0.37	14	14	0
S ₇	(1,5)	(0 0 0 0 0 1 1 1 1 1)	0.40	19	18	1
S ₈	(5,7)	(0 0 0 0 1 1 1 1 1 1)	0.62	14	10	4
S ₉	(9,1)	(1 1 1 1 1 1 1 0 0 0)	0.45	14	12	2
S ₁₀	(5,10)	(0 0 0 0 0 0 0 1 1 1)	0.32	13	10	3
S ₁₁	(3,8)	(0 0 0 0 0 1 1 1 1 1)	0.35	19	16	3
S ₁₂	(1,9)	(0 0 0 0 0 1 1 1 1 0)	0.56	17	13	4
S ₁₃	(10,4)	(0 0 0 0 0 0 1 1 1 1)	0.63	15	15	0
S ₁₄	(9,6)	(0 0 0 0 1 1 1 1 1 1)	0.57	13	11	2
S ₁₅	(4,3)	(0 0 0 0 1 1 1 1 1 0)	0.38	12	10	2
S ₁₆	(4,4)	(0 0 0 0 1 1 1 1 1 1)	0.40	20	15	5
S ₁₇	(2,1)	(1 1 1 1 1 1 1 1 1 1)	0.35	18	17	1
S ₁₈	(8,4)	(0 0 1 1 1 1 1 1 0 0)	0.35	20	18	2
S ₁₉	(1,7)	(0 0 1 1 1 1 0 0 0 0)	0.35	12	7	5
S ₂₀	(2,8)	(0 0 0 0 0 1 1 1 1 1)	0.56	15	10	5
S ₂₁	(1,6)	(0 0 0 0 0 0 1 1 1 1)	0.43	13	9	4
S ₂₂	(6,7)	(1 1 1 1 1 1 0 0 0 0)	0.65	13	10	3
S ₂₃	(3,4)	(0 0 0 0 0 1 1 1 1 0)	0.41	19	18	1
S ₂₄	(10,1)	(0 1 1 1 1 1 1 1 0 0)	0.45	14	9	5
S ₂₅	(7,5)	(0 0 0 0 0 1 1 1 1 1)	0.53	14	14	0
S ₂₆	(2,10)	(1 1 1 1 1 1 1 1 1 0)	0.45	18	17	1
S ₂₇	(8,8)	(0 0 0 0 0 1 1 1 1 1)	0.52	16	14	2
S ₂₈	(10,4)	(0 0 0 0 0 0 1 1 1 1)	0.48	13	11	2
S ₂₉	(10,5)	(1 1 1 1 1 1 1 0 0 0)	0.47	17	14	3
S ₃₀	(7,2)	(0 0 0 1 1 1 1 1 1 0)	0.32	19	18	1

Table 5

Demand information of the demanders

D _i	$(a_{i}^{d}, b_{i}^{d})$	$T_{jk}^{d}$	$P_{i}^{d}$	Dist _i	n _i	$A_{i}^{d}$	$B_{i}^{d}$	$C_{i}^{d}$
D ₁	(4,2)	(0 0 0 0 0 0 1 1 1 1)	0.73	2	1	16	12	4
D ₂	(1,3)	(0 0 0 0 1 1 1 0 0 0)	0.62	3	1	16	13	3
D ₃	(8,1)	(0 1 1 1 0 0 0 0 0 0)	0.61	5	1	15	11	4
D ₄	(1,7)	(0 1 1 1 1 1 1 1 0 0)	0.61	4	1	16	15	1
D ₅	(4,2)	(0 0 0 0 1 1 0 0 0 0)	0.79	3	0	14	12	2
D ₆	(7,10)	(0 1 1 1 1 1 1 1 1 0)	0.67	4	1	17	12	5
D ₇	(9,7)	(0 1 1 0 0 0 0 0 0 0)	0.62	4	0	11	11	0
D ₈	(1,1)	(1 1 1 1 1 0 0 0 0 0)	0.80	2	1	17	15	2
D ₉	(7,4)	(0 1 1 1 1 1 1 0 0 0)	0.76	4	0	11	8	3
D ₁₀	(9,6)	(0 0 0 0 0 1 1 1 1 0)	0.62	3	0	19	16	3
D ₁₁	(3,10)	(1 1 1 1 1 1 1 1 1 0)	0.71	5	1	13	13	0
D ₁₂	(9,2)	(0 0 0 0 0 0 0 0 1 1)	0.81	4	1	20	20	0
D ₁₃	(6,4)	(0 0 0 0 0 0 0 0 1 1)	0.65	3	1	11	8	3
D ₁₄	(6,2)	(0 0 0 0 1 1 1 1 0 0)	0.68	3	1	16	15	1
D ₁₅	(3,8)	(0 0 0 0 1 1 1 1 0 0)	0.74	4	0	20	19	1
D ₁₆	(9,4)	(0 0 1 1 1 1 1 1 1 0)	0.65	5	0	18	14	4
D ₁₇	(5,9)	(1 1 1 1 1 1 1 0 0 0)	0.74	4	0	18	18	0
D ₁₈	(4,1)	(0 0 0 0 0 0 1 1 0 0)	0.81	3	1	20	15	5
D ₁₉	(1,2)	(0 0 0 0 0 0 0 1 1 1)	0.72	3	1	11	10	1
D ₂₀	(4,2)	(0 1 1 1 1 0 0 0 0 0)	0.89	4	1	18	18	0
D ₂₁	(8,7)	(1 1 1 1 1 1 1 1 0 0)	0.76	4	1	11	8	3
D ₂₂	(10,2)	(0 0 0 0 0 0 1 1 1 0)	0.76	2	1	16	15	1
D ₂₃	(7,8)	(0 1 1 1 1 1 1 1 1 0)	0.89	3	1	11	10	1
D ₂₄	(4,7)	(0 0 0 0 0 1 1 1 1 1)	0.62	4	1	13	9	4
D ₂₅	(9,6)	(0 0 0 0 1 1 1 1 1 0)	0.89	5	0	12	1	5
D ₂₆	(7,2)	(0 1 1 0 0 0 0 0 0 0)	0.80	3	0	18	16	2
D ₂₇	(2,5)	(1 1 1 1 0 0 0 0 0 0)	0.82	4	1	19	17	2
D ₂₈	(6,8)	(0 0 1 1 1 0 0 0 0 0)	0.62	3	0	17	17	0
D ₂₉	(5,7)	(0 1 1 1 1 0 0 0 0 0)	0.62	5	1	18	18	0
D ₃₀	(4,9)	(0 0 1 1 0 0 0 0 0 0)	0.86	4	1	15	10	5
D ₃₁	(9,4)	(0 1 1 1 1 0 0 0 0 0)	0.71	3	1	16	16	0
D ₃₂	(9,9)	(0 0 0 0 0 1 1 1 0 0)	0.71	4	0	15	15	0
D ₃₃	(6,7)	(0 0 0 0 1 1 1 1 1 0)	0.64	3	1	20	17	3
D ₃₄	(6,5)	(0 0 0 0 0 1 1 1 0 0)	0.85	5	1	13	8	5
D ₃₅	(4,5)	(0 0 0 0 1 1 1 1 1 0)	0.81	3	1	20	19	1
D ₃₆	(2,2)	(0 0 0 0 0 1 1 0 0 0)	0.72	4	1	17	13	4
D ₃₇	(7,3)	(0 0 0 0 0 0 0 1 1 1)	0.68	3	0	13	11	2
D ₃₈	(10,5)	(0 0 1 1 0 0 0 0 0 0)	0.71	2	1	17	12	5
D ₃₉	(6,1)	(0 0 0 0 0 0 0 1 1 0)	0.80	4	0	12	8	4
D ₄₀	(8,6)	(0 0 0 0 0 1 1 1 0 0)	0.69	3	0	17	12	5

According to the information in Tables 4 and 5, we use formulas [1] and [2] to calculate the priorities of the parking spaces and the demanders respectively. The results are shown in Tables 6 and 7.

Table 6

Priorities of the parking spaces

$W_{1}^{s}$	$W_{2}^{s}$	$W_{33}^{s}$	$W_{4}^{s}$	$W_{5}^{s}$	$W_{6}^{s}$	$W_{7}^{s}$	$W_{8}^{s}$	$W_{9}^{s}$	$W_{10}^{s}$
0.1714	0.0852	0.119	0.0583	0.1716	0	0.047	0.1697	0.1128	0.1558
$W_{11}^{s}$	$W_{12}^{s}$	$W_{13}^{s}$	$W_{14}^{s}$	$W_{155}^{s}$	$W_{16}^{s}$	$W_{17}^{s}$	$W_{18}^{s}$	$W_{19}^{s}$	$W_{20}^{s}$
0.1235	0.1587	0	0.119	0.1259	0.1637	0.0497	0.0852	0.1442	0.1705
$W_{21}^{s}$	$W_{22}^{s}$	$W_{23}^{s}$	$W_{24}^{s}$	$W_{25}^{s}$	$W_{26}^{s}$	$W_{27}^{s}$	$W_{28}^{s}$	$W_{29}^{s}$	$W_{30}^{s}$
0.1714	0.1558	0.0474	0.1667	0	0.0497	0.102	0.119	0.1333	0.0474

Table 7

Priorities of the demanders

$W_{1}^{d}$	$W_{2}^{d}$	$W_{3}^{d}$	$W_{4}^{d}$	$W_{5}^{d}$	$W_{6}^{d}$	$W_{7}^{d}$	$W_{8}^{d}$	$W_{9}^{d}$	$W_{10}^{d}$
0.1629	0.1387	0.1667	0.0551	0.1128	0.1709	0	0.0972	0.1667	0.1235
$W_{11}^{d}$	$W_{12}^{d}$	$W_{13}^{d}$	$W_{14}^{d}$	$W_{15}^{d}$	$W_{16}^{d}$	$W_{17}^{d}$	$W_{18}^{d}$	$W_{19}^{d}$	$W_{200}^{d}$
0	0	0.1667	0.0551	0.0452	0.1544	0	0.1637	0.0758	0
$W_{21}^{d}$	$W_{22}^{d}$	$W_{23}^{d}$	$W_{24}^{d}$	$W_{25}^{d}$	$W_{26}^{d}$	$W_{27}^{d}$	$W_{28}^{d}$	$W_{29}^{d}$	$W_{30}^{d}$
0.1667	0.0551	0.0758	0.1714	0.1442	0.0929	0.089	0	0	0.1705
$W_{31}^{d}$	$W_{32}^{d}$	$W_{33}^{d}$	$W_{34}^{d}$	$W_{35}^{d}$	$W_{36}^{d}$	$W_{37}^{d}$	$W_{38}^{d}$	$W_{39}^{d}$	$W_{40}^{d}$
0	0	0.119	0.1587	0.0452	0.1587	0.119	0.1709	0.1709	0.1709

After obtaining the multi-objective optimization model, the improved NSGA-II algorithm designed in this paper is used to solve it. MATLAB R2018b serves as the programming environment, and the algorithm is implemented on an Intel Core i5-8250u processor and Windows 10 computer with 8G memory. After repeated experiments, the algorithm parameters are set as follows: population size is 100, maximum iteration number is 80, and mutation probability p_m = 1. To reduce the error from a single experiment, the algorithm is run 10 times. The Pareto optimal solutions obtained by the final operation are shown in Fig. 5.

Fig. 5

Pareto optimal solutions.

Figure 5 comprises 9 subplots, which depict the 9 Pareto optimal solutions. In the subplots, the color of the lines represents the parking space. The abscissa range of a line represents the demander’s parking time window and the ordinate value of a line represents the demander. For example, in the first subplot, demander D₆ is matched with parking spaces S₂₂ and S₈ with respective parking time windows [1, 4] and [4, 9].

In Fig. 6, a small blue triangle represents a Pareto optimal solution, and the X-axis, Y-axis, and Z-axis correspond to the objective functions Z₁, Z₂ and Z₃ respectively. From Fig 6, we can see that the larger Z₁ is, the more demanders will match with a parking space successfully; the larger Z₂ is, the more parking spaces with higher priority will successfully match with a demander; the larger Z₃ is, the more demanders with high priority will successfully match with a parking space.

It can be seen from Table 8 and Fig. 6 that if the platform prefers maximizing the number of matched demanders, solution 3 is the best choice for the matching scheme. However, it may lead to more unmatched parking spaces or demanders that have low matching success rates and low default rates in history and hence have high priorities. Although there is a larger number of demanders who get matched successfully in solution 3, the total priorities of parking spaces and demanders are relatively lower than those of other solutions. Similarly, if the platform prefers maximizing the total priority of owners of parking space, solution 7 may be the best choice. However, it may reduce the number of matched demanders, and the total priority of the parking spaces that match with a demander successfully. If the platform prefers maximizing demanders’ total priority, solution 6 may be the best choice. However, it may reduce the number of the demanders who get matched successfully and the total priority of the demanders. Note that both D₁₁ and D₂₉ are matched although either has a priority of 0. This is because although matching D₁₁ and D₂₉ cannot increase Z₃, it will increase Z₁ and Z₂, That D₁₁ and D₂₉ get matched guarantees solution 6 a Pareto optimal solution. Moreover, according to the Euclidean compromise solution defined in [32], a compromise scheme that comprehensively considers the three objectives is solution 3 as its Euclidean distance from the three maximal objectives is the minimum. Therefore, when devising the matching scheme for the parking spaces and their demanders, the platform should ensure that the number of the demanders who are successfully matched is sufficiently large, the total priority of the parking spaces is high enough and the total priority of the demanders is sufficiently high.

Table 8

Objectives of the Pareto optimal solutions

Objectives	Pareto optimal solutions
	1	2	3	4	5	6	7	8	9
Z ₁	20	21	22	21	21	19	20	20	19
Z ₂	0.8496	0.8496	0.7784	0.8279	0.8102	0.6443	1.0004	0.8284	0.868
Z ₃	1.3738	1.3329	1.5235	1.6038	1.6126	1.6175	1.3518	1.4477	1.5194

Fig. 6

Objectives of Pareto optimal solutions.

7 Conclusion

In the context of the sharing economy, the urban planning community can draw support from online shared parking platforms and our matching method to address parking problems. The platforms can integrate and leverage shared private idle parking spaces to meet the parking requirements without taking up more urban space to build new parking facilities.

To leverage the parking spaces, we study the problem of how to match the parking spaces with their demanders.

In our setting, the platform provides demanders with parking relocation services, which enable more than one demander to match with one parking space. This broke the limitation in previous research where the utilization rate of parking spaces was relatively low because previous research does not concern parking relocation service and requires one demander to match with no more than one parking space.

Moreover, we innovatively consider the priority of demanders and parking spaces to prevent the parking spaces or the demanders from withdrawing from parking platforms. The priority concerns historical matching information such as the number of demanders’ applications, the number of demanders’ previous successful matchings, the number of demanders’ cancellations, and the number of suppliers’ defaults. The historical data has great potential to be utilized but has been overlooked in previous research. With the goal of maximizing the total priority, the demander or parking space with low priority will be given a low priority to match. In this way, the platform can discourage the parking spaces or the demanders from exiting from sharing platforms.

For the parking space-demander matching problem, a multi-objective optimization model is constructed to maximize the number of matched demanders, the total priority of the parking spaces, and the total priority of the demanders.

We improve the NSGA-II algorithm, which is usually used to solve multi-objective optimization models. We take the feasible choices as the alleles of individuals, which reduced the probability of generating infeasible solutions after crossover and mutation and improved the speed of the NSGA-II algorithm in solving our model.

In future work, we can further consider the cost incurred by the parking relocation service, along with the matching problems where the parking spaces and the demanders arrive randomly. In addition, future research can pay attention to matching methods for shared private idle parking spaces and their demanders according to empirical data on parking behavior.

Footnotes

Acknowledgment

This work was supported by the National Natural Science Foundation of China under Grants 71871048 and 72371065.

References

Chen

, Ding

, Gong

, Ma

and Tang

, Impact of shared parking in the central business district on real estate value appreciation, Journal of Urban Planning and Development 148 (2022), 04021069.

Chen

, Wang

and Pan

, Characteristics of parking in central Shanghai, China, Journal of Urban Planning and Development 142 (2016), 05015012.

Lin

, Zhou

and Lu

, Dynamic reservation and allocation in private parking slot sharing system, Systems Engineering –Theory & Practice 38 (2018), 2907–2917.

Ayala

, Wolfson

, Xu

, Dasgupta

, Lin

Parking slot assignment games, in: Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Association for Computing Machinery, NewYork,NY, USA, 2011: pp. 299–308.

Arnott

, Rave

and Schöb

, Alleviating urban traffic congestion, MIT Press Books 1 (2005).

Ding

, Wang

, Zheng

, Xi

, Wang

, Xu

Research on parking choice model based on shared private parking space, in: International Conference on Green Intelligent Transportation System and Safety, Springer, 2016: pp. 935–948.

Shao

, Yang

, Zhang

and Ke

, A simple reservation and allocation model of shared parking lots, Transportation Research Part C: Emerging Technologies 71 (2016), 303–312.

S.X.

, Cheng

, Kong

X.T.R.

, Yang

and Huang

G.Q.

, Private parking slot sharing, Transportation Research Part B: Methodological 93 (2016), 596–617.

Xiao

, Xu

and Gao

, Shared parking problem: A novel truthful double auction mechanism approach, Transportation Research Part B: Methodological 109 (2018), 40–69.

10.

Guo

, Zhang

, Xu

, Zhang

and Li

, Parking spaces repurchase strategy design via simulation optimization, Journal of Intelligent Transportation Systems 20 (2016), 255–269.

11.

Chou

S.Y.

, Arifin

, Dewabharata

Optimal decision of reservation policy for private parking sharing system, in: 2018 International Conference on Computer, Control, Informatics and Its Applications (IC3INA), 2018: pp. 66–71.

12.

Jiang

Y.P.

, Shao

X.R.

and Song

X.C.

, Matching model between private idle parking slots and demanders for parking slot sharing, Journal of Transportation Engineering, Part A: Systems 147 (2021), 04021028.

13.

Tang

, Jiang

and Yang

, An efficient Lagrangian relaxation algorithm for the shared parking problem, Computers & Industrial Engineering 176 (2023), 108860.

14.

Truong

N.L.

, A note on the optimal stopping parking problem, Operations Research Letters 43 (2015), 96–98.

15.

, Chen

, Sun

and Yang

, Reservation based optimal parking lot recommendation model in Internet of Vehicle environment, China Communications 11 (2014), 38–48.

16.

Zou

, Kafle

, Wolfson

and (Jane) Lin

, , A mechanism design based approach to solving parking slot assignment in the information era, Transportation Research Part B: Methodological 81 (2015), 631–653.

17.

and Gong

, Stochastic Poisson game for an online decentralized and coordinated parking mechanism, Transportation Research Part B: Methodological 87 (2016), 44–63.

18.

Abidi

, Krichen

, Alba

and Bravo

J.M.M.

, A hybrid heuristic for solving a parking slot assignment problem for groups of drivers, International Journal of Intelligent Transportation Systems Research 15 (2017), 85–97.

19.

Cheng

, Ji

, Yin

, Du

and Sun

, Designing a time limited–parking management plan for large-scale parking lots, Journal of Transportation Engineering, Part A: Systems 144 (2018), 04018027.

20.

Kokolaki

, Karaliopoulos

, Stavrakakis

Trading public parking space, in: Proceeding of IEEE International Symposium on aWorld ofWireless, Mobile and Multimedia Networks 2014, IEEE, 2014: pp. 1–6.

21.

Mladenović

, Delot

, Laporte

and Wilbaut

, The parking allocation problem for connected vehicles, J Heuristics 26 (2020), 377–399.

22.

Shin

J.-H.

, Jun

H.-B.

and Kim

J.-G.

, Dynamic control of intelligent parking guidance using neural network predictive control, Computers & Industrial Engineering 120 (2018), 15–30.

23.

Xie

, Wu

, Guo

and Zhan

, Parking lot allocation model considering conversion between dynamic and static traffic, Journal of Intelligent & Fuzzy Systems 41 (2021), 5207–5217.

24.

, Wan

, Li

Optimal distribution model of shared parking space in large shopping malls at night, in: IOP Conference Series: Earth and Environmental Science, IOP Publishing, 2018: p. 032006.

25.

Y.Y.

Shared parking time window of hotels in central areas, Nanjing: Southeast University (2016).

26.

Mejri

, Ayari

, Langar

, Kamoun

, Pujolle

, Saidane

Cooperation versus competition towards an efficient parking assignment solution, in: 2014 IEEE International Conference on Communications (ICC), 2014: pp. 2915–2920.

27.

Tang

, Jiang

and Yang

, Online stochastic weighted matching algorithm for real-time shared parking,. , International Transactions in Operational Research 30 (2022).

28.

Goto

, Iwasaki

, Kawasaki

, Kurata

, Yasuda

and Yokoo

, Strategyproof matching with regional minimum and maximum quotas, Artificial Intelligence 235 (2016), 40–57.

29.

Deb

, Pratap

, Agarwal

and Meyarivan

, A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Transactions on Evolutionary Computation 6 (2002), 182–197.

30.

Elarbi

, Bechikh

, Gupta

, Said

L.B.

and Ong

Y.S.

, A new decomposition-based NSGA-II for many-objective optimization, IEEE Transactions on Systems, Man and Cybernetics: Systems 48 (2017), 1191–1210.

31.

Sivanandam

S.N.

, Deepa

S.N.

Introduction to genetic algorithms, Springer, Berlin; New York, 2007.

32.

Voorneveld

, van den Nouweland

and McLean

, Axiomatizations of the Euclidean compromise solution, International Journal of Game Theory 40 (2011), 427–448.