Parallel tabu search for real-time vehicle routing and dispatching

An abundant literature about vehicle routing and scheduling problems is ava ilable in the scientific community. However, a large fraction of this work deals with static problems where all data are known before the routes are c onstructed Recent technological advances now create environments where deci sions are taken quickly, using new or updated information about the current routing situation. This paper describes such a dynamic problem, motivated from courier service applications, where customer requests with soft time w indows must be dispatched in real time to a fleet of vehicles in movement A tabu search heuristic, initially designed for the static version of the pr oblem, has been adapted to the dynamic case and implemented on a parallel p latform to increase the computational effort. Numerical results are reporte d using different request arrival rates, and comparisons are established wi th other heuristic methods.