Month: July 2006

UPS, OR, and US News and World Report

US News and World ReportUS 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.

Bird flu Logistics

J. Michael SteeleJ. Michael Steele has a blog on “Bird Flu Economics”, looking at economic aspects of an avian inluenza pandemic. His blog provides a welcome dose of reality in the arguments about effect and appropriate response to the avian flu. A recent post of his points out how little logistics (read OR) planning has been done in this area.

Logistical nightmares are at the heart of every H5N1 pandemic senario anyone has ever concocted, yet it is hard to tell if anyone in the OR community is currently looking hard at this.

Isn’t it clear that pandemic logistics is a research area that deserves encouragement at every level?

Let’s at least catalog what is being done — or not being done!

Steele has done lots of interesting work. In the early 1980s, he did a lot of fundamental work in the use of probabilistic analysis in combinatorial optimization, including writing a great chapter in the Traveling Salesman book (as an aside: it is a travesty that the book costs more than $250; while dated on the TSP, it still provides a great overview of the various themes associated with combinatorial optimization and remain one of my favorite books of all time). His current work is primarily in mathematical finance and statistical modeling. He has a recent book on the Cauchy-Schwarz inequality (a much more reasonable $30!).

More OR in the New York Times

There is more OR in the New York Times, not that they would mention our field by name. There is an article today about new air-taxi services. There are a number of new airplanes in the lightweight group (under 10,000 pounds) able to carry 4 passengers or so. This is leading a number of companies to start serious air-taxi services:

Enter the air taxi, an idea whose time has come. At least that is the hope of the entrepreneurs placing big bets on a new niche they plan to create in aviation. Their idea is to offer faster, more convenient air travel at a price that falls somewhere between private jets and commercial airlines.

For years, questions about the size of an air taxi market have been largely theoretical. But that will change this year, as Eclipse Aviation of Albuquerque begins building the Eclipse 500, a six-seat plane. The company expects the plane will receive its long-awaited certification from the Federal Aviation Administration as soon as this week.

With the Eclipse, two start-up airlines, Linear Air and DayJet, say they can ferry business travelers to hard-to-reach outposts with fewer frustrations — and get them home in time for dinner with their families.

Economically, these jets cost somewhere between commercial prices and charter prices:

Air taxi operators say they can offer customers seats ranging from $1 to $3 a mile, compared with $9 to $13 a mile on charter jets, or up to $15 a mile on slightly larger private jets. Regional commercial airlines like SkyWest, by contrast, average less than 16 cents a mile flying 50-seat planes, but as much as five times that on less-traveled routes where air taxis plan to compete, industry executives say.

Of course, key to efficiency is (what else?) operations research:

Making Mr. Iacobucci’s flying limo work will require substantial computing power to analyze routes and passengers’ schedules almost instantly. That does not deter Mr. Iacobucci, who spent his career in the software industry, first at I.B.M. and later at Microsoft. He spent $20 million and four years developing DayJet’s reservation system. DayJet has already ordered 239 Eclipse 500’s, making it Eclipse Aviation’s biggest customer.

I love the way newspapers use a word like “analyze” when the reality is that signficant modeling and optimization must be done to handle systems such as this.

Open Source and Optimization

I am attending a conference at DIMACS on COIN-OR, which is an activity to encourage and support open source development in operations research. At the moment, most of COIN-OR revolves around linear and integer programming codes, but there are efforts in nonlinear programming, metaheuristics, and other areas.

COIN-OR addresses one of my pet peeves about research in OR (including my own!): developed codes are very rarely available and even more rarely useable by others. So people either reinvent previous work or simply compare new results to old results (perhaps trying to correct for computer speed). COIN-OR tries to develop a repository of open source codes. So, for instance, if you are doing research on a new type of cut for integer programming, you can simply add a short code to a full-featured IP code and see the results.

The codes being developed are very impressive, though a little overwhelming for a casual user. But different people are working for different target audiences. I hope the audience “I want to put together a branch-and-price algorithm in an afternoon” (e.g. me!) is addressed a bit more in the future.

One of the key goals for COIN-OR is highlighted on the home page:

Our goal is to create for mathematical software what the open literature is for mathematical theory.

If we are to advance as a field, we need much, much more of this sort of effort.New COIN-OR logo

COIN-OR is an example of a strong community in our field. It is great watching people who have only emailed over the past years meet each other for the first time.

And in breaking news, COIN-OR has chosen a new logo, as illustrated here.

Looking for Another Editor!

I am on the search committee to find Matt Saltzman’s successor as Editor-in-Chief of INFORMS Online. I was the first such editor, then Matt took over for the last six years. It was great being the first editor (1995-2000): there was so much to do that anything we did was better than what we had. Matt has worked hard to bring IOL up to a higher professional level, so now the webpage doesn’t look like something an amateur put together in an afternoon (which is what I did!). Behind the scenes, Matt and his team put IOL on a much stronger technical base.

Now, after 11 years, even the role of IOL Editor is undergoing change. Why have an OR professional be the Editor of IOL? After all, the Editor of OR/MS Today is not an OR professional: he is a journalist. Should IOL be any different?

I think having an OR person as editor of IOL is still very valuable. The goal of IOL is to create community, and outsiders would have a hard time figuring out what community would be valuable to an OR/MS person. What we need is a technologically savvy person with a broad interest in OR and advancing the field.

This position is absolutely key to INFORMS and to our field in general. I hope there are many applications, and many thoughtful discussions of the role of Editor of IOL.

The full Call for Nominations is here:

Continue reading “Looking for Another Editor!”

Looking for an Editor

ITORInternational Transactions of Operational Research is looking its next editor. I chair the search committee. We just did a review of the journal, and I think it offers an interesting opportunity to the right person. The key is trying to make the journal not just a “me-too” journal, taking the rejects from higher-ranked journals. The issue is finding the right niche. Since the journal is sponsored by IFORS, making the journal a key outlet for “international operations research” seems a very promising direction.

But what is “international operations research”? Lots of OR seems country/culture-independent. Certainly much of “mathematical programming”-type operations research does not seem “international” in any way. But there are issues of particular interest to developing countries that seem quite international. And there are many topics in international management that seem to fit (models in international operations for instance).

I guess I am hoping that someone out there will come up with a convincing vision of what “International OR” could be and how ITOR could play an important role in achieving that vision.

IFORS feels strongly about wanting the journal to succeed. The Administrative Committee has budgeted some funds for the activities that generate journal material (workshops, datasets, etc.) to help make the journal a success.

Here is the full call for nominations:

Continue reading “Looking for an Editor”

Large Storage Research

Gene Cooperman (Northeastern)Gene Cooperman of Northeastern University received an NSF grant in order to put together a system that can store 10-20 TB of data, as reported by Computerworld. This grant is getting some press since one application he talks about is storing configurations of a Rubik’s Cube. From the Computerworld article:

Cooperman, director of the Institute for Complex Scientific Software at Northeastern University in Boston, is studying Rubik’s Cubes as a way of setting up machines to study combinatorial problems in science and operations research. He wants to record as many different states of the Rubik’s Cube as possible, which he says will exceed the 20TB of capacity the $200,000 National Science Foundation grant recently afforded him.

Cooperman said that what he learns about the cube could be applied to operations research problems with business applications, such as determining the most efficient way to move goods to consumers.

“Operations research is about efficiently using resources,” he said. “The Rubik’s Cube is the same kind of mathematical problem.”

The article doesn’t go into detail of why one might be interested in storing such a thing. The reason is, as always in operations research, how one would use such storage. Gene’s annotated bibliography of his research (a very handy thing that we should all be doing), gives a bit better insight:

I was led to issues of groups of transformations, groups of symmetries, and presentations (defining equations for a group). Since Larry Finkelstein at Northeastern University was kind enough to give me an introduction to the field of computational group theory, which was still at a relatively early stage when I entered it, and I found much to do in building up the appropriate computational tools. These tools were sharpened and tried on some large applications. There were some early successes. For example, a one Megabyte data structure was pre-computed by which any state in Rubik’s 2 x 2 x 2 cube (Rubik’s cube with corners only) can be solved, and the shortest sequence of moves can be written out in a few milliseconds. (I found that Rubik’s cube can always be solved in at most 11 moves.)

So by storing configurations of the cube, algorithms can be applied to precompute solution approaches.

These issues of computational group theory have many other applications in operations research. My colleague here at Carnegie Mellon, Francois Margot, uses approaches like this to try to handle symmetries in integer programming formulations. I wonder if I can talk him into getting a 30TB machine?

Poker and Airline Scheduling

There is a nice post on the Math and Poker blog on the importance of identifying key variables and the flexibility that is available for many decisions in a process. The example begins with a standard critical-path type scheduling example, making the point that jobs not on the critical path have some flexibility. This point is extremely well known, of course, but it is interesting to think about what to do with this flexibilty. In poker, the author of the blog (I can’t see who it is), notes that there are a lot of situations where the difference between the best and next best decision is not a lot, but can be used to set up the opponents in particular ways (EV in the following is Expected Value):

The way that most people think about EV in poker is like treating each of these tasks independently. If I bet this hand what happens? Things like folding when the pot is small even if calling is +EV for this hand are ignored even though doing so might set up other players, or that player, to make a big bluff on some other hand.

If you really want to optimize your stratagy and maximize your win, they you just have to look at the game in a global sense. A strategic Expected Value of a collection of actions is what you need to consider, not a tactical Expected Value of one action.

So what does this have to do with airline scheduling? A lot of work is being done right now to combat the fragility of airline schedules. David Ryan of the University of Auckland gave a talk last week at the EURO conference on his work with New Zealand Air (my plans are to visit David for most of next year, so I was particularly interested in his work). In this work, David had a measure of fragility of a schedule (generally due to crews changing planes with a short layover: one late plane could quickly affect many others). David showed that there were near-optimal solutions (based on the main objective of minimizing cost) that had much better properties with regards to fragility. Things got even better if the schedule could be modified slightly.
The problem with both the poker example and crew scheduling is that the objective is much “fuzzier” than the underlying main objective. And that makes it much harder to “optimize”.

EURO Gold Medal Winner

The winner of this year’s EURO Gold Medel is Luk Van Wassenhove. Luk is having an amazing career, and I am delighted in this award to him. In my previous incarnation as President of the Carnegie Bosch Institute, I was able to support some of his work in full cycle logistics and he was a member of my Advisory Committee. Congratulations Luk!

In addition to his work in reverse logistics, Luk has also been a creator of the field “Humanitarian Logistics”. Luk began with work with the Red Cross, trying to change their view from “responsiveness” to preparation.