OpenTripPlanner has made rapid progress over the last few years and is now being used in production systems providing multi-modal itineraries to public transit riders, pedestrians, and cyclists around the world.
However, the routing engine at its core has the potential to answer much more general questions about efficient paths through the city. These possibilities are what originally drew me to OpenTripPlanner, and my primary role within the project is now expanding OTP’s range of applications beyond passenger information into the areas of spatial analysis, urban planning, accessibility research, and transportation engineering.
All paths explored while finding a single itinerary (with goal direction disabled)
Many of these applications require very large batches of near-identical requests with the origin or destination taking on every value in some set. That set might be the centroids of census tracts when evaluating effects of a public transit service cut, the location of all real estate transactions over a given year in a housing price study, or a regular grid of cells or pixels in urban accessibility and travel time mapping applications.
At first glance, using OTP to find paths from some origin to thousands or millions of individual destinations seems like an excruciatingly slow process – and it would be if we adopted the naïve strategy of making the same request to the server over and over, changing only the destination each time. However, algorithms that find a shortest (a.k.a. lowest cost or “best”) path through a multi-modal transportation network produce a great deal of internal information that is discarded after only a few itineraries are returned to the user. With appropriate modifications this data about alternate paths can be retained and put to use in a variety of ways.
The OTP Analyst extension does just that. When finding an itinerary from point A to point B, many path search algorithms, from Edsger Dijkstra’s 1959 classic to it’s newer timetable-friendly variants, also produce paths to every point closer than B as a byproduct with no extra effort. By simply letting the algorithm run a little longer until the search reaches every corner of the graph, we obtain every shortest path branching out from a given origin point.
Taken together, all these paths form a “tree” rooted at a given departure point (or arrival point in the case of an arrive-by search). This data structure contains a lot of implicit information about the temporal landscape of the city as perceived from its root. We can for example calculate travel time to an arbitrary point within the geographic area covered by our OTP server by simply finding the closest segments in the street network, taking the perpendicular distance to those segments, and adding the travel time for the final leg to that given by the path tree. Travel time is then a function defined over a continuous 2D domain (a surface), and this function can be evaluated at any set of points specified by the user. Once computed, relationships between these points and neighboring streets can be cached, allowing results to be rapidly re-evaluated when some search parameter is changed.
The problem remains of how to meaningfully display or analyze all this information. Perhaps the most straightforward option is a map layer using colors or transparency to indicate travel times. In this case, the travel time function is simply evaluated at a regular grid of points corresponding to the individual pixels that make up a map in a particular projection. OpenTripPlanner exposes this method as a WMS service and a tile layer that can be overlayed on any standard base map.
A regular grid of points linked to the nearest street segments in an OTP routing graph.
As a demonstration of these capabilities, we have set up a demo at http://analyst.opentripplanner.org/opentripplanner-analyst-client/. Since the Analyst module was recently merged into OTP proper, all the usual trip planner parameters now apply to Analyst requests, including departure time, mode of transportation, and maximum walking distance. The screen capture below shows public transit travel time from a point in central Washington, DC, with each color band representing 30 minutes of travel time in the order green, blue, yellow, red. Note that these are not solid blocks of color – the travel time gradient is expressed to one-minute resolution by varying saturation within each band.
Travel times from a point in central Washington, DC. Each color bands represents 30 minutes.
Multiple rasters can also be combined on the server side. A good example is the potential path area visualization, labeled “Hägerstrand” in the demo after the geographer who theorized it. Given an origin and destination place and time, it maps the remaining time to perform some activity along the route. This is essentially a 2.5D projection of Hägerstrand’s time/space prism onto the map surface. The image below shows the part of Washington, DC accessible to someone who must leave the green marker after 8:00 AM and arrive at the red marker before 9:30 AM via public transit. Greater transparency indicates a larger amount of time available to perform some activity at the intermediate location.
Potential path area via public transit for departure after 8:00 AM and arrival before 9:30 AM.
We are by no means limited to examining travel time. Any information accumulated in OTP State objects during the search is a candidate for display or analysis. For example, here is a map of the number of vehicles boarded in the lowest-cost path to each point in the Washington, DC area, starting from the New Carrollton station of the proposed Purple Line (but with service on that line disabled):
Number of vehicles boarded in lowest-cost paths to destinations in Washington, DC. (green:0, blue:1, yellow:2, red:3)
Over the coming months we will be identifying alternative metrics for transit quality of service and urban accessibility. The most effective ones will make their way into OTP Analyst. We are also not constrained to presenting our results as an image or on a regular grid. It is equally possible to substitute some other arbitrary set of endpoints from a shapefile or spatial database. As with map tiles, their relationships with streets are pre-computed, accelerating subsequent evaluations of the same points. The resulting data sets can be analyzed in external tools such as the open-source R statistical package.
Linear least-squares model for relative housing prices as a function of transit travel time from the city center. R-squared 0.20, p-value: <2.2e16
The growing worldwide availability of open transit data in de facto standard formats means that once developed, spatial analysis tools can serve in both comparative and targeted studies in a large number of places. My hope is that besides enabling citizens to appropriate transportation planning methods and mobilize their resulting expertise in defense of the public interest and quality of life, the Analyst extensions to OpenTripPlanner will help the academic and planning communities to better grasp the syntax of the urban environment and factors favoring spatial legibility for those of us navigating it via shared, scheduled and non-motorized transport.