An Adaptive Dynamic Programming Algorithm for the Heterogeneous Resource Allocation Problem

Transportation Science - Tập 36 Số 2 - Trang 231-249 - 2002
Warren B. Powell1, Joel A. Shapiro1, Hugo Simão1
1Department of Operations Research and Financial Engineering, Princeton University, Princeton, New Jersey 08544

Tóm tắt

We consider an aggregated version of a large-scale driver scheduling problem, derived from an application in less-than-truckload trucking, as a dynamic resource allocation problem. Drivers are aggregated into groups characterized by an attribute vector which capture the important attributes required to incorporate the work rules. The problem is very large: over 5,000 drivers and 30,000 loads in a four-day planning horizon. We formulate a problem that we call the heterogeneous resource allocation problem, which is more general than a classical multicommodity flow problem. Since the tasks have one-sided time windows, the problem is too large to even solve an LP relaxation. We formulate the problem as a multistage dynamic program and solve it using adaptive dynamic programming techniques. Since our problem is too large to solve using commercial solvers, we propose three independent benchmarks and demonstrate that our technique appears to be providing high-quality solutions in a reasonable amount of time.

Từ khóa


Tài liệu tham khảo

Ahuja R., 1992, Network Flows: Theory, Algorithms and Applications

10.1002/net.3230080107

10.1007/BFb0121115

Beale E., 1980, Stochastic Programming, 387

Bertsekas D., 1996, Neuro-Dynamic Programming

10.1287/opre.44.6.951

Crainic T. G., 1987, INFOR, 25, 136

Desrosiers J., 1995, Handbook in Operations Research and Management Science, 35

10.1002/net.3230140406

10.1287/ijoc.11.4.370

10.1287/trsc.24.1.40

10.1007/BF01585938

10.1007/BF01585162

10.1287/trsc.17.2.123

Kennington J., 1980, Algorithms for Network Programming

10.1016/0377-2217(88)90377-3

Powell W. B., 1988, Vehicle Routing: Methods and Studies, 249

10.1016/S0377-2217(96)00373-6

10.1287/trsc.32.2.90

10.1287/trsc.32.2.110

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

Powell W. B., 1995, Handbook in Operations Research and Sci., 141

10.1287/trsc.31.2.159

Sutton R., 1998, Reinforcement Learning

10.1109/9.580874

10.1002/net.3230020304

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

Transportation Science

Tập 36 Số 2

231-249

Thông tin tác giả