Fare Hacking on BART

Stephen Brennan • 23 July 2016

Imagine that you're taking a long train ride on the BART. Maybe from Millbrae to North Concord. Chances are, at the very same moment, somebody else is going the other direction. For example, maybe from Pittsburgh/Bay Point to San Bruno. In case you haven't memorized BART's stops, here's a useful map illustrating these rides:

You're the cyan rider (starting at the chevron and ending at the octagon), and the other person is in magenta.

Now, if you both bought correct tickets, your trips would cost a little more than $7 each. That's not unreasonable, but there's a way you could pay less, so long as you know the Magenta rider.

Instead of buying a ticket for Millbrae to North Concord, you just buy a ticket for Millbrae to San Bruno. Magenta buys a ticket for Pittsburgh/Bay Point to North Concord. Halfway through, you both get off your trains, meet on the platform, and swap your tickets. Then you continue on the next train to your destinations.

This ends up saving both of you around $5, but in the process you lose 20 minutes standing around on a platform in Oakland! Probably not worth it. But, what if there were a way to do this electronically so that you never had to get off the train? After all, Clipper Cards (the electronic ticket of choice on the BART system) use NFC, which is a technology built into some smartphones. Although Clipper Cards currently aren't cloneable or spoofable, if they were, an app could theoretically use the principle from above to swap tickets around, reducing everyone's fares!

I've had this idea bouncing around in my head for a couple weeks. Thursday and Friday were Hackathon days at Yelp, which gave me the perfect opportunity to take a shot at making this app. I successfully implemented what I think is a pretty neat algorithm and API, and then ran it on some real BART data. My results indicate that an app like this could save its users between 20 and 40% on BART fares, depending on time of day. Read on for all the gory details—I think it's pretty fascinating!

One final note before I dive in: this algorithm is essentially large scale ticket swapping, which is obviously illegal and unethical. I don't believe that it would be ethical to use this in the real world. I value safe and smooth travel more than I value the 20-40% of my fare I could save by stealing from BART. With that said, I still think this is a really cool problem, and since Clipper cards are not cloneable, this work can't be used to facilitate this large-scale theft.

The algorithm

In order to write an algorithm, we should always step back and formulate the problem as clearly as we can. In this case, the input to our problem is a bunch of people who would like to go from point A to point B. Our job is to "purchase" tickets that we can assign to people on entry, and then swap to other people on exit, so that we minimize the total cost of these tickets.

Let's go back to the toy example I presented in the beginning. Why does it work? What is the fundamental property we are taking advantage of? It's actually pretty simple: BART would like to enforce that everyone who travels from point A to point B buys a ticket for that source and destination. However, with just turnstiles at stations, they can't enforce that. The best they can enforce is that each person entering a station has a valid ticket for a trip starting there, and that each person exiting a station has a valid ticket for a trip ending there.

This gives us a set of constraints. Our algorithm can purchase whatever tickets it wants, so long as we end up with the same number of people entering and leaving each station. Since we're minimizing the total cost of the tickets, we have a classic optimization problem. In particular, this problem can be expressed as an Integer Linear Program.

Linear programs are math problems where you are trying to choose values for a vector (i.e. a list) of variables , such that you minimize a cost function. Typically, each variable in has an associated cost , and so the cost function is just the sum of the 's times their costs. But, you have to satisfy some constraints, which are usually expressed as equations, like this:

We can have lots of constraints we need to satisfy, so we typically number the constraints from one to . We can compactly write all the constraints using a matrix form like this:

Here, is an row (one for each constraint) by column (one for each variable) matrix containing the coefficients from all the constraints. Usually we also have the constraint that , and for integer linear programs, we also