Deep-learning-based partial pricing in a branch-and-price algorithm for personalized crew rostering

The personalized crew rostering problem (CRP) consists of assigning pairings (sequences of flights, deadheads, connections, and rests, forming one or several days of work) to individual crew members to create a feasible roster that maximizes crew satisfaction. This problem is often solved using a branch-and-price algorithm. In this paper, we propose a partial pricing scheme for the CRP in which the column generation subproblem of each crew member only contains the pairings that are likely to be selected in an optimal or near-optimal solution. The task of selecting which pairings to include in each network is performed by a deep neural network trained on historical data. We test the proposed method on several large instances. Our results show that our method finds solutions of similar quality as that of the classical branch-and-price algorithm in less than half of the computational time.

Automated summary

A new partial pricing scheme is proposed in this paper for the personalized crew rostering problem, utilizing a deep neural network trained on historical data to select pairings likely to be included in an optimal or near-optimal solution. Testing on large instances shows that the method achieves solutions of similar quality as the classical algorithm in less computational time.