We’ve just released TransitTimes+ 2.1, and this version shows fare calculations for trips, based on the data specified in the fare_attributes.txt and fare_rules.txt file in agencies’ GTFS feeds.

(Fares are shown in footer of the trip description, if made available by the transit agency. In this case, TriMet of Portland supply this data)

Rather than describing the structure of these files, you can read the specification and then read some detailed examples.

If you read these examples, you’ll see that it can be quite complex to calculate a fare, especially when one or more transfers are involved. Here’s how we’ve done it in TransitTimes+:

1. Find qualifying fares for each segment of a trip, disregarding transfer options
2. Create every combination of fares possible
3. Find the cheapest total, this time accounting for transfers

1. Find Qualifying Fares

To determine a qualifying fare for a trip, you must typically know its start and finish stop. When a transit agency includes fare information, they must also include zone information with each stop. If a stop doesn’t have a zone specified, then a fare cannot be calculated.

(Note: technically, some fares don’t rely on zone information, in which case they don’t have corresponding rules in fare_rules.txt. In this case, the zone is not required).

You can then determine qualifying fares using the route_id, origin_id, destination_id and contains_id fields.

It’s important to understand the fare examples (linked above) to see how the contains_id field works, as a trip must pass through the zone IDs as exactly specified in the rules in order to qualify.

2. Create Fare Combinations

At this point, every segment in a trip will have 0 or more fare options associated with it. If it has 0, then it’s not possible to estimate the fare.

Assuming we can calculate the fare, we use a recursive algorithm to build up every combination of fares. For instance, if Segment A has fares 1, 2, 3, and Segment B has 4, 5, 6, our combinations are 1-4, 1-5, 1-6, 2-4, 2-5, 2-6, 3-4, 3-5, 3-6.

3. Find The Cheapest Total

Once you’ve created all fare combinations, this is a case of looping over each combination and calculating the total. Lowest total wins.

When calculating the price, you must account for transfers. Transfers can be time-based (e.g. unlimited usage for 2 hours) or quantity-based (e.g. up to 1 transfer).

There is some ambiguity in the specification about when the transfer time starts (does it begin from start of initial trip, and can the transfer time expire during the subsequent segment?). For these we must make assumptions.

In TransitTimes+, we made the assumption that if the subsequent trip starts before the transfer time expires, then the transfer qualifies.

Conclusion

As you can see, it’s not the easiest thing to calculate fares. GTFS was designed in such a way that most transit agencies can accurately model their pricing scheme in the same generic way.

There are some drawbacks with this system, one which is that there’s no time-based information specified. This is a problem in a city such as Adelaide, where fares are cheaper between 9am and 3pm on weekdays.

Additionally, the whole GTFS fare system is designed around “adult fares” (that is, the full fare - no concessions or discounts). This means it’s not possible to specify different rates for children or seniors.

Also, it’s not possible to account for bulk purchasing of tickets, so when displaying fares using GTFS information it’s generally calculated using the one-off ticket price.

One of the files that may be included by transit agencies in GTFS feeds is the shapes.txt file. This file is used to describe the various paths that bus or trains (or any route type for that mater) take on their trips.

Every record in shapes.txt corresponds to a single point for a single shape. Some shapes may consist of thousands of points. While it’s awesome that some agencies provide this level of detail, some devices may struggle to represent this data efficiently.

One of the challenges I faced with TransitTimes was the memory constraints of iOS devices. Rendering a polyline with 2000 points is just not feasible using iOS MKMapView.

The following image shows a portion of a shape from Transperth’s GTFS feed. This shape is made up of 400 points (the entire shape is actually 1700 points - I cut this down for simplicity).

As you might imagine, an iPhone 3G struggled immensely trying to draw this map, and once drawn it was almost impossible to actually scroll around the map. (In actual fact, the iPhone 4 also struggled).

This level of detail has no benefit to the user - especially if they can’t interact with their device.

The following image shows the exact same shape, but this time it’s made up of 70 points. This is far more manageable for mobile devices.

To automate this reduction of points, I used the Douglas-Peucker algorithm. This is a recursive algorithm that finds the point furthest away orthogonally from two other points.

The following image demonstrates this.

If this point is within a given tolerance, the point is discarded. If it’s outside the tolerance, the point is kept and the algorithm continues. When it continues, the algorithm is called twice: once for the line connecting the original start point and the new point, and again, this time for the line connecting the new point and the original end point.

I’ve written an article on PhpRiot about implementing this algorithm in PHP: Reducing a Map Path Using Douglas-Peucker Algorithm.

Using this algorithm, I’ve managed to remove upwards of 95% of shape points from GTFS files I’ve processed, without any significant loss of quality.

The other point I haven’t touched on: removing more than 95% of shape data also results in significant savings of space. For instance, the shapes.txt file for Transperth is over 40 MB in size. Reducing this file by 95% would make the file about 2 MB.

Since this blog will dedicate many posts to General Transit Feed Specification - GTFS - let me provide an introduction.

Firstly, from the official documentation:

The GTFS transit feed specification defines a common format for public transportation schedules and associated geographic information.

The “G” in GTFS is commonly thought of as standing for Google, since they created this specification so they can display transit info on Google Maps.

Transit agencies distribute (well, provide a link on their web site typically) to a ZIP file that contains a number of CSV (comma-separated values) files - each of which is described at the above URL.

Agencies distribute updates to their feeds at their own intervals. For instance, Auckland provide one month of data at a time, while others may provide 6 or 12 months worth of data.

The GTFS format isn’t overly strict, meaning:

• There’s no fixed format for identifiers (such as route_id or trip_id)
• Agencies tend to omit fields as they please
• Agencies sometimes add fields that aren’t in the spec (this doesn’t really matter - you can choose to use the extra info provided, or simply have your CSV parser ignore it)
• Many agencies tend to misuse the calendar.txt and calendar_dates.txt files

There’s no versioning included in GTFS. Each agency has adopted GTFS at different stages of its lifetime, so they build their files. For instance, when Perth adopted GTFS, the direction_id field in trips.txt wasn’t part of the spec. For a given route, “inbound” and “outbound” of the same route are treated as separated entries in the routes.txt file.

In later posts I’m going to discuss some of the various differences and challenges associated with the feeds from the feeds of various cities.

Hopefully this brief introduction gives you some idea of GTFS. It’s a somewhat simple specification, although some aspects are hard to comprehend until you’ve dealt with the data for a while.