An Optimization Approach to Routing Aircraft

The optimal solution for an aircraft routing model is developed for use in the route construction process of an airline operating in long haul markets. The problem is to determine the sequence of stops for each aircraft from one base through a network of cities terminating at the original or second base. A mixed integer linear programming model is formulated to maximize the profit derived from each routing. The special structure of the mixed integer model is solved by an application of Benders’ Decomposition Method. Methods to improve the computational efficiency of the technique are examined and tested. Finally, an implementation plan for incorporating the routing model into the airline scheduling process is presented.