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 has also become part of Cornell Engineering’s research domain. Cornell Operations and Information Engineering Professor David Shmoys and graduate student Eoin O’Mahony are introducing new methods and strategies to help keep the system in balance. “Analytics-based advances in rebalancing strategy have helped the Citi Bike system cope with steadily rising ridership demand,” said Shmoys.
Bikes in the system are often taken on over ten trips each day. The bikes are used in large part for one way trips, for example by commuters heading to work, which means that left alone, the system would rapidly run out of bikes at some stations and places to dock them at others. To counter this, managing the process of moving bikes from station to station to rebalance the system “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.
It’s an interesting and novel scientific problem,” Shmoys was recently quoted in the journal Science, noting that “there may be 20 to 30 researchers that are devoting significant parts of their research agendas to rebalancing” on bike sharing systems in major cities around the world.
Shmoys and O’Mahony recently outlined the Cornell approach. “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 as rides take place 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,” he continued. Sometimes, for example at Penn Station— where commuters arrive and depart by train and use bikes for the ‘last mile’— “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.”
“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,” said Shmoys. He and O’Mahony worked out algorithms to accomplish this.
O’Mahony and Shmoys formulated a new “integer programming” mathematical model that state of-the-art open-source software can use to compute the optimal route for a single truck to take in shuttling bikes from stations which have too many bikes to where they are needed, typically picking up at one station, dropping off at the next, and so on. They devised a heuristic method that compiles such routes into a good solution for the system as a whole, and incorporated the results into a web tool that displays a map that Pellegrino and his dispatching staff use to guide the rebalancing. Each night dispatchers use the map, together with some pre-computed routes, to deploy trucks to shuttle bikes from stations which have too many, to stations where they are needed.
To move bikes around during rush hour, when trucks carrying around 25 bikes can be slowed to a crawl by traffic, a different strategy is needed. “We found that trailers, pulled by bicycles and carrying up to three bikes at a time, can move more bikes per hour than trucks” said O’Mahony. To make the most productive use of the trailers, he and Shmoys found it possible to devise a matching algorithm to pair stations that are typically saturated with stations not far away that are typically starved for bikes, for example pairing one at 44th Street and Fifth Avenue with one alongside Grand Central Station.
Instead of moving small numbers of bikes between individual stations to precisely rebalance the system during the day, “we focused on areas of the city rather than individual locations, and on using bike trailers to satisfy these needs”, said O’Mahony. “Although it is nearly impossible the keep the entire system balanced this ensures people are not too far from an empty dock or a bike,” and the Citi Bike smartphone app shows them where these are.”
Unlike a purely academic exercise, this real-world problem provides the researchers with constant feedback and data that they can use to rerun and refine their models. “The system is in constant flux,” said O’Mahony. “As much as 95% of the usage is by commuters, but commuting patterns can change from month to month.”
Also 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 Operations Director Pellegrino, “and the Cornell team has helped us use our rebalancing resources much more efficiently.”