Air Express Network Design with Hub Sorting

Abstract

This dissertation examines an innovative strategic operation for next day air package delivery. The proposed system, in which some packages are sorted twice at two distinct hubs before arriving at their destinations, is investigated for its potential savings. A two-stage sorting operation is proposed and compared to the currently operated single-stage sorting operation. By considering the endogenous optimization of hub sorting and storage capacities, cost minimization models are developed for both operations and used for performance comparison.

Two solution approaches are presented in this study, namely the Column Generation (CG) approach and the Genetic Algorithm (GA) approach. The first method is implemented to optimize the problem by means of linear programming (LP) relaxation, in which the resulting model is then embedded into a branch-and-bound approach to generate an integer solution. However, for solving realistic problem sizes, the model is intractable with the conventional time-space formulation. Therefore, a Genetic Algorithm is developed for solving a large-scale problem. The GA solution representation is classified into two parts, a grouping representation for hub assignment and an aircraft route representation for aircraft route cycles. Several genetic operators are specifically developed based on the problem characteristics to facilitate the search.

After optimizing the solution, we compare not only the potential cost saving from the proposed system, but also the system's reliability based on its slack. To provide some insights on the effects of two-stage operation, several factors are explored such as the location of regional hubs, single and multiple two-stage routings and aircraft mix. Sensitivity analyses are conducted under different inputs, including different demand levels, aircraft operating costs and hub operating costs. Additional statistics on aircraft utilization, hub capacity utilization, circuity factor, average transfers per package, and system slack gain/loss by commodity, are analyzed to elucidate the changes in system characteristics.