W.B. Powell, B. Bouzaiene-Ayari, Clark Cheng, Sourav Das, Ricardo Fiorillo, Coleman Lawrence, “Locomotive Planning at Norfolk Southern using Approximate Dynamic Programming,” Interfaces, (to appear). (c) Informs
This paper describes the implementation of PLASMA at the Norfolk Southern Railroad.Click here for more details.
(Click here to download paper)
Belgacem Bouzaiene-Ayari, C. Cheng, S. Das, R. Fiorillo, W.B. Powell, “From Single Commodity to Multiattribute Models for Locomotive Optimization: A Comparison of Integer Programming and Approximate Dynamic Programming,” Transportation Science, Appeared online, August 4, 2014. http://dx.doi.org/10.1287/trsc.2014.0536 (c) Informs
The paper compares three optimization models for the locomotive planning problem for Norfolk Southern railroad: an aggregate model that is used in production to provide high level guidance on locomotive flows, a more detailed multicommodity flow formulation (which could be solved only over a three day horizon), and a very detailed model based on the modeling and algorithmic framework of approximate dynamic programming. The ADP-based formulation, called PLASMA, has been used by NS for a number of years for strategic fleet planning, and for daily operational planning. NS (as of this writing) only uses the deterministic version of the code, but this paper describes experiments using stochastic travel times (a major issue at North American freight railroads) and demonstrates that ADP produces much more robust solutions. Click here for more details.
(Click here to download paper)
Powell, W.B., Belgacem Bouzaiene-Ayari, Clark Cheng, Ricardo Fiorillo, Sourav Das, “Strategic, Tactical and Real-Time Planning of Locomotives at Norfolk Southern using Approximate Dynamic Programming,” ASME Conference, Philadelphia, April, 2012.
This paper summarizes a 10-year project to develop a production locomotive planning system for Norfolk Southern Railroad. The effort uses the modeling and algorithmic technology of approximate dynamic programming, which combines the power of mathematical programming and simulation. This makes it possible to model locomotives at a high level of detail, while simultaneously using optimization principles to give the model intelligent behavior. The system handles foreign power and shop routing, including congestion at yards. While Norfolk Southern runs the model in its deterministic form, we demonstrate the power of ADP to handle randomness in transit times and yard delays, producing results that are much more robust.
(Click here to download paper) – short version published in the proceedings of the ASME
(Click here to download paper) – long version (pre-publication)
Wu, Tongqiang, W.B. Powell and A. Whisman, “The Optimizing-Simulator: An Illustration using the Military Airlift Problem,” ACM Transactions on Modeling and Simulation, Vol. 19, No. 3, Issue 14, pp. 1-31 (2009).
There is a growing sense that the modeling of complex problems in transportation and logistics require drawing on the skills of both mathematical programming and simulation. This paper accomplishes this, combining the modeling and algorithmic framework of approximate dynamic programming with pattern matching and proximal point algorithms. The paper is organized along the theme of modeling not just the physical process, but also the organization and flow of information and decisions. The paper proposes that a decision function can be a modeling choice, and shows how you can use four classes of information to build a family of decision functions.
(click here to download paper)
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, published online doi 10.1287/trsc.1080.0238 (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.
(click here to download paper) See also the companion paper below:
Simao, H. P. A. George, Warren B. Powell, T. Gifford, J. Nienow, J. Day, “Approximate Dynamic Programming Captures Fleet Operations for Schneider National,” Interfaces, Vol. 40, No. 5, pp. 342-352, 2010. (c) Informs
This paper is a lite version of the paper above, submitted for the Wagner competition. This paper does with pictures what the paper above does with equations.
(click here to download paper)
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.
(Click here to download paper)
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.
(click here to download paper)
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.
(Click here to download paper)
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 Dynamic Fleet Management, 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 Dynamic Fleet Management, 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).
(Click here to download paper I)
(Click here to download paper II)
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.
(Click here to download paper)
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.
(Click here to download paper)
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.
(Click here to download paper)
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.
(Click here to download paper)
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).
(Click here to download paper)
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.
(click here to download paper)
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
(click here to download paper)
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.
(click here to download paper)
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.
(click here to download paper)
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.
(click here to download paper)
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.