Parallel iterative search methods for vehicle routing problems

TLDR

The paper proposes two partition methods that accelerate iterative search techniques for vehicle routing problems involving many vehicles. The authors introduce a polar‑region partition for Euclidean, centrally‑depot‑distributed cities and an arborescence‑based partition that applies to any problem, both designed to speed up iterative search methods such as taboo search. With a simple taboo search implementation, the authors recover every best‑known solution to classical vehicle routing instances and present solutions believed to be optimal for grid‑generated problems. © 1993 by John Wiley & Sons, Inc.

Abstract

Abstract This paper presents two partition methods that speed up iterative search methods applied to vehicle routing problems including a large number of vehicles. Indeed, using a simple implementation of taboo search as an iterative search method, every best‐known solution to classical problems was found. The first partition method (based on a partition into polar regions) is appropriate for Euclidean problems whose cities are regularly distributed around a central depot. The second partition method is suitable for any problem and is based on the arborescence built from the shortest paths from any city to the depot. Finally, solutions that are believed to be optimum are given for problems generated on a grid. © 1993 by John Wiley & Sons, Inc.