MULTIMODAL EXPRESS PACKAGE DELIVERY: A SERVICE NETWORK DESIGN APPLICATION

The focus of this research was to model and solve a large-scale service network design problem involving express package delivery. The objective was 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. The authors developed a model for large scale transportation service network design problems with time windows. With the use of route-based decision variables, complex cost structures and operating regulations and policies were captured. The poor linear programming bounds limited the ability to solve the problem, so linear programming relaxation was strengthened by adding valid inequalities. By exploiting problem structure using a specialized network representation and applying a series of novel problem reduction methods, dramatic decreases in problem size without compromising optimality of the model were achieved. The authors' 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 other computational experiments, it was concluded 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.

• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/oclc/1767714
• Corporate Authors:

  Institute for Operations Research and the Management Sciences (INFORMS)

  901 Elkridge Landing Road, Suite 400
  Linthicum, MD  United States  21090-2909
• Authors:
  • Kim, D
  • Barnhart, C
  • Ware, K
  • Reinhardt, G
• Publication Date: 1999-11

Language

• English

Media Info

• Features: Figures; References; Tables;
• Pagination: p. 391-407
• Serial:
  • Transportation Science
  • Volume: 33
  • Issue Number: 4
  • Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
  • ISSN: 0041-1655
  • Serial URL: http://transci.journal.informs.org/

Subject/Index Terms

• TRT Terms: Costs; Courier service; Express service; Fleet management; Heuristic methods; Minimization; Multimodal transportation; Networks; Operating costs; Package service; Routes and routing; Savings
• Subject Areas: Aviation; Finance; Freight Transportation; Highways; Planning and Forecasting; Public Transportation; Railroads; I72: Traffic and Transport Planning;

Filing Info

• Accession Number: 00780037
• Record Type: Publication
• Files: TRIS
• Created Date: Dec 8 1999 12:00AM