Article ID: | iaor2003776 |
Country: | United States |
Volume: | 36 |
Issue: | 1 |
Start Page Number: | 21 |
End Page Number: | 39 |
Publication Date: | Feb 2002 |
Journal: | Transportation Science |
Authors: | Powell W.B., Godfrey G.A. |
Keywords: | vehicle routing & scheduling, adaptive processes |
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.