Scheduling flights at hub airports

In a typical hub airport, incoming flights from many origins feed outgoing flights to equally many destinations. If an incoming flight is late, outgoing flights that are fed by it may also be delayed. Alternatively, aircraft may leave before some feeding flights arrive, thereby incurring high misconnection penalties. By optimizing the scheduled ground time of each plane, we can minimize the expected sum of costs and penalties. In this paper we develop generalized newsboy models for this purpose. In particular, we investigate in detail a pure-waiting model in which no misconnections are allowed and discuss a no-waiting model in which aircraft that are ready to leave never wait for late-feeding flights. The models show that to maximize the system level of service at a given cost, the level of service of individual flights should be allowed to vary. The models can also be applied to similar problems such as express parcel deliveries and ground transportation hubs. The problems we address are nonlinear and highly combinatorial, so for life-size problems it is not practical to solve them to optimality. Therefore, an important part of the paper is devoted to heuristic solutions and the promising numerical experience achieved with them.