This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Spivey, M. Z. Articles by Powell, W. B. Search for Related Content

The Dynamic Assignment Problem

Department of Operations Research and Financial Engineering, Princeton University, Princeton, New Jersey 08544
Department of Operations Research and Financial Engineering, Princeton University, Princeton, New Jersey 08544
mzspivey{at}alumni.princeton.edu
powell{at}princeton.edu

There has been considerable recent interest in the dynamic vehicle routing problem, but the complexities of this problem class have generally restricted research to myopic models. In this paper, we address the simpler dynamic assignment problem, where a resource (container, vehicle, or driver) can serve only one task at a time. We propose a very general class of dynamic assignment models, and propose an adaptive, nonmyopic algorithm that involves iteratively solving sequences of assignment problems no larger than what would be required of a myopic model. We consider problems where the attribute space of future resources and tasks is small enough to be enumerated, and propose a hierarchical aggregation strategy for problems where the attribute spaces are too large to be enumerated. Finally, we use the formulation to also test the value of advance information, which offers a more realistic estimate over studies that use purely myopic models.

Key Words: dynamic vehicle routing; dynamic assignment; approximate dynamic programming
History: Received: June 2001; revised: June 2002; revised: March 2003; accepted: May 2003.

This article has been cited by other articles:

				H. P. Simao, J. Day, A. P. George, T. Gifford, J. Nienow, and W. B. Powell An Approximate Dynamic Programming Algorithm for Large-Scale Fleet Management: A Case Application Transportation Science, May 1, 2009; 43(2): 178 - 197. [Abstract] [PDF]

				C. E. Cortes, D. Saez, A. Nunez, and D. Munoz-Carpintero Hybrid Adaptive Predictive Control for a Dynamic Pickup and Delivery Problem Transportation Science, February 1, 2009; 43(1): 27 - 42. [Abstract] [PDF]

				S. Ichoua, M. Gendreau, and J.-Y. Potvin Exploiting Knowledge About Future Demands for Real-Time Vehicle Dispatching Transportation Science, May 1, 2006; 40(2): 211 - 225. [Abstract] [PDF]