Title | ||
---|---|---|
An Adaptive Dynamic Programming Algorithm for the Heterogeneous Resource Allocation Problem |
Abstract | ||
---|---|---|
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 theheterogeneous 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. |
Year | DOI | Venue |
---|---|---|
2002 | 10.1287/trsc.36.2.231.561 | Transportation Science |
Keywords | Field | DocType |
adaptive dynamic programming technique,theheterogeneous resource allocation problem,dynamic resource allocation problem,heterogeneous resource allocation problem,aggregated version,attribute vector,large-scale driver scheduling problem,lp relaxation,one-sided time windows,classical multicommodity flow problem,adaptive dynamic programming algorithm,multistage dynamic program,scheduling,mathematical models,cluster analysis,traffic flow,logistics,truck,trucks,resource allocation,linear programming,dynamic programming,algorithms | Partition problem,Mathematical optimization,Computational problem,Job shop scheduling,Resource allocation,Cutting stock problem,Function problem,Linear programming,Multi-commodity flow problem,Operations management,Mathematics | Journal |
Volume | Issue | ISSN |
36 | 2 | 0041-1655 |
Citations | PageRank | References |
14 | 0.81 | 13 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Warren B. Powell | 1 | 1614 | 151.46 |
Joel A. Shapiro | 2 | 316 | 29.93 |
Hugo Simão | 3 | 106 | 8.38 |