Premium
Parallel iterative search methods for vehicle routing problems
Author(s) -
Taillard É.
Publication year - 1993
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230230804
Subject(s) - partition (number theory) , mathematical optimization , computer science , vehicle routing problem , iterative method , grid , shortest path problem , euclidean geometry , routing (electronic design automation) , algorithm , mathematics , combinatorics , theoretical computer science , graph , computer network , geometry
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.