Adaptive Labeling Algorithms for the Dynamic Assignment Problem

Powell, Warren B.; Snow, Wayne; Cheung, Raymond K.
February 2000
Transportation Science;Feb2000, Vol. 34 Issue 1, p50
Academic Journal
We consider the problem of dynamically routing a driver to cover a sequence of tasks (with no consolidation), using a complex set of driver attributes and operational rules. Our motivating application is dynamic routing and scheduling problems, which require fast response times, the ability to handle a wide range of operational concerns, and the ability to output multiple recommendations for a particular driver. A mathematical formulation is introduced that easily handles real-world operational complexities. Two new optimization-based heuristics are described, one giving faster performance and the second providing somewhat higher solution quality. Comparisons to optimal solutions are provided, which measure the quality of the solutions that our algorithms provide. Experimental tests show that our algorithms provide high quality solutions, and are fast enough to be run in real-time applications.


Related Articles

  • Heuristic-Programming Solution of a Flowshop-Scheduling Problem. Krone, Martin J.; Steiglitz, Kenneth // Operations Research;May/Jun74, Vol. 22 Issue 3, p629 

    This paper considers the static flowshop-scheduling problem with the objective of minimizing, as a cost function, the mean job-completion time. Within the more general framework of combinatorial optimization problems, it defines a heuristic search technique--an approach that has been successful...

  • A Guaranteed-Accuracy Round-off Algorithm for Cyclic Scheduling and Set Covering. Bartholdi III, John J. // Operations Research;May/Jun81, Vol. 29 Issue 3, p501 

    The problem of cyclic staff scheduling is solved by a linear programming round-off heuristic for which a bound on the absolute error is established. The quality of the bound is independent of the resource requirements. Moreover, the quality of the bound improves as the matrix of resource...

  • A Network-Based Primal-Dual Heuristic for the Solution of Mulitcommodity Network Flow Problems. Barnhart, Cynthia; Sheffi, Yosef // Transportation Science;May93, Vol. 27 Issue 2, p102 

    In this paper, we present a primal-dual, heuristic solution approach for large-scale multicommodity network flow problems. The original problem is solved indirectly by repeatedly solving restated feasibility problems. Restrictions on problem size imposed by exact methods are overcome by solving...

  • A tabu-search heuristic for the flexible-resource flow shop scheduling problem. Daniels, Richard L.; Mazzola, Joseph B. // Annals of Operations Research;1993, Vol. 41 Issue 1-4, p207 

    This paper presents a tabu-search heuristic for the flexible-resource flow shop scheduling (FRFS) problem [7]. The FRFS problem generalizes the classic flow shop scheduling problem by allowing job-operation processing times to depend on the amount of resource assigned to an operation; the...

  • A HEURISTIC ALGORITHM FOR THE n JOB, m MACHINE SEQUENCING PROBLEM. Campbell, Herbert G.; Dudek, Richard A.; Smith, Milton L. // Management Science;Jun70, Vol. 16 Issue 10, pB-630 

    This paper describes a simple algorithm for the solution of very large sequence problems without the use of a computer. It produces approximate solutions to the n job, m machine sequencing problem where no passing is considered and the criterion is minimum total elapsed time. Up to m-1 sequences...

  • On a Real-Time Scheduling Problem. Dhall, Sudarshan K.; Iiu, C. L. // Operations Research;Jan/Feb78, Vol. 26 Issue 1, p127 

    We study the problem of scheduling periodic-time-critical tasks on multiprocessor computing systems. A periodic-time-critical task consists of an infinite number of requests, each of which has a prescribed deadline. The scheduling problem is to specify an order in which the requests of a set of...

  • Single machine scheduling with batch set-up time to minimize maximum lateness. Hariri, A. M. A.; Potts, C. N. // Annals of Operations Research;1997, Vol. 70 Issue 1-4, p75 

    This paper considers a problem of scheduling N jobs on a single machine to minimize the maximum lateness. A partitioning of the jobs into F families is given. A set-up time is required at the start of each batch, where a batch is a largest set of contiguously scheduled jobs from the same family....

  • Stochastic scheduling of a batch processing machine with incompatible job families. Duenyas, Izak; Neale, John J. // Annals of Operations Research;1997, Vol. 70 Issue 1-4, p191 

    We consider the control of a single batch processing machine with random processing times and incompatible job families (jobs from different families cannot be processed together in the same batch). Holding costs are incurred for each unit of time that a job waits in the system before being...

  • Two-machine no-wait flow shop scheduling with missing operations. Glass, C. A.; Gupta, J. N. D.; Potts, C. N. // Mathematics of Operations Research;Nov99, Vol. 24 Issue 4, p911 

    This article considers the operations research problem on the no-wait scheduling of n jobs in a two-machine flow shop, where some jobs require processing on the first machine only. The purpose is to minimize the maximum completion time, or makespan. In view of its NP-hardness, the article...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics