Our research focuses on three dimensions: modeling (the translation of physical problems into mathematics), algorithms (covering both theoretical and experimental research), and implementation. Some papers are listed under multiple headings. Where available, we have provided downloadable versions of papers.
Overviews of selected lines of research (with a historical bibliography) are given in Research Areas.
General introduction:
General purpose methods:
Models and algorithms for specific problem classes:
Of general interest:
What's new?(back)
Below we provide a list of working papers (under review at various journals) and papers that have been recently accepted or which have appeared recently.
Recent working papers (in various stages of review): Upated April 5, 2008
Powell, W. B. and P. Frazier, “Optimal Learning – A tutorial,”
He, M., L. Zhao and W. B. Powell, “Optimal control of dosage decisions in controlled ovarian hyperstimulation,”
Powell, W.B., “Merging AI and OR to Solve High-Dimensional Resource Allocation Problems using Approximate Dynamic Programming”
Frazier, P. and W. B. Powell, “The knowledge gradient stopping rule for ranking and selection,”
D. R. Ronconi and W. B. Powell, “Minimizing Total Tardiness in a Single Machine Scheduling Problem using Approximate Dynamic Programming,”
J. Nascimento and W. B. Powell, “An Optimal Solution to a General Jet Fuel Hedging Problem,”
Marar, A. and W. B. Powell, “Using Static Flow Patterns in Time-Staged Resource Allocation Problems,”
Wu, Tongqiang, W.B. Powell and A. Whisman, “An Integrated Optimizing-Simulator for the Military Airlift Problem,”
J. Enders, W. B. Powell, D. Egan, “A Dynamic Model for the Failure Replacement of Aging High-Voltage Transformers,”
P. Frazier, W. B. Powell, S. Dayanik, “The Knowledge-Gradient Policy for Correlated Rewards,”
Frazier, P., W. B. Powell and S. Dayanik, “A Knowledge Gradient Policy for Sequential Information Collection,”
Nascimento, J. and W. B. Powell, “Dynamic programming models and algorithms for the mutual fund cash balance problem,”
H. P. Simao and W. B. Powell, “Approximate Dynamic Programming for Managing High Value Spare Parts,”
Nascimento, J. and W. B. Powell, “An Optimal Approximate Dynamic Programming Algorithm for the Lagged Asset Acquisition Problem,”
J. Enders, W. B. Powell and D. Egan, “A Two-Stage Stochastic Program for the Allocation of High-Voltage Transformer Spares in the Electric Grid,”
Frazier, P. and W. B. Powell, “Approximate Value Iteration Converges Slowly When Smoothed with a 1/n Stepsize,”
W. B. Powell, B. Bouzaiene-Ayari, J. Berger, A. Boukhtouta, A. George, “The Effect of Robust Decisions on the Cost of Uncertainty in Military Airlift Operations,”
George, A., W.B. Powell and S. Kulkarni, “Value Function Approximation Using Hierarchical Aggregation for Multiattribute Resource Management,”
Papers which have recently appeared::
Simao, H. P., J. Day, A. George, T. Gifford, W. B. Powell, “An Approximate Dynamic Programming Algorithm for Large-Scale Fleet Management: A Case Application,” Transportation Science (to appear) (c) Informs
This is a major application paper, which summarizes several years of development to produce a model based on approximate dynamic programming which closely matches historical performance. The model represents drivers with 15 attributes, capturing domicile, equipment type, days from home, and all the rules (including the 70 hour in eight days rule) governing drivers. The model gets drivers home, on weekends, on a regular basis (again, closely matching historical performance). The value functions produced by the ADP algorithm are shown to accurately estimate the marginal value of drivers by domicile.
S. Dayanik, W. Powell, and K. Yamazaki (2007). “Index policies for discounted bandit problems with availability constraints,” Journal of Applied Probability (to appear).
One of the most famous problems in information collection is the multiarmed bandit problem, where make a choice (out of a discrete set of choices), observe a reward, and use this observation to update estimates of the future value of rewards. This problem can be solved by choosing the option with the highest index (known as the Gittins index). In this paper, we present an index problem for the case where not all the choices are available each time. As a result, it is sometimes important to make an observation just because the observation is available to be made.
Powell, W.B., “Real-time dispatching for truckload motor carriers,” in Logistics Engineering Handbook (G. Don Taylor, ed.), CRC Press, 2007, pp. 15-1 – 15-30. (c) CRC Press.
This paper describes our experience implementing a real-time optimization model at Burlington Motor Carriers. Intended for a broad audience, it describes the basics of the model and some of tbe behind-the-scenes events that were encountered during implementation.
Topaloglu, H. and W.B. Powell, “Incorporating Pricing Decisions into the Stochastic Dynamic Fleet Management Problem,” Transportation Science, Vol. 41, No. 3, pp. 281-301 (2007). (c) Informs
There have been many papers addressing the problem of efficiently managing fleets of vehicles. This paper addresses this problem from the perspective of pricing. Using an approximate dynamic programming to optimize the flows of vehicles, we derive gradient information that allows us to adjust the prices at the same time. The model requires that we have a model of how demand responds to price. The paper shows that we get near-optimal solutions to prices while we simultaneously optimize flows.
Cheung, R. K.-M., N. Shi, W. B. Powell, and H. P. Simao, “An Attribute-Decision Model for Cross-Border Drayage Problem,” Transportation Research E: Logistics and Transportation Review, Volume 44, No. 2, pp. 217-234 (2008). (c) Elsevier
This paper illustrates a modeling and algorithmic strategy for multi-layered resource scheduling, using the context of the cross-border drayage problem.
Topaloglu, H. and W. B. Powell, “Sensitivity Analysis of a Dynamic Fleet Management Model Using Approximate Dynamic Programming” Operations Research, Vol. 55, No. 2, pp. 319-331 (2007). (c) Informs
We present tractable algorithms to assess the sensitivity of a stochastic dynamic fleet management model to fleet size and load availability. In particular, we show how to compute the change in the objective function value in response to an additional vehicle or an additional load introduced into the system. The novel aspect of our approach is that it does not require multiple simulations with different values of the model parameters, and in this respect it differs from trial-and error-based “what-if” analyses. Numerical experiments show that the proposed methods are accurate and computationally attractive.
Papadaki, K. and W. B. Powell, “Monotonicity in Multidimensional Markov Decision Processes for Batch Service Problems,” Operations Research Letters, Vol. 35, pp. 267-272 (2007).
Structural properties of stochastic dynamic programs are essential to understanding the nature of the solutions and in
deriving appropriate approximation techniques.We concentrate on a class of multidimensional Markov decision processes and
derive sufficient conditions for the monotonicity of the value functions. We illustrate our result in the case of the multiproduct
batch dispatch (MBD) problem.
Surveys/reviews/book chapters (back)
This section contains a series of tutorial articles and book chapters. Often, these are an easy place to start. Journal articles can be quite technical, and they also represent our first attempt to write up a piece of research. These book chapters synthesize a lot of our research, and they tend to be a little better written (practice makes perfect!).
Powell, W.B., “Real-time dispatching for truckload motor carriers,” in Logistics Engineering Handbook (G. Don Taylor, ed.), CRC Press, 2007, pp. 15-1 – 15-30. (c) CRC Press.
This paper describes our experience implementing a real-time optimization model at Burlington Motor Carriers. Intended for a broad audience, it describes the basics of the model and some of tbe behind-the-scenes events that were encountered during implementation.
Powell, W.B., A. George, B. Bouzaiene-Ayari and H. Simao, “Approximate Dynamic Programming for High Dimensional Resource Allocation Problems,” Proceedings of the IJCNN, Montreal, August 2005.
This is an easy introduction to the use of approximate dynamic programming for resource allocation problems. It shows how math programming and machine learning can be combined to solve dynamic programs with many thousands of dimensions, using techniques that are easily implemented on a laptop.
Powell, W.B., “Approximate Dynamic Programming for High-Dimensional Problems ,” Proceedings of the Winter Simulation Conference, December, 2007.
This short tutorial article, prepared for the Winter Simulation Conference, presents notation and fundamental algorithmic ideas to solve the types of high-dimensional applications which arise in a broad range of resource allocation problems.
Powell, W.B., “The Optimizing-Simulator: Merging Simulation and Optimization using Approximate Dynamic Programming,” Proceedings of the Winter Simulation Conference, December, 2005.
Approximate dynamic programming involves iteratively simulating a system. As a result, it often has the appearance of an "optimizing simulator." This short article, presented at the Winter Simulation Conference, is an easy introduction to this simple idea.
Powell, W.B. and B. van Roy, “Approximate Dynamic Programming for High Dimensional Resource Allocation Problems," (in Learning and Approximate Dynamic Programming: Scaling up to the Real World, J. Si, A. Barto, W.B. Powell and D. Wunsch, eds.), John-Wiley and Sons, New York, 2004.
We have done a lot of work that involves solving multistage linear programs for resource allocation using dynamic programming. This relatively short chapter is a quick introduction to this work, and brings together the themes of approximate dynamic programming and linear programming.
Powell, W.B., B. Bouzaiene-Ayari and H.P. Simao, “Dynamic Models for Freight Transportation,” Handbooks in Operations Research and Management Science: Transportation (G. Laporte and C. Barnhart, eds.), Elsevier, Amsterdam, 2007.
This chapter focuses on modeling the organization and flow of decisions and information in transportation. The chapter describes how to model sequential information and decision processes, and discusses four classes of information and the algorithmic strategies that are associated with each class. Approximate dynamic programming methods are introduced and illustrated for several classes of problems that arise in transportation and logistics.
Powell, W. B. and H. Topaloglu, “Stochastic Programming in Transportation and Logistics,” Handbooks in Operations Research and Management Science: Stochastic Programming (A. Shapiro and A. Ruszczynski, eds.), Elsevier, Amsterdam, pp. 555-635, 2003..
We introduce adaptive learning algorithms in the context (and notation) of stochastic programming, using fleet management (and particularly freight car distribution) as the illustrative application. The chapter is a good review of different approximation strategies, and uses the freight car distribution problem to illustrate how some problems exhibit separability and how to solve problems that are nonseparable.
Powell, W.B., “Dynamic Models of Transportation Operations,” Handbooks in Operations Research and Management Science: Supply Chain Management, (S. Graves and T. A. G. de Tok, eds.), Elsevier, Amsterdam, pp. 677-756, 2003.
This chapter provides an overview of problems in freight transportation, and a modeling and algorithmic strategy for solving these problems. For students looking for a single reference that covers the DRTP modeling framework and our approximate dynamic programming strategies, this is a good overview.
Powell, W.B. and H. Topaloglu, “Fleet Management,” in Applications of Stochastic Programming, (S. Wallace and W. Ziemba, eds.), Math Programming Society - SIAM Series in Optimization, Philadelphia,pp. 185-216, 2005.
Stochastic programming has been steadily making its way into a variety of application areas. This chapter demonstrates the use of a class of stochastic programming methods for fleet management applications, using the freight car distribution problem as a problem context.
Powell, W. B., P. Jaillet and A. Odoni, "Stochastic and Dynamic Networks and Routing," Handbook in Operations Research and Management Science, Vol. 4, Networks, (M.O. Ball, T.L. Magnanti, C.L. Monma and G.L. Nemhauser, eds.), pp. 141-295, 1995.
The hard part about writing a chapter for a handbook on dynamic models is that the field is very new and evolving quickly. However, this chapter contains a fairly extensive literature review and should serve as a useful reference for research prior to 1993-94.
- (Click here to view paper)
"Optimization Models and Algorithms: An Emerging Technology for the Motor Carrier Industry," Special Issue of IEEE on Intelligent Vehicle /Highway Systems, pp. 68 - 80, 1990. (Winner, Best Paper on Land Transportation from IEEE Section on Vehicular Technologies, 1992.)
This is a survey of a variety of optimization strategies for routing and scheduling of vehicles. The best part of this paper was that I received a marriage proposal from an appreciative reader.
"Toward a Unified Framework for Real-Time Logistics Control," Military Journal of Operations Research, Vol. I, No. 4, Winter, 1996, pp. 69-79.
Books (back)
J. Si, A. Barto, W.B. Powell and D. Wunsch (eds.), Learning and Approximate Dynamic Programming: Scaling up to the Real World, John-Wiley and Sons, New York, 2004.
This edited volume is based on the NSF workshop held in Playacar, Mexico in 2002. It represents the diversity of communities that are using, and contributing to, the general area of approximate dynamic programming.
W.B. Powell, Approximate Dynamic Programming, John Wiley and Sons, 2007 (available in October, 2007).
This is the first book to bridge the growing field of approximate dynamic programming with operations research. Dynamic programming has often been dismissed because it suffers from "the curse of dimensionality." In fact, there are three curses of dimensionality when you deal with the high-dimensional problems that typically arise in operations research (the state space, the outcome space and the action space). This book shows how we can estimate value function approximations around the post-decision state variable to produce techniques that allow us to solve dynamic programs which exhibit states with millions of dimensions (approximately).
The book is aimed at an advanced undergraduate/masters level audience with a good course in probability and statistics, and linear programming (for some applications). For the advanced Ph.D., there is an introduction to fundamental proof techniques in "why does it work" sections. The book emphasizes solving real-world problems, and as a result there is considerable emphasis on proper modeling. The book includes dozens of algorithms written at a level that can be directly translated to code. The material in this book is motivated by numerous industrial applications undertaken at CASTLE Lab, as well as a number of undergraduate senior theses.
Optimal learning (back)
Optimal learning represents the problem of making observations (or measurements) in an efficient way to achieve some objective. This is our newest area of research, with a number of papers on the way.S. Dayanik, W. Powell, and K. Yamazaki (2007). “Index policies for discounted bandit problems with availability constraints,” Journal of Applied Probability (to appear).
One of the most famous problems in information collection is the multiarmed bandit problem, where make a choice (out of a discrete set of choices), observe a reward, and use this observation to update estimates of the future value of rewards. This problem can be solved by choosing the option with the highest index (known as the Gittins index). In this paper, we present an index problem for the case where not all the choices are available each time. As a result, it is sometimes important to make an observation just because the observation is available to be made.
Approximate dynamic programming (back)
Much of our work falls in the intersection of stochastic programming and dynamic programming. The dynamic programming literature primarily deals with problems with low dimensional state and action spaces, which allow the use of discrete dynamic programming techniques. The stochastic programming literature, on the other hands, deals with the same sorts of higher dimensional vectors that are found in deterministic math programming. However, the stochastic programming community generally does not exploit state variables, and does not use the concepts and vocabulary of dynamic programming.
Our contributions to the area of approximate dynamic programming can be grouped into three broad categories: general contributions, fleet management problems, which we have broadened into general resource allocation, discrete routing and scheduling problems, and batch service problems.
W.B. Powell, Approximate Dynamic Programming, John Wiley and Sons, 2007 (available in November, 2007).
This is the first book to bridge the growing field of approximate dynamic programming with operations research. Dynamic programming has often been dismissed because it suffers from "the curse of dimensionality." In fact, there are three curses of dimensionality when you deal with the high-dimensional problems that typically arise in operations research (the state space, the outcome space and the action space). This book shows how we can estimate value function approximations around the post-decision state variable to produce techniques that allow us to solve dynamic programs which exhibit states with millions of dimensions (approximately).
The book is aimed at an advanced undergraduate/masters level audience with a good course in probability and statistics, and linear programming (for some applications). For the advanced Ph.D., there is an introduction to fundamental proof techniques in "why does it work" sections. The book emphasizes solving real-world problems, and as a result there is considerable emphasis on proper modeling. The book includes dozens of algorithms written at a level that can be directly translated to code. The material in this book is motivated by numerous industrial applications undertaken at CASTLE Lab, as well as a number of undergraduate senior theses.
George, A.,W. B. Powell and S. Kulkarni, "Value Function Approximation using Hierarchical Aggregation for Multiattribute Resource Management"
In this paper we address the problem of estimating the value of a multiattribute asset. In approximate dynamic programming algorithms, we cannot sample the value of every type of asset (the attribute space is too large). We can estimate the value at an aggregate level, but then we face the challenge of finding the right level of aggregation. Some parts of the attribute space are sampled more than others. In this paper, we introduce the idea of estimating the value of a resource with a vector of attributes at different levels of aggregation at the same time. We then use a weighted combination of these estimates. Formulas for optimal weights are derived and compared to simple inverse variance weights. The inverse variance formula (which ignores correlations in the weights) is shown to work extremely well, and we explain why.
George, A. and W.B. Powell, “Adaptive Stepsizes for Recursive Estimation with Applications in Approximate Dynamic Programming,” Machine Learning, Vol. 65, No. 1, pp. 167-198, (2006). (c) Springer
One of the first challenges anyone will face when using approximate dynamic programming is the choice of stepsizes. Use the wrong stepsize formula, and a perfectly good algorithm will appear not to work. Deterministic stepsize formulas can be frustrating since they have parameters that have to be tuned (difficult if you are estimating thousands of values at the same time). This paper reviews a number of popular stepsize formulas, provides a classic result for optimal stepsizes with stationary data, and derives a new optimal stepsize formula for nonstationary data. This result assumes we know the noise and bias (knowing the bias is equivalent to knowing the answer). A formula is provided when these quantities are unknown. Our result is compared to other deterministic formulas as well as stochastic stepsize rules which are proven to be convergent. The numerical work suggests that the new optimal stepsize formula (OSA) is very robust. It often is the best, and never works poorly.
Powell, W.B., A. George, B. Bouzaiene-Ayari and H. Simao, “Approximate Dynamic Programming for High Dimensional Resource Allocation Problems,” Proceedings of the IJCNN, Montreal, August 2005.
This is an easy introduction to the use of approximate dynamic programming for resource allocation problems. It shows how math programming and machine learning can be combined to solve dynamic programs with many thousands of dimensions, using techniques that are easily implemented on a laptop.
Powell, W.B., “The Optimizing-Simulator: Merging Simulation and Optimization using Approximate Dynamic Programming,” Proceedings of the Winter Simulation Conference, December, 2005.
Approximate dynamic programming involves iteratively simulating a system. As a result, it often has the appearance of an "optimizing simulator." This short article, presented at the Winter Simulation Conference, is an easy introduction to this simple idea.
Approximate dynamic programming in fleet management:
Simao, H. P., J. Day, A. George, T. Gifford, W. B. Powell, “An Approximate Dynamic Programming Algorithm for Large-Scale Fleet Management: A Case Application,” Transportation Science (to appear) (c) Informs
This is a major application paper, which summarizes several years of development to produce a model based on approximate dynamic programming which closely matches historical performance. The model represents drivers with 15 attributes, capturing domicile, equipment type, days from home, and all the rules (including the 70 hour in eight days rule) governing drivers. The model gets drivers home, on weekends, on a regular basis (again, closely matching historical performance). The value functions produced by the ADP algorithm are shown to accurately estimate the marginal value of drivers by domicile.
Topaloglu, H. and W.B. Powell, “Dynamic Programming Approximations for Stochastic, Time-Staged Integer Multicommodity Flow Problems,” Informs Journal on Computing, Vol. 18, No. 1, pp. 31-42 (2006). (c) Informs.
This paper applies the technique of separable, piecewise linear approximations to multicommodity flow problems. This technique worked very well for single commodity problems, but it was not at all obvious that it would work well for multicommodity problems, since there are more substitution opportunities. The experimental comparisons against multistage nested Benders (which is very slow) and more classical rolling horizon procedures suggests that it works very well indeed. This paper also provides a more rigorous treatment of what is known as the "multiperiod travel time" problem, and provides a formal development of a procedure for accelerating convergence.
Powell, W.B. and T. Carvalho, "Dynamic Control of Logistics Queueing Networks for Large Scale Fleet Management," Transportation Science, Vol. 32, No. 2, pp. 90-109, 1998. (c) Informs.
This paper introduces the use of linear approximations of value functions that are learned adaptively.
Powell, W.B., J. Shapiro and H. P. Simao, "An Adaptive, Dynamic Programming Algorithm for the Heterogeneous Resource Allocation Problem," Transportation Science, Vol. 36, No. 2, pp. 231-249 (2002). (c) Informs.
This paper also used linear approximations, but in the context of the heterogeneous resource allocation problem. In this setting, we assume that the size of the attribute state space of a resource is too large to enumerate. As a result, estimating the value of resource with a particular set of attributes becomes computationally difficult. We resort to hierarchical aggregation schemes.
Godfrey, G. and W.B. Powell, “An Adaptive Dynamic Programming Algorithm for Single-Period Fleet Management Problems I: Single Period Travel Times,” Transportation Science, Vol. 36, No. 1, pp. 21-39 (2002). (c) Informs.
This paper introduces the use of adaptive, piecewise linear approximations using the CAVE algorithm.
Powell, W.B., A. Ruszczynski and H. Topaloglu, “Learning Algorithms for Separable Approximations of Stochastic Optimization Problems,” Mathematics of Operations Research, Vol 29, No. 4, pp. 814-836 (2004). (c) Informs.
We have been doing a lot of work on the adaptive estimation of concave functions. This paper represents a major plateau. It describes a new algorithm dubbed the Separable Projective Approximation Routine (SPAR) and includes 1) a proof that the algorithm converges when we sample all intervals infinitely often, 2) a proof that the algorithm produces an optimal solution when we only sample the optimal solution of our approximation at each iteration, when applied to separable problems, 3) a bound when the algorithm is applied to nonseparable problems such as two-stage stochastic programs with network resource, and 4) computational comparisons against deterministic approximations and variations of Benders decomposition (which is provably optimal). The experiments show that the SPAR algorithm, even when applied to nonseparable approximations, converges much more quickly than Benders decomposition.
Approximate dynamic programming in discrete routing and scheduling:
Spivey, M. and W.B. Powell, “The Dynamic Assignment Problem,” Transportation Science, Vol. 38, No. 4, pp. 399-419 (2004). (c) Informs.
This paper proposes a general model for the dynamic assignment problem, which involves the assignment of resources to tasks over time, in the presence of potentially several streams of information processes. It proposes an adaptive learning model that produces non-myopic behavior, and suggests a way of using hierarchical aggregation to reduce statistical errors in the adaptive estimation of the value of resources in the future. Finally, it reports on a study on the value of advance information. Past studies of this topic have used myopic models where advance information provides a major benefit over no information at all. Our model uses adaptive learning to bring forecast information into decisions made now, providing a more realistic estimate of the value of future information.
Approximate dynamic programming for batch service problems
Papadaki, K. and W.B. Powell, “An Adaptive Dynamic Programming Algorithm for a Stochastic Multiproduct Batch Dispatch Problem,” Naval Research Logistics, Vol. 50, No. 7, pp. 742-769, 2003.
One of the oldest problems in dynamic programming arises in the context of planning inventories. You can use textbook backward dynamic programming if there is only one product type, but real problems have multiple products. In this paper, we consider a multiproduct problem in the context of a batch service problem where different types of customers wait to be served. Arrivals are stochastic and nonstationary. We show that an approximate dynamic programming strategy using linear value functions works quite well and is computationally no harder than a simple myopic heuristics (once the iterative learning is completed).
Papadaki, K. and W.B. Powell, “Exploiting structure in adaptive dynamic programming algorithms for a stochastic batch service problem,” European Journal of Operational Research, Vol. 142, No. 1, pp. 108-127 (2002). (c) Elsevier.
This paper compares an optimal policy for dispatching a truck over a single link (with one product type) against an approximate policy that uses approximations of the future. Why would we approximate a problem that is easy to solve to optimality? Because the optimal policy only works on single link problems with one type of product, while the other is scalable to much harder problems.
Modeling complex problems with incomplete information:
It is common in practice to run an optimization model, critique the answer, and go through a process of "fixing the costs" to get the right behavior. Not only can this process be time consuming and expensive, sometimes it is simply not possible to "fix the costs." Practitioners are accustomed to using surrogate costs to push the model in a particular direction. We found that when domain experts want to obtain a particular behavior, the behaviors they are looking for can be expressed in the form of low-dimensional patterns. The three papers below propose algorithms for different settings which allow a user to guide the behavior of a model through low dimensional patterns which are incorporated into the model through a proximal point term:
Marar, A. and W.B. Powell, “Combining Cost-Based and Rule-Based Knowledge in Complex Resource Allocation Problems,” IIE transactions Vol. 38 (2), pp. 159-172 2006.
Assume that we wish to solve a (static) resource allocation problem. We have a cost model, but it is not perfect. We also have observations of how resources (each described by a vector of attributes) behave in the field. However, the data from history is typically at a more aggregate level. For example: "team drivers like long loads", "high powered locomotives are best pulling merchandise trains" are examples of aggregate behaviors that we would like to replicate in a model, while also trying to minimize costs.
(Click here to download paper)
Marar, A. and W.B. Powell, “Capturing Incomplete Information in Resource Allocation Problems using Numerical Patterns”
Marar, A. and W.B. Powell, “Using Static Flow Patterns in Time-Staged Resource Allocation Problems”
Powell, W.B., T. Wu, H. P. Simao and A. Whisman, “Using Low Dimensional Patterns in Optimizing Simulators: An Illustration for the Military Airlift Problem,” Mathematical and Computer Modeling 29, pp. 657-675 (2004).
Sometimes a knowledgeable user will look at the results of a model and claim "You cannot send C-141's into Saudi Arabia!". Complaints such as these are instances of low-dimensional patterns, and represent an expression of a desirable behavior that is fairly easy to capture. The problem is that these simplistic rules are not enough to build an entire simulation. In this paper, we draw on the results of Marar to guide the behavior of a simulation model for the military airlift problem.
Modeling and problem representation (back)
Shapiro, J, W.B. Powell and D.E. Bernstein, “A Flexible Java Representation for Uncertainty in Online Operations Research Models,” Journal of Computing, Vol. 13, No. 1, pp. 29-55, 2001. (c) Informs.
Sometimes a fresh perspective on an old problem produces some really nice insights. In this paper, Joel Shapiro observed that the classical way of representing random variables in software was neither accurate mathematically nor elegant from a software engineering perspective. The problem is that it is common in simulation packages to sample a random variable before it is ``known.'' In this paper, he introduces an Information object that captures whether a quantity is known or not, and introduces the use of the event listener paradigm to notify a decision function when the information is updated.
Powell, W.B., J. Shapiro and H.P. Simao, “A Representational Paradigm for Dynamic Resource Transformation Problems,” Annals of Operations Research on Modeling (C. Coullard, R. Fourer, and J. H. Owen, eds), Vol. 104, pp. 231-279, 2001.
This paper is the fundamental modeling paradigm for our work. It evolved over a fouryear period starting in 1997. As we have worked on harder and more complex problems, it became clear that we needed to focus attention on notation. This paper formally introduces a problem class that we call Dynamic Resource Transformation Problems. (This can be abbreviated DRTP, but we use DRiP since it is more pronouncable.) click here.
Powell, W.B. "On Languages for Dynamic Resource Scheduling Problems," in Fleet Management and Logistics, (T. G. Crainic and G. Laporte, eds.), Kluwer Academic Publishers, Boston, 1998.
This paper was written for a speciality conference on routing and scheduling in honor of the 25th anniversary of the Centre de recherche sur les transports. We were asked to think about the future, and it caught me at a time when I was struggling with the problem of modeling complex operational problems. The paper reflected my frustration with the standard modeling paradigms that our community was using. This was the foundational work for the creation of the DRiP problem class.
"Toward a Unified Framework for Real-Time Logistics Control," Military Journal of Operations Research, Vol. I, No. 4, Winter, 1996, pp. 69-79.
An early application of the DRiP framework for airlift operations.
General
dynamic resource management (back)
Almost all the work in CASTLE Lab can be described as dynamic resource management. However, most of this work has been presented in the contextual domains of fleet management or driver routing and scheduling. In this section, we are going to list papers that are written using the general framework of the DRiP paradigm which can be viewed as general purpose dynamic resource management problems.
Shapiro, J. and W.B. Powell, “A Metastrategy for Dynamic Resource Management Problems based on Informational Decomposition,” Informs Journal on Computing, Vol. 18, No. 1, pp. 43-60 (2006). (c) Informs.
We do a lot of work on very large scale problems in transportation. These are typically characterized by multiagent decision making, which also means multiagent information structures. This paper provides a fairly general model of the organization of information and decisions, and a method for decomposing and linking these decisions so that the individual agents, operating separately, produce near optimal overall solutions.
Topaloglu, H. and W.B. Powell, “Dynamic Programming Approximations for Stochastic, Time-Staged Integer Multicommodity Flow Problems,” Informs Journal on Computing, Vol. 18, No. 1, pp. 31-42 (2006). (c) Informs.
This paper applies the technique of separable, piecewise linear approximations to multicommodity flow problems. This technique worked very well for single commodity problems, but it was not at all obvious that it would work well for multicommodity problems, since there are more substitution opportunities. The experimental comparisons against multistage nested Benders (which is very slow) and more classical rolling horizon procedures suggests that it works very well indeed. This paper also provides a more rigorous treatment of what is known as the "multiperiod travel time" problem, and provides a formal development of a procedure for accelerating convergence.
Powell, W.B., “Dynamic Models of Transportation Operations,” Handbook in Operations Research and Management Science: Supply Chain Management, (S. Graves and T. A. G. de Tok, eds.), (to appear).
This chapter provides an overview of problems in freight transportation, and a modeling and algorithmic strategy for solving these problems. For students looking for a single reference that covers the DRTP modeling framework and our approximate dynamic programming strategies, this is a good overview.
Powell, W.B., J. Shapiro and H.P. Simao, “A Representational Paradigm for Dynamic Resource Transformation Problems,” Annals of Operations Research on Modeling (C. Coullard, R. Fourer, and J. H. Owen, eds), Vol. 104, pp. 231-279, 2001.
This paper is the fundamental modeling paradigm for our work. It evolved over a two year period starting in 1997. As we have worked on harder and more complex problems, it became clear that we needed to focus attention on notation. This paper formally introduces a problem class that we call Dynamic Resource Transformation Problems. (This can be abbreviated DRTP, but we use DRiP since it is more pronouncable.) For more on this subject click here.
Powell, W.B., J. Shapiro and H. P. Simao, "An Adaptive, Dynamic Programming Algorithm for the Heterogeneous Resource Allocation Problem," Transportation Science, Vol. 36, No. 2, pp. 231-249 (2002). (c) Informs.
This paper provides a general model for a two-layer DRiP with heterogeneous resources and tasks. The technique was applied to a driver scheduling problem involving 5,000 drivers and 30,000 loads.
Godfrey, G. and W.B. Powell, "An Adaptive, Distribution-Free Algorithm for the Newsvendor Problem with Censored Demands, with Application to Inventory and Distribution Problems," Management Science, Vol. 47, No. 8, pp. 1101-1112, (2001). (c) Informs.
This paper proposes a novel approximation procedure for stochastic resource allocation problems. The technique works with a series of stochastic gradients which are then used to maintain a concave estimate of the value function. When applied to problems with known optimal solutions, the method provides results within a fraction of a percent of optimal. One byproduct is a fast algorithm for the newsvendor problem that does not require knowledge of the underlying demand distribution. The technique is also applied to separable distribution problems.
Godfrey, G. and W.B. Powell, “An Adaptive Dynamic Programming Algorithm for Single-Period Fleet Management Problems I: Single Period Travel Times,” Transportation Science, Vol. 36, No. 1, pp. 21-39 (2002). (c) Informs
Godfrey, G. and W.B. Powell, “An Adaptive Dynamic
Programming Algorithm for Single-Period Fleet Management Problems II: Multiperiod
Travel Times,” Transportation Science, Vol. 36, No. 1, pp. 40-54 (2002).
(c) Informs
This paper adapts the CAVE algorithm to stochastic multistage problems. The paper demonstrates both rapid convergence of the algorithm as well as very high quality solutions. We found that the use of nonlinear approximations was complicated by the presence of multiperiod travel times (a problem that does not arise when we use linear approximations).
Stochastic optimization (back)
S. Dayanik, W. Powell, and K. Yamazaki (2007). “Index policies for discounted bandit problems with availability constraints,” Journal of Applied Probability (to appear).
One of the most famous problems in information collection is the multiarmed bandit problem, where make a choice (out of a discrete set of choices), observe a reward, and use this observation to update estimates of the future value of rewards. This problem can be solved by choosing the option with the highest index (known as the Gittins index). In this paper, we present an index problem for the case where not all the choices are available each time. As a result, it is sometimes important to make an observation just because the observation is available to be made.
Papadaki, K. and W. B. Powell, “Monotonicity in Multidimensional Markov Decision Processes for Batch Service Problems,” Operations Research Letters, Vol. 35, pp. 267-272 (2007).
Structural properties of stochastic dynamic programs are essential to understanding the nature of the solutions and in
deriving appropriate approximation techniques.We concentrate on a class of multidimensional Markov decision processes and
derive sufficient conditions for the monotonicity of the value functions. We illustrate our result in the case of the multiproduct
batch dispatch (MBD) problem.
Topaloglu, H. and W.B. Powell, “Dynamic Programming Approximations for Stochastic, Time-Staged Integer Multicommodity Flow Problems,” Informs Journal on Computing, Vol. 18, No. 1, pp. 31-42 (2006). (c) Informs.
This paper applies the technique of separable, piecewise linear approximations to multicommodity flow problems. This technique worked very well for single commodity problems, but it was not at all obvious that it would work well for multicommodity problems, since there are more substitution opportunities. The experimental comparisons against multistage nested Benders (which is very slow) and more classical rolling horizon procedures suggests that it works very well indeed. This paper also provides a more rigorous treatment of what is known as the "multiperiod travel time" problem, and provides a formal development of a procedure for accelerating convergence.
Powell, W.B., A. Ruszczynski and H. Topaloglu, “Learning Algorithms for Separable Approximations of Stochastic Optimization Problems,” Mathematics of Operations Research, Vol 29, No. 4, pp. 814-836 (2004).(c) Informs
We have been doing a lot of work on the adaptive estimation of concave functions. This paper represents a major plateau. It describes a new algorithm dubbed the Separable Projective Approximation Routine (SPAR) and includes 1) a proof that the algorithm converges when we sample all intervals infinitely often, 2) a proof that the algorithm produces an optimal solution when we only sample the optimal solution of our approximation at each iteration, when applied to separable problems, 3) a bound when the algorithm is applied to nonseparable problems such as two-stage stochastic programs with network resource, and 4) computational comparisons against deterministic approximations and variations of Benders decomposition (which is provably optimal). The experiments show that the SPAR algorithm, even when applied to nonseparable approximations, converges much more quickly than Benders decomposition.
Spivey, M. and W.B. Powell, “Some Fixed Point Results for the Dynamic Assignment Problem,” Annals of Operations Research, Vol. 124, (G. Mitra, ed.), Kluwer Academic Publishers, pp. 15-33 (2003).
In the course of conducting research on the use of linear value function approximations for the dynamic assignment problem, we ran across a class of problems where the right linear value function would produce the optimal solution. This paper summarizes this result and provides a proof.
Topaloglu, H. and W.B. Powell, “An Algorithm for Approximating Piecewise Linear Concave Functions from Sample Gradients,” Operations Research Letters, Vol. 31, No. 1, pp. 66-76 (2003).
We often find ourselves needing to approximate the marginal value of an additional resource, where we would like to estimate a piecewise linear concave function. But we have to do this with sample gradient information, which is random. And we still want the function to be concave. This paper proves convergence of an algorithm which maintains concavity by "leveling out" parts of the function that violate concavity.
Chen, Z.-L. and W.B. Powell, "A Convergent Cutting Plane and Partial Sampling Algorithm for Multistage Linear Programs with Recourse," Journal of Optimization Theory and Applications, Vol. 103, No. 3, pp. 497-524 (1999). (c) Plenum Publishing.
This paper provides a proof of convergence for a class of nested Bender's cutting-plane algorithm. The basic model allows only right-hand side randomness, and requires independence between stages. The algorithm is computationally tractable for problems that are much larger than any prior algorithm for which a proof of convergence has been produced. It requires a finite sample space, but it may have thousands of realizations per stage, and the technique can handle dozens (even hundreds) of stages. Numerical performance will depend on the specific problem class.
R. K.-L. Cheung and W.B. Powell, "SHAPE – A Stochastic, Hybrid Approximation Procedure for Two-Stage Stochastic Programs,” Operations Research, Vol. 48, No. 1, pp. 73-79 (2000) (c) Informs.
This paper offers a provably convergent algorithm for two-stage stochastic programs. The method uses a differentiable (strictly convex) auxiliary function, and then "tilts" it using stochastic gradient information. The algorithm is very easy to implement.
Godfrey, G. and W.B. Powell, "An Adaptive, Distribution-Free Algorithm for the Newsvendor Problem with Censored Demands, with Application to Inventory and Distribution Problems," Management Science, Vol. 47, No. 8, pp. 1101-1112, (2001). (c) Informs.
This paper proposes a novel approximation procedure for stochastic resource allocation problems. The technique works with a series of stochastic gradients which are then used to maintain a concave estimate of the value function. When applied to problems with known optimal solutions, the method provides results within a fraction of a percent of optimal. One byproduct is a fast algorithm for the newsvendor problem that does not require knowledge of the underlying demand distribution. The technique is also applied to separable distribution problems.
(Click here to download paper)
Godfrey, G. and W.B. Powell, “An Adaptive Dynamic Programming Algorithm for Single-Period Fleet Management Problems I: Single Period Travel Times,” Transportation Science, Vol. 36, No. 1, pp. 21-39 (2002). (c) Informs.
Godfrey, G. and W.B. Powell, “An Adaptive Dynamic Programming Algorithm
for Single-Period Fleet Management Problems II: Multiperiod Travel Times,”
Transportation Science, Vol. 36, No. 1, pp. 40-54 (2002). (c) Informs.
This paper adapts the CAVE algorithm to stochastic multistage problems. The paper demonstrates both rapid convergence of the algorithm as well as very high quality solutions. We found that the use of nonlinear approximations was complicated by the presence of multiperiod travel times (a problem that does not arise when we use linear approximations).
Cheung, R.K.-M. and W.B. Powell, "An Algorithm for Multistage Dynamic Networks with Random Arc Capacities, with an Application to Dynamic Fleet Management," Operations Research, Vol. 44, No. 6, pp. 951-963. (1996). (c) Informs.
This paper applies the work in the paper immediately below to multistage problems. The motivating problem is dynamic fleet management with stochastic demands. This technique produces an approximate nonlinear function for the value of resources in a particular state. These nonlinear functions are then used in the context of a rolling horizon procedure. Numerical experiments indicate that the method outperforms rolling horizon procedures with deterministic demand forecasts. Note, however, that the nonlinear approximations are not updated iteratively.
Cheung, R.K.-M. and W.B. Powell, "Network Recourse Decomposition Method for Dynamic Networks with Random Arc Capacities," Networks, Vol. 24, No. 7, pp. 369-384 (1994).
We consider a two-stage stochastic transshipment network. Our goal is to develop nonlinear approximations for the value of flow into a node at the beginning of the second stage. We decompose the second stage (which is assumed to be a dynamic transshipment network) into a series of trees, which allows us to use the tree recourse algorithm (described in the paper below) to find the exact value function. Because the second stage network is a transshipment network, we use a Lagrangian approach to decompose the network into trees. An iterative algorithm then updates the multipliers.
Cheung, R.K.-M. and W.B. Powell, "Stochastic Programs over Trees with Random Arc Capacities," Networks, Vol. 24, pp. 161-175 (1994).
This paper considers the problem of a tree with random arc capacities. If S units of flow enter the root node, where they are to be rounded through n stages before they depart through the leavese of the tree, then we are interested in finding V(S), which is the expected value of S units of flow. We propose an efficient, exact algorithm for finding V(S), which works for both single stage (all arc capacities are known at the same time) or n stages (the arc capacities are learned only after a stage is progressed).
Powell, W.B. and L. Frantzeskakis, "Restricted Recourse Strategies for Dynamic Networks with Random Arc Capacities," Transportation Science , Vol. 64, pp. 261-287, 1996. (c) Informs.
General stochastic networks are quite complex. Not surprisingly, it is easier to analyze problems with special structure. In this paper, we explore specialized recourse strategies that arise in stochastic networks. We cover simple recourse (where the action is implemented regardless of the outcome, meaning that the state of the system in the future is deterministic), nodel recourse (where we assume that a decision is made at a node regarding which outbound arc should be chosen), and tree recourse (where we make the decision of how to route ourselves over a tree). Variations are also considered.
Frantzeskakis, L. and W.B. Powell, "Restricted Recourse Strategies for Bounding the Expected Network Recourse Function" Annals of Operations Research on Stochastic Programming, (J. Higle and S. Sen, eds), Vol. 64, pp. 261-287, 1996.
We investigate bounds for stochastic networks drawing on the principles of restricted recourse strategies, and concepts drawn from the work of Stein Wallace. Not for the faint of heart. As with a lot of the work on bounds for stochastic programs, this is a difficult intellectual exercise with a lot of input for very little output.
(click here to download paper)
See also:
Frantzeskakis, L. and W.B. Powell, "Bounding Procedures for Dynamic Networks with Random Link Capacities, with Application to Stochastic Programming," Networks , Vol. 23, pp. 575-595 (1993).
Here we actually produce a computationally tractable bound for multistage dynamic networks with random arc capacities. We use our ability to successively solve to optimality network recourse functions with linear value functions. If we choose the right constant, we can produce a bound. But, don't get your hopes up; the bounds are not very tight.
Deterministic optimization (back)
Chen, Z.-L. and W.B. Powell, "A Note on Bertsekas' Small-Label-First Strategy," Networks, Vol. 29, No. 2, pp. 111-116 (1997).
A neat little technical result showing that an algorithm by Bertsekas is NP, and how it can be easily fixed.
Chen, Z.L. and W.B. Powell, "A Generalized Threshold Algorithm for the Shortest Path Problem with Time Windows," in Network Design: Connectivity and Facilities (P. Pardalos, D. Du, eds.), pp. 303-318 (1998).
We look at the resource constrained shortest path problem (by Desroschers, Desrosiers and Soumis) and show that Klingman's threshold algorithm is faster in side by side comparisons of code programmed by the same programmer. This is yet another experimental demonstration that the algorithm with the better complexity bound (label setting) is not quite as good as label correcting algorithms (the threshold algorithm is a member of this class).
Jones, K.L., I.J. Lustig, W.B. Powell and J.M. Farvolden, "Multicommodity network flows: The impact of formulation on decomposition," Mathematical Programming, Vol. 62, pp. 95-117 (1993).
When this research was done, it was "common knowledge" that Dantzig-Wolfe decomposition did not work. It was common practice (primarily in the 1980's) to use decompositions that produced small master problems. Here, we show that it is possible to get dramatic increases in speed by breaking extreme point solutions (which might be a solution to a network flow problem) into more elementary representations (trees or paths). This produces much larger master problems (an issue in the 80's, but less important now) but much faster convergence.
Farvolden, J.M., W.B. Powell and I.J. Lustig, "A Primal Partitioning Solution for the Arc-Chain Formulation of a Multicommodity Network Flow Problem," Operations Research , Vol. 41, No. 4, pp. 669-693 (1993). (c) Informs.
A fast, neat algorithm for multicommodity network flow problems where we show that the basis can be partitioned and exploited to produce a very fast algorithm. Our experiments are primarily on dynamic graphs, and commodities that represent O/D flows.
Powell, W.B., E. Berkkam and I.J. Lustig, "On Algorithms for Nonlinear Dynamic Networks", in Network Optimization Problems: Algorithms, Complexity and Applications (Dingzhu Du and Panox Pardalos, eds.) World Scientific Press, New Jersey, pp. 203-231 (1993).
Powell, W.B. "A Review of Sensitivity Results for Linear Networks and a New Approximation to Reduce the Effects of Degeneracy," Transportation Science, Vol. 23, No. 4, pp. 231-243 (1989). (c) Informs
This paper is perhaps the most frequently used result in CASTLE Lab. The paper shows how to quickly obtain left and right derivatives with respect to resource constraints using flow augmenting paths. The basic result appears to be "well known" in the research community, but we could not find any documentation of the algorithm or formal writeup of the theory.
Queueing theory (back)
Simao, H. and W.B. Powell, "Numerical Methods for Simulating Transient, Stochastic Queueing Networks - I: Methodology," Transportation Science , Vol. 26, No. 4, pp. 296-311 (1992). (c) Informs
Simao, H. and W.B. Powell, "Numerical Methods for Simulating Transient, Stochastic Queueing Networks - II: Experimental Results," Transportation Science , Vol. 26, No. 4, pp. 312-329 (1992). (c) Informs
Simao, H. and W.B Powell, "Waiting Time Distributions for Bulk Arrival, Bulk Service Queues with Vehicle Holding and Cancellation Strategies," Naval Research Logistics Quarterly, Vol. 34, No. 2, pp. 207-228 (1987).
Simao, H. and W.B Powell, "Waiting Time Distributions for Transient Bulk Queues with General Vehicle Dispatching Strategies," Naval Research Logistics Quarterly, Vol. 35, pp. 285-306 (1988).
Powell, W.B. and P. Humblet, "The Bulk Service Queue with a General Control Strategy: Theoretical Analysis and a New Computational Procedure," Operations Research, Vol. 34, No. 2, pp. 267-275 (1986). (c) Informs
Powell, W.B. "Iterative Algorithms for Bulk Arrival, Bulk Service Queues with Poisson and non-Poisson Arrivals," Transportation Science, Vol. 20, No. 2, pp. 65-79 (1986). (c) Informs
Powell, W.B. "Approximate, Closed Form Moment Formulas for Bulk Arrival, Bulk Service Queues," Transportation Science, Vol. 20, No. 1, pp. 13-23 (1986). (c) Informs
Powell, W.B. "Analysis of Vehicle Holding and Cancellation Strategies in Bulk Arrival, Bulk Service Queues," Transportation Science, Vol. 19, No. 4, pp. 352-377 (1985). (c) Informs
Powell, W.B. and H. Simao, "Stochastic Properties of Flows in Freight Consolidation Networks," Elsevier, pp. 437-457, 1987. Tenth International Symposium on Transportation and Traffic Theory, (N. Gartner and N. Wilson, eds.)
Powell, W.B.,"Bulk Service Queues with Deviations from Departure Schedules: The Problem of Correlated Headways," Transportation Research, Vol. 17B, No. 3, pp. 221-232, (1982).
Dynamic fleet management (back)
Simao, H. P., J. Day, A. George, T. Gifford, W. B. Powell, “An Approximate Dynamic Programming Algorithm for Large-Scale Fleet Management: A Case Application,” Transportation Science (to appear) (c) Informs
This is a major application paper, which summarizes several years of development to produce a model based on approximate dynamic programming which closely matches historical performance. The model represents drivers with 15 attributes, capturing domicile, equipment type, days from home, and all the rules (including the 70 hour in eight days rule) governing drivers. The model gets drivers home, on weekends, on a regular basis (again, closely matching historical performance). The value functions produced by the ADP algorithm are shown to accurately estimate the marginal value of drivers by domicile.
Topaloglu, H. and W. B. Powell, “Sensitivity Analysis of a Dynamic Fleet Management Model Using Approximate Dynamic Programming” Operations Research, Vol. 55, No. 2, pp. 319-331 (2007). (c) Informs
We present tractable algorithms to assess the sensitivity of a stochastic dynamic fleet management model to fleet size
and load availability. In particular, we show how to compute the change in the objective function value in response to an
additional vehicle or an additional load introduced into the system. The novel aspect of our approach is that it does not
require multiple simulations with different values of the model parameters, and in this respect it differs from trial-anderror-
based “what-if” analyses. Numerical experiments show that the proposed methods are accurate and computationally
attractive.
Topaloglu, H. and W.B. Powell, “Dynamic Programming Approximations for Stochastic, Time-Staged Integer Multicommodity Flow Problems,” Informs Journal on Computing, Vol. 18, No. 1, pp. 31-42 (2006). (c) Informs.
This paper applies the technique of separable, piecewise linear approximations to multicommodity flow problems. This technique worked very well for single commodity problems, but it was not at all obvious that it would work well for multicommodity problems, since there are more substitution opportunities. The experimental comparisons against multistage nested Benders (which is very slow) and more classical rolling horizon procedures suggests that it works very well indeed. This paper also provides a more rigorous treatment of what is known as the "multiperiod travel time" problem, and provides a formal development of a procedure for accelerating convergence.
Powell, W.B. and H. Topaloglu, “Fleet Management,” in Applications of Stochastic Programming, (S. Wallace and W. Ziemba, eds.), Math Programming Society - SIAM Series in Optimization, Philadelphia,pp. 185-216, 2005.
Stochastic programming has been steadily making its way into a variety of application areas. This chapter demonstrates the use of a class of stochastic programming methods for fleet management applications, using the freight car distribution problem as a problem context.
Godfrey, G. and W.B. Powell, “An Adaptive Dynamic Programming Algorithm for Single-Period Fleet Management Problems I: Single Period Travel Times,” Transportation Science, Vol. 36, No. 1, pp. 21-39 (2002). (c) Informs.
Godfrey, G. and W.B. Powell, “An Adaptive Dynamic Programming Algorithm
for Single-Period Fleet Management Problems II: Multiperiod Travel Times,”
Transportation Science, Vol. 36, No. 1, pp. 40-54 (2002). (c) Informs.
This paper adapts the CAVE algorithm to stochastic multistage problems. The paper demonstrates both rapid convergence of the algorithm as well as very high quality solutions. We found that the use of nonlinear approximations was complicated by the presence of multiperiod travel times (a problem that does not arise when we use linear approximations).
Carvalho, T. and W.B. Powell, "A Multiplier Adjustment Method for Dynamic Resource Allocation Problems," Transportation Science, Vol. 34, No. 2, pp. 150-164 (2000). (c) Informs.
This paper gives our best results using linear value functions. The algorithm ("Lama" = linear approximation, mutliplier adjustment) uses a multiplier adjustment procedure to introduce the highest level of precision. The method is not suitable for stochastic problems.
Powell, W.B. and T. Carvalho, "Dynamic Control of Logistics Queueing Networks for Large Scale Fleet Management," Transportation Science, Vol. 32, No. 2, pp. 90-109, 1998. (c) Informs.
This paper launched an entirely new line of investigation into dynamic fleet management, using adaptively estimated linear value functions. Linear value functions by themselves are too unstable, so we used upper bounds to keep the flow from bouncing around too much. Since this paper, we have investigated the use of auxiliary functions to stabilize the flows, and nonlinear value function approximations. Both of these approaches appear to be quite promising.
Powell, W.B. and T. Carvalho, "Real-Time Optimization of Containers and Flatcars for Intermodal Operations," Transportation Science, Vol. 32, No. 2, pp. 110-126, 1998. (c) Informs.
This paper demonstrates the flexibility of the "LQN" modeling framework for solving a very complex problem arising in railroads. The challenge here was the assignment of trailers and containers to flatcars. The problem was that the rules for determining what trailer/container combinations could be assigned to a particular flatcar are quite complex. We used our ability to break the entire problem into a sequence of very small subproblems, representing each terminal at each point in time. Here, we were able to use a very precise, but computationally demanding, algorithm that captured the rules for capacity allocation with a high level of detail. The resulting algorithm was quite tractable, and we showed how the downstream gradients provided significantly better overall performance.
Powell, W.B. "A Stochastic Formulation of the Dynamic Assignment Problem, with an Application to Truckload Motor Carriers," Transportation Science. Vol. 30, No. 3, pp. 195-219 (1996). (c) Informs.
A summary of my work, primarily from the 1980's, in truckload trucking. This was the first model to integrate the load matching problem with forecasting, using a neat nonlinear approximation of the future. The paper summarizes the research of several masters theses, which investigated the impact of advance information on system performance.
Powell, W.B., T. Carvalho, G. Godfrey and H. Simao, "Dynamic Fleet Management as a Logistics Queueing Network.," Annals of Operations Research, Vol. 6, pp. 165--188 (1995). (c) Informs.
Our very earliest effort in this direction. If this topic seems interesting, look at (click here)
Carvalho, T. and W.B. Powell, "Dynamic Control of Multicommodity Logistics Queueing Networks," European Journal of Operations Research, Vol. 98, No. 3, 1997.
This was an attempt to apply the LQN-methodology (basically, linear approximations of the value of the future) to multicommodity problems. It is not trivial. Our current thinking is to use the nonlinear approximations of Topaloglu.
Cheung, R. K.-M. and W.B. Powell, "An Algorithm for Multistage Dynamic Networks with Random Arc Capacities, with an Application to Dynamic Fleet Management," Operations Research, Vol. 44, No. 6, pp. 951-963. (1996). (c) Informs.
Here we use the static, nonlinear approximations developed for stochastic trees in the context of multistage problems. The best available at the time, but even better results yet to come (see the work of Topaloglu).
Frantzeskakis, L. and W. B. Powell, "A Successive Linear Approximation Procedure for Stochastic, Dynamic Vehicle Allocation Problems," Transportation Science, Vol. 24, No. 1, pp. 40 - 57 (1990). (c) Informs.
Powell, W.B. and L. Frantzeskakis, "Restricted Recourse Strategies for Dynamic Networks with Random Arc Capacities," Transportation Science , Vol. 64, pp. 261-287, 1996. (c) Informs
Powell, W.B. "A Comparative Review of Alternative Algorithms for the Dynamic Vehicle Allocation Problem," Vehicle Routing: Methods and Studies (B. Golden and A. Assad, eds.), North Holland, pp. 249-291 (1988).
This was the first paper to formulate the dynamic vehicle allocation problem as a multistage stochastic network with random arc capacities. This insight was the foundation of the work on approximations and bounding by Frantzeskakis, and the work on tree recourse by Cheung.
Powell, W.B.,"An Operational Planning Model for the Dynamic Vehicle Allocation Problem with Uncertain Demands," Transportation Research , Vol. 21B, No. 3, pp. 217-232 (1987).
This is the first paper I wrote that used a separable approximation to produce piecewise linear recourse functions to capture the value of trucks in a region. The beauty of this paper is that it was able to produce a computationally tractable formulation that combined fleet management, which is a network problem, and the forecasts of future activities. It took me 15 years to really close the loop on this work with the paper:
Powell, W.B., A. Ruszczynski and H. Topaloglu, “Learning Algorithms for Separable Approximations of Stochastic Optimization Problems,” Mathematics of Operations Research, Vol 29, No. 4, pp. 814-836 (2004). (c) Informs.
which proved some key theorems and relaxed the core assumption of the separability of the objective function.
Hughes, R. and W.B. Powell, "Mitigating End Effects in the Dynamic Vehicle Allocation Model," Management Science, Vol. 34, No. 7, pp. 859-379 (1988). (c) Informs.
An extension of work by Grinold and Hopkins to the fleet assignment problem.
Powell, W.B., "A Stochastic Model of the Dynamic Vehicle Allocation Problem," Transportation Science Vol. 20, pp. 117-129 (1986).
My first stochastic fleet management paper - this paper extends (and fills some holes in) the seminal paper by Jordan and Turnquist for empty freight car distribution.
Multiagent control (back)
Topaloglu, H. and W.B. Powell, “A Distributed Decision-Making Structure for Dynamic Resource Allocation with Nonlinear Functional Approximations,” Operations Research, Vol. 53, No. 2, pp. 281-297 (2005) (c) Informs
Many complex problems in transportation are characterized by multiple decision-makers who control their own decisions with their own information. Coordinating these decision makers is a well-recognized challenge. This paper proposes to use a nonlinear approximation architecture, where the impact of decisions to move resources from one part of the network to another is captured using a nonlinear function. This introduces unique complications that do not arise with more traditional linear architectures, but produces much better results.
Shapiro, J. and W.B. Powell, “A Metastrategy for Dynamic Resource Management Problems based on Informational Decomposition,” Informs Journal on Computing, Vol. 18, No. 1, pp. 43-60 (2006). (c) Informs.
We do a lot of work on very large scale problems in transportation. These are typically characterized by multiagent decision making, which also means multiagent information structures. This paper provides a fairly general model of the organization of information and decisions, and a method for decomposing and linking these decisions so that the individual agents, operating separately, produce near optimal overall solutions.
(Click here to download paper)
Vehicle routing and scheduling (back)
Spivey, M. and W.B. Powell, “The Dynamic Assignment Problem,” Transportation Science, Vol. 38, No. 4, pp. 399-419 (2004). (c) Informs.
This paper proposes a general model for the dynamic assignment problem, which involves the assignment of resources to tasks over time, in the presence of potentially several streams of information processes. It proposes an adaptive learning model that produces non-myopic behavior, and suggests a way of using hierarchical aggregation to reduce statistical errors in the adaptive estimation of the value of resources in the future. Finally, it reports on a study on the value of advance information. Past studies of this topic have used myopic models where advance information provides a major benefit over no information at all. Our model uses adaptive learning to bring forecast information into decisions made now, providing a more realistic estimate of the value of future information.
Powell, W.B., M.T. Towns and A. Marar, "On the Value of Globally Optimal Solutions for Dynamic Routing and Scheduling Problems," Transportation Science, Vol. 34, No. 1, pp. 50-66 (2000). (c) Informs.
This paper addresses the issue of user noncompliance - what happens when the user does not do what the model recommends. Not surprisingly, the value of global optimization methods is diminished. Perhaps more surprisingly, suboptimal algorithms which are more greedy in nature work even better than an optimal solution.
Powell, W.B., W. Snow and R. K.-M. Cheung, "Adaptive Labeling Algorithms for the Dynamic Assignment Problem," Transportation Science, Vol. 34, No. 1, pp. 67-85 (2000). (c) Informs.
Chen, Z.L. and W.B. Powell, "A Generalized Threshold Algorithm for the Shortest Path Problem with Time Windows," in Network Design: Connectivity and Facilities (P. Pardalos, D. Du, eds.), pp. 303-318 (1998).
We look at the resource constrained shortest path problem (by Desroschers, Desrosiers and Soumis) and show that Klingman's threshold algorithm is faster in side by side comparisons of code programmed by the same programmer. This is yet another experimental demonstration that the algorithm with the better complexity bound (label setting) is not quite as good as label correcting algorithms (the threshold algorithm is a member of this class).
Powell, W.B. "A Stochastic Formulation of the Dynamic Assignment Problem, with an Application to Truckload Motor Carriers," Transportation Science. Vol. 30, No. 3, pp. 195-219 (1996). (c) Informs.
A summary of my work, primarily from the 1980's, in truckload trucking. This was the first model to integrate the load matching problem with forecasting, using a neat nonlinear approximation of the future. The paper summarizes the research of several masters theses, which investigated the impact of advance information on system performance.
Koskosidis, I A., W.B. Powell and M. Solomon, "An Optimization-Based Heuristic for Vehicle Routing and Scheduling with Soft Time Window Constraints," Transportation Science, Vol. 26, No. 2, pp. 69-85, 1992. (c) Informs
Powell, W.B. and D. Gittoes, "An Approximate Labeling Algorithm for the Dynamic Assignment Problem," Advanced Methods in Transportation Analysis, (L. Bianco, P. Toth, M. Bielli, eds.), Springer, New York, pp. 547-584, 1996.
Koskosidis, I.A. and W.B. Powell, "Clustering Algorithms for Consolidation of Customer Orders into Vehicle Shipments," Transportation Research, Vol. 26B, No. 5, pp. 365-379, 1992.
(Click here to download paper)
Military operations (back)
Powell, W. B., Belgacem Bouzaiene-Ayari, Jean Berger, Abdeslem Boukhtouta, Abraham P. George, “The Effect of Robust Decisions on the Cost of Uncertainty in Military Airlift Operations”, under review.
This paper shows that approximate dynamic programming can produce robust strategies in military airlift operations. Simulations are run using randomness in demands and aircraft availability. When demands are uncertain, we vary the degree to which the demands become known in advance. The results show that if we allocate aircraft using approximate dynamic programming, the effect of uncertainty is significantly reduced. These results call into question simulations that examine the effect of advance information which do not use robust decision-making, a property that we feel reflects natural human behavior.
Wu, T. T., W. B. Powell and A. Whisman, “The Optimizing Simulator: An Intelligent Analysis Tool for the Military Airlift Problem” under review.
In this paper, we model the military airlift problem as a Dynamic Resource Transformation Problem, and propose a family of simulation strategies based on modeling specific classes of information. We propose four classes of information, and create decision functions for each subset of classes. The classes are knowledge (what we know about the state of the system now), forecasts of exogenous information processes, forecasts of the impact of decisions now on the future, and forecasts of decisions (in the form of low-dimensional patterns). The goal of the paper is to bridge the traditional gap between classical rule-based simulators and math programming models.
Service network design (back)
Service network design covers the problem of when to move a truck that can carry multiple shipments. In a static setting, this produces large integer programming problems. In a dynamic setting, it creates batch service processes.
Dall’Orto, L. C., T. G. Crainic, J. E. Leal and W. B. Powell, “The Single-Node Dynamic Service Scheduling and Dispatching Problem,” European Journal of Operations Research, Vol. 170, No. 1, pp. 1-23 (2005).
Network design problems represent one of the hardest classes of integer programming problems. Time-staged versions of these problems are even harder. In this paper we extend the approximate dynamic programming strategy introduced by Katerina Papadaki for the single link problem to a problem where trucks are being dispatched out of a single node to multiple destinations. We have to figure out where to send trucks, and what freight to put on each truck. A truck going to destination j may carry freight to a final destination k. We treat the cost function from j to k as linear, and focus on the integer programming problem out of the origin node i. We solve one time period at a time, using a linear approximation to capture the impact of holding customers from time t to t+1. A metaheuristic is used to solve the single node (multiple link) problem, which while not very large, has to be solved very quickly (since it has to be solved iteratively).
Papadaki, K. and W.B. Powell, “An Adaptive Dynamic Programming Algorithm for a Stochastic Multiproduct Batch Dispatch Problem,” Naval Research Logistics, Vol. 50, No. 7, pp. 742-769, 2003.
One of the oldest problems in dynamic programming arises in the context of planning inventories. You can use textbook backward dynamic programming if there is only one product type, but real problems have multiple products. In this paper, we consider a multiproduct problem in the context of a batch service problem where different types of customers wait to be served. Arrivals are stochastic and nonstationary. We show that an approximate dynamic programming strategy using linear value functions works quite well and is computationally no harder than a simple myopic heuristics (once the iterative learning is completed).
Papadaki, K. and W.B. Powell, “Exploiting structure in adaptive dynamic programming algorithms for a stochastic batch service problem,” European Journal of Operational Research, Vol. 142, No. 1, pp. 108-127 (2002).
This paper compares an optimal policy for dispatching a truck over a single link (with one product type) against an approximate policy that uses approximations of the future. Why would we approximate a problem that is easy to solve to optimality? Because the optimal policy only works on single link problems with one type of product, while the other is scalable to much harder problems.
J.B. Braklow, W. Graham, K. Peck, S. Hassler, and W.B. Powell, "Interactive Optimization Improves Service and Performance for Yellow Freight System," Interfaces, Vol. 22, No. 1, 1992, pp. 147-172.
This was a finalist in the 1991 Franz Edelman competition, and for many years one of the most requested videotapes from the Edelman library. The paper documents a strategic planning system implemented at Yellow in the late 1980's which is still in production at Yellow as of this writing (2005). The system uses interactive optimization techniques to build a service network that delivers packages both efficiently and with high service.
Farvolden, J.M. and W.B. Powell, "Subgradient Optimization for the Service Network Design Problem," Transportation Science, Vol. 28, No. 3, pp. 256-272. (c) Informs
Powell, W.B. "A Local Improvement Heuristic for the Design of Less-Than-Truckload Motor Carrier Networks," Transportation Science, Vol 20, No. 4, pp. 246-257 (1986). (c) Informs
Koskosidis, I.A. and W.B. Powell, "Shipment Routing Algorithms with Tree Constraints," Transportation Science Vol 26, No. 3, pp. 230-245, 1992. (c) Informs
Less-than-truckload networks require that shipments be routed over links where the cost on a link is a piecewise linear function of the flow. Such problems could be solved as classical traffic assignment problems, but LTL networks (at the time) require that the routing of the shipments be communicated iin a way that follows a tree so that they can be described with the instruction "a shipment at i, headed to destination k, be sent on a truck going to j." This paper formulates the problem and describes a solution procedure.
Powell, W.B. and Y. Sheffi, "Design and Implementation of an Interactive Optimization System for Network Design in the Motor Carrier Industry," Operations Research, Vol. 37, No. 1, pp. 12-29 (1989). (c) Informs.
This paper describes a production system for static load planning for less-than-truckload motor carriers. The problem is determining where a carrier should offer "direct service". If we run trucks from i to j, it will carry freight that not only originates and i and terminates at j, but also other origin-destination pairs for which this link in the network helps them move quickly and at low cost. The problem the carrier faces is that the trucks have to move at least once a day, and possibly more. So, if there is not enough freight to fill the trucks, then it is possible that it is better to not run trucks between these points, and force freight through links with higher density. While this can be set up as a large-scale integer network design problem, the practical reality is that there are issues not captured by the cost model. This system solves the problem interactively, which also means that the calculations had to be *really* fast (on 1980's vintage computers). Developed at Princeton University, this system was one of the founding products of the Princeton Transportation Consulting Group, and has been used by numerous LTL carriers in the 1990's.
Powell, W.B. and Y. Sheffi, "The Load Planning Problem of Motor Carriers: Problem Description and a Proposed Solution Approach," Transportation Research, Vol. 17A, No. 6, pp. 471-480, (1983).
Machine Scheduling (back)
An important subclass of resource allocation problems fall under the general category of machine scheduling. These problems arise when there are resources that must be assigned to tasks over time. The machine scheduling literature focuses on problems where the "machines" (resources) are few and relatively (or completely) homogeneous.
Chen, Z.-L. and W.B. Powell, "Solving Parallel Machine Scheduling Problems by Column Generation," Informs Journal of Computing, Vol. 11, No. 1, Winter 1999. (c) Informs
This is the first paper to use column generation for parallel machine scheduling problems. Optimal solutions are presented demonstrating the computational efficiency of the technique.
Chen, Z.-L. and W.B. Powell, Chen, Z.-L. and W.B. Powell, "A Column-Generation Based Decomposition Algorithm for a Parallel Machine Just-In-Time Scheduling Problem," European Journal of Operations Research, Vol. 116, pp. 220-232 (1999).
Chen, Z.L. and W.B. Powell, “Exact Algorithms for Scheduling Multiple Families of Jobs on Parallel Machines,” Naval Research Logistics, Vol. 50, No. 7, pp. 823-840, 2003.
Physical distribution (back)
Godfrey, G. and W.B. Powell, "An Adaptive, Distribution-Free Algorithm for the Newsvendor Problem with Censored Demands, with Application to Inventory and Distribution Problems," Management Science, Vol. 47, No. 8, pp. 1101-1112, (2001). (c) Informs.
This paper proposes a novel approximation procedure for stochastic resource allocation problems. The technique works with a series of stochastic gradients which are then used to maintain a concave estimate of the value function. When applied to problems with known optimal solutions, the method provides results within a fraction of a percent of optimal. One byproduct is a fast algorithm for the newsvendor problem that does not require knowledge of the underlying demand distribution. The technique is also applied to separable distribution problems.
"Models and Algorithms for Distribution Problems with Uncertain Demands," Transportation Science, Vol. 30, No. 1, pp. 43-59 (with R. K.-M. Cheung). (c) Informs
Air transportation (back)
"Toward a Unified Framework for Real-Time Logistics Control," Military Journal of Operations Research, Vol. I, No. 4, Winter, 1996, pp. 69-79.
This paper was written in the context of the airlift flow problem for the military. It used an early version of the DRiP modeling paradigm.
"A Stochastic Passenger Loading Model of Airline Schedule Performance," Transportation Research, Vol. 17B, No. 5, pp. 399-410, (1983).
"Analysis of Airline Operating Strategies Under Stochastic Demand," Transportation Research, Vol. 16B, No. 1, pp. 31-44, (1982).
Public transportation (back)
These are papers from an earlier life. The most important papers from this era (actually, before I started my dissertation) were:
Powell, W.B. and Y. Sheffi, "The Convergence of Equilibrium Algorithms with Predetermined Step Sizes," Transportation Science, Vol. 16, No. 1, pp. 45-55, (1982). (c) Informs
Sheffi, Y. and W.B. Powell, "An Algorithm for the Equilibrium Assignment Problem with Random Link times," Networks, Vol. 12, No. 1, pp. 191-207, (1982).
These papers were the first to discover the use of stochastic approximation procedures for solving complex traffic assignment problems. These papers applied a theory developed by Kiefer and Wolfowitz and Blum from the early 1950's to solving stochastic optimization problems where the challenge was finding the stepsize. These papers "adapted" this theory, in a somewhat heuristic way, to the constrained optimization problem posed for modeling static traffic assignment problems.
Other papers:
Powell, W.B.,"A Stochastic Passenger Loading Model of Airline Schedule Performance," Transportation Research, Vol. 17B, No. 5, pp. 399-410, (1983).
Powell, W.B. and C. Winston, "A Numerical Investigation of the Impact of Uncertain Demand and Varying Risk Preferences on the Pricing and Capacity Decisions of Transportation Firms: the Case of Airlines," Transportation Research, Vol. 17B, No. 6, pp. 471-490 (1983).
Powell, W.B. and Y. Sheffi, "A Probabilistic Model of Bus Route Performance," Transportation Science, Vol. 17, No. 4, pp. 376-404, (1983). (c) Informs
Sheffi, Y., H. Mahmassani, and W.B. Powell, "Evacuation Studies for Nuclear Power Plant Sites: A New Challenge for Transportation Engineers," Journal of the Institute of Traffic Engineers, Vol. 51, No. 6, pp. 25-28, (1981).
Sheffi, Y. and W.B. Powell, "A
Comparison of Stochastic and Deterministic Traffic Assignment
Over Congested Networks," Transportation Research, Vol. 15B,
No. 1, pp. 53-64, (1980).
Freight demand estimation (back)
OK, so we don't have a long list of papers on statistical estimation. At the same time, we have had to put an inordinate amount of work into forecasting (with very little time to write it up). It turns out that if you want to develop stochastic models, you have to create your own estimates of the future. We never anticipated needing to add to the forecasting literature, but forecasting for freight applications has a number of unique characteristics.
G. Godfrey and W.B. Powell, "Adaptive Estimation of Daily Demands with Complex Calendar Effects," Transportation Research, Vol. 34, No. 6, pp. 451-469 (2000).
Stories from the field (back)
Powell, W.B., “Real-time dispatching for truckload motor carriers,” in Logistics Engineering Handbook (G. Don Taylor, ed.), CRC Press, 2007, pp. 15-1 – 15-30. (c) CRC Press.
This paper describes our experience implementing a real-time optimization model at Burlington Motor Carriers. Intended for a broad audience, it describes the basics of the model and some of tbe behind-the-scenes events that were encountered during implementation.
Powell, W.B., A. Marar, J. Gelfand, and S. Bowers, “Implementing Operational Planning Models: A Case Application from the Motor Carrier Industry,” Operations Research, Vol. 50, No. 4, (2002). (c) Informs
This paper summarizes our experience implementing a real-time load matching model at a large motor carrier. As part of the research, we compiled a roughly six month history of actual dispatch decisions, and then compared what actually happened to what our model would do. The company was liquidated about five years after the project was terminated. Makes you wonder what might have happened if they had used the systems more aggressively.
J.B. Braklow, W. Graham, K. Peck, S. Hassler, and W.B. Powell, "Interactive Optimization Improves Service and Performance for Yellow Freight System," Interfaces, Vol. 22, No. 1, 1992, pp. 147-172. This paper was our entry for the 1991 Franz Edelman Competition, in which we were a finalist. (c) Informs
This was a finalist in the 1991 Franz Edelman competition, and for many years one of the most requested videotapes from the Edelman library. The paper documents a strategic planning system implemented at Yellow in the late 1980's which is still in production at Yellow as of this writing (2005). The system uses interactive optimization techniques to build a service network that delivers packages both efficiently and with high service.
Powell, W.B., Y. Sheffi, K. Nickerson, K. Butterbaugh and S. Atherton, "Maximizing Profits for North American Van Lines' Truckload Division: A New Framework for Pricing and Operations," Interfaces, Vol. 18, No. 1, pp. 21-41 (1988). This paper was our entry for the 1987 Franz Edelman competition, in which we placed second. (c) Informs
(click here to download paper)
"Finding the Yellow Brick Road" is a seven part series that is written in short-story format, that is intended to give the reader an idea of some of the issues that arise from a management perspective. The paper features an academic consulting (modeled after myself) and the president of a trucking firm, modeled after Don Mayoras (currently the president of two trucking firms). The sequence appeared as the following papers:
Powell, W.B. and D. Mayoras, "Finding the Yellow Brick Road: Part I, "Toto, I Have a Feeling We're Not in Kansas Anymore!", Interfaces, Vol. 26, No. 5, pp. 26-33 (1996). (c) Informs
- (Click here to view paper)
Powell, W.B. and D. Mayoras, "Finding the Yellow Brick Road: Part II, "Lions and Tigers and Bears!", Interfaces, Vol. 26, No. 6, pp. 57-67 (1996). (c) Informs
- (Click here to view paper)
Powell, W.B. and D. Mayoras, "Finding the Yellow Brick Road: Part III, "The Wizard of Oz", Interfaces, Vol. 27, No. 1, pp. 143-154 (1997). (c) Informs
- (Click here to view paper)
Powell, W.B. and D. Mayoras, "Finding the Yellow Brick Road: Part IV, "I Wish I had a Brain", Interfaces, Vol. 27, No. 2, pp. 37-47 (1997). (c) Informs
- (Click here to view paper)
Powell, W.B. and D. Mayoras, "Finding the Yellow Brick Road: Part V: Through the Crystal Ball" Interfaces, Vol. 27, No. 3, pp. 14-21 (1997). (c) Informs
- (Click here to view paper)
Powell, W.B. and D. Mayoras, "Finding the Yellow Brick Road: Part VI: Courage!" Interfaces, Vol. 27, No. 4, pp. 12-22 (1997). (c) Informs
- (Click here to view paper)
Powell, W.B. and D. Mayoras, "Finding the Yellow Brick Road: Part VII: I Finally Have a Brain!," Interfaces, Vol. 27, No. 5, pp. 9-14. (1997). (c) Informs
- (Click here to view paper)