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

Transportation Science - Tập 36 Số 1 - Trang 21-39 - 2002
Gregory A. Godfrey1, Warren B. Powell1
1Department of Operations Research and Financial Engineering, Princeton University, Princeton, New Jersey 08544

Tóm tắt

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.

Từ khóa


Tài liệu tham khảo

Bertsekas D., 1996, Neuro-Dynamic Programming

10.1287/opre.33.5.989

Birge J., 1997, Introduction to Stochastic Programming

10.1287/trsc.34.2.150.12305

10.1023/A:1022641805263

10.1287/opre.44.6.951

10.1287/opre.48.1.73.12452

10.1137/0328072

10.1287/mnsc.1.3-4.197

10.1007/978-3-642-61370-8

10.1287/trsc.24.1.40

10.1287/mnsc.47.8.1101.10231

Godfrey G. A., 2002, Transportation Sci., 36

10.1287/moor.16.3.650

Infanger G., 1994, Planning Under Uncertainty: Solving Large-scale Stochastic Linear Programs

10.1287/trsc.17.2.123

Kall P., 1994, Stochastic Programming

10.1007/BF01582895

10.1287/trsc.20.2.117

10.1016/0191-2615(87)90005-1

10.1287/trsc.23.4.231

10.1287/trsc.32.2.90

Powell W. B., 2002, Ann. Oper. Res.

10.1002/9780470316887

Rockafellar R. T., 1972, Convex Analysis, 2

10.1287/moor.16.1.119

10.1007/BF01581643

10.1287/moor.12.1.32

Sutton R., 1998, Reinforcement Learning

10.1137/0117061

Thông tin
Thông tin xuất bản

Transportation Science

Tập 36 Số 1

21-39

Thông tin tác giả