Introduction
It has been estimated that close to 30% of the cars circling a city at any given time are doing so as drivers look for parking (Donald Shoup, Professor of Urban Planning, UCLA, (2011)). In addition to the drivers’ frustration, those cars are creating traffic congestion. In 2014, the World Bank estimated that urban drivers waste 111 hours a year on congestion, which translates into $2 trillion a year in lost productivity. From an environmental perspective, this congestion translates into large amounts of wasted fuel and carbon emissions. Congestion and parking are closely correlated, since cruising for a parking space creates additional delays and harms local traffic circulation. In central areas of large cities, cruising may account for more than 10% of the local circulation, as drivers can spend 20 minutes looking for a parking spot (Dr. Jean-Paul Rodrigue of Hofstra University). In an effort to make urban parking much easier, EasyPark developed a smartphone application that makes it quicker and easier to find, pay, administer, operate and plan parking through the use of mathematical optimization.
The Problem
The key inputs of the parking optimization capabilities are:
The destination: Determines where the user would like to park.
Parking spots: A map of all parking spots in the city (including time-of-day restrictions).
Predicted availability: Probability of a spot being available (at the current time, by city block).
Route information: Maps for reaching areas that have available spots near user destinations.
The first step to deploy EasyPark in any city is to create a map of all parking spots. EasyPark collects data related to street parking by sending their vehicles to crawl the streets and take photos. Data scientists at the company use machine-learning models to read and interpret the photos taken. In addition, EasyPark collects data related to off-street paid lots. The resulting database is typically more accurate than the data managed by the city itself. The data science team estimates the probability of finding a spot by time and by city block, using a Bayesian statistical model. There are five main data sources for the predictions:
Historical transactional data: This data can help identify patterns. For example, if several people leave at 5 pm, then it is likely that this event happens again on the next day.
Mapping operations: EasyPark has vehicles that travel the city central areas block by block and keep track of all the open parking spots. This data is more accurate for those places that have been checked recently.
Geographic information system (GIS): EasyPark does the mapping and gets information about the availability of parking spots. However, they cannot cover every spot in a city. Therefore, to estimate availability of nearby streets, EasyPark takes under consideration bars, restaurants, schools, etc. and they also look at congestion of a sampling of nearby streets.
User transaction data: EasyPark allows customers to pay for parking directly through their app, giving EasyPark real-time information on when parking spots open up.
User route data: The EasyPark app tracks the user’s location. If the user is moving and not stopping on a particular street, it means that there is no parking available on that stretch of the street.
The Solution
EasyPark uses a mixed-integer programming (MIP) model to compute the best route to search for a spot. The key inputs of the MIP model are:
User destination.
Probability of finding a spot on a block, which decreases significantly the second time the user traverses the block.
The objective function is to minimize the time to reach the destination, which is equal to the time it takes to find a spot, plus the time to walk to the actual destination. The output of the MIP model is the route the user needs to follow. This route may need to traverse low-probability blocks to reach high-probability blocks.
Results
The benefits that EasyPark has identified from the MIP solution are:
30-50% reduction in time required to find a parking spot.
Better parking data compared to traditional data recording done by the municipalities themselves.
Potential value extends beyond finding an open spot.
Demand-based pricing to adjust parking prices to reflect expected congestion.
Ability to determine best locations for adding additional parking capacity
The MIP model was built by Yossi Amgar. Yossi has a bachelor’s degree in computer science and does not have formal training in mathematical optimization. EasyPark chose Gurobi for three reasons:
Performance: Gurobi solved the problem faster than competing solvers.
Support: Great technical support that is easy to reach.
Modern IT: Gurobi’s cloud solution scales easily.
About EasyPark
EasyPark was founded in 1997 in Stockholm, Sweden. EasyPark operates in more than 700 cities across 13 countries, primarily in Europe and Australia. The company’s vision is to make “urban life easier – one parking spot at a time.” EasyPark is a smartphone application that helps you pay for parking, as well as find an open parking spot with the help of optimization. For more information visit: easyparkgroup.com.
