key: cord-0286399-f0d9j832 authors: Rahaman, Mohammad Saiedur; Shao, Wei; Salim, Flora D.; Turky, Ayad; Song, Andy; Chan, Jeffrey; Jiang, Junliang; Bradbrook, Doug title: MoParkeR : Multi-objective Parking Recommendation date: 2021-06-10 journal: nan DOI: 10.1145/3468791.3468810 sha: 0aa2e19ee18513cbddcb32ed2fef97c1994318b1 doc_id: 286399 cord_uid: f0d9j832 Existing parking recommendation solutions mainly focus on finding and suggesting parking spaces based on the unoccupied options only. However, there are other factors associated with parking spaces that can influence someone's choice of parking such as fare, parking rule, walking distance to destination, travel time, likelihood to be unoccupied at a given time. More importantly, these factors may change over time and conflict with each other which makes the recommendations produced by current parking recommender systems ineffective. In this paper, we propose a novel problem called multi-objective parking recommendation. We present a solution by designing a multi-objective parking recommendation engine called MoParkeR that considers various conflicting factors together. Specifically, we utilise a non-dominated sorting technique to calculate a set of Pareto-optimal solutions, consisting of recommended trade-off parking spots. We conduct extensive experiments using two real-world datasets to show the applicability of our multi-objective recommendation methodology. Finding street parking in crowded cities is challenging and thus requires a highly functional and efficient parking management strategy. Searching for available parking can cause congestion and wasted land use. A research found that vehicles cruising for suitable parking in Los Angles were responsible for 730 tons of carbon emissions through the burning of 47,000 gallons of gasoline in one year [10] . The research also identified that the distance travelled during the search for parking was equivalent to 38 trips around the world. These problems can be minimised by providing drivers with effective recommendations about their parking choices. However, effective parking recommendation is very complex as it is influenced by various factors such as parking fare, rule, walking distance to the destination location, total travel time, and likelihood of parking locations be available at a given timestamp. Moreover, these factors can be conflicting with each other. For instance, a lowfare parking spot may require long-distance walking to destination. Additionally, some of these factors (e.g. fare, parking rules) may vary across different times of the day which makes the parking recommendation problem more complex. With the growing trends in adopting ubiquitous technologies, many cities around the world have implanted smart sensors to collect data related to parking events. Many researchers use this data to extract meaningful information. The current research mainly focuses on predictive analytics of parking events using univariate and multi-variate signals. Another research direction uses event logs from parking sensor data to make new policies (e.g. new parking rule or dynamic parking price) [9, 13] . There are a few research that provides parking recommendation based on future availability [18] . However, this group of research rarely consider user preferences as it is challenging and complex due to the presence of multiple factors. The presence of various factors in user preferences makes the existing parking recommender systems ineffective. arXiv:2106.07384v1 [cs.IR] 10 Jun 2021 In this paper, we address the challenges associated with parking recommendations by defining a multi-objective optimization problem. We develop a recommendation engine that takes users' conflicting preferences as input and provides a set of recommended parking spots in the Pareto-front. We leverage two real-world large parking datasets to extract conflicting factors and compute personalized parking recommendations. In particular, the contributions of this paper are as follows: • Introduce a new parking recommendation problem called multi-objective parking recommendation which has a range of prospective implications for smart cities. • Design of a multi-objective parking recommendation engine based on a non-dominated sorting technique. This approach is further refined by adopting a crowding distance mechanism with objective-thresholding. • Design a system prototype that is able to compute and present end-to-end travel routes connecting recommended parking spots. This section discusses current research utilizing parking sensor data and the application of multi-objection recommendations in various fields. We also highlight the challenges of integrating multiobjective optimization in parking recommendations considering the current state of research. Finding an available car park is challenging for urban drivers. To help drivers find parking locations in the CBD areas, various research has been conducted that use probabilistic and machine learning models to predict parking occupancy or duration. In this cohort of research, various types of sensor feed (e.g. vision-based sensors, physical sensors) are used Since most parking data are recorded from in-ground sensors, many researchers tend to study on extracting features from time-series data and spatio-temporal data to explore the correlation between contextual information and parking availability [1, 14, 16] . Recommender systems suggest items so that the users' potential interests are met or at least optimized. In multi-objective recommendation, users have more than one preference to be considered by the recommendation engine. Usually multi-objective recommendation is considered as a multi-objective optimization problem [2] . One of the approaches to address this problem is to find a set of Pareto-optimal solutions. Several domain-specific research has been conducted in this area [15, 17] . To investigate the multi-objective parking recommendation, this research utilises smart parking datasets from two city councils in Victoria, Australia. The first dataset is a continuous log of more than 4650 in-ground parking sensors around the Melbourne CBD area. The sensors are capable of detecting parking events. A total of 5.9 million records are present in the 2017-18 parking dataset which is publicly available through the open data portal of the City of Melbourne 1 . The second dataset was collected from the city of Rye as part of Victorian government's Smart City and Smart Suburb project. This dataset integrates parking-event feeds from in-ground as well as vision-based sensors. Both of the datasets have similar attributes to describe a particular parking event in a time-series manner. To understand the parking behavior in these two cities, we plot heatmaps of parking locations in terms of frequencies of parking events and time-usage. Figures 1 and 2 illustrate different parking patterns in these two cities. The heatmap in Figure 1 (a) shows average parking events of two-weeks between 8.30 am and 9.00 am in different parts of Melbourne CBD while Figure 1 (b) depicts a time-usage heatmap of parking locations. We can see that the parking locations with a high number of parking events are also accounted for high utilisation times. However, there are many other locations with lower parking events that turned out to be highly utilised by single parking events within the selected time window. In contrast, similar locations seemed to be highly utilised in terms of both events and time-usage in Rye as can be seen from Figures 2(a)-(b). We plot the average utilisation in the first two weeks of January 2020 between 2.00 pm and 2.30 pm. This may be due to the fact that Rye is a busy tourist spot on the coastline where these parking locations provide easy access to the beaches and shops. In this section, we present MoParkeR, a multi-objective parking recommendation engine. Our parking recommendation engine has two main components: i) parking sensor data processing and ii) user query and response. The key components of the MoParkeR is given in Figure 3 . 3.2.1 Parking sensor data processing. In this module, parking events data collected from sensors (i.e. in-ground and vision-based) are stored in the central storage. Since two side-by-side parking bays are of less significance in terms of their physical location, we cluster those to form parking lots. We adopted a spatial-clustering technique to form parking lots consists of multiple parking bays. Specifically, two parking bays are part of a single parking bays (i.e. cluster) if both are connected to each other, or the distance between these slots is within a specific value and they have the same parking restriction (e.g. 1 hour, 2 hours, loading zone). This processed data is then stored in a parking lot database which is used to handle user queries. This module is responsible for processing user queries to provide parking recommendations. As can be seen from Figure 3 , a user-defined query consists of a user's source location, the destination location, and a set of objectives. Once a query is defined, it is sent to the parking sensor data processing module which returns the locations of parking lots. The APIs in response generator utilises these locations of the parking lots to compute the objective values and create a response dataset. In practice, the likelihood of parking spaces needs to be estimated from real-time data. One of the APIs plays as a sub-module of the 'Response generator' which is responsible for Likelihood prediction of parking spaces. This prediction API uses state-of-the-art techniques to generate likelihood prediction. To provide a multi-objective parking recommendation, this research computes four response factors associated with each parking lot. First, we consider the total travel time from source to destination for a recommended parking lot. Given a source location , destination location , and any parking lot , the total travel time is defined as follows. Here, ( ) is the total travel time if a drive needs to park at parking lot . ( , ) is the travel time from source location to parking lot while ( , ) denotes travel time between parking lot and destination . Second, we define the required walking distance from any parking lot to destination as follows. Here, ( , ) is the walking distance between and . Third, for a parking duration of in a parking lot , we consider the dynamic parking fare as follows. Here, ≥ 0 is the parking fare for duration of parking at . Fourth, we compute the likelihood of a parking spot being available as follows. Here, ( ) ≥ 0 and 0 ≤ ( ) ≤ 1; ( ) is the occupied time of any parking bay within a parking lot , is the number of parking bays within , and is the length of the time window when a driven will arrive at . Therefore, =1 ( ) is the average occupied time of parking lot . Once the responses are computed using Eq. 1-4, it is forwarded to the multi-objective parking recommendation engine which computes recommended parking lots. The recommended lots are used by the routing engine to provide routing support to the user. Multi-objective parking recommendation engine. A driver who is planning to drive from a source to a destination needs to find a suitable parking location to park her car before walking to the destination. The suitability of a parking location can be dependent on various crucial factors including the total travel time, required walking distance from any parking lot to the destination, parking fare, and likelihood of getting a parking lot available. We assume the user would prefer the path that connects a parking lot with lower parking fare, shorter travel time and walking distance, and a higher likelihood of getting an available bay in a parking lot. However, in practice, these factors may be in conflict with each other. In this case, one should provide a set of trade-off parking lots, which are termed the pareto-optimal parking lots, instead of one single global optimal solution. In our research, we have three objectives to minimize and one objective to maximize. The four objectives to be minimized or maximized in parking recommendation can be described as follows: where, ( ) is the total travel time from source to destination if parking lot is chosen, ( ) is the walking distance from to destination, and ( ) is the fare of , and ( )is the likelihood of getting an free parking bay at . Given two parking lots ,1 and ,2 , ,1 is said to dominate ,2 if and only if all the objective values of ,1 are no worse than those of ,2 , and there is at least one objective for which ,1 has a better value than ,2 . We denote ,1 ≺ ,2 for ,1 dominating ,2 . A parking lot * is said to be Pareto-optimal, if and only if there is no other parking lot that dominates * . The goal of this problem is to find all the possible Pareto-optimal parking lot and provide a smaller list as recommendation. In this paper, we employed an epsilon-nondomination based multi-objective sorting algorithm to find the Pareto-optimal parking lots. The details of epsilon-domination framework are described in [3, 8] . Since there could be many elements in the Pareto front, we adopted a Crowding distance technique to achieve a smaller number of parking lots for final recommendation. The concept of crowding distance is to measure the relative isolation of a solution in the Pareto front from other solutions. The greater the crowding distance, the greater is its isolation and hence, higher chance to be included in the final recommendation. We further refine the selected solutions by applying an objective-thresholding. Specifically, we consider a threshold for an objective, e.g., for parking likelihood in our case to ensure that the solution subset only comprises of the parking spaces with high likelihood. Algorithm 1 illustrates the deployed crowding distance calculation mechanism in our study. Given a set of candidate solutions and objective-threshold , this algorithm computes crowding distance of all candidate solutions in . The computation starts by initializing all candidates to 0. Upon satisfying the objective-threshold , the candidates are sorted in ascending order in turn for each objective. Note that the first and last candidates (i.e. boundary points) from the sorted list are selected automatically as they have an only neighbor candidate in total. Hence, we assign the largest crowding distance score of ∞. Give any objective, the crowding distance for the rest of the candidates in are calculated as follows. First, we subtract the objective value of candidate −1 from the objective value of candidate +1. Then the result is divided by the ( . ) − ( . ) where, ( . ) and ( . ) are the maximum and minimum objective values in for objective . The final crowding distance is computed by repeating this process and taking the sum over all of the objectives. Routing engine. Once computed, the recommended parking lots are considered to generate journeys from any source location to the destination location connecting all recommended parking lots. Specifically, driving routes from the source location to parking lots are constructed before generating walking routes from parking lots to the destination location. For route generation, APIs such as Google Map can be utilised. In this section, we present the experiential results of the proposed approach. To evaluate our approach, we develop a system prototype and conducted two case studies for two cities in Victoria, Australia including the city of Melbourne and the city of Rye. These cities are good examples for the experimental studies as one of these is a busy business district while the other is a popular tourist spot. In this case study, we find connecting parking lots for journeys between the source location, State Library (point A), and destination location, St Vincent's hospital (point B). These two locations are situated in inner-city Melbourne. Figure 4 shows four journeys connecting four different parking lots computed by our MoParkeR engine. These parking lots are chosen arbitrarily from the set of recommended parking lots for illustration purposes. A full list of recommended trade-off parking lots are given by Table 1 . To generate these journeys, we first applied MoParkeR to calculate a set of non-dominated (i.e., Pareto-optimal) parking lots. The computed Pareto front can have a large number of parking lots since we have four objectives to consider. To reduce the users' information burden, this number is further reduced by applying a crowding distance mechanism and objective-threshold in the computed Pareto-front before presenting the final recommendations. Upon calculation of final recommendations, the journeys can be constructed by using direction services (e.g. Google API). We can see from Figure 4 that the four recommended parking LotIDs have non-dominated objective values in terms of travel time, walk to a destination, parking fare, and parking likelihood. For instance, the LotID-172 requires a driver smallest walking to the destination (i.e. 0.4 km) with an end-to-end travel time of 14 minutes, a fare of $0.6 and a very certain likelihood of parking. On the other hand, LotID-5129 provides users with a free parking lot but costs a long walk to destination after parking the car which also causes a longer travel time. All these trade-off parking lots satisfy our recommendation refinement criteria (i.e. likelihood ≥ 0.7) for an increased chance of getting a parking spot available to park. This case study was conducted by selecting a random pair of source and destination locations in Rye which is a tourist hot-spot of regional Victoria in Australia. We employ MoParkeR recommendation engine to construct journeys from Rye community house to Rye pier on a Saturday afternoon (i.e., 11th of January 2020) as it was peak-time for tourist visits before COVID-19 lock-down in Australia. These locations are marked in Figure 5 as A and B respectively. MoParkeR computed seven trade-off parking lots to construct journeys between A and B. Our MoParkeR engine constructed seven journeys from A to B connecting all of these parking lots. For illustration purpose, four journeys are projected in Figure 5 . We can see that all these recommended parking lots reside within four different routes are non-dominating to each other in terms of our defined conflicting objectives (i.e. minimal travel time, minimal walk to destination, minimal parking fare and maximal parking likelihood) and all of those satisfy the objective-threshold for likelihood which is 0.7 or more in our experiments. To demonstrate the effectiveness of MoParkeR, we conduct a utility analysis. First, we conduct a utility comparison with currently available parking recommendation solutions. As can be seen from Table 3 , no other solutions except MoParkeR provides trade-off parking lots considering parking cost, walking distance to destination, total ✓ proximity to dest. Parking Assignment [6] ✓ Parking rank [4] ✓ parking space count ROSAP [11] ✓ Park Indicator [12] proximity to parking MoParkeR ✓ ✓ ✓ ✓ travel time from the source location to destination and likelihood of getting a parking lot available. One of the solutions considers two utilities (i.e. parking cost and proximity to destination). However, since this approach does not consider parking likelihood, the recommendation can be ineffective when the driver arrives at the parking location with no availability. Additionally, since there is no standard approach for multiobjective parking recommendation, we design a greedy approach to conduct a further comparison with MoParkeR. Unlike considering the proximity of the parking lots in relation to the current location of the vehicle, the greedy approach recommends a parking slot based on a predefined proximity threshold with respect to the destination location. Since MoParkeR employs a non-dominated sort, it generates a set of trade-off recommendations considering four utilities associated with a parking lot: fare, walking to a destination, travel time, and parking likelihood. It is guaranteed to always pick parking lots with the lowest travel time, smallest walking distance to destination, lowest parking fare, and high likelihood in addition to other trade-off recommendations. On the other hand, the greedy algorithm rarely picks parking lots with these finest constraints as it employs a random approach. We run both approaches 100 times and log the proportion of times a parking lot with these finest constraints were chosen. MoParkeR always selects parking lots with the smallest fare, travel time, walking, and the largest likelihood in both Melbourne and Rye datasets. In contrast, the greedy approach rarely picks parking lots with the lowest fare in Melbourne and Rye datasets (i.e. 14% and 18% cases respectively). For the smallest travel time, these ratios are 11% and 14% for Melbourne and Rye respectively. The greedy approach selects parking lots that require the smallest walking to destination in 13% and 16% cases in these two datasets. However, the likelihood of getting parking spaces available within the recommended solutions is very low (i.e. 7% and 10% in Melbourne and Rye datasets respectively). We also show that the parking likelihood used for recommendation generation is predictable. The prediction API resides in the 'Response generator' module of MoParkeR implements three stateof-the-art time-series prediction models to both of our datasets. Table 4 shows that LightGBM outperforms the other two deep learning models for both datasets and ConvLSTM does a better job in the Melbourne data in terms of MAE. All methods achieve good results in parking availability prediction, which suggests that the parking vacancy is predictable. Therefore, seeking for a vacant parking slot in advance considering the likelihood is possible by using time-series prediction approaches. The primary goals of the paper are to formalize a novel problem called multi-objective parking recommendation and to present a solution by designing a multi-objective parking recommendation engine that considers various conflicting goals together. These goals have been achieved by formalizing a novel problem and employing a non-dominated sorting technique to calculate a set of recommended parking spots in the Pareto-front. The results show that our MoParkeR is able to provide a wide range of reasonably good parking lots in terms of travel time, walking distance to the destination, parking fare, and parking likelihood. The developed MoParkeR can make several implications and benefits to the users including: • Improved total journey information provided by MoParkeR could be ultimately accessible for users to find the optimal parking location will only assist to support the economic, environmental, and amenity of towns and cities. • Tourists and visitors will also be able to plan trips more effectively dependant on their individual needs for a more enjoyable visit to a high demand attraction consequently ensuring economic stimulus to regions. • Social benefits are also feasible with special users with for example that need to locate the convenient disabled parking bay that minimises walking distances and total trip time. • For parking management and planning, MoParkeR could be utilised to assess the ratings of various trip scenarios to establish the optimal parking fees and parking control time limits to match user tolerances and requirements. We presented a solution to the multi-objective parking recommendation problem. We adopted an epsilon-domination approach to compute trade-off parking lots in the Pareto front considering four objectives: total travel time, walking distance to destination, parking fare, and parking likelihood. We further refine the recommendations using a crowding distance and objective-threshold computation. The applicability of our MoParkeR engine is illustrated by the deployment in two cities in Australia. Future research may include a user study to investigate the user experience of using such a multi-objective parking recommendation engine along with the inclusion of more objectives and ways to provide a reduced number of parking recommendations by considering the actions of other drivers. Parking allocation upon the recommendation in real-time is another avenue of research that will be inspired by our work. A blockchainbased architecture for integrated smart parking systems Multi-objective optimization using evolutionary algorithms Evaluating the -Domination Based Multi-Objective Evolutionary Algorithm for a Quick Computation of Pareto-Optimal Solutions Parking rank: A novel method of parking lots sorting and recommendation based on public information New "smart parking" system based on resource allocation and reservations Parking Assignment: Minimizing Parking Expenses and Balancing Parking Demand Among Multiple Parking Lots iParker-A new smart car-parking system based on dynamic resource allocation and pricing Combining convergence and diversity in evolutionary multiobjective optimization Dynamic pricing and reservation for intelligent urban parking management Parknet: drive-by sensing of road-side parking statistics Reservation-based multiobjective smart parking approach for smart cities Park Indicator: Book Your Parking Spot Optimal dynamic parking pricing for morning commute considering expected cruising time Wait time prediction for airport taxis using weighted nearest neighbor regression CAPRA: A contourbased accessible path routing algorithm Clustering big spatiotemporal-interval data A multi-population memetic algorithm for dynamic shortest path routing in mobile ad-hoc networks A real-time parking prediction system for smart cities This work is supported by the Australian Government and Mornington Peninsula Shire Council through the provision of a Smart Cities and Suburbs Grant.