An Adaptive Dynamic Programming Algorithm for Dynamic Fleet Management,I: Single Period Travel Times

Godfrey, Gregory A.; Powell, Warren B.
February 2002
Transportation Science;Feb2002, Vol. 36 Issue 1, p21
Academic Journal
We consider a stochastic version of a dynamic resource allocation problem. In this setting, reusable resources must be assigned to tasks that arise randomly over time. We solve the problem using an adaptive dynamic programming algorithm that uses nonlinear functional approximations that give the value of resources in the future. Our functional approximations are piecewise linear and naturally provide integer solutions. We show that the approximations provide near-optimal solutions to deterministic problems and solutions that significantly outperform deterministic rolling-horizon methods on stochastic problems.


Related Articles

  • An Adaptive Dynamic Programming Algorithm for Dynamic Fleet Management,II: Multiperiod Travel Times. Godfrey, Gregory A.; Powell, Warren B. // Transportation Science;Feb2002, Vol. 36 Issue 1, p40 

    In a companion paper (Godfrey and Powell 2002) we introduced an adaptive dynamic programming algorithm for stochastic dynamic resource allocation problems, which arise in the context of logistics and distribution, fleet management, and other allocation problems. The method depends on estimating...

  • A Combined Vehicle Routing and Inventory Allocation Problem. Federgruen, Awl; Zipkin, Paul // Operations Research;Sep/Oct84, Vol. 32 Issue 5, p1019 

    We address the combined problem of allocating a scarce resource among several locations, and planning deliveries using a fleet of vehicles. Demands are random, and holding and shortage costs must be considered in the decision along with transportation costs. We show how to extend some of the...

  • Management of water resource systems in the presence of uncertainties by nonlinear approximation techniques and deterministic sampling. Baglietto, M.; Cervellera, C.; Sanguineti, M.; Zoppoli, R. // Computational Optimization & Applications;Oct2010, Vol. 47 Issue 2, p349 

    Two methods of approximate solution are developed for T-stage stochastic optimal control (SOC) problems, aimed at obtaining finite-horizon management policies for water resource systems. The presence of uncertainties, such as river and rain inflows, is considered. Both approaches are based on...

  • Dynamic Programming Approximations for a Stochastic Inventory Routing Problem. Kleywegt, Anton J.; Nori, Vijay S.; Savelsbergh, Martin W. P. // Transportation Science;Feb2004, Vol. 38 Issue 1, p42 

    This work is motivated by the need to solve the inventory routing problem when implementing a business practice called vendor managed inventory replenishment (VMI). With VMI, vendors monitor their customers inventories and decide when and how much inventory should be replenished at each...

  • DYNAMIC PROGRAMMING MODELS OF THE NONSERIAL CRITICAL PATH-COST PROBLEM. Esogbue, Augustine O.; Marks, Barry R. // Management Science;Oct77, Vol. 24 Issue 2, p200 

    One of the major contributions to the planning and management of Research and Development organizations is the evolution of methods for dealing with PERT-Cost or CPM-Cost problems. Classically however, variations of the critical path-cost (CPM-Cost) problem, arising when different cost duration...

  • Dynamic-Programming Approximations for Stochastic Time-Staged Integer Multicommodity-Flow Problems. Topaloglu, Huseyin; Powell, Warren B. // INFORMS Journal on Computing;Winter2006, Vol. 18 Issue 1, p31 

    In this paper, we consider a stochastic and time-dependent version of the min-cost integer multicommodity-flow problem that arises in the dynamic resource allocation context. In this problem class, tasks arriving over time have to be covered by a set of indivisible and reusable resources of...

  • A Multiechelon Inventory Model with Fixed Replenishment Intervals. Graves, Stephen C. // Management Science;Jan1996, Vol. 42 Issue 1, p1 

    This paper develops a new model for studying multiechelon inventory systems with stochastic demand. For the model we assume that each site in the system orders at preset times according to an order-up-to policy, that delivery times are deterministic, and that the demand processes are stochastic...

  • Fixed-Dimensional Stochastic Dynamic Programs: An Approximation Scheme and an Inventory Application. Wei Chen; Dawande, Milind; Janakiraman, Ganesh // Operations Research;Jan/Feb2014, Vol. 62 Issue 1, p81 

    We study fixed-dimensional stochastic dynamic programs in a discrete setting over a finite horizon. Under the primary assumption that the cost-to-go functions are discrete Lí„®-convex, we propose a pseudo-polynomial time approximation scheme that solves this problem to within an arbitrary...

  • A Column Generation Algorithm for a Rich Vehicle-Routing Problem. Ceselli, Alberto; Righini, Giovanni; Salani, Matteo // Transportation Science;Feb2009, Vol. 43 Issue 1, p56 

    We present an optimization algorithm developed for a provider of software-planning tools for distribution logistics companies. The algorithm computes a daily plan for a heterogeneous fleet of vehicles that depart from different depots and must visit a set of customers for delivery operations. In...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics