Crew assignment via constraint programming: Integrating column generation and heuristic tree search

Crew assignment via constraint programming: Integrating column generation and heuristic tree search

0.00 Avg rating0 Votes
Article ID: iaor20031363
Country: Netherlands
Volume: 115
Issue: 1
Start Page Number: 207
End Page Number: 225
Publication Date: Sep 2002
Journal: Annals of Operations Research
Authors: , , ,
Keywords: programming: integer, programming: assignment
Abstract:

The Airline Crew Assignment Problem (ACA) consists of assigning lines of work to a set of crew members such that a set of activities is partitioned and the costs for that assignment are minimized. Especially for European airline companies, complex constraints defining the feasibility of a line of work have to be respected. We developed two different algorithms to tackle the large scale optimization problem of Airline Crew Assignment. The first is an application of the Constraint Programming (CP) based Column Generation Framework. The second approach performs a CP based heuristic tree search. We present how both algorithms can be coupled to overcome their inherent weaknesses by integrating methods from Constraint Programming and Operations Research. Numerical results show the superiority of the hybrid algorithm in comparison to CP based tree search and column generation alone.

Reviews

Required fields are marked *. Your email address will not be published.