Bike shares can be perfect!: Solving the commuting algorithm

Mathematicians and urban planners are working together to make sure there's a bicycle exactly where you need it

Topics: Dream City, Bike share, sustainability, Editor's Picks, , , , ,

Bike shares can be perfect!: Solving the commuting algorithm (Credit: AP/Craig Ruttle/Vadim Georgiev via Shutterstock/Salon)

The mathematician and the mayor have little in common, but each would like to bridge the gap. Mayors are absorbed by the idea that data can anticipate traffic jams and crowded trains. Mathematicians are enticed by the challenge of the city. Just as the Fibonacci sequence arises in flower petals and the Golden Ratio structures the nautilus shell, so fractals can model suburban development patterns and power laws predict a city’s infrastructure-to-population ratio.

Bike share systems provide a particularly appealing meeting point. For researchers working from travel data, a bike share system is a unique record of how people move in the city. For mathematicians, bike share is a riddle with real-world implications. Between data mining and mathematical models, analysts hope the complexities of designing and managing a bike share system can be reduced to numbers and algorithms, or even solved.

This week, Dream City looks at the unruly mix of math, experience and politics that goes into the management of a bike share system. In a second column next Saturday, I’ll turn to the data that emerges from the system, and the secrets it may hold for the city.

In 2006, there were 25 bike share services worldwide. Now there are about 500. Each of those networks, which range in size from a few dozen bikes to several thousand, produces travel information that constitutes what Jon Froehlich, a professor at the University of Maryland and one of the first to study bike share, calls a ”digital footprint of where people are.”

In order for that footprint to emerge, though, operators must address the major problem that plagues all bike share systems: rebalancing. As bike share members know, the bikes tend to stick together. They follow the morning commute into downtown and the evening commute back to residential neighborhoods. They are pedaled down hills but rarely back up. A beautiful morning and a rainy afternoon can leave the system hopelessly discombobulated.

The solution is a fleet of trucks and vans that reposition bicycles from what academics call “attractive” stations to “repulsive” stations. On the one hand, this is ironic: Bike share is widely praised as a sustainable transit solution but requires the round-the-clock service of heavy vehicles to keep it primed for operation.

But it’s a crucial element of a successful system. If bike share is to be taken seriously as a transit mode — and its staunchest supporters believe it is an indispensable tool in the planner’s arsenal — it must be able to meet the demands of professional life. Every time a user is unable to find a bike or a place to park, the system’s reliability is jeopardized. “People are only going to let that happen once or twice,” Froehlich says. And if bike share use is limited to a subset of leisurely errands and frivolous excursions, the value of its remarkably detailed data (to say nothing of the system itself) is compromised.

What if a computer program could engineer the optimal rebalancing solution? For mathematicians, the “rebalancing” question is a twist on a long line of puzzles called “pickup and delivery” problems or “traveling salesman” problems. Rebalancing a bike share system has some advantages over other such puzzles (e.g., bikes are interchangeable), but with dozens of stations and hundreds of bicycles, its mathematical expression is arcane.

Over the past decade, dozens of mathematicians have published papers on the rebalancing problem. Some are purely theoretical, studies of perfect puzzles that model bike share like chess models war. But other researchers, like Tal Raviv, a professor of industrial engineering at the University of Tel Aviv, have more practical aims. Raviv intends to improve the operation of bike share systems in the real world.

It has been slow going. Bike share systems are largely still run, Raviv notes with displeasure, “in an intuitive way.” A human dispatcher monitors docks in real time and communicates instructions to van drivers. ”It’s a shame not to use computerized tools and algorithms to make the procedure more efficient, especially since it’s so crucial to the success of a bike sharing system,” says Raviv. “It’s not easy to convince the operators.”

You Might Also Like

“It’s not as perfect as we wish it was,” admits Eric Gilliland, the director of Capital Bikeshare in Washington, D.C, which has served as a model system for many North American cities. “We’ve been so busy making the system run, we haven’t had as much time as we’d like to dig into the math behind it.”

Then again, it doesn’t take a rocket scientist to rearrange bicycles for better use, particularly in cities like D.C. with stark divides between business and residential districts. Capital Bikeshare’s six bicycle vans shuttle their cargo around town from 5 in the morning to shortly after midnight. They respond to directions from a centralized dispatcher, but they also follow routines: By clearing out downtown racks midway through the morning rush hour, they enable a second-wave commute. Every year, CaBi rebalances 300,000 bicycles — the equivalent of squeezing a whole extra month of usage into the year. “Our rebalancing makes the system seem a lot larger than it really is,” Gilliland says.

How much improvement could a computer make on those figures? No one is sure, because no city has fully automated the process. Armed with data, simulations and mathematically expressed priorities, a software program could improve on human ability in several obvious ways. It could anticipate which empty stations need to be filled most, based on nearby station loads or forecasting. It could instantly evaluate how hundreds of possible routes would link various full or empty docks, optimizing the utility of each van. A computer could know not only where bikes are needed now, but where they will be needed in 30 minutes.

But chaos of city life doesn’t always lend itself to automatic management. “The complexity of rebalancing is something that would be very, very difficult to capture in a theoretical model,” says Neal Lathia, a senior researcher at Cambridge whose bike share Google Group is a popular forum for like-minded enthusiasts. “It’s going to be very challenging to pick up on the little fluctuations that happen on a day-to-day basis.” Weather can change bicycle use patterns in an instant; traffic can snarl even the “optimized” van route.

Some of the gap between bike share’s imperfect reality and mathematical efficiency is more systemic. The agreement D.C. struck with management company Alta Bicycle Share requires that no rack remains entirely empty for more than two hours. That’s a good way of making sure no station simply drops out of the system, but it’s far from optimal in a mathematical sense. If an empty station is surrounded by stations with bikes, Raviv suggests, it could be left alone all day. If the goal is providing the most bike rides to the most people, vans should be focused on stations in heavy use — and abandon some out-of-the-way stations entirely.

That leads to an important distinction between city life and math. Cities generally choose the locations of bike share docks before turning over control of the system to a managing entity like Alta. Station placement is derived from GIS maps, census data and the expertise of city planners, but it must pass muster with local politicos as well.

“There’s a bit of a conflict between what you should do, based on what succeeds or fails, and what could be a good intervention to improve a neighborhood,” Lathia notes.

Cities place and maintain docks in areas with low ridership — as a political gesture, in anticipation of future use, or to provide a transit option to an otherwise isolated place. Could a computer be made aware of these priorities, which may detract from the system’s total ridership per bicycle? If a computer program prized bicycle miles traveled over total rides taken, how would the rebalancing effort be different? These are some of the challenges operators face in incorporating rebalancing algorithms into their work.

“It’s really a unique balance of math and experience,” says Kim Lucas, who manages the bike share program for the District.

The question, for bike share operators and mathematicians, is whether math can render experience obsolete.

More Related Stories

Featured Slide Shows

  • Share on Twitter
  • Share on Facebook
  • 1 of 13
  • Close
  • Fullscreen
  • Thumbnails

    The 12 most incredible pint-size look-alikes in "Orange Is the New Black" season 3

    Young Daya has yet to become entirely jaded, but she has the character's trademark skeptical pout down pat. And with a piece-of-work mother like Aleida -- who oscillates between jealousy and scorn for her creatively gifted daughter, chucking out the artwork she brings home from summer camp -- who can blame her?

    The 12 most incredible pint-size look-alikes in "Orange Is the New Black" season 3

    With her marriage to prison penpal Vince Muccio, Lorna finally got to wear the white veil she has fantasized about since childhood (even if it was made of toilet paper).

    The 12 most incredible pint-size look-alikes in "Orange Is the New Black" season 3

    Cindy's embrace of Judaism makes sense when we see her childhood, lived under the fist of a terrifying father who preached a fire-and-brimstone version of Christianity. As she put it: "I was raised in a church where I was told to believe and pray. And if I was bad, I’d go to hell."

    The 12 most incredible pint-size look-alikes in "Orange Is the New Black" season 3

    Joey Caputo has always tried to be a good guy, whether it's offering to fight a disabled wrestler at a high school wrestling event or giving up his musical ambitions to raise another man's child. But trying to be a nice guy never exactly worked out for him -- which might explain why he decides to take the selfish route in the Season 3 finale.

    The 12 most incredible pint-size look-alikes in "Orange Is the New Black" season 3

    In one of the season's more moving flashbacks, we see a young Boo -- who rejected the traditional trappings of femininity from a young age -- clashing with her mother over what to wear. Later, she makes the decision not to visit her mother on her deathbed if it means pretending to be something she's not. As she puts it, "I refuse to be invisible, Daddy. Not for you, not for Mom, not for anybody.”

    The 12 most incredible pint-size look-alikes in "Orange Is the New Black" season 3

    We still don't know what landed Brooke Soso in the slammer, but a late-season flashback suggests that some seriously overbearing parenting may have been the impetus for her downward spiral.

    The 12 most incredible pint-size look-alikes in "Orange Is the New Black" season 3

    We already know a little about Poussey's relationship with her military father, but this season we saw a softer side of the spunky fan-favorite, who still pines for the loving mom that she lost too young.

    The 12 most incredible pint-size look-alikes in "Orange Is the New Black" season 3

    Pennsatucky had something of a redemption arc this season, and glimpses of her childhood only serve to increase viewer sympathy for the character, whose mother forced her to chug Mountain Dew outside the Social Security Administration office and stripped her of her sexual agency before she was even old enough to comprehend it.

    The 12 most incredible pint-size look-alikes in "Orange Is the New Black" season 3

    This season, we got an intense look at the teenage life of one of Litchfield's most isolated and underexplored inmates. Rebuffed and scorned by her suitor at an arranged marriage, the young Chinese immigrant stored up a grudge, and ultimately exacted a merciless revenge.

    The 12 most incredible pint-size look-alikes in "Orange Is the New Black" season 3

    It's difficult to sympathize with the racist, misogynist CO Sam Healy, but the snippets we get of his childhood -- raised by a mentally ill mother, vomited on by a homeless man he mistakes for Jesus when he runs to the church for help -- certainly help us understand him better.

    The 12 most incredible pint-size look-alikes in "Orange Is the New Black" season 3

    This season, we learned a lot about one of Litchfield's biggest enigmas, as we saw the roots of Norma's silence (a childhood stutter) and the reason for her incarceration (killing the oppressive cult leader she followed for decades).

    The 12 most incredible pint-size look-alikes in "Orange Is the New Black" season 3

    While Nicki's mother certainly isn't entirely to blame for her daughter's struggles with addiction, an early childhood flashback -- of an adorable young Nicki being rebuffed on Mother's Day -- certainly helps us understand the roots of Nicki's scarred psyche.

  • Recent Slide Shows


Loading Comments...