A Branch-and-Price Algorithm for the Tail Assignment Problem under Hour-to-Cycle Ratio Constraints

Çiya Aydoğan

Operating lease is a frequently used and increasingly popular method of acquiring aircraft for airlines. However, this method typically imposes specific restrictions on the lessee's aircraft utilization decisions, such as a target hour-to-cycle ratio for the aircraft. Failing to meet this target over a certain period of time may result in supplementary rental payments. This study considers hour-to-cycle ratio constraints in the tail assignment problem. The aim is to develop exact solution approaches for the problem. We propose a branch-and-price algorithm. To enhance its performance, we introduce a beam search-based algorithm that generates feasible solutions for the problem and also devise a dancing links-based heuristic approach that finds upper bounds. The proposed algorithms successfully solved instances with up to 60 aircraft and 446 flights to optimality, while CPLEX, which was solving a connection network-based mathematical formulation, was unable to find a feasible solution within an hour.

Short Bio

Çiya Aydoğan is currently a research assistant and a Ph.D. candidate at the Industrial Engineering Department at METU. He obtained both his BS and MS degrees from the same department. His research on energy-efficient robotic cell scheduling problems was published in the International Journal of Production Research and the Flexible Services and Manufacturing Journal. His current research focuses on aircraft scheduling problems with hour-to-cycle ratio constraints. He has published a preceding work on this problem in the Journal of Air Transport Management.

Venue

Friday, May 23rd, 2025, 4:00 pm

IE Building, Halim Doğrusöz Auditorium (Ground Floor-03)