Selecting aircraft routes for long-haul operations: A formulation and solution method

In this paper the authors consider the routing of long-haul aircraft from a main base to one or more terminal bases. For these long-haul markets, the routing decision becomes critical because route profitability must be evaluated for the extremely large number of feasible routes covered by the operation. In addition, the route selection task is complicated by the ‘pickup-and-delivery’ characteristic of the problem. Therefore, the development of an efficient procedure for selecting good candidate routes will facilitate the iterative flight scheduling process and may lead to more profitable timetables. The authors define an aircraft routing problem that captures the important profit-generating factors (such as intercity traffic estimates, revenues, operating costs, and aircraft capacities) in the route selection decision. They formulate this problem as a mixed integer program, and develop a Lagrangian-based solution procedure that exploits the special structure of the problem. Computational results for several test problem indicate that the procedure is able to select a small number of profitable candidate routes, and provide good bounds that confirm the near-optimality of the generated solutions.