Authors: Crainic, Teodor Gabriel
Gendreau, Michel
Hansen, Pierre
Mladenović, Nenad 
Title: Cooperative parallel variable neighborhood search for the p-median
Journal: Journal of Heuristics
Volume: 10
Issue: 3
First page: 293
Last page: 314
Issue Date: 1-Jan-2004
Rank: M22
ISSN: 1381-1231
DOI: 10.1023/B:HEUR.0000026897.40171.1a
We propose a cooperative multi-search method for the Variable Neighborhood Search (VNS) meta-heuristic based on the central-memory mechanism that has been successfully applied to a number of difficult combinatorial problems. In this approach, several independent VNS meta-heuristics cooperate by asynchronously exchanging information about the best solutions identified so far, thus conserving the simplicity of the original, sequential VNS ideas. The p-median problem (PM) serves as test case. Extensive experimentations have been conducted on the classical TSPLIB benchmark problem instances with up to 11948 customers and 1000 medians, without any particular calibration of the parallel method. The results indicate that, compared to sequential VNS, the cooperative strategy yields significant gains in terms of computation time without a loss in solution quality.
Keywords: Cooperative search | p-median problem | Parallel optimization | Variable Neighborhood Search
Publisher: Springer Link

Show full item record


checked on May 16, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.