General Dynamic Resource Management

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 DRTP paradigm which can be viewed as general purpose dynamic resource management problems. The major paper summarizing this modeling framework is the first paper below. Virtually all the others represent applications of this modeling framework:

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.

(Click here to download paper)

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)

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.

(click here to download paper)

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)

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., “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.

(Click here to download paper)

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.

(Click here to download paper)

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 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)