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

156 Downloads (Pure)

Abstract

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
Volume94
Early online date13 Feb 2018
DOIs
Publication statusPublished - Jun 2018

Funding

This research is based upon work supported by the Air Force Office of Scientific Research under award number FA9550-17-1-0234.

FundersFunder number
Air Force Office of Scientific ResearchFA9550-17-1-0234

    Keywords

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

    Fingerprint

    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