2002-2003 Program: Optimization
Talk
Abstracts:
November
11-15, 2002
Material
from Talks
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
