IMPLEMENTING AN INSERTION HEURISTIC FOR VEHICLE ROUTING ON PARALLEL HARDWARE

In this paper, the authors report about the implementation of an insertion heuristic for the Vehicle Routing and Scheduling Problem with Time Windows on parallel hardware. As it is experimentally demonstrated on a standard set of test problems, a good parallel implementation can produce a very substantial reduction in computation time. In particular, two procedures are described for reducing communication and idle time when the number of processors grows up. (A)