Taxis 2.0: Streamlining City Transport With Graph Theory

Big city taxi systems could be 40% more efficient with device
enabled taxi sharing.

As reported by the Medium: Everything today is about information and algorithms for processing it. Think of what Google’s PageRank algorithm did for web search, transforming an impenetrable jungle of web pages into an easy-to-use and hugely powerful information resource. That was then, in the late 1990s. Now think taxis.

In New York City, people take more than 100 million taxi trips every year, as individual parties hail cabs or book them by phone to suit their own needs. Taxis, as a result, criss-cross the city in a tangle of disorganized mayhem. Cabs run in parallel up and down Madison Avenue, often carrying isolated people along the same path. Those people could share a cab, yet lack a mechanism to achieve that coordination. But that mechanism might soon exist, and it could make taxi transport everywhere a lot more efficient.

That’s the message of some fascinating new research by a group of network theorists (the paper is unpublished, currently under review at a journal). It’s fairly mathematical, and relies on some technical results from graph theory (as did Google’s PageRank algorithm), but the basic insight from which it starts is quite simple: a good fraction of the trips that taxis take in a city overlap, at least partially, and so present opportunities for people to share cabs. Using real data from NYC, they’ve shown that a simple algorithm can calculate which rides could easily be shared by two parties without causing either much delay. In principle, the algorithm could be exploited by smart phones to help people organize themselves — it could make NYC taxi system 40% more efficient, reducing miles traveled, pollution, and costs.

7 days of taxi traffic history.

A little more detail: Imagine that you label every taxi ride by its origin and destination, plus departure and arrival time. Represent each such ride by a point on some very big page. For NYC in 2011, there were some 150 million rides starting or ending in Manhattan, so imagine a page with 150 million points on it, each labelled by the above data. These points, in effect, show you all the taxi rides that took place to get people in NYC to the places they wanted to go. 

What Santi and colleagues do is to ask whether some of these rides might have been “shareable,” in the sense that they actually traveled along parallel routes (or between the same points, along different routes) at close to the same time. If so, then people given the right knowledge could have shared a portion of the trip.

This huge collection of points becomes a mathematical graph once you begin linking together the points for any pair of rides that are “shareable.” By studying the properties of this graph, the researchers show that if people were willing to be delayed by up to ten minutes on their journeys, then there are roughly 100 billion pairs of trips that were shareable. If people are more choosy — unwilling to accept more than a five minutes delay — then fewer rides become shareable, but still enough to reduce the total miles driven by taxis by 40%. That 40% might be slightly optimistic, they note, given the constraints on any network system attempting to process this information in real time (and thereby having less than perfect knowledge of the whole set of taxi journeys).

The point is that people make their decisions about taxis in an information vacuum, knowing only what they require themselves, and nothing about all the other taxi needs of others around them. Information vacuum isn't good. How many times have you needed a taxi and waited as ten of them zipped by, all traveling in your direction, with each one carrying just one or two passengers? For a few minute delay, many of those people might have been wiling to save some money by sharing part of the ride. To make this happen requires information and algorithms to sift through it, plus a means for sharing this information with everyone who wants it.

All of which may be a reality soon. For more detail on this work, see the website of the HubCab project.