Multimodal express package delivery: A service network design application

Abstract

The focus of this research is to model and solve a large-scale service network design problem involving express package delivery. The objective is to find the cost minimizing movement of packages from their origins to their destinations, given very tight service windows, limited package sort capacity, and a finite number of ground vehicles and aircraft. We have developed a model for large scale transportation service network design problems with time windows. With the use of route-based decision variables, we capture complex cost structures and operating regulations and policies. The poor linear programming bounds limit our ability to solve the problem, so we strengthen our linear programming relaxation by adding valid inequalities. By exploiting problem structure using a specialized network representation and applying a series of novel problem reduction methods, we achieve dramatic decreases in problem size without compromising optimality of the model. Our solution optimization approach synthesizes column and row generation optimization techniques and heuristics to generate solutions to an express package delivery application containing hundreds of thousands of constraints and billions of variables, using only a small fraction of the constraint matrix. The results are potential savings in annual operating costs of tens of millions of dollars, reductions in the fleet size required, dramatic decreases in the time required to develop operating plans, and scenario analysis capabilities for planners and analysts. Through this and additional computational experiments, we conclude that, although state-of-the-art integer programming methods can work well for relatively small, uncongested service network design problems, they must be used in concert with heuristics to be effective for large-scale, congested problems encountered in practice.