An Efficient Implementation of a Static Move Descriptor-based Local Search Heuristic

Onne Beek, Birger Raa*, Wout Dullaert, Daniele Vigo

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

121 Downloads (Pure)


This paper proposes several strategies for a more efficient implementation of the concept of Static Move Descriptors (SMDs), a recently developed technique that significantly speeds up Local Search-based algorithms. SMDs exploit the fact that each local search step affects only a small part of the solution and allow for efficient tracking of changes at each iteration, such that unnecessary reevaluations can be avoided. The concept is highly effective at reducing computation times and is sufficiently generic to be applied in any Local Search-based algorithm. Despite its significant advantages, the design proposed in the literature suffers from high overhead and high implementational complexity. Our proposals lead to a much leaner and simpler implementation that offers better extendibility and significant further speedups of local search algorithms. We compare implementations for the Capacitated Vehicle Routing Problem (CVRP) - a well-studied, complex problem that serves as a benchmark for a wide variety of optimization techniques.

Original languageEnglish
Pages (from-to)1-10
Number of pages10
JournalComputers and Operations Research
Early online date13 Feb 2018
Publication statusPublished - Jun 2018


  • Efficient Local Search
  • Heuristic Priority Queue
  • Static Move Descriptors
  • Vehicle Routing


Dive into the research topics of 'An Efficient Implementation of a Static Move Descriptor-based Local Search Heuristic'. Together they form a unique fingerprint.

Cite this