An integrated column generation solution framework for optimal aircrew vacation planning subject to seniority ranking and priority preference satisfaction

We consider the vacation planning problem in the context of commercial aviation, which aims to devise optimal vacation periods for a group of crew members, while also ensuring that the efficient operation of the airline remains intact. The problem definition includes two objectives treated lexicographically, the maximization of crew satisfaction with respect to specific vacation preferences (bids) they have expressed in advance, and the minimization of the collective vacation entitlement that remains unassigned. We develop an integrated solution framework for this problem, which consists of two independent phases executed sequentially. The first one (bid award phase) focuses exclusively on crew satisfaction, exploiting an innovative optimization model that examines the approval of each bid individually, according to the distribution logic in effect. Each grant/reject decision is made based on whether bid acceptance retains the feasibility of this model. The second one (auto-allocation phase) employs a column generation solution algorithm which assigns complementary vacation periods to the crew members for maximizing the total number of vacation days assigned combinedly to the group. We report computational results on realistic problem instances with variable characteristics, which demonstrate the behavior of the proposed solution methodology, assess its computational performance, and highlight its effectiveness. These results confirm that it succeeds in identifying robust solutions accommodating the highly variable user requirements of practical airline environments in satisfactory computational times.