A two-phase genetic algorithm for large-scale bidline-generation problems at Delta Air Lines

We developed a two-phase algorithm for solving Delta Air Lines' bidline-gen eration problem: assigning trips (tasks) to monthly schedules for crew memb ers (called bidlines.) The system must produce bidlines that conform to all rules, and it should maximize average total value and the quality of the b idlines as measured by their purity. The first phase of the algorithm (the purity phase) constructs as many high-quality lines as possible, and the se cond (the GA phase) completes the assignments by constructing high-total-va lue valid lines from the remaining open trips. Delta obtains significant sa vings in staffing by using this algorithm. The bidlines produced are of com parable quality to those built with the semiautomatic process that Delta Ai r Lines used before.