Integrated aircraft-path assignment and robust schedule design with cruise speed control

Assignment of aircraft types, each having different seat capacity, operational expenses and availabilities, critically affects airlines' overall cost. In this paper, we assign fleet types to paths by considering not only flight timing and passenger demand, as commonly done in the literature, but also operational expenses, such as fuel burn and carbon emission costs associated with adjusting the cruise speed to ensure the passenger connections. In response to flight time uncertainty due to the airport congestions, we allow minor adjustments on the flight departure times in addition to cruise speed control, thereby satisfying the passenger connections at a desired service level. We model the uncertainty in flight duration via a random variable arising in chance constraints to ensure the passenger connections. Nonlinear fuel and carbon emission cost functions, chance constraints and binary aircraft assignment decisions make the problem significantly more difficult. To handle them, we use mixed-integer second order cone programming. We compare the performance of a schedule generated by the proposed model to the published schedule for a major U.S. airline. On the average, there exists a 20% overall operational cost saving compared to the published schedule. To solve the large scale problems in a reasonable time, we also develop a two-stage algorithm, which decomposes the problem into planning stages such as aircraft-path assignment and robust schedule generation, and then solves them sequentially.