Parallel local search

M.G.A. Verhoeven, E.H.L. Aarts

Research output: Contribution to journalArticleScientificpeer-review

Abstract

We present a survey of parallel local search algorithms in which we review the concepts that can be used to incorporate parallelism into local search. For this purpose we distinguish between single-walk and multiple-walk parallel local search and between asynchronous and synchronous parallelism. Within the class of single-walk algorithms we differentiate between multiple-step and single-step parallelism. To describe parallel local search we introduce the concepts of hyper neighborhood structures and distributed neighborhood structures. Furthermore, we present templates that capture most of the parallel local search algorithms proposed in the literature. Finally, we discuss some complexity issues related to parallel local search.
Original languageEnglish
Pages (from-to)43-65
Number of pages23
JournalJournal of Heuristics
Volume1
Issue number1
DOIs
Publication statusPublished - 1995
Externally publishedYes

Cite this

Verhoeven, M.G.A. ; Aarts, E.H.L. / Parallel local search. In: Journal of Heuristics. 1995 ; Vol. 1, No. 1. pp. 43-65.
@article{ab78091c1d1a49b6977be2191d3f1fd5,
title = "Parallel local search",
abstract = "We present a survey of parallel local search algorithms in which we review the concepts that can be used to incorporate parallelism into local search. For this purpose we distinguish between single-walk and multiple-walk parallel local search and between asynchronous and synchronous parallelism. Within the class of single-walk algorithms we differentiate between multiple-step and single-step parallelism. To describe parallel local search we introduce the concepts of hyper neighborhood structures and distributed neighborhood structures. Furthermore, we present templates that capture most of the parallel local search algorithms proposed in the literature. Finally, we discuss some complexity issues related to parallel local search.",
author = "M.G.A. Verhoeven and E.H.L. Aarts",
year = "1995",
doi = "10.1007/BF02430365",
language = "English",
volume = "1",
pages = "43--65",
journal = "Journal of Heuristics",
issn = "1381-1231",
publisher = "Springer Netherlands",
number = "1",

}

Parallel local search. / Verhoeven, M.G.A.; Aarts, E.H.L.

In: Journal of Heuristics, Vol. 1, No. 1, 1995, p. 43-65.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Parallel local search

AU - Verhoeven, M.G.A.

AU - Aarts, E.H.L.

PY - 1995

Y1 - 1995

N2 - We present a survey of parallel local search algorithms in which we review the concepts that can be used to incorporate parallelism into local search. For this purpose we distinguish between single-walk and multiple-walk parallel local search and between asynchronous and synchronous parallelism. Within the class of single-walk algorithms we differentiate between multiple-step and single-step parallelism. To describe parallel local search we introduce the concepts of hyper neighborhood structures and distributed neighborhood structures. Furthermore, we present templates that capture most of the parallel local search algorithms proposed in the literature. Finally, we discuss some complexity issues related to parallel local search.

AB - We present a survey of parallel local search algorithms in which we review the concepts that can be used to incorporate parallelism into local search. For this purpose we distinguish between single-walk and multiple-walk parallel local search and between asynchronous and synchronous parallelism. Within the class of single-walk algorithms we differentiate between multiple-step and single-step parallelism. To describe parallel local search we introduce the concepts of hyper neighborhood structures and distributed neighborhood structures. Furthermore, we present templates that capture most of the parallel local search algorithms proposed in the literature. Finally, we discuss some complexity issues related to parallel local search.

U2 - 10.1007/BF02430365

DO - 10.1007/BF02430365

M3 - Article

VL - 1

SP - 43

EP - 65

JO - Journal of Heuristics

JF - Journal of Heuristics

SN - 1381-1231

IS - 1

ER -