"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," says Eoin O'Mahony, "and the Citi Bike smartphone app shows them where these are." (Credit: Billie Ward/Flickr)

algorithms

Algorithm gets bikes to where people need them

With more than a million rides each month, Citi Bike deploys 6,000 bikes throughout New York City and each one often goes on more than 10 trips in a day.

In the morning, commuters pick up a bike near home and drop it off near work. 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,” says Michael Pellegrino, director of operations for NYC Bike Share LLC, the operators of Citi Bike.

David Shmoys, professor and director of the School of Operations Research and Information Engineering at Cornell University, and graduate student Eoin O’Mahony have developed algorithms and data analysis tools to help rebalance the Citi Bike system as efficiently as possible.

“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 says.

“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.”

A solution for the ‘last mile’

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 says. “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 adds.

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.

By truck or pedal power?

There have been adjustments along the way, O’Mahony reports. 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,” says O’Mahony.

The 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.

[related]

“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,” says 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 says, and many are working on rebalancing bike-sharing systems in major cities around the world.

O’Mahony described the system at the 2014 INFORMS Annual Meeting, “Bridging Data and Decisions,” in November in San Francisco.

Source: Cornell University

Related Articles