Bike Triangle
The "bike triangle" is a feature of the A-Train multimodal planner in Atlanta that allows users to quickly specify the relative importance of three distinct routing options for bicycle trips. Implementation of a similar feature in OTP has been identified as a priority for the October 2011 OTP beta launch in Portland.
The three variables are:
- Distance - the total length of the route
- Topography - the relative "steepness" of a route
- Facility type (consider renaming?) - the degree to which a trip is routed on bike-friendly facilities (separated bikeways, low traffic streets, etc.)
From a programmatic standpoint, the user-specified weights are communicated from the client to the server as three floating point values -- call them D, T, and F -- with each ranging from 0.0 to 1.0, and D + T + F = 1.0. (In reality, only two of the three need to be transmitted; the third can be easily deduced by subtracting the sum of the other two from 1.0).
The triangle widget allows users to specify any possible combination of weights. Following are some example (D,T,F) triplets and the corresponding desired trip type:
- (1, 0, 0) -- the shortest possible trip, regardless of how hilly it is or the types of facilities used
- (0, 0.5, 0.5) -- a relatively flat trip on generally bike-friendly facilities, which could be fairly long
- (.333, .333, .333) -- a "balanced" trip where each factor is considered equally
The A-Train widget was written in Javascipt and consists of a two dimensional slider superimposed against a static bitmap background image () that contains the outline of the triangle and the three labels for each variable (D,T, and F). The Yahoo YUI toolkit was used to implement the slider. Most of the JS code should be reusable, though we may want to consider using a different library for the slider, and perhaps consider scrapping the image background for an a vector-based approach so that the widget can be resized dynamically. The HTML5 canvas element is a possibility here, though this presents browser compatibility issues.
A necessary step is to precompute static numeric factors that reflect the topographic and facility-type "costs" associated with each edge. These two factors are stored as fields within the graph, and both range from 0.0 to 1.0, where 0 is the "best" possible value (i.e. a totally flat/downhill segment or the most bike-friendly facility possible) and 1 is the "worst" (i.e. a very steep segment or a highly bike-hostile roadway).
There are a number of potential ways to approach the computation of these factors. Outlined below is a the technique I used for A-Train, but the implementation of this feature in OTP presents an opportunity to tweak or completely rethink these approaches.
Topographic Factor
The objective with the topographic factor is to generate an index that conveys the relative uphill steepness of an edge on a scale from 0 to 1. This can be thought of as the topographic "cost" associated with traversing the edge, with higher values less desirable. The index is computed based on the topographic profiles computed for each edge from NED or similar data. These profiles are assumed to consist of a series of elevation values sampled at a defined interval along the edge; e.g. for a 500' edge sampled at a regular 100' interval, there should be 6 distinct data points.
It is important to note that the topographic cost for a given edge is different for the two possible directions of travel (assuming two way travel is allowed); an edge from A to B that is entirely uphill will have a very high topographic cost in the A->B direction, but zero cost in the B->A direction. This results in two distinct factors that are independently computed and stored for each edge.
Given the inputs of the edge length and topographic profile, the following steps will compute the topo index for a single direction of travel:
- Compute the vertical rise and horizontal run for each of the edges segments defined by the topographic profile. Proceed only with the uphill segments (i.e. where rise > 0), disregarding flat and downhill ones.
- Compute the angle of inclination for each of the uphill segments. For example, a segment that rises 3 feet over 100 feet has an angle of inclination of arctan(3/100) ~= 1.72 deg.
- Compute the average angle of inclination for each of the uphill segments.
- Divide the average by 5 deg to produce a index between 0 and 1. If the average exceeds 5 deg, the index is capped at 1. This number is the final value assigned to this edge for this particular direction.
If applicable, repeat these steps for the other direction of travel.
The following figure shows an example computation of the topographic factor in both directions for a 500' edge, with elevation data (sampled every 100') ranging from 10' to 16'.
Facility Type
Similar to the topographic index, the objective with the facilty type index is to produce a "cost" or penalty associated with each edge vis-a-vis its facility type, so that a bike-hostile facility (e.g. a high traffic arterial with no bike accomodations) will have a higher cost than a bike-friendly one (e.g. an off-street bike trail).
The method used for the A-Train planner is fairly simplistic, essentially consisting of a predefined lookup table of values for each possible facility type. (Each eadge is asssumed to be the same type of facility for its entire length.) The values below are specific to the hierarchy of facilities in the A-Train street graph (which was based on local agency data rather than OSM), and for OTP may need to be rethought in light of the standard OSM facility classifications.
The computation consisted essentially of two steps:
- Compute the "base" cost:
- Major thoroughfare: 1.0
- Minor thoroughfare: .75
- Local / low-traffic street: 0.5
- Off-street bike trail: 0
- For street-based edges, several potential adjustments are considered that can reduce the cost:
- Striped onstreet bike lane (no buffer or physical separation): -0.25
- Physically separated or protected bike lane / "cycle tracks": -0.5
Example computations:
- Major thoroughfare w/ no bike accommodations: 1
- Minor thoroughfare with striped lanes: 0.5
- Minor thoroughfare with cycle track: 0.25
- Local street with protected bike lanes: 0.
These final values are stored with each edge in the graph. Note that unlike the topo factor where separate values are computed for the two directions of travel, in this case a single value applies for both directions of travel.
The computation of the optimal path based on is achieved using a standard weighted shorted path algorithm such as Dijkstra's, with the edge weights dynamically computed for each search based on both the static properties of the edge (the length and the topo / fac. type factors) and the user-specified weights.
For any given edge, the following formula used to compute the total edge weight. Where D, T, and F are the user-specified weights, TopoFact and TypeFact are the edge's topography and facility type factors as computed above, and len is the length of the edge.
edge weight = (len * D) + (len * TopoFact * T) + (len * TypeFact * F)