-The problem of finding parking spaces in big urban areas is one of the unsolved challenges of Smart Cities causing traffic congestion, increased carbon emission and time wasting. Network and sensor technologies available today allow to foresee Smart Cities equipped with applications able to provide real-time information on parking space availability, which can be used to assist motorists in looking for a parking space. In the present work, we propose a smart parking application that relies on the use of software agent negotiation as a mechanism to automate the selection of parking spaces according to the user preferences, but at the same time to take into account city needs in terms of areas motorists should avoid, or car pars occupancy at a specific time. Both city needs and user's preferences are dynamic information managed by the negotiation mechanism at the time a user's request is processed, so providing a dynamic-based selection of a parking space.
One of the big unsolved challenges to make Smart Cities
a reality is the provision of Smart Parking applications. The
overall objective of Smart Cities is to improve city life, so
the provision of smart and sustainable parking solutions is
becoming a key priority. In fact, several studies made it
evident how the problem of searching for a parking space in
high populated urban areas is a source of traffic congestion,
increased carbon emission and, not least, a very frustrating and
time consuming experience for motorists [
Several industry efforts have already produced solutions in this direction by making use of advanced Information and Communication Technologies including vehicle sensors, wireless communications, and data analytics in order to improve urban mobility. Some cities have adopted these solutions in pilot areas installing wireless sensors able to detect parking space occupancy in real time. In addition, smart parking meters, allowing for a wide variety of available payment methods, are being developed in conjunction with the dissemination of parking availability information.
Based on the information that can be collected on parking
spaces occupancy, location and directions, applications
assisting users in selecting a parking space are being developed.
Many of the proposed approaches deal with the smart parking
problem mainly as an optimization process from the drivers
point of view. However, Smart City applications have to
include benefits and revenues for the city itself. In fact, effective
smart parking applications should be designed not only to
make it easy for motorists to search for parking spaces, but
also to take into account specific city needs that cannot always
been known in advance and that may change in time according
to volatile events effecting car circulation at specific time
intervals. At this purpose in [
In this paper, we present a prototype implementation of
a web-based application for smart parking, based on the
negotiation-based approach presented in [
II.
A smart parking system is a complex system composed
of several hardware devices able to detect the city occupancy
level of parking spaces, and software components integrated to
manage the allocation of these parking spaces by redirecting
cars accordingly (see Figure 1). Usually, such systems are
designed to assist motorists in the localization of available
parking spaces, so that they can decide which space to select
according to their own needs [
In the present work, we assume that Smart Cities will be equipped with such a complex system, and we propose to extend it with a software module implementing an application that can make decisions on where to park on behalf of a motorist, taking into account not only his/her needs, but also the social benefit for the city. In the proposed approach, a decision on where to park is the result of an automated negotiation process between two software agents: the User Agent (UA) acting on behalf of the motorist, and the Parking Manager (PM) who is responsible for managing parking spaces belonging to different car parks located in the city, which are offered to users as a global city facility. This means that different car parks owners agreed to subscribe to a City Parking System, managed by the Parking Manager, by delegating the selling of their parking spaces (partially or globally) to it. Hence, the Parking Manager is the authority responsible for allocating the parking spaces, virtually belonging to the City Parking System, but it is also responsible for collecting the information concerning specific city needs regarding transportation that will be gathered from the city council offices managing it.
Negotiation is used in order to accommodate both users and city needs that are different and, more importantly, conflicting. In fact, the Parking Manager has the objective to sell parking spaces to make a profit, but to prevent, as much as possible, motorists to park in a specified area, while users would prefer to save as much money as possible, and at the same time, to park close to the city destination they require.
In many decision-making situations in transportation, the competitive alternatives and their characteristics are reasonably well known in advance to the decision makers (passenger, driver). On the other hand, motorists usually discover different parking alternatives one by one in a temporal sequence. Clearly, this temporal sequence has a very strong influence on the driver’s final decision about the parking space. In our work, the Parking Manager selects a set of car parks belonging to the City Parking System, but the temporal sequence in which they are offered during negotiation privileges first car parks meeting also city needs requirements.
The goal of the negotiation between the User Agent and the
Parking Manager is to select a parking space that represents
a viable compromise between the driver’s and the city needs
(represented by the Parking Manager preferences), so reaching
a sort of utilitarian social welfare. In other words, we propose
to find an allocation of parking spaces that is viable from
a global social benefit point of view. The concept of social
welfare, as studied in welfare economics, is an attempt to
characterize the well-being of a society in relation to the
welfare enjoyed by its individual members [
The possibility to monitor parking availability in real time
opens up an opportunity for the provision of smart parking
solutions that facilitate advance parking space reservation by
setting up dynamic pricing policies, as in [
Dynamic pricing can serve a number of purposes. It can
be used to maximize revenues for parking operators by setting
higher fees during peak times and in more demanded areas
[
Obviously, parking pricing should be carefully studied in the context of the considered city. In this work, it is assumed that the Parking Manager tries to incentive drivers to park far from areas that are either highly congested, or where specific events affecting traffic take place, such as concerts, demonstrations, road works, and so on. The use of negotiation allows to consider these events at the time a parking request is issued, so managing the dynamic nature of such type of information.
In order to push users to avoid some city areas, a dynamic cost model is associated to the City Parking System. Once a specific zone to be avoided is selected by the Parking Manager, we refer to as a red zone, the area around this zone is divided in several rings, referred to as sectors, that account for the distance between a car park and the specific red zone. The first sector, named sector 1, is centered in the red zone with a radius that can be set according to some criteria. The price associated to parking spaces depends on the sector the corresponding car park belongs to, so the farther the car park is from the red zone, the cheaper it is. In addition, in order to incentivize the occupancy of less crowded car parks, a discount factor is applied to each car park in accordance to its occupancy w.r.t. its total capacity.
In the present work, we adopt the negotiation mechanism
reported in [
At the first negotiation round, the UA issues a request (i.e.
a call for proposal) for a parking space specifying his/her
destination location, the time interval he/she needs to park for,
and the importance level (weight) for the considered parking
space attributes. The PM may either reject the call, if there
are not offers available, or it sends back an offer consisting
in a parking space solution selected from the set of available
offers. The PM calculates, at the first negotiation round, the
entire set of available offers by selecting a set of car parks
within an area centered around the user’s requested destination
location, and whose dimensions are set according to some
criteria (e.g. a small area if the user wants to park far from
the red, and wider in the opposite case). Once the set of car
parks is selected, the PM calculates the corresponding prices to
offer according to the price model previously described. Then,
it ranks the offers according to its own preference criteria that
take into account the city needs. The offers are sent one by one,
at each negotiation round, in their ranking decreasing order.
When receiving an offer, the UA evaluates it, according to
its own evaluation criteria, to decide whether to accept or to
reject it. In the case of rejection it can iterate the negotiation
process by sending another call for proposal. It should be noted
that an offer proposed by the PM in a negotiation round is
not considered available in future rounds once it is rejected.
This assumption models the possibility that a rejected parking
space may be offered to another user in the meantime, or its
price may change according to the parking market trends as
in [
Both the PM and UA preference criteria on a parking space
offer are modeled through utility functions based on the
MultiAttribute Utility Theory defined on independent issues [
attri normf actori ) (1) where n is the number of considered parking space attributes attri, normf actori is the corresponding normalization factor, n and wi is the corresponding weight, with P wi = 1. i=1
Here the same utility functions presented in [
In order to provide Smart Cities with an intelligent smart parking solution to be integrated in a more complex City Parking System, we designed and implemented a web-based multi-agent application to automatically select parking spaces in reply to user’s requests. The application was tested in a case study based on both real and simulated information, to assess the suitability of software agent negotiation in the context of intelligent parking. The architecture of the implemented prototype is shown in Figure 2 reporting its main components.
The negotiation module is implemented by using the JADE
framework [
and travel time from a selected car park to the user’s destination location, the Car Park Database to retrieve information on the available car parks,
ing roads accessibility-related information.
The contents of the Car Park Database are retrieved from the
OpenStreetMap application [
In order to assess how software agent negotiation can be used in the selection of parking spaces in a urban area, a set of experiments were carried out considering the city of Naples as the target area. The negotiation mechanism is proposed as a means to incentive motorists to consider parking space solutions that are related not only to their own preferences.
Our reference scenario consists of a set of users that make requests to park in different zones of Naples on the day a football match will take place. For this reason, it is considered beneficial for the city to make motorists to avoid the area around the football stadium for parking, in order to limit traffic congestion. So, the red zone is represented by the city sector (sector 1) centered in the location of the football stadium, with a radius set to 500m (the radius value can be set by the PM according to several factors such as viability conditions in the surrounding area, the number of car parks available in the surrounding areas, and so on). The rest of the city is split in sectors as well, starting from sector 1, with an exponential increased radius. The experiments simulate 60 queries (qi) with destination locations distributed in sectors 1, 2 and 3 (20 queries in each sector), as shown in Figure 3. The sectors are determined with respect to the red zone (target t), and the destination locations are randomly generated. The threshold value for all users is set to 0.7 in all the experiments.
For each generated query the negotiation process between the UA and the PM takes place. In Table I we report, for each set of queries (respectively for sector 1, sector 2 and sector 3), the mean value together with the standard deviation of the following attributes of the parking space (si) selected after the negotiation: the UA and PM utilities (UUA and UP M ), its distance from the red zone (Dist(t)), its walking distance (Dist(qi)) and travel time distance with public transportation (T ime(qi)) from the query destination location, its offered price (P rice), its position in the PM ranking (RankP M ), and the social welfare value (SW ), obtained as the sum of UA and PM utilities. The ranking position of si corresponds to the number of the negotiation round at which the offer was sent by the PM, so representing the length of the negotiation (i.e., the number of rounds necessary to reach an agreement between the UA and the PM).
The obtained results show that the PM and UA utility values for the selected parking space increase when users’ destination locations are far from the red zone. Furthermore, the negotiation length increases when users want to park in the red zone, since it is more difficult to find a compromise. In fact, when users require destination locations far from the red zone the social welfare (last column of Table I) increases since the needs of both the PM and the UA are easily satisfied. The distribution of the selected parking spaces for the considered queries is reported in Figure 4, showing that the parking spaces are selected in accordance with the objective to prevent motorists from parking in the red zone.
In order to evaluate the benefit in using negotiation to find a compromise between the PM and the UA, we also evaluated the attribute values of parking spaces chosen respectively by the PM and the UA without negotiation. In this case, the PM and the UA select respectively the best parking space that maximizes their own utility functions. Of course, in order for the PM and the UA to chose the best parking space, it is assumed that they both share the same information concerning the available parking spaces.
In Table II the same attributes described in Table I are reported for the best parking space for the UA (U Abest). As expected, in this case, the UA preferences are privileged while the PM utility value increases only for locations far from the red zone. Note that the ranking position of the selected parking space for the PM is in average 20, meaning that in case of negotiation such parking space would be offered to the UA only after 20 rounds, so requiring a longer (and hence more costly) negotiation w.r.t. the case reported in Table I, where the average number of rounds is 5.5. Finally, the price of the U Abest is in the average higher then the price of the si because it corresponds to parking spaces nearer to the query locations and, hence, nearer, in average, to the red zone.
In Table III the same information as Table II is reported, but considering the best parking space for the PM (P Mbest). In this case the PM preferences are privileged, while the UA utility value increases only for locations far from the red zone. Of course, the ranking value of the best parking space for the PM is 1, because it represents the best choice for the PM, whose utility value is 1 because it is normalized w.r.t. the max values of the parking attributes available for each query. P rice e 4:5 1:0 2:8 0:4 1:5 1:0 2:9 1:5
RankP M 34 5 17 6 9 6 20 12
The average values of social welfare, reported in the last rows of Tables II and III, are lower than the one obtained with negotiation, since in these cases only the needs of one agent (respectively the UA and the PM) are taken into consideration. By the way, the average values of SW in the three tables are very close, but the values relative to each sector differ, so showing that negotiation is useful to improve social welfare when users want to park close to a red zone (i.e., for sector 1), while for sector 2 and 3 the social welfare is comparable.
The distribution of the best parking spaces for the UA, reported in Figure 5, is similar to the distribution of query locations, meaning that without negotiation users are not prevented from parking in the red zone. While the distribution of the best parking spaces for the PM, reported in Figure 6, is similar to the distribution of the parking spaces selected with negotiation since in this case the PM needs are considered.
V.
RELATED WORKS
Multi-agent negotiation was already used in Intelligent
Transportation System applications. In [
Dynamic pricing mechanisms are being used in the context
of parking applications. In [
The optimal allocation of cars in car parks was also studied
in [
CONCLUSION
Smart parking applications should make it easier for motorist to find a parking space, and so help in reducing traffic congestion, carbon emission, and users frustrations and time wasting, leading to a benefit for the whole city as a side effect. But in order to really improve the living conditions of city life, Smart Cities should rely also on the contribution of local authorities providing information regarding city regulations and decisions that, if shared, could help to design smarter applications. Typically, this type of information is very dynamic depending also on unforeseen events. For these reasons, we proposed a smart parking application having as a main objective to reach a social benefit as well as helping users. The implemented mechanism aims to maximize the social welfare of users and city managers finding a compromise between their goals sometimes in conflict. The classical way to achieve such a compromise is through negotiation, that we propose as the underling mechanism of a smart parking application.
In this paper, we described a first prototype of the negotiation process in order to assess its suitability in the context of smart parking. The experimental results, obtained in testing the application, showed that negotiation may improve the social welfare mainly when the goals are conflicting. In future works we plan to extend the experimentation to evaluate the possibility of achieving optimal social welfare by varying the values of parameters that characterize the negotiation mechanism.
The research leading to these results has received funding from the EU FP7-ICT-2012-8 under the MIDAS Project, Grant Agreement no. 318786, and the Italian Ministry of University and Research and EU under the PON OR.C.HE.S.T.R.A. project (ORganization of Cultural HEritage for Smart Tourism and Real-time Accessibility).