Stochastic programming models for scheduling airlift operations

This article describes an analytic approach to flight scheduling within an airlift system. The model takes explicit account of the uncertainty present in cargo requirements or demands. For computational feasibility, the approach consists of two related models: (1) a monthly planning model that produces an initial schedule, and (2) a daily model for making periodic changes in the schedule. Both are formulated as two‐stage stochastic linear programs. A detailed mathematical description of each model and its physical interpretation is given. The monthly model determines the number of flights each type of aircraft in the fleet. Excess demands on certain routes are assumed to be met, at least in part, by spot procurement of commerical lift from outside the system. The flight assignment is determined by minimizing the expected total system cost, which consists of operating costs, costs of reallocating aircraft to different routes, spot commercial procurement costs, and other penalty costs of excess demand. The model accounts for limitations on the number of flying hours and the carrying capacities of various aircraft in satisfying demands. In the daily model the number of aircraft of each type to switch from one route to another and the number of commercial flights on spot contract to add on the current day are the principal decision variables. These are determined by balancing operating, procurement, and redistribution costs against the expected costs of additional cargo delay. The current state of the system — the amount of unmoved cargo on various routes andathe position of aircraft throughout the system — plays a role in determining these decisions. A description of two variants of an algorithm recently developed for this class of problems is presented. Both versions, which use ideas from convex programming, make extensive use of linear programming codes for the brunt of the calculations. The models may thus be solved by augmenting existing linear programming routines.