Category: Applications

The February 2007 issue of the Harvard Business Review has an article on “Breakthrough Ideas for 2007” (sorry, pay-only link: HBR isn’t much for making stuff available for free). One of the breakthrough ideas is given by Michael Schrage of the MIT Media Lab under the title “Algorithms in the Attic”, a play on the title Rembrandts in the Attic, a book on unlocking the value of patents (for better or worse). Schrage argues:

For a powerful perspective on future business, take a hard look at mathematics past. As computing gets ever faster and cheaper, yesterday’s abstruse equations are becoming platforms for tomorrow’s breakthroughs. Companies in several industries are now dusting off these formulas and putting them in the service of new products and processes.

Examples Schrage cites are include:

Procter & Gamble has been restructuring its supply chain with complex “expressive bidding” algorithms–based on 1950s linear-programming equations– that allow suppliers to bid online with bundled offerings of products and service levels rather than with standardized lots. Google’s search engine was possible only because the founders adapted a century-old theorem about matrices to software for ranking Web pages according to links from other sites. Networks like the Web can be expressed as matrices, and a relatively simple calculation gives a ranking of how well each site is connected to the rest of the Web. That formula for automatic ranking – which could be understood and appreciated without a PhD – is one of the most lucrative algorithms ever. The math was there for the taking.

Well-known OR researcher Dick Larson gives a nice quote:

“There are huge hidden assets in the operations-research community,” says the MIT professor Richard Larson, a pioneer in probabilistic modeling techniques. “If you gave an army of 20 grad students the mission to rake through the published literature of the past 30
years, they would find stuff that has untapped business potential worth billions
of dollars. There are many clever ideas my students worked on decades
ago that in today’s networked environment would not be an academic exercise
but a real business opportunity.”

Schrage concludes:

Whether looking for breakthroughs or just trying to improve decision making, companies will benefit from greatersophistication around even simple mathematics. A decade ago, big firmsbegan to realize that they were sitting on a treasure trove of underutilized patentsand know-how that could be commercialized for willing buyers. Those “Rembrandts in the attic,” as Kevin G.Rivette and David Kline put it in their 2000 book by that name, needed thekeen eye of an intellectual property curator to appreciate their value. Similarly, we now require quantitative entrepreneurs to seek out existing equations that meet today’s pressingbusiness needs. Technology continues to make that quest faster, easier, and cheaper.

Hmmm…. thinking over my past research doesn’t immediately lead to thoughts of business opportunity, but maybe it is time to pull out those dusty journal articles.

Thanks to Chad, a Tepper MBA student, who pointed out the the Wall Street Journal of March 6, 2007 has an article on optimizing international airline routes. It turns out that countries have complicated costs for airplanes flying in their space, and rerouting the planes can lead to pretty significant savings (on the order of $1,400/flight, which multiplies out to millions per year). From the article:

The formulas countries use to compute their overflight fees vary widely. Cameroon, in Africa, bases its charges on the maximum takeoff weight, with an international flight passing over the country paying from €102 to €204 ($134 to $267). Canada assesses 3.6 Canadian cents (3 U.S. cents) times the distance flown times the weight of the aircraft, plus C$97 per flight for air-traffic control coverage over the North Atlantic. United Kingdom overfly rates are three times as high as Ireland’s rates, and German rates are at least twice as high as Canada’s, according to international aviation specialists.
The U.S. funds its air-traffic-control system differently. Instead of flyover fees, passengers pay multiple taxes to the airlines, which pass the money on to a trust fund. On domestic flights fliers pay 7.5% of the cost of the ticket, plus $3.40 for each flight segment. Passengers on international flights pay $15.10 in fees for coming into and leaving the U.S. Minimizing overflight fees must be balanced against additional fuel costs if an alternative route is less direct. The software systems track a slew of additional data: weather; airport locations and runways; weight and performance of each airplane in the carrier’s fleet; temporarily blocked airspace and the locations of fixed air routes, which change daily due to winds.
The computers churn through multiple scenarios, including minimum time, minimum fuel and minimum cost, and determine which is the best solution for the maximum payload, given up-tothe-minute wind and weather information.

It is surprising the savings possible:

British Airways in 2003 finished installing such software on its route network, replacing a homemade system that one pilot describes as “a blunt instrument.” As a result, it has drastically changed the routing of its Sao Paulo-London flight. Instead of flying in a straight line and crossing over Portugal, Spain and France before entering U.K. airspace, the airline now takes a northerly track over the Atlantic and enters the U.K. over Cornwall. Capt. Tim de la Fosse, BA’s general manager of flight technical, says the new path saves £3,000 ($5,767) per one-way flight in European overfly fees, uses one fewer ton of fuel and is 18 minutes shorter in duration.

Operations research has been getting a lot of press recently due to a study about the effectiveness of “no-fly” lists in preventing terrorism. Long-time researcher of airline safety, Arnie Barnett along with Harvey Mudd professor Susan Martonosi found, using OR models of course, that it is best to screen all passengers, rather than try to pre-screen so-called safe passengers. Here are some excerpts from the LA Times:

Operations research is a little-known but valuable tool for such things as scheduling airline flight crews, planning National Football League seasons and even designing waiting lines at Walt Disney World. And in a report released on Monday, it was used to assess the effectiveness of the nation’s security screening of airline passengers.

Using a mathematical model, Susan E. Martonosi, an assistant professor of mathematics at Harvey Mudd College in Claremont, and Arnold Barnett, a professor of management science at MIT, sought to explore the effectiveness of the “no-fly” lists in preventing terrorism. The conclusions they reached were less remarkable perhaps than the way they evaluated the program.

They found that improving the screening required of all passengers at security checkpoints would do more to enhance security than further refinements to the pre-screening of passengers by no-fly lists.

Here is a presentation on the topic.  Check out your December issue of Interfaces for the full paper, along with a number of other papers on homeland security.

US News and World Report has an article in their July 31 issue on how UPS uses technology to better handle packages. In the hypercompetitive world of package delivery, the need to use OR to create efficiencies is very strong.

Perhaps no industry has more effectively embraced the power of digital technology to modernize operations–even more so than airlines, which were long seen as leaders in cutting costs and boosting revenues through computers. “The delivery companies have leapfrogged ahead,” says Satish Jindel of SJ Consulting Group.

In their tight competition, industry leaders UPS and FedEx have one-upped each other for years in rolling out hand-held computers, wireless links, and new uses of mainframe computing power. Now UPS is pushing automation to the last mile of its delivery network, down to charting the order in which packages are loaded on a truck and the most efficient route for delivering them. Dubbed “package flow technology,” the latest upgrade is costing $600 million and taking three or four years to implement across the company’s 70,000 routes. When the upgrade is in place, UPS says it should get back that $600 million every year in saved costs, as more-efficient routes cut 100 million miles of driving time and 14 million gallons of gas. “It’s fundamental–a major, major change that will even change the way our drivers run their routes,” says Chief Information Officer David Barnes.

They even found room for a quote from me:

Pushing automation to the fringes of its operations is only possible because of the mass of data that UPS computers have been collecting as parcels move through its central hubs, and thanks to advances in math and computing power. Delivery companies have become leaders in “operations research,” a growing field that uses mathematical models to streamline processes, says Michael Trick of Carnegie Mellon University. “It used to be that only airlines could worry about issues like routing,” he says.

Hmm… did I really say the last part? Well, the point I was trying to make was that while airlines where at the forefront of practical OR, we are now seeing it in lots more places. UPS is a good example, though they are catching up with firms that caught the OR bug early, like FedEx:

Bart Haberstroh, who delivers for UPS in St. Charles, Mo., a St. Louis suburb, remembers when “the joke was that the sharpest tech UPS had was a sharp pencil,” he says as he wheels his brown van through familiar streets.

With the amount of OR pouring into their systems, that is no longer the case.