This image from Pascal Van Hentenryck’s lab shows how his computer models improved the efficiency of a hypothetical shipping company. Click to see it full-size.
Expecting the unexpected
Brown computer scientists are developing models that will help organizations cope with potentially costly contingencies.
|
November 18, 2008 |
Email to a friend
Let’s say a major hurricane strikes the United States. By now, government agencies have elaborate plans to respond to such disasters. But what happens when, say, a bridge collapses, and needed supplies can’t reach their destination? Or a vital road is clogged with debris? Too often, planners faced with such unpleasant surprises must scramble to find a solution.
Pascal Van Hentenryck is working on a way to minimize the effects of such disruptions. The Brown computer science professor is building elaborate models that can help companies, agencies, and other organizations anticipate contingencies before they arise and suggest how to respond most effectively.
To be sure, businesses always are trying to figure out how best to deal with uncertainty and how to adjust their operations when the best-hatched plans go awry. But thanks to greater computing power, better tracking technology, and more robust mathematics, predictive models can now be revised nearly instantaneously to meet changing conditions. This emerging research trend is called online stochastic optimization.
Pascal Van Hentenryck
“These are the questions that companies are asking themselves: How do I model this so I can best react to different circumstances?” van Hentenryck says.
Van Hentenryck has assembled a team of graduate students who are constructing algorithms – mathematical steps – to support the optimization models. The group received federal funding this fall to work with the Los Alamos National Laboratory on a system for inventorying and routing supplies after a natural disaster. The team also has the first Navy Experimental Program to Stimulate Competitive Research (EPSCoR) grant in Rhode Island to develop algorithms.
In addition, Van Hentenryck’s group is working closely with computer science professor Eli Upfal on a National Science Foundation grant to explore the theoretical underpinnings of the modeling. “The ultimate goal in computer science is to show these algorithms work fast and produce the best or as close to the best solution as possible,” Upfal says.
To demonstrate the research, Van Hentenryck pulls up on his laptop a scenario involving a hypothetical shipping company. The firm wants to serve 95 customers in a four-hour span on a Saturday. The company’s goal is to pick up and deliver packages for every customer and to manage new orders during that time as efficiently as possible. Using current planning software, the company serves 66 customers but rejects 29. Using algorithms developed by Van Hentenryck’s team, the company serves 93 customers, rejecting only two.
To do that, the models map the most efficient delivery routes based on where customers are clustered, the shortest distances between groups, and other objectives. The model also has the critical built-in flexibility to recast the pickup/delivery route when new orders are placed – in essence, anticipating that changes will occur and having new routes ready to replace the original plan.
“What we do is we basically make a decision every 30 seconds to two minutes (after a change to the system),” Van Hentenryck explains. “Either a customer makes an order or a vehicle reaches a customer, and we have to do that online, to optimize that.
“If you told me we could get those results five years ago, I’d say there’s no way,” Van Hentenryck adds.
Industries have responded favorably to the idea. Van Hentenryck said airlines use optimization models to allocate seats on planes – juggling various price classes with the ebb and flow of demand for spaces. Television networks in Europe are using the models to slot commercials a week in advance, requiring models nimble enough to take into account the different price structures depending on the time of day.
But companies also can be conservative about change, and in an economic downturn, change means spending money that businesses may not have.
“It is ready at many levels, but it is new technology,” Van Hentenryck says. “People have to understand that they can trust it, that they can be convinced the system that we propose is better than what they do.”
In addition to Van Hentenryck and Upfal, Brown researchers involved in the research are Carleton Coffrin and Yue Kwen Justin Yip, both graduate students in the computer science department; and Steffen Godskesen, a visiting PhD student from Denmark. Other institutions with noteworthy programs in optimization modeling are Cornell University, the Georgia Institute of Technology, and the Massachusetts Institute of Technology.
For more information, visit the Optimization Lab’s web site.
Pascal Van Hentenryck is working on a way to minimize the effects of such disruptions. The Brown computer science professor is building elaborate models that can help companies, agencies, and other organizations anticipate contingencies before they arise and suggest how to respond most effectively.
To be sure, businesses always are trying to figure out how best to deal with uncertainty and how to adjust their operations when the best-hatched plans go awry. But thanks to greater computing power, better tracking technology, and more robust mathematics, predictive models can now be revised nearly instantaneously to meet changing conditions. This emerging research trend is called online stochastic optimization.
Pascal Van Hentenryck
“These are the questions that companies are asking themselves: How do I model this so I can best react to different circumstances?” van Hentenryck says. Van Hentenryck has assembled a team of graduate students who are constructing algorithms – mathematical steps – to support the optimization models. The group received federal funding this fall to work with the Los Alamos National Laboratory on a system for inventorying and routing supplies after a natural disaster. The team also has the first Navy Experimental Program to Stimulate Competitive Research (EPSCoR) grant in Rhode Island to develop algorithms.
In addition, Van Hentenryck’s group is working closely with computer science professor Eli Upfal on a National Science Foundation grant to explore the theoretical underpinnings of the modeling. “The ultimate goal in computer science is to show these algorithms work fast and produce the best or as close to the best solution as possible,” Upfal says.
To demonstrate the research, Van Hentenryck pulls up on his laptop a scenario involving a hypothetical shipping company. The firm wants to serve 95 customers in a four-hour span on a Saturday. The company’s goal is to pick up and deliver packages for every customer and to manage new orders during that time as efficiently as possible. Using current planning software, the company serves 66 customers but rejects 29. Using algorithms developed by Van Hentenryck’s team, the company serves 93 customers, rejecting only two.
To do that, the models map the most efficient delivery routes based on where customers are clustered, the shortest distances between groups, and other objectives. The model also has the critical built-in flexibility to recast the pickup/delivery route when new orders are placed – in essence, anticipating that changes will occur and having new routes ready to replace the original plan.
“What we do is we basically make a decision every 30 seconds to two minutes (after a change to the system),” Van Hentenryck explains. “Either a customer makes an order or a vehicle reaches a customer, and we have to do that online, to optimize that.
“If you told me we could get those results five years ago, I’d say there’s no way,” Van Hentenryck adds.
Industries have responded favorably to the idea. Van Hentenryck said airlines use optimization models to allocate seats on planes – juggling various price classes with the ebb and flow of demand for spaces. Television networks in Europe are using the models to slot commercials a week in advance, requiring models nimble enough to take into account the different price structures depending on the time of day.
But companies also can be conservative about change, and in an economic downturn, change means spending money that businesses may not have.
“It is ready at many levels, but it is new technology,” Van Hentenryck says. “People have to understand that they can trust it, that they can be convinced the system that we propose is better than what they do.”
In addition to Van Hentenryck and Upfal, Brown researchers involved in the research are Carleton Coffrin and Yue Kwen Justin Yip, both graduate students in the computer science department; and Steffen Godskesen, a visiting PhD student from Denmark. Other institutions with noteworthy programs in optimization modeling are Cornell University, the Georgia Institute of Technology, and the Massachusetts Institute of Technology.
For more information, visit the Optimization Lab’s web site.