United Parcel Service, better known as UPS, is the world's largest package distribution company. Serving more than 200 countries and territories, UPS transports more than 3 billion parcels annually, including upwards of 325 million during Peak, the four to five weeks between Thanksgiving and Christmas. To do this, UPS operates more than 600 aircraft, 88,000 vehicles, and 1,700 facilities. It is a logistics problem of the highest order, and UPS analysts like Keith Ware are taking linear modeling to the maximum in order to solve it.

BA: Hello Keith. Thanks for taking the time to speak with us.

KW: You’re quite welcome.

BA: So getting right to it, tell us a little bit about your group.

KW: Essentially the Operations Research group has two sides to it, an optimization group and a simulation group. On the simulation side, our main focus right now is a huge new facility that we’re in the process of building in Louisville. We started work on it about three years ago and it’s scheduled to be fully operational next summer, at which time it will be the largest automated sorting facility in the world. The simulation group does a lot of work using models to analyze various ways of aligning the building’s sorting systems, determining which load goes where, and looking at how to feed containers to the unloads from the ramps where they’re taken off the aircraft. The goal is to minimize the time it takes to run the sort operation.

On the optimization side - and I think this is what your readers will be most interested in - is the linear programming that we’ve been developing to address the job of aircraft routing. We’ve been working on the project for 4 or 5 years now - together with Professor Cindy Barnhart of MIT and several of her students - conducting research into different algorithms for solving this incredibly massive problem.

BA: What are some of the parameters?

KW: Primarily we’re looking at the airline’s operating costs. We’ve got fuel costs, maintenance costs, cycle costs - every time an aircraft goes through a cycle of taking off and landing it incurs a certain cost. We also have an ownership cost, which is particularly significant when you are comparing possible scenarios for expanding the fleet, or when you’re looking to lease aircraft to handle the volume increase during Peak. Though really [laughing] we never have enough aircraft to move the volume we have between November and December.

BA: How many planes do you have in the fleet?

KW: We own approximately 240 planes - that’s heavy jets, DC-8s, A300s, and the like. We also lease or charter another 275 to 300. A lot of those are smaller, corporate-size aircraft that we use for our feeder operation - that is, getting packages from a place like Bangor, ME, to our nearest heavy-et airport, which in that case would be Manchester, NH.

BA: You said “a lot of those are smaller planes,” but not all?

KW: That’s right. We also lease heavy-jet aircraft, especially for Peak. In fact, we’ve actually been using our linear programming model to support the Peak planners in analyzing the heavy-jet leases that we have. For example, we’ll lease DC-10s, 747s, and DC-8s, and the question is what’s the mix? What did we do last year?

BA: Can you tell us a little more specifically about the model?

KW: Our main model is a linear programming model - actually it’s an integer programming model, because a linear programming model would give you half a plane or a quarter of an plane. One of the main problems is size. Just in terms of the domestic overnight network, which is what we’re focusing on right now, we’re talking about 80 to 90 aircraft operating out of 90 to 100 different locations, flying into 7 different hubs, and then flying back out to that same set of 90 to 100 locations. Computationally, the number of routing possibilities simply explodes.

Essentially, though, it is a covering type of problem. You want to cover all the demand out of a particular location, subject to the capacity constraints of the routes and the hubs. But you also have additional constraints, such as the number of aircraft that can operate in and out of various locations at different time periods. For example, since we opened the parallel runway in Louisville, we can take in aircraft at a rate of about 1 every 30 seconds and depart them at a little less than 1 every minute. But it’s not the same everywhere, so you’re limited in how fast you can bring in and send off the airplanes. You also have limits on ramp capacity. On top of that, the Next Day operation doesn’t exist in isolation. There’s an international operation that is feeding in and out of it. Airplanes will cross over. A plane will come in on an international route and then take off on a domestic route. Then we also have our Second Day operation. So what we do is have boundary conditions that specify how many aircraft of each type we have to have in a particular location. Some places don’t have to have any particular type restrictions. For those locations all the model requires is that at the end of the night they have the same number and type of planes that they started with.

The problem that you fight with an integer programming model is size, and to deal with this the folks at MIT developed the composite variable modeling technique that allows us to condense a whole lot of decisions into one decision. It’s a technique that I think you’re going to hear more about if you’re in the operations research area. It also allows us to couple decisions about package-flow with the way that routes are built. We’ve even gotten to the point where we’re building a single variable inside the model that can contain multiple routes, which allows certain things to happen in the model such as ramp swamps.

BA: Ramp swaps?

KW: Let me give you an example. Let’s say I have one airplane that leaves Jackson, MS, and flies to Louisville with a stop in Memphis, and another that leaves Little Rock, AK, and flies to Columbia, SC that also stops in Memphis. In this situation, the Little Rock plane could carry all the volume from Little Rock that’s going either to Columbia or Louisville to Memphis, and the Jackson plane could carry all the volume originating Jackson that is bound for either Columbia or Louisville to Memphis. While both planes are sitting on the ramp in Memphis, the containers are switched so that all Louisville volume is on the first plane, and all Columbia volume is on the second. That is a very difficult situation to model, but we do it quite a bit in practice. These are some instances in which we use some very complex structures that have evolved over the years.

BA: Evolved how?

KW: The way the model was initially built, it ignored this ramp transfer possibility, and we found that we were actually requiring additional aircraft because we had to have a flight from every place to every hub where it sent volume. Composite variables were originally developed to allow us to combine the capacity of multiple aircraft of different types on a single route. By implementing these methodologies, where we were considering multiple routes and multiple flows and binding it all together into a single constraint, all we had to think about was do we cover the demand or don’t we? We then saw that this could be extended to combining different routes, and then different hubs. Finally, we were able to generate route, fleet, and hub structures that handled ramp transfers. As a result, we can now solve some models that before we couldn’t solve at all, and we’re generating good answers with relatively small IP/LP gaps in matters of hours.

BA: What is the IP/LP gap?

KW: The IP/LP gap measures the difference between the solution of an integer program - an IP - and the solution obtained solving the problem as a linear program - an LP. You can solve an integer program as a linear program - all you have to do is relax the fact that the answers have to be integral. The difficulty, as I mentioned before, is that you’re going to get a half of an airplane here, a quarter of an airplane there. Still, the LP solution can give you a good idea of the quality of your IP solution. For example, if you have an integer solution on the order of $10,000,000 but the LP solution is $1,000,000, your IP/LP gap is $9,000,000. You really have no idea if there is another integer solution in that area that has a lower cost. But if the difference between the IP and LP solution is only 5% or 10%, you can be pretty confident. There may be another solution that’s better, but not a whole lot better.

BA: In terms of optimization, how often would you use the model?

KW: We’ve run the model 50 to 100 times in the last six months, both for the network planners - those are the guys who are responsible for our day to day operation - and also the guys working on Peak - they are the ones who focus all year on what happens between Thanksgiving and Christmas. And then we’ve also done some work for Long Range. They are the folks who look two years out and even further, the ones who try to answer questions along the lines of what should our fleet size look like and what locations should we be operating in and out of in 5 or 10 years.

BA: I’m just curious: have you tried other techniques, neural nets for example?

KW: Not really. The problem just lends itself so well to a linear type solution. The main obstacle as I’ve said is size and we think we now have a good handle on it using composite variables. We’re now looking at ways to use these techniques to isolate one portion of the network. Let’s say we want to look at just the Northeast or the Southeast - what you do is look at the rest of the network as simply one large composite variable. You assume that it’s covered, fix it to 1 and sets it’s cost to 0, so that the model isn’t going to touch it. It’s going leave that part of the country just as it is, so that now you can focus on just the region you’re interested in.

BA: Generally speaking, is the overnight business still growing or is it leveling off somewhat?

KW: With recent events and the economy slowing, we’re not growing as fast as we anticipated last year, but over the last few years it’s grown explosively, and we do anticipate that the long-term trend is that the growth will continue.

BA: Clearly, the kind of work that you’re doing represents a major undertaking in both time and money. UPS must see value in the investment?

KW: First of all, UPS is a company that is very grounded in industrial engineering approaches. We do a lot of analysis so this type of investment is really an outgrowth of our culture, which is finding the most efficient ways to do things. I sometimes tell people my job is to think so far outside the box that people look at me like I’ve got 3 eyes. At the same time though, if a few years from now we can say as a result of our work that the company can defer the purchase of aircraft that were slated for acquisition, we’ve paid for all the research, all the machinery, all the people who work for me, and still have an ungodly return on investment because the numbers are just so big.

BA: And going forward?

KW: One of the things that is really interesting is that the planners have become better as a result of the interaction. They’re now looking for things they weren‘t before. But at the same time, the problem has grown to the point that to do it on their end they would have to bring in 20 or 30 planners and have them work for 6 months to do what the model can do in days or hours. For the moment though, the system requires an analyst to run it. Eventually what we’d like is to put the system directly in the hands of the planners.

More Features