Jesse Winter

Professor David Shmoys, left, and graduate student Eoin O'Mahony discuss "rebalancing" with Citi Bike worker Kelly McGowan in New York City. McGowan will use the rickshaw-like trailer on the right to move up to four bikes smoothly through traffic, making sure bikes will be available at another station and opening more docking space at this one.

With more than a million rides per month, the Citi Bike system has quickly become a part of the fabric of New York City. It’s now serving commuters a little better, thanks to Cornell research.

Citi Bike deploys 6,000 bikes throughout the city that are often taken on more than 10 trips each day. In the morning, commuters pick up a bike near home and drop it off near their job. Near home, supplies dwindle, while midtown stations fill up, sometimes leaving few places to dock. During the day, similar imbalances occur across town. The solution is to “rebalance,” using trucks to move bikes from crowded locations to empty ones. Managing the process “is a good part of my day-to-day,” said Michael Pellegrino, director of operations for NYC Bike Share LLC, the operators of Citi Bike.

David Shmoys, the Laibe/Acheson Professor and Director of the School of Operations Research and Information Engineering, and graduate student Eoin O’Mahony have developed algorithms and data analysis tools to help rebalance the Citi Bike system as efficiently as possible.

O’Mahony described the system at the 2014 INFORMS Annual Meeting, “Bridging Data and Decisions,” in November in San Francisco. He earned first place and a $1,000 cash prize in the “Doing Good with Good OR” student competition with his paper, “Smarter Tools for (Citi)Bike Sharing.”

“We first needed to analyze massive quantities of data to determine usage patterns and determine how many bikes would be found at each station at key times during the day,” Shmoys said. “The next step is to figure out how many bikes should be at each station at key times, so riders would find bikes available as well as open docks to put them in at the end of a ride.”  

At locations where commuters arrive and depart by train and use bikes for the "last mile," such as Penn Station, “it was clear early on that they would need to make more open docks available,” he said. “But just adding docks or bikes to the system would do little to resolve the imbalance - bikes must be moved around.”

The system generates a map showing dispatchers where bikes are needed the most, given the current state and expected usage.

“Deciding how many bikes to take from one station to another - and how to get them there - is a hard problem to solve, certainly by hand, but even by computer,” Shmoys added. It’s a problem in “optimization.”

In the morning, many Citi Bike users are departing from stations shown in blue and arriving at those in red. Morning commuters will find bikes waiting because trucks have moved them there overnight, following a computer-generated plan developed by Cornell researchers. During the day, bikes will be moved around to balance downtown locations.

The computer must calculate many possible solutions across the entire city and choose the one with the best overall result. The algorithm starts by representing each possible route as a separate point in a high-dimension space, then repeatedly recalculating to eliminate a large fraction of those points in each step. This approach, known as integer programming, exploits the fact that it is computationally simpler to manipulate not just these isolated points, but a “filled-in” version instead; once only one integer solution remains – one that comes out even with no decimal points – that must be the optimal solution.

There have been adjustments along the way, O’Mahony reported. Drivers often balked at being told to pick up less than a full load, and some of the most efficient solutions turned out to be those that called for moving full truckloads. 

To move bikes during rush hour, when trucks carrying around 20 bikes can be slowed to a crawl by traffic, Citi Bike uses small pedal-powered trailers that carry just four bikes.

“We found that trailers can move more bikes per hour than trucks,” said O’Mahony. The Cornell researchers developed additional algorithms to pair nearby locations that are often out of balance, for example pairing one at 44th Street and Fifth Avenue with one at Grand Central Station, sending trailers back and forth between them.

“Although it is nearly impossible to keep the entire system balanced, this ensures people are not too far from an empty dock or a bike,” said O’Mahony, “and the Citi Bike smartphone app shows them where these are.”

Moving forward, the researchers are developing a system to choose the best locations for new bike-sharing sites, based on data from taxi usage and neighborhood boundaries.

The problem intrigues computer scientists, Shmoys said, and many are working on rebalancing bike-sharing systems in major cities around the world.

Unlike a purely academic exercise, the researchers get very personal real-world feedback.  Shmoys and O’Mahony provide “the overarching vision for how we like our system to look,” said Pellegrino, “and the Cornell team has helped us use our rebalancing resources much more efficiently.”