A Lagrangian Relaxation Approach to Assigning Aircraft to Routes in Hub and Spoke Networks

The problem of assigning aircraft to routes to maximize profits in a hub and spoke network is formulated as an integer linear programming problem. A Lagrangian relaxation of the problem is outlined together with heuristics for converting the Lagrangian solutions into primal feasible solutions and for improving on the solutions. Computational results from 324 runs spanning a range of problem sizes are reported. The results suggest that the Lagrangian relaxation is effective at providing an upper bound on the profits and the heuristics yield good solutions when the maximum number of aircraft required to fly all routes in the schedule is less than or equal to the number of available aircraft.