A PARALLEL TABU SEARCH HEURISTIC FOR THE VEHICLE-ROUTING PROBLEM WITHTIME WINDOWS

The vehicle routing problem with time windows models many realistic ap plications in the context of distribution systems. In this paper, a pa rallel tabu search heuristic for solving this problem is developed and implemented on a network of workstations. Empirically, it is shown th at parallelization of the original sequential algorithm does not reduc e solution quality, for the same amount of computations, while providi ng substantial speed-ups in practice. Such speed-ups could be exploite d to quickly produce high quality solutions when the time available fo r computing a solution is reduced, or to increase service quality by a llowing the acceptance of new requests much later, as in transportatio n on demand systems. (C) 1997 Elsevier Science Ltd.