An adaptive dynamic programming algorithm for the heterogeneous resource allocation problem

Warren Buckler Powell, Joel A. Shapiro, Hugo P. Simão

Research output: Contribution to journalArticle

34 Scopus citations

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

Original languageEnglish (US)
Pages (from-to)231-249
Number of pages19
JournalTransportation Science
Volume36
Issue number2
DOIs
StatePublished - Jan 1 2002

All Science Journal Classification (ASJC) codes

  • Transportation

Fingerprint Dive into the research topics of 'An adaptive dynamic programming algorithm for the heterogeneous resource allocation problem'. Together they form a unique fingerprint.

Cite this