In a medical emergency, ambulance response times could make the difference between life and death, but those response times are impacted by a number of variables. In any given city, where are the ambulances stationed? What happens when an ambulance is called away from its base—how is that area then covered?
These are just some of the questions that Shane G. Henderson, Operations Research and Information Engineering (ORIE), tackles—both in collaboration with organizations and in theoretical modeling. “We work on problems where you’re making decisions in the face of pretty significant uncertainty about what might happen,” Henderson says, “and yet your decisions do have an impact—they really do change what will happen. So how do you make the right choice?”
Simulating Familiar Problems, Developing Algorithms for Best Practices
The way Henderson answers these difficult types of questions, in a broad set of applications, is through simulation. “Pretty much everything I do centers on this idea,” he says.
As an example, take the problem of road construction on a college campus. “We might simulate the operations of all the commuters coming onto campus and experiment with different road closures to see what kinds of delays might happen: where people might drive to; where the worst congestion points would be,” Henderson says. “The simulation looks kind of like a video game, but we’re mimicking something about reality.”
Henderson uses a combination of simulation and simulation optimization to find ideal solutions. “Simulation optimization is where you use a simulation model, with rules and things built in, but you’re not experimenting with all of the real constraints of the system,” Henderson says. “So that means you can have carte blanche in trying whatever you like. Then you collect statistics on how things go and use that as a way to evaluate ideas.”
Henderson has used these simulation methods to develop algorithms that determine the best practices for ambulance fleets in cities all over the world. He has worked on problems addressing the complexity of MRI scheduling, radiation treatment methods, and call center planning.
Working with an air ambulance company in Ontario, his team’s algorithms help determine the most efficient way to get patients from the sparsely populated northern regions to hospitals in the province’s cities. “Every night our software is run to figure out how to do that,” Henderson says. “The algorithms save tremendously on costs and give consistency from day to day in terms of the quality of the plans and the quality of care.”
New York’s Citi Bike and Cloud Computing
Henderson, in collaboration with ORIE colleague David B. Shmoys, has also helped write algorithms to design New York City’s Citi Bike program and to keep it running smoothly. The program has 500 stations and 8,000 bikes that residents use for recreation and to commute to and from work.
“There are these tremendous tidal flows in the city, people moving from the East Village into the city and back out again at night,” Henderson says. “So how do we position the bikes overnight so things work well in the morning? Are the stations in the right places? Do they have enough bikes to keep people happy during the day?
“The problem with these kinds of questions,” Henderson continues, “is that there’s so many different ways of designing the system, of setting things up, and only a few of them are actually pretty good. It’s sort of a needle-in-a-haystack problem.”
“The simulation looks kind of like a video game, but we’re mimicking something about reality.”
To give a sense of scale, Henderson explains: “Imagine, for Citi Bike, that there are only two bike stations, and you’re trying to figure out how many bikes to put at each station. Let’s say you have the option of putting no bikes, one bike, two bikes—up to nine bikes at each station, so there are 10 options for each spot and 100 total options.”
Three stations would yield 1,000 options, Henderson continues—and 500 stations would offer 10500 choices. It follows that if one station is running out of bikes mid-afternoon, there are going to be a huge number of strategies to try to solve the problem, and, as Henderson says, only a few will work. Here’s an example of where cloud computing is changing the field of Operations Research.
“With just one computer, we might run a simulation of New York’s bike share operations for a day, then repeat that multiple times to get statistics of what could happen, because every day is different,” Henderson says. “Then we would tweak the allocation of bikes across the city in a careful way and run it again to see if we could get improvements.”
With cloud computing, Henderson can input the problem on 1,000 cores. “We can take a single plan and run that plan for 1,000 different days simultaneously,” he explains. “Or we could take 1,000 plans and run one day for each and very quickly check out how good the plans are.”
With this kind of brute force, many difficult problems can now be solved quickly—which has allowed Henderson to focus on more sophisticated challenges. “There’s always been this line between what’s brute forcible and what has to be carefully analyzed. That line has now moved dramatically because we can brute force so much more,” Henderson says.
To address more complex problems, Henderson incorporates structure, “something about the problem that we understand,” he says. “Once we understand structure in a system, we can exploit that to solve bigger problems than we could just by trying things. It makes our searches more intelligent, and it allows us to tackle problems that help us advance in the field—that give us new ideas and insights.”
Finding the Right Fit
Henderson started out studying physics and math, with success, but it didn’t feel quite right. “I was doing fine in the pure math classes, but I always had to give myself some kind of context to understand results,” he says. “That’s what operations research really gives you—it’s this beautiful combination of mathematical rigor applied to solve real problems.”
Having grown up in rural New Zealand, Henderson says that, even as a graduate student, he didn’t intend to become a professor. “I never thought I was in that league. I showed up at Stanford and thought everybody was going to be walking around with huge heads, and I’d be this country hick,” he says.
Henderson more than kept up with the group, however, earning his master’s and PhD from Stanford and taking a position at Cornell after stints at the University of Michigan and University of Auckland. “When I was coming to interview at Cornell, the thing that really struck me was the humble, relaxed feel in the corridors,” he says. “And that feeling was in combination with really really good work. Those two things together are not that common. It’s a kind of magic of this place.
“The path was really pretty organic and has ended up fitting well,” Henderson adds. “I love teaching, research, and thinking about problems that have social relevance, that help people in their everyday lives.”