Airline Crew Scheduling with Regularity

Kiabjan, Diego; Johnson, Ellis L.; Nemhauser, George L.; Gelman, Eric; Ramaswamy, Srini
November 2001
Transportation Science;Nov2001, Vol. 35 Issue 4, p359
Academic Journal
The airline crew scheduling problem is the problem of assigning crew itineraries to flights. The problem is hard due to a large number of itineraries and the complicated cost function of an itinerary. The classic approach, which uses a set partitioning formulation, only captures the objective function of minimizing cost. We add a second goal of maximizing the repetition or regularity of itineraries over a weekly horizon and we develop models that capture regularity. We present a new algorithm that solves the crew scheduling problem over a weekly horizon. Solutions are reported that improve on existing solutions used by an airline.


Related Articles

  • A Technique for the Solution of Massive Set Covering Problems, with Application to Airline Crew Scheduling. Rubin, Jerrold // Transportation Science;Feb73, Vol. 7 Issue 1, p34 

    Recent set covering algorithms have been able to solve problems for which the constraint matrix has as many as 104 columns. Unfortunately, in certain applications, the number of columns is combinatonately dependent on the number of rows, and can reach many orders of magnitude greater, for...

  • Benders Decomposition for Simultaneous Aircraft Routing and Crew Scheduling. Cordeau, Jean-François; Stojković, Goran; Soumis, François; Desrosiers, Jacques // Transportation Science;Nov2001, Vol. 35 Issue 4, p375 

    Given a set of flight legs to be flown by a single type of aircraft, the simultaneous aircraft routing and crew scheduling problem consists of determining a minimum-cost set of aircraft routes and crew pairings such that each flight leg is covered by one aircraft and one crew, and side...

  • The Operational Airline Crew Scheduling Problem Stojkovi&caacute;, Mirela; Soumis, Fran�ois; Desrosiers, Jacques // Transportation Science;Aug98, Vol. 32 Issue 3, p232 

    This paper describes the operational airline crew scheduling problem and represents a first published attempt to solve it. The problem consists of modifying, as necessary, personalized planned monthly assignments of airline crew members during day-to-day operations. It requires covering, at...

  • A Graph Partitioning Approach to Airline Crew Scheduling. Ball, Michael; Roberts, Anito // Transportation Science;May85, Vol. 19 Issue 2, p107 

    In this paper, we present a computerized procedure for scheduling airline crews. The procedure performs set partitioning on a graph by decomposing the problem into a series of subproblems which are solved as matching problems. Computational tests of the algorithm reveal consistent performance in...

  • Airline crew scheduling: A new formulation and decomposition algorithm. Vance, Pamela H.; Barnhart, Cynthia; Johnson, Ellis L.; Nemhauser, George L. // Operations Research;Mar/Apr97, Vol. 45 Issue 2, p188 

    Airline crew scheduling is concerned with finding a minimum cost assignment of flight crews to a given flight schedule while satisfying restrictions dictated by collective bargaining agreements and the Federal Aviation Administration. Traditionally, the problem has been modeled as a set...

  • IMPROVING CREW SCHEDULING BY INCORPORATING KEY MAINTENANCE ROUTING DECISIONS. Cohn, Amy Mainville; Barnhart, Cynthia // Operations Research;May/Jun2003, Vol. 51 Issue 3, p387 

    Crew costs are the second-largest operating expense faced by the airline industry, after fuel. Thus, even a small improvement in the quality of a crew schedule can have significant financial impact. Decisions made earlier in the airline planning process, however, can reduce the number of options...

  • Airline Crew Recovery. Lettovský, Ladislav; Johnson, Ellis L.; Nemhauser, George L. // Transportation Science;Nov2000, Vol. 34 Issue 4, p337 

    An airline schedule rarely operates as planned. It is often disrupted by maintenance problems or severe weather conditions. In a typical day, several flights may be delayed or canceled, and aircraft and crews may miss the rest of their assigned flights. Airline coordinators have to find a...

  • Solving a multi-objective master planning problem with substitution and a recycling process for a capacitated multi-commodity supply chain network. Chern, Ching-Chin; Lei, Seak-Tou; Huang, Kwei-Long // Journal of Intelligent Manufacturing;Feb2014, Vol. 25 Issue 1, p1 

    This study focuses on solving the multi-objective master planning problem for supply chains by considering product structures with multiple final products using substitutions, common components, and recycled components. This study considers five objectives in the planning process: (1) minimizing...

  • A Generalized Uniform Processor System. Ishii, Hiroaki; Martel, Charles; Masuda, Teruo; Nishida, Toshio // Operations Research;Mar/Apr85, Vol. 33 Issue 2, p346 

    This paper considers a scheduling problem whose objective is to determine both the optimal speeds of processors and an optimal schedule in a pre-emptive multiprocessor environment. The jobs are independent and each processor can be assigned any speed; however, the cost associated with each...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics