Office of Operations
21st Century Operations Using 21st Century Technologies
Table of Contents

Chapter 2. Project Description

Methodology and Approach

The approach in this project is to create and demonstrate a free, publicly available tool that municipalities and other interested parties can use to understand cruising for parking and the effects of policy interventions on parking search behaviors.

There are two segments to the project: developing a GPS-dependent system, Cruise Detector, to analyze parking search, and a GPS-independent cruise estimator (G-ICE). The methodology for developing each is described in turn.

Cruise Detector

Cruise Detector uses large data sets comprised of GPS locations (or breadcrumbs) harvested from smartphones or navigation devices. By studying the circuity of paths and concentrations of circuitous paths, an analyst can visualize and quantify the extent of cruising for parking. A circuitous path, defined as 200 meters in excess of a counterfactual shortest path, is designated as excess travel due to parking search, or simply as cruising. Geographic information system (GIS) analysis shows where cruising trips are located within the geography the data are analyzed.

The project developed a methodology and related code to analyze the breadcrumb data. Instructions for how to use the code are given in appendix B. Components of the code are described in detail in a number of journal articles that are incorporated in this document by reference. The process is divided into these steps:

  1. Determine streams of GPS location pings that represent travel.
  2. Match the GPS data streams to a street network.18 Each trace match is given a probability score.
    1. If the probability score exceeds a certain user-defined threshold, the match is considered acceptable for analysis.
    2. If the probability score is below the user-defined threshold, the trace is rejected and dropped from further analysis.
  3. Build a potential parking search radius around the final location.
  4. Determine a shortest path from the search radius boundary to the final location.
  5. Compare the path taken with the shortest path.
    1. If the path taken is equal to the shortest path or longer, up to 200 meters, the trip is designated as not cruising.
    2. If the path taken is greater than 200 meters longer than the shortest path, the trip is designated as cruising.
  6. Analyze the processed data to gain insight into cruising conditions in the area of interest.

Two data approaches to using Cruise Detector are tested. The first approach uses raw location data purchased directly from a data consolidator. This preserves the geometry of the trip, enabling the analyst to aggregate to spatial units and time periods for which there are sufficient data and allowing for insight regarding the actual search paths. The Chicago analysis and some of the Seattle analysis rely on these disaggregate data. The second approach relies on processed output of the system described here. A third-party owns the relevant data and processes the data behind a privacy firewall using the software developed in this project. The output is provided as point data at the street or block group level (or a requested aggregation). The shortcoming of this approach is the inability to understand the parking search path.

Using raw location data purchased from a vendor is likely to be the more common implementation of Cruise Detector. Many such data consolidators are available, and the data will vary from one vendor to the next. In some cases, data may already be segmented into trips, while in other cases the vendor may provide unprocessed GPS points and require the user to clean the data and identify which points represent trips rather than a static location, such as home or work.

This project does not attempt to assess consolidators, as the relative strengths are highly dynamic. Instead, users of Cruise Detector will have to assess data quality when using the tool. Privacy protections are dynamic and can affect data quality. Even within the time line of this project, applications that had previously broadcast steady streams of location data were modified to allow users to set preferences as to whether data would be transmitted only when that application was in use or at all times. This privacy protection limits the quantity and quality of data that had previously been available. Appendix A provides a data comparison between the processed output and the raw location data.

Determine Streams of Global Positioning System Location Pings That Represent Travel

The data will come in the form of anonymized location data from navigation devices or an unknown set of cellular phone applications. The data are messy and of variable quality but there is generally a large quantity, and sufficient trips can be identified to make inferences about relative frequency of trips and cruising trips. The data are unweighted and not useful for making inferences about the total number of trips or trip lengths.

Location pings from each specific device are organized chronologically and linked together to form traces. If there is a 10-minute or greater gap between two location pings, a new trace designating a new trip is formed. To create a trip that can be fitted to a street network, a trace must comprise relatively consistent and frequent pings. A threshold of 90-second intervals is a minimum requirement; otherwise, some cruising trips are likely to be missed and results will be biased downward. Greater frequency is preferred. Pings with low horizontal accuracy, i.e. incorrectly recorded latitude and longitude, are removed. Pings that would require unrealistic travel speeds to get from one location to the next are also removed.

Many of the traces represent only that the transmitting device is being moved around a single location, such as the owner’s home or office. To be considered a trip, a minimum distance of 400 meters must exist between the start and the end of the trace. The final trip filter required the trip to be at least 5 minutes in duration. Figure 2 illustrates a series of pings overlaid on a hypothetical street grid. Figure 3 includes lines that link the dots in chronological order. The various groupings show 10-minute or greater gaps between the end of one trace and the beginning of the next. Once the trips are established they are matched to a map so useful comparisons to network paths can be made.

This illustration represents a street grid and depicts a series of pings, represented by dots, overlaid at various points on the grid.

Source: FHWA.

Figure 2. Illustration. Locations overlaid on a hypothetical street grid.

This illustration represents a street grid and depicts a series of pings, represented by dots, overlaid at various points on the grid.

Source: FHWA.

Figure 3. Illustration. Locations linked chronologically.
This illustration represents a street grid and depicts a series of pings, represented by dots, overlaid at various points on the grid. The dots are connected by solid and dashed lines, which represent discrete chronological movements between the points.

Match the Global Positioning System Data Streams to a Street Network

Figure 4 shows how the trace is aligned to the street grid. The cluster in the top-right of the figure fails the criterion of 400 meters from beginning to end; it is therefore rejected as a trip (it may well represent someone walking around a home or an office). The ping in the bottom-right of the figure that attaches to points in the top-left of the figure fails the credible speed test and is also eliminated. After these trip parsing and data cleaning steps, the mapmatch algorithm determines the most likely path a trip will have taken.

This illustration represents a street grid and depicts a series of pings, represented by dots, overlaid at various points on the grid.

Source: FHWA.

Figure 4. Illustration. Probable trips.
This illustration represents a street grid and depicts a series of pings, represented by dots, overlaid at various points on the grid. The dots are connected by solid and dashed lines, which represent chronological movements between the points. A set of dots in the upper right is unbound by lines and is labeled entire trace dropped. A single dot at lower right is labeled ping dropped.

The matching relies on a probabilistic model that considers candidate streets on which a ping might actually belong; from there, the actual path is estimated with probability.19 Each trace is given a score reflecting the likelihood it is correctly matched to the underlying street grid. The analyst would select and only use the ones that meet a threshold for likelihood of being a good match.

Build a Potential Parking Search Radius around the Final Location

The next three steps are to: 1) build a parking search radius around the end point of each trip, 2) determine the shortest path between the trip end point and the point of entry to the search radius, and 3) map the actual path taken from the point of entry to the trip end point. Figure 5 shows all three steps. The star in Figure 5 indicates the final ping of the trip, the dashed line shows the path taken, and the dotted line shows the shortest path. In this example, the path taken exceeds the shortest path by over 200 meters and the trip is identified as cruising.

This illustration represents a street grid and depicts a star in the center of the mapped area representing the end of trace.

Source: FHWA. Map data ©2022 OpenStreetMap® contributors.

Figure 5. Illustration. Cruising: identified when paths traveled exceed shortest paths.
This illustration represents a street grid and depicts a star in the center of the mapped area representing the end of trace. A dotted line circles the star, representing a 400-meter buffer. Beginning at the left edge of the circle, a dotted line extends right by about two and a half blocks before turning left and continuing for about half a block before reaching the end of trace. This represents the shortest path. Beginning at the same starting point on the left side of the circle, a line representing the matched line extends right for five and a half blocks before turning left. The matched line proceeds then one block before turning left and continues for four blocks before turning right and circling a block. It then continues straight for half a block and ends at the end of trace point.

It is assumed that drivers do not begin searching for parking until they are 400 meters from their final location. The trace is truncated so that it includes all points after it enters the 400-meter radius, plus the preceding point. The trace can enter and leave the 400-meter radius several times—for example, if drivers cruise for parking over an extended area. Figure 5 illustrates the boundary and a hypothetical trip that has left and reentered the search area.

Determine a Shortest Path from the Search Radius Boundary to the Final Location

The pgRouting package is used to calculate the shortest path to their final location from when the driver first enters the 400-meter radius. The path takes account of one-way streets and turn restrictions, provided they are correctly mapped in the underlying street network data. This analysis uses OpenStreetMap® data, which is high quality and freely available. Again, refer to Figure 5.

Compare the Path Taken with the Shortest Path

The difference between the actual (map-matched) path and the shortest path indicates whether cruising occurs. If the difference is greater than 200 meters, the trip is classified as cruising. If the difference is zero, the driver takes the most direct route and no cruising occurs. The 200-meter threshold20 is used because small deviations from the shorter path are generally due to irregularities in the street grid or other imperceptible differences to the driver.

Analyze the Processed Data to Gain Insight into Cruising Conditions

The final step is to analyze the processed trips. Chapter 3 provides four use cases that demonstrate how the data can be analyzed. Statistics of interest could include average time spent cruising in different parts of a city or at different times of day, before-after-analyses bracketing a policy change, or location of cruising hot spots. Analysis can be presented as maps. Figure 6 shows cruising in Chicago based on disaggregate data and Figure 7 shows cruising in Atlanta based on data aggregated to the census block group level. Analysis can also be presented as a tabulation, as shown in Table 1, or a graph, as shown in Figure 8.

This map is a mesoscopic view of a section of Chicago. Cruising frequency is depicted on the map using color-coded hot spots.

Source: FHWA.

Figure 6. Map. Example showing Chicago cruising hot spots disaggregate data.
This map is a mesoscopic view of a section of Chicago. Cruising frequency is depicted on the map using color-coded hot spots. Darker hot spots represent a cruising frequency of 30 percent on in the more congested downtown area at the middle right of the map and on the bottom middle of the map. Hot spots appear sporadically throughout the map and represent a cruising frequency of less than 30 percent but more than 10 percent at most intersections.

This map provides a mesoscopic-level view of Atlanta with both Downtown and Buckhead labeled. It indicates that the downtown area experiences medium-high to high impacts resulting from cruising trips weighted by time spent per day cruising.

Source: FHWA.

Figure 7. Map. Example showing Atlanta cruising hot spots aggregate data.
This map provides a mesoscopic-level view of Atlanta with both Downtown and Buckhead labeled. It indicates that the downtown area experiences medium-high to high impacts resulting from cruising trips weighted by time spent per day cruising. Some areas south of Buckhead also experience these impacts, as do areas southwest of the downtown area.

Table 1. Seattle mean cruising time by street type and time of day, in seconds.

Street Type

2–4 p.m.

6–8 p.m.

Other Times

Metered streets

148

140

113

Near metered

110

117

111

Non-metered

57

49

56

This line graph plots all trips and cruising trips. The y-axis is labeled “Share” and ranges from 0 to 8 percent. The x-axis is labeled “end hour” and ranges from 0 to 24 hours.

Source: FHWA.

Figure 8. Graph. Example showing diurnal distribution of trips and cruising trips Washington, DC.
This line graph plots all trips and cruising trips. The y-axis is labeled “Share” and ranges from 0 to 8 percent. The x-axis is labeled “end hour” and ranges from 0 to 24 hours. The all-trips line starts at 1.5 percent share at 0 hours and decreases to a minimum of .5 percent share at 3 hours. It then sharply rises, peaking at 7.5 percent around hour 8. The all-trips line then declines to 5.5 percent around hour 11 and levels out before gradually ascending to 7 percent at hour 17. It then sharply declines and ends at just over 2 percent share in hour 23. The cruising trips line starts at 2 percent share in hour 0 then drops, hitting a minimum of .5 percent between hours 3 and 4. It then sharply rises, peaking at 7 percent in hour 12. The all trips line slightly decreases to around 6.3 percent and remains flat until hour 16, when it peaks again at 6.6 percent. From there, it sharply drops and ends at 2 percent in hour 24.

The project used and tested two primary data sources in the project execution. The first data source and accompanying basic analysis accrue to a GPS data aggregator that provides other transportation planning data analysis. The code developed in this project was given to the data aggregator and run on its secure server. The aggregator’s data represent trips inferred from large samples of location data collected from smartphone applications. The second data source is also a GPS data aggregator that sells data, but it does not provide other data analysis services. Using these location data, the project team inferred directly from raw location data and conducted further analysis to determine the extent of cruising.

Code Development

Cruise Detector uses three bespoke software processes. The first process converts location data into trips. The second process is a map-matching algorithm that snaps the trips to a transportation network so the trips can be analyzed and compared against an underlying transportation network; this is done to make a fair comparison to shortest path. This process determines the likelihood that a series of location points is correctly aligned with a known underlying geographic path. The third process compares trips to a potential shortest path and determines, with probability, whether a trip implied excess driving in pursuit of a parking place. Appendix B provides instructions for using the code.

Global Positioning System-Independent Cruising Estimates Model

Not every jurisdiction will be able to obtain GPS data, or GPS data of sufficient quantity and quality to be of use. A project goal had been to develop G-ICE, a GPS-independent cruise estimator. After several development attempts, the project team determined that, based on the data available, an effective tool could not be developed. Appendix C provides details of this effort.

18 Adam Millard-Ball, Robert C. Hampshire & Rachel R. Weinberger, “Map-Matching Poor-Quality GPS Data in Urban Environments: The pgMapMatch Package,” Transportation Planning and Technology 42, no 6 (2019): 539-553, 10.1080/03081060.2019.1622249. [ Return to Note 18 ]

19 Adam Millard-Ball, Robert C. Hampshire & Rachel R. Weinberger, Map-Matching Poor-Quality GPS Data in Urban Environments: The pgMapMatch Package” (2019). [ Return to Note 19 ]

20 Rachel Weinberger, Adam Millard-Ball, & Robert Hampshire, Parking search caused congestion: Where’s all the fuss?. Transportation Research Part C: Emerging Technologies (2020). 120. 102781. 10.1016/j.trc.2020.102781. [ Return to Note 20 ]