Air network design for express shipment service

Express shipment service requires that shipments be picked up and delivered within specified time intervals (e.g. 24 hours, 48 hours or 3–5 days). In this paper, we describe the express shipment service design problem faced by a carrier and present a model and column generation approach for its solution. Our approach can find near optimal air service designs for a fixed aircraft fleet or for a fleet of unspecified size and make-up. In the latter case, the service design, fleet size and fleet composition are determined simultaneously. We have implemented our solution procedure, and a large carrier is using it to plan their air service operations and to evaluate various operating scenarios. The results indicate that service designs are generated that allow for improved service with a reduction in annual operating costs measuring in the millions of dollars.