Multimodal express package delivery: A service network design application

The focus of this research is to model and solve a large-scale service netw ork design problem involving express package delivery. The objective is to find the cost minimizing movement of packages from their origins to their d estinations, given very tight service windows, Limited package sort capacit y, 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, rue capture c omplex cost structures and operating regulations and policies. The poor lin ear programming bounds limit our ability to solve the problem, so we streng then our linear programming relaxation by adding valid inequalities. By exp loiting problem structure using a specialized network representation and ap plying a series of novel problem reduction methods, we achieve dramatic dec reases in problem size without compromising optimality of the model. Our so lution optimization approach synthesizes column and row generation optimiza tion techniques and heuristics to generate solutions to an express package delivery application containing hundreds of thousands of constraints and bi llions of variables, using only a small fraction of the constraint matrix. The results are potential savings in annual operating costs of tens of mill ions of dollars, reductions in, the fleet size required, dramatic decreases in the time required to develop operating plans, and scenario analysis cap abilities for planners and analysts. Through this and additional computatio nal experiments, we conclude that, although state-of-the-art integer progra mming methods can work well for relatively small, uncongested service netwo rk design problems, they must be used in, concert with heuristics to be eff ective for large-scale, congested problems encountered in practice.