e 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. We consider the problem of assigning a set of homogeneous vehicles (or resources) to customer demands (or tasks) that arise randomly over time. Each vehicle is in a particular state (typically, a geographical location), and each task requires a resource in a particular state. The assignment of a resource to a task generates revenue and removes the task from the system. It also changes the state of the resource. A resource in one state can be transformed into a resource in selected other states at a cost. A task may be assigned to resources in a specified subset of states. Finally, we assume that all transitions require one time period (such as four hours or a day). Needless to say, we are generally interested in integer solutions to this problem. Our problem arose in the context of managing fleets of vehicles that are allocated spatially over time. Vehicles might be trailers, boxcars, or containers, or they may be rental cars and trucks. The same problem structure also arises in machine scheduling with setups (moving a truck from one city to the next is identical to a machine with a setup cost and time), as well as other forms of resource transformation (such as personnel training). Even in transportation, the movement of a vehicle from one location to the next may involve more than a change in space: the truck may have less fuel; the driver may have reduced hours of service; and a chemical trailer may become dirty and, therefore, may need to be cleaned. We refer to this problem as the stochastic dynamic resource allocation problem (SDRAP), a problem class with its roots in fleet management. It arises in a variety of settings, including: fleet management (how many empty box cars or trailers should be moved empty from one location to the next and which loads should be served first), car rental fleets (how many rental cars, and which types, should be assigned to a particular pool), dynamic crew scheduling (assigning drivers to move loads from origin to destination, taking into account all the characteristics of each type of driver), training of military personnel (how many recruits should receive a particular type of specialty training), and remnant inventory (given bins of pipes of different lengths, we wish to choose a pipe that is at least as long as the required demand, cut it down to the needed size, and then put the leftover piece in the appropriate bin).
In REF , an adaptive dynamic programming approach was proposed to model stochastic dynamic resource allocation.
An Adaptive Dynamic Programming Algorithm for Dynamic Fleet Management, I: Single Period Travel Times
Transportation Science
Transportation Science
Mathematics Computer Science