HOME    »    PROGRAMS/ACTIVITIES    »    Annual Thematic Program
Talk Abstracts
Travel and Transportation
November 11-15, 2002

2002-2003 Program: Optimization

Michael O. Ball (Robert H. Smith School of Business and Institute for Systems Research, University of Maryland College Park, MD 20742)  mball@rhsmith.umd.edu  http://www.rhsmith.umd.edu/dit/Faculty/ball.htm

Resource Rationing and Exchange Methods in Air Traffic Management    Slides:    html    pdf

The Federal Aviation Administration (FAA), and the airline community within the US, have recently adopted a new paradigm for air traffic flow management called Collaborative Decision Making (CDM). In this seminar we present a comprehensive analysis of the CDM resource allocation procedures. The CDM procedures consist of three components: a resource (arrival slot) allocation step, an intra-airline resource optimization step and an inter-airline exchange step. We model the first step as a fair resource allocation problem. We define a set of fair allocation axioms and then derive those allocation rules that satisfy these axioms. We investigate the problem of determining an actual allocation as close as possible to an .ideal. allocation produced by an allocation rule. We show that this problem is related to certain just-in-time scheduling problems. Based on this analysis, we show how certain inequities in the treatment of long-haul vs. short-haul air carriers can be substantially mitigated through the use of the new optimization procedures.

We also analyze the resource exchange process known as compression (step 3). We should that it can be interpreted as a mediated 1-for-1 exchange process. Using this interpretation we propose an extension to the use of 2-for-2 exchanges. We develop an efficient integer programming model that solves the mediator.s problem. We also show that, while the system-wide performance of the current exchange process (based on 1-for-1 exchanges), can yield results substantially below system optimal, the new procedure (based on 2-for-2 exchanges) can come very close to produced system optimal results.

Cynthia Barnhart ( Civil & Environmental Engineering Department,Co-Director, Operations Research Center, Co-Director, Center for Transportation and Logistics Studies, Massachusetts Institute of Technology)  cynthia_barnhart@mit.edu  http://web.mit.edu/cbarnhar/www/cb.htm

Aircraft Scheduling and Recovery: The Impact on Passengers

In this research, we examine trends in airline passenger delays and explore the effects of various scheduling and recovery strategies on passengers. We present models and algorithms for schedule recovery that optimize flight departure postponement and cancellation decisions, considering aircraft and crew costs, feasibility AND passenger delays. Further, we evaluate the impact on passengers of different scheduling strategies. For example, de-banking strategies smooth out the arrival and departure of flights into and out of hubs to achieve less peaking, and a more uniform distribution of arrivals/ departures. We assess the impacts of "de-banking" hubs by quantifying changes in aircraft utilization and passenger travel time under the new strategy.

Guy Desaulniers (Mathematics and Industrial Engineering, Ecole Polytechnique and GERAD)  Guy.Desaulniers@gerad.ca

Bus and Driver Scheduling in Urban Mass Transit Systems    Slides:    html    pdf    ppt

Bus and driver scheduling plays a central role in the operations planning process of mass transit systems. For more than one decade, optimization-based software packages have been used by several public transport companies to solve these problems. Given the size of these problems in practice, most of these softwares rely on heuristic strategies. In this talk, we will review the latest exact mathematical programming approaches for solving these problems and discuss their applicability to real-world instances. We will also suggest future research avenues.

Brenda L. Dietrich (Mathematical Sciences, T J Watson Research Center)  dietric@us.ibm.com

Continual Optimization: A Travel Industry Example

I will discuss the use of optimization to support real time resource allocation. The talk will cover technology capability and business drivers, and will include at least one example that is under deployment.

Anton J. Kleywegt (School of Industrial and Systems Engineering, Georgia Institute of Technology)  anton@isye.gatech.edu

Optimal Control of a Revenue Management Process

A stochastic optimal control problem for revenue management is presented. In the model, prices are chosen dynamically to sell multiple products to multiple customer classes over time. The products share a number of scarce resources. All parameters, such as the arrival rates of customers, their purchasing probabilities, their cancellation rates, and the cancellation refunds, are allowed to be time dependent. The limiting process under fluid scaling is considered. A solution method for the fluid problem as well as some numerical results are presented.

Gilbert Laporte (Centre de recherche sur les transports, Universite de Montreal)  gilbert@crt.umontreal.ca  http://www.crt.umontreal.ca/~gilbert

A Guide to Vehicle Routing Heuristics    Slides

The Vehicle Routing Problem (VRP) holds a central place in distribution management and is an important combinatorial optimization problem. To this day, only relatively small instances can be solved optimally. Hence, most researchers and practitioners in the field use heuristics. I will review the most important heuristics proposed over the past forty years for the VRP. The first generation of heuristics, often called "classical heuristics," are mostly based on simple insertion and exchange rules. In recent years, more powerful heuristics, often called "metaheuristics", have been developed. These perform a much more thorough exploration of the solution space. The best of these is probably tabu search. I will present a descriptive and critical review of these heuristics with an emphasis on four performance criteria: accuracy, speed, simplicity and flexibility. Comparative computational results will be presented.

Julian E. Pachon (Caleb Technologies Corp.)  julian.pachon@calebtech.com

Effective Pilot Manpower Planning for Major US Airlines    Slides:    html    pdf    ppt

Effective manpower planning is a key element for success in the highly competitive airline industry. Pilot staffing and training costs represent one of the largest expenses for an airline. Due to the dynamic nature of the business, airlines are constantly evaluating which markets to serve, the number and utilization of fleets and the number of aircraft to operate. Hence, adequate decisions for the number of pilots required to operate the flight schedule, the timing of when to hire or furlough pilots and the locations where the pilots will be based are critical. We will describe the pilot transition and training problem, present a 2-phase optimization model to solve this problem and discuss the impact at a major United States airline.

Bruce W. Patty (Exostrategy Partners LLC)  bpatty@exostrategy.com   http://www.exostrategy.com

The Use of Optimization to Improve Freight Railroad Service Reliability    Slides:    html    pdf    ppt

A major impediment to railroads being able to garner a larger share of the freight transportation market has been their poor service reliability. The inability to deliver a shipment to a customer on-time can be caused by several events such as lack of adequate locomotive power, oversubscription of scheduled trains, and external factors like weather, as well as by poor planning. The ways in which optimization tools can be used to improve service reliability will be discussed in this session. Examples of current and proposed tools will be provided.

Georgia Perakis (School of Management, MIT)  georgiap@mit.edu

Fluid Dynamics Models and their Applications in Transportation and Pricing

Fluid dynamics models provide a powerful deterministic technique to approximate stochasticity in a variety of application areas. In this talk, we present two classes of fluid models, investigate their relationship as well as some of their applications. This will allow us to provide analytical models of travel times as they arise in dynamically evolving environments, such as transportation networks as well as supply chains. In particular, using the laws of hydrodynamic theory, we first propose and examine a general second order fluid model. We consider a first-order approximation of this model and show how it is helpful in analyzing the dynamic traffic equilibrium problem. Furthermore, we present an alternate class of fluid models. By interpreting travel times as price/inventory-sojourn-time relationships, we are also able to connect this approach with a tractable fluid model in the context of dynamic pricing and inventory management. Finally, we investigate the relationship between these two classes of fluid models we discuss.

David M. Ryan (Department of Engineering Science, University of Auckland)  d.ryan@auckland.ac.nz

Bicriteria Robustness versus Cost Optimisation in the Generation of Aircrew Pairings    Slides:   html    pdf    ppt

Besides constructing aircrew Tours of Duty or Pairings with minimal cost, airlines also wish to construct pairings which are robust in that flight schedule disruptions are less likely to propagate delays into the future. In general a minimal cost solution is likely to lack robustness and conversely a solution with maximum robustness (however this is to be measured) is likely to be more expensive. A measure of robustness for each pairing will be developed and the concept of a robustness objective will be discussed. The two objectives of cost and robustness will be treated in a bicriteria optimisation to generate "efficient" pairings which do not allow a simultaneous improvement in cost and robustness. We show that treating the cost objective as a constraint while maximizing robustness leads to very difficult integer programming problems. This situation can be overcome by treating the cost objective as an elastic constraint and penalizing violations of the constraint in the robustness objective.

Martin W.P. Savelsbergh (The Logistics Institute, School of Industrial and Systems Engineering, Georgia Institute of Technology)  mwps@isye.gatech.edu  http://www.isye.gatech.edu/~mwps

Decision Support for Consumer Direct Grocery Initiatives    Slides:    pdf

Many companies with consumer direct service models, especially grocery delivery services, have found that home delivery poses an enormous logistical challenge due to the unpredictability of demand coupled with strict delivery windows and low profit margin products. These systems have proven difficult to manage effectively and could benefit from new technology, particularly to manage the interaction between order capture and promise and order delivery. In this talk, we define routing and scheduling problems that capture important features of this emerging business model and propose algorithms, based on insertion heuristics, for their solution. The emphasis is on profit maximization. The vendor has to decide which requests to accept and in which time slot to guarantee delivery, for those that are accepted. Computational experiments demonstrate the importance of an integrated approach to order capture and promise and order delivery and the quality and value of the proposed algorithms.

Barry C. Smith (Research Group, Sabre, Inc.)  Barry.Smith@sabre.com

Optimization in Airline Planning and Marketing    Slides:    html    pdf    ppt

Airline profitability is driven by the quality of planning and marketing decisions. Due to its scale and complexity, the planning/marketing process has been decomposed into tractable components. The application of optimization to these components has lead to several successful business processes such as yield management and fleet assignment. Significant opportunities for improvement remain through integration of currently separate models, more realistic modeling of the business environment and expansion of modeling scope. In this talk we will address: 1) the planning and marketing landscape; 2) examples of current state of the art in the application of optimization; 3) future opportunities and challenges.

Pravin Varaiya (Department of Electrical Engineering and Computer Science, University of California, Berkeley)  varaiya@eecs.berkeley.edu  http://paleale.eecs.berkeley.edu/~varaiya/

Constructing Transportation System "Intelligence" from Loop Detector Data    Slides:    pdf

The integration of Information Technology at all levels of the transportation system can construct the "intelligence" in Intelligent Transportation Systems (ITS) required to exploit the numerous opportunities in the operations, planning and investment procedures that constitute today's transportation systems.

The talk gives a glimpse into the opportunities for enhancing the productivity of freeway systems. The discussion is based on three years of experience with the Performance Measurement System or PeMS, a database system that collects and stores large amounts of loop detector data from California freeways. PeMS applications convert the data into useful information. We illustrate how this information can improve system management, challenge current understanding of freeway traffic behavior, and assist travelers. All the examples are from Los Angeles freeways.

Material from Talks

Travel and Transportation

2002-2003 Program: Optimization