Augmented Lagrangian Based Hybrid Subgradient Method for Solving Aircraft Maintenance Routing Problem

Abstract In this paper, a new version of the aircraft maintenance routing problem, which is an important component of the airline planning process, is studied. We define the big-cycle aircraft maintenance routing problem on a connection network and formulate it as an asymmetric travelling salesman problem with fleet size and maintenance violation constraints, which takes maintenance resource availability into account. In the connection network, flight legs are represented by nodes and connections between flight legs are denoted by arcs. In our approach, decision variables denote the connections between flight legs. We develop a hybrid solution method for this problem, which combines the Gasimov’s modified subgradient algorithm and the ant colony optimization metaheuristic. The performance of the proposed method, is demonstrated and analyzed through detailed computational experiments. Performances of the proposed method, conventional subgradient algorithm and ant colony optimization algorithm are compared on different test problems. The analysis of the quality of the results demonstrates that the proposed method outperforms the mentioned methods.