Adaptive labeling algorithms for the dynamic assignment problem

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 s cheduling problems, which require fast response times, the ability to handl e a wide range of operational concerns, and the ability to output multiple recommendations for a particular driver. A mathematical formulation is intr oduced that easily handles real-world operational complexities. Two new opt imization-based heuristics are described, one giving faster performance and the second providing somewhat higher solution quality. Comparisons to opti mal 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 applica tions.