A Matheuristic for Aircraft Maintenance Routing Problem Incorporating Cruise Speed Control

Aircraft maintenance routing problem incorporating cruise speed control (AMRP-CSC) is an extension of the well-known aircraft maintenance routing problem (AMRP) where the flexible cruise times of flights are considered in route construction. Changing cruise times in AMRP can transform the infeasible flight connections into feasible ones, resulting in a larger solution space and further opportunities for efficiently routing. This may open up the possibility for a substantial improvement in aircraft utilization, but also increases resolution complexity. In this study, a new solution methodology, namely a matheuristic approach, is proposed for this problem. It is composed of three main components: an improved ant colony optimization (IACO) algorithm, a set partitioning (SP) procedure, and a neighborhoods search (NS) procedure. The IACO algorithm serves as a route generator, populating a pool of routes with promising feasible aircraft maintenance routes. Then, a SP model, which features the high-quality columns corresponding to the routes in the pool, is solved to produce a possible better solution. Finally, this solution is further improved by a NS procedure that iteratively solves the reduced AMRP-CSC instances to optimality. This matheuristic approach is analyzed and tested using the data extracting from the Bureau of Transportation Statistics (BTS), and then its accuracy and the efficiency have been demonstrated by experiment analyses.