Application of a hybrid genetic algorithm to airline crew scheduling
Computers & Operations ResearchPublished 1 June 1996
David Levine
Citations119
SJR quartileQ1
SJR score1.60
SNIP2.02
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The hybrid algorithm consists of a steady-state genetic algorithm and a local search heuristic and it found the optimal solution for half the problems, and good solutions for 9 others.
Abstract
This paper discusses the development and application of a hybrid genetic algorithm to airline crew scheduling problems. The hybrid algorithm consists of a steady-state genetic algorithm and a local search heuristic. The hybrid algorithm was tested on a set of 40 real-world problems. It found the optimal solution for half the problems, and good solutions for 9 others. The results were compared to those obtained with branch-and-cut and branch-and-bound algorithms. The branch-and-cut algorithm was significantly more successful than the hybrid algorithm, and the branch-and-bound algorithm slightly better.
Keywords
Computer ScienceDecision SciencesEngineering
Choice Reviews OnlineGenetic algorithms in search, optimization, and machine learning
49,278 Citations1989
This book brings together the computer techniques, mathematical tools, and research results that will enable both students and practitioners to apply genetic algorithms to problems in many fields.
The MIT Press eBooksAdaptation in Natural and Artificial Systems
35,568 Citations1992John H. Holland
Initially applying his concepts to simply defined artificial systems with limited numbers of parameters, Holland goes on to explore their use in the study of a wide range of complex, naturally occuring processes, concentrating on systems having multiple factors that interact in nonlinear ways.
Handbook of Genetic Algorithms
7,308 Citations1991Lawrence Davis
Journal of the Operational Research SocietyInteger and Combinatorial Optimization
5,548 Citations1990H. P. Williams, George L. Nemhauser +1 more
Foundations of genetic algorithmsA Comparative Analysis of Selection Schemes Used in Genetic Algorithms
2,400 Citations1991David E. Goldberg, Kalyanmoy Deb
A number of selection schemes commonly used in modern genetic algorithms are compared on the basis of solutions to deterministic difference or differential equations, verified through computer simulations to provide convenient approximate or exact solutions and useful convergence time and growth ratio estimates.
Management ScienceSolving Airline Crew Scheduling Problems by Branch-and-Cut
540 Citations1993Karla Hoffman, Manfred Padberg
Management ScienceOptimal Solution of Set Covering/Partitioning Problems Using Dual Heuristics
254 Citations1990Marshall L. Fisher, Pradeep K. Kedia
An algorithm for a mixed set covering/partitioning model that includes as special cases the well-known set covering problem and set partitioning problem is presented.
Foundations of genetic algorithmsGenetic Algorithms Are NOT Function Optimizers
235 Citations1993Kenneth De Jong
It is argued that a proper understanding of GAs in this broader adaptive systems context is a necessary prerequisite for understanding their potential application to any problem domain and insights are used to better understand the strengths and limitations ofGAs as function optimizers.
Transportation ScienceThe Airline Crew Scheduling Problem: A Survey
175 Citations1969J. P. Arabeyre, Jacques Fearnley +2 more
NetworksExact solution of crew scheduling problems using the set partitioning model: Recent successful applications
128 Citations1981Roy E. Marsten, Fred Shepardson
This paper focuses on recent developments that have made this model more attractive and have resulted in several successful implementations, as well as new solution techniques employing Lagrangian relaxation and subgradient optimization.
MetaheuristicsA Parallel Genetic Algorithm for the Set Partitioning Problem
126 Citations1996David Levine
This dissertation developed a distributed steady-state genetic algorithm in conjunction with a specialized local search heuristic for solving the set partitioning problem and found that performance improved as additional subpopulations were added to the computation.
IBM Systems JournalA global approach to crew-pairing optimization
111 Citations1992Ranga Anbil, R. Tanga +1 more
The methodology developed during a joint study by IBM and American Airlines Decision Technologies to use the IBM Optimization Subroutine Library in conjunction with TRIP to improve on crew-pairing solutions by taking a global approach has been a reduction of 5 to 11 percent in excess crew cost.
Management ScienceApplication of Combinatorial Programming to a Class of All-Zero-One Integer Programming Problems
97 Citations1968J.F. Pierce
SIAM Journal on OptimizationParallel Branch-and-Bound Algorithms for General Mixed Integer Programming on the CM-5
81 Citations1994Jonathan Eckstein
This “proof of concept” paper describes parallel solution of general mixed integer programs by a branch-and-bound algorithm on the CM-5 multiprocessing system, achieving near-linear speedups using 64–128 processors on a variety of difficult problems derived from real applications.