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

In this paper we 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. We 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. We 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 problems 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.