Learning to branch for the crew pairing problem

, , , , et

référence BibTeX

Crew pairing problems (CPP) are regularly solved by airlines to produce crew schedules. The goal of CPPs is to find a set of pairings (sequence of flights and rests forming one or more workdays) that cover all flights in a given period at a minimum cost. The CPP is a NP-hard combinatorial problem that is usually solved approximately using a branch-and-price heuristic. A common branching heuristics selects the closest-to-one pairing variable and fixes it without backtracking, which allows finding good solutions quickly. By contrast, variable selection strategies based on strong branching typically produce better solutions but are computationally prohibitive. This paper explores the possibility of learning efficient branching strategies for diving heuristics from strong branching decisions. To help the learning process, we propose a new normalisation of the branching scores which is able to better distinguish the good and bad branching candidates. Our results demonstrate that our learnt strategies make better branching decisions than the greedy strategy while executing in approximately the same computational time.

, 17 pages

Axe de recherche

Application de recherche


G2231.pdf (570 Ko)