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

Onne Beek, Birger Raa, Wout Dullaert, Daniele Vigo

Research output: Contribution to JournalArticleAcademicpeer-review

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.

LanguageEnglish
Pages1-10
Number of pages10
JournalComputers and Operations Research
Volume94
Issue numberJune
DOIs
StatePublished - 2018

Fingerprint

Efficient Implementation
Local Search
Descriptors
Heuristics
Vehicle routing
Local Search Algorithm
Vehicle Routing Problem
Optimization Techniques
Speedup
Benchmark
Iteration
Local search
Concepts

Keywords

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

Cite this

@article{ae008099f093417f93fd0f38a2bc0ade,
title = "An Efficient Implementation of a Static Move Descriptor-based Local Search Heuristic",
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.",
keywords = "Efficient Local Search, Heuristic Priority Queue, Static Move Descriptors, Vehicle Routing",
author = "Onne Beek and Birger Raa and Wout Dullaert and Daniele Vigo",
year = "2018",
doi = "10.1016/j.cor.2018.01.006",
language = "English",
volume = "94",
pages = "1--10",
journal = "Computers and Operations Research",
issn = "0305-0548",
publisher = "Elsevier Limited",
number = "June",

}

An Efficient Implementation of a Static Move Descriptor-based Local Search Heuristic. / Beek, Onne; Raa, Birger; Dullaert, Wout; Vigo, Daniele.

In: Computers and Operations Research, Vol. 94, No. June, 2018, p. 1-10.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

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

AU - Beek,Onne

AU - Raa,Birger

AU - Dullaert,Wout

AU - Vigo,Daniele

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

KW - Efficient Local Search

KW - Heuristic Priority Queue

KW - Static Move Descriptors

KW - Vehicle Routing

UR - http://www.scopus.com/inward/record.url?scp=85041821999&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85041821999&partnerID=8YFLogxK

U2 - 10.1016/j.cor.2018.01.006

DO - 10.1016/j.cor.2018.01.006

M3 - Article

VL - 94

SP - 1

EP - 10

JO - Computers and Operations Research

T2 - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

IS - June

ER -