TY - JOUR

T1 - An adaptive dynamic programming algorithm for the heterogeneous resource allocation problem

AU - Powell, Warren Buckler

AU - Shapiro, Joel A.

AU - Simão, Hugo P.

PY - 2002/5

Y1 - 2002/5

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0036567426&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036567426&partnerID=8YFLogxK

U2 - 10.1287/trsc.36.2.231.561

DO - 10.1287/trsc.36.2.231.561

M3 - Article

AN - SCOPUS:0036567426

SN - 0041-1655

VL - 36

SP - 231

EP - 249

JO - Transportation Science

JF - Transportation Science

IS - 2

ER -