PARALLEL ITERATIVE SEARCH METHODS FOR VEHICLE-ROUTING PROBLEMS

This paper presents two partition methods that speed up iterative sear ch methods applied to vehicle routing problems including a large numbe r of vehicles. Indeed, using a simple implementation of taboo search a s an iterative search method, every best-known solution to classical p roblems was found. The first partition method (based on a partition in to polar regions) is appropriate for Euclidean problems whose cities a re regularly distributed around a central depot. The second partition method is suitable for any problem and is based on the arborescence bu ilt from the shortest paths from any city to the depot. Finally, solut ions that are believed to be optimum are given for problems generated on a grid. (C) 1993 by John Wiley & Sons, Inc.