PROVE THE VALUE
More Efficient Planning and Delivery at UPS
The world's largest package delivery company, UPS relies on the efficient design and operation of its hub-and-spoke air network – seven hubs and nearly 100 additional airports in the U.S. – to move over a million domestic Next Day Air packages every night. Bringing greater efficiency to such an enormous system was a challenge. Known methods for solving large-scale network design problems were inadequate for planning the UPS air network. The primary obstacles were the complexity and immense size of the air operation, which involves over 17,000 origin-destination flows and more than 160 aircraft of nine different types. Solving these problems required operations research expertise in large-scale optimization, integer programming, and routing.
The O.R. Solution
UPS Air Group worked with an MIT specialist in transportation. The joint research and development effort resulted in an optimization-based planning system for designing the UPS aircraft network. To ensure overnight delivery, the approach simultaneously determined minimal-cost aircraft routes, fleet assignments, and allocation of packages to routes. The project team built integer programming formulations that were equivalent to conventional network design formulations, but yielded greatly improved linear programming-based bounds. This enabled realistic instances of the original planning problem to be solved typically in less than six hours, with many instances solving in less than one hour – substantial time savings.
UPS planners now use solutions and insights generated by the system to create improved plans. UPS management credits the system with identifying operational changes that have saved over $87 million to date, and is anticipating additional savings of $189 million over the next ten years. Other benefits include reduced planning time, reduced peak and non-peak costs, reduced aircraft fleet requirements, and improved planning.