Solving the Capacitated Arc Routing Problem with Time Windows using Column Generation (2009)
Johnson, Ellis L., Wøhlk, Sanne
In this paper we consider the Capacitated Arc Routing Problem with Time windows. We suggest two algorithms for solving the problem to optimality and a heuristic for obtaining high quality solutions....
Julián Aráoz, Lisa Evans, Ralph E. Gomory, Ellis L. Johnson
Abstract. Any integer program may be relaxed to a group problem. We define the master cyclic group problem and several master knapsack problems, show the relationship between the problems, and give...
14 Airline Crew Scheduling 14.1 Introduction 14.1.1 Crew Scheduling (2008)
Cynthia Barnhart, Amy M. Cohn, Ellis L. Johnson, Diego Klabjan, George L. Nemhauser, Pamela H. Vance
Operational Airline Reserve Crew Planning (2008)
Milind G. Sohoni, Ellis L. Johnson, T. Glenn Bailey
Airlines are continually faced with the challenge of efficient utilization of their cockpit crew resources. In addition to regular flying crews, some airlines have to maintain significant reserve...
Airport Terminal Capacity Planning using Delay Time Approximations and Multistage Stochastic (2008)
Programming Senay Solak, Senay Solak, Ellis L. Johnson
An important part of the airport terminal design process is the determination of the optimal design capacities for di#erent areas of the terminal under the uncertainty of future demand levels and...
A Multicommodity Flow Based Multistage Stochastic (2008)
Programming Approach To, Senay Solak, Ellis L. Johnson
An important part of the airport terminal design process is the determination of the optimal design capacity levels for different areas of the terminal under the uncertainty of future demand levels...
Approved by: CUTTING PLANES FOR LARGE MIXED INTEGER PROGRAMMING MODELS (2006)
G. Goycoolea, William J. Cook, George L. Nemhauser, Ellis L. Johnson, Robin Thomas, Zonghao Gu
A Stochastic Model of Airline Operations (2002)
Jay M. Rosenberger, Andrew J. Schaefer, David Goldsman, Ellis L. Johnson, Anton J. Kleywegt, George L. Nemhauser
Decision makers in air transportation face many uncertainties. In spite of this, airline planning models do not explicitly consider uncertainty in operations. As a result, there is often a notable...
Airline Crew Scheduling under Uncertainty (2001)
Andrew J. Schaefer, Ellis L. Johnson, Anton J. Kleywegt, George L. Nemhauser
Airline crew scheduling algorithms widely used in practice assume no disruptions. Since disruptions often occur, the actual cost of the resulting crew schedules is often significantly greater. We...
Progress in linear programming-based algorithms for integer programming: An exposition (2000)
Ellis L. Johnson, George L. Nemhauser, W. P. Savelsbergh
This paper is about modeling and solving mixed integer programming (MIP) problems. In the last decade, the use of mixed integer programming models has increased dramatically. Fifteen years ago,...
SIMAIR: A stochastic model of airline operations (2000)
Jay M. Rosenberger, Andrew J. Schaefer, David Goldsman, Ellis L. Johnson, Anton J. Kleywegt, George L. Nemhauser
Airline transportation systems are inherently random. However, airline planning models do not explicitly consider stochasticity in operations. Because of this, there is often a notable discrepancy...
Airline Yield Management - Optimal Bid Prices for Single-Hub Problems without Cancellations (1999)
Dirk P. Günther, Ellis L. Johnson
In recent years, the most successful approaches to solving the airline yield management (YM) problem have been based on bid pricing. Bid price control assigns a threshold price to each flight leg....
Branch-and-price: Column generation for solving huge integer programs (1998)
Cynthia Barnhart, Ellis L. Johnson, George L. Nemhauser, Pamela H. Vance
We discuss formulations of integer programs with a huge number of variables and their solution by column generation methods, i.e., implicit pricing of nonbasic variables to generate new columns or to...
A Markov Decision Problem Based Approach to the Airline YM Problem (1998)
Dirk Günther, Ellis L. Johnson
The task of allocating capacity to the different fare classes so that an airline's revenue is maximized is known as the Yield Management (YM) problem. In this research we develop a new approach...
Branch-and-price: Column generation for solving huge integer programs (1998)
Cynthia Barnhart, Ellis L. Johnson, George L. Nemhauser, Pamela H. Vance
We discuss formulations of integer programs with a huge number of variables and their solution by column generation methods, i.e., implicit pricing of nonbasic variables to generate new columns or to...
A Heuristic Branch-and-Price Approach for the Airline Crew Pairing Problem (1997)
Pamela H. Vance, Alper Atamturk, Cynthia Barnhart, Eric Gelman, Ellis L. Johnson, Alamuru Krishna, ...
We describe a methodology for finding near-optimal solutions to airline crew pairing problems. We use a dynamic column generation scheme to identify crew work schedules combined with a customized...
Airline Crew Scheduling: A New Formulation and Decomposition Algorithm (1995)
Pamela H. Vance, Cynthia Barnhart, Ellis L. Johnson, George L. Nemhauser
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...
Solving for an optimal airline yield management policy via statistical learning
Dirk Günther, Ellis L. Johnson
The yield management (YM) problem considers the task of maximizing a company's revenue. For the competitive airline industry, profit margins depend on a good YM policy. Research on airline YM is...
Short-term booking of air cargo space
Chew, Ek-Peng, Huang, Huei-Chuen, Johnson, Ellis L., Nemhauser, George L., Sokol, Joel S., Leong, Chun-How
Solving the Capacitated Arc Routing Problem with Time Windows using Column Generation
Johnson, Ellis L., Wøhlk, Sanne
In this paper we consider the Capacitated Arc Routing Problem with Time windows. We suggest two algorithms for solving the problem to optimality and a heuristic for obtaining high quality solutions....
Airport terminal capacity planning
Solak, Senay, Clarke, John-Paul B., Johnson, Ellis L.
The airport terminal capacity planning problem deals with determining the optimal design and expansion capacities for different areas of the terminal in the presence of uncertainty with regards to...