An efficient implementation of a static move descriptor-based local search heuristic

Onne Beek, Birger Raa, Wout Dullaert

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

The Vehicle Routing Problem is a well-studied problem. Since its formulation in 1959, a great number of powerful solution methods have been designed. However, for large scale problems, few techniques are able to consistently find good solutions within an acceptable time limit. In this paper, the concept of Static Move Descriptors, a recently published technique for speeding up Local Search algorithms, is analyzed and an efficient implementation is suggested. We describe several changes that significantly improve the performance of an SMD-based Local Search algorithm. The result is an efficient and flexible technique that can easily be adapted to different metaheuristics and can be combined with other complexity reduction strategies.

LanguageEnglish
Title of host publicationICORES 2013 - Proceedings of the 2nd International Conference on Operations Research and Enterprise Systems
Pages277-282
Number of pages6
Publication statusPublished - 2013
Event2nd International Conference on Operations Research and Enterprise Systems, ICORES 2013 - Barcelona, Spain
Duration: 16 Feb 201318 Feb 2013

Conference

Conference2nd International Conference on Operations Research and Enterprise Systems, ICORES 2013
CountrySpain
CityBarcelona
Period16/02/1318/02/13

Fingerprint

Heuristics
Local search
Metaheuristics
Vehicle routing problem

Keywords

  • Efficient local search
  • Heuristic priority queue
  • Static move descriptors
  • Vehicle routing

Cite this

Beek, O., Raa, B., & Dullaert, W. (2013). An efficient implementation of a static move descriptor-based local search heuristic. In ICORES 2013 - Proceedings of the 2nd International Conference on Operations Research and Enterprise Systems (pp. 277-282)
Beek, Onne ; Raa, Birger ; Dullaert, Wout. / An efficient implementation of a static move descriptor-based local search heuristic. ICORES 2013 - Proceedings of the 2nd International Conference on Operations Research and Enterprise Systems. 2013. pp. 277-282
@inproceedings{ae76324234674cc28fbbf7714e62285f,
title = "An efficient implementation of a static move descriptor-based local search heuristic",
abstract = "The Vehicle Routing Problem is a well-studied problem. Since its formulation in 1959, a great number of powerful solution methods have been designed. However, for large scale problems, few techniques are able to consistently find good solutions within an acceptable time limit. In this paper, the concept of Static Move Descriptors, a recently published technique for speeding up Local Search algorithms, is analyzed and an efficient implementation is suggested. We describe several changes that significantly improve the performance of an SMD-based Local Search algorithm. The result is an efficient and flexible technique that can easily be adapted to different metaheuristics and can be combined with other complexity reduction strategies.",
keywords = "Efficient local search, Heuristic priority queue, Static move descriptors, Vehicle routing",
author = "Onne Beek and Birger Raa and Wout Dullaert",
year = "2013",
language = "English",
isbn = "9789898565402",
pages = "277--282",
booktitle = "ICORES 2013 - Proceedings of the 2nd International Conference on Operations Research and Enterprise Systems",

}

Beek, O, Raa, B & Dullaert, W 2013, An efficient implementation of a static move descriptor-based local search heuristic. in ICORES 2013 - Proceedings of the 2nd International Conference on Operations Research and Enterprise Systems. pp. 277-282, 2nd International Conference on Operations Research and Enterprise Systems, ICORES 2013, Barcelona, Spain, 16/02/13.

An efficient implementation of a static move descriptor-based local search heuristic. / Beek, Onne; Raa, Birger; Dullaert, Wout.

ICORES 2013 - Proceedings of the 2nd International Conference on Operations Research and Enterprise Systems. 2013. p. 277-282.

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - An efficient implementation of a static move descriptor-based local search heuristic

AU - Beek, Onne

AU - Raa, Birger

AU - Dullaert, Wout

PY - 2013

Y1 - 2013

N2 - The Vehicle Routing Problem is a well-studied problem. Since its formulation in 1959, a great number of powerful solution methods have been designed. However, for large scale problems, few techniques are able to consistently find good solutions within an acceptable time limit. In this paper, the concept of Static Move Descriptors, a recently published technique for speeding up Local Search algorithms, is analyzed and an efficient implementation is suggested. We describe several changes that significantly improve the performance of an SMD-based Local Search algorithm. The result is an efficient and flexible technique that can easily be adapted to different metaheuristics and can be combined with other complexity reduction strategies.

AB - The Vehicle Routing Problem is a well-studied problem. Since its formulation in 1959, a great number of powerful solution methods have been designed. However, for large scale problems, few techniques are able to consistently find good solutions within an acceptable time limit. In this paper, the concept of Static Move Descriptors, a recently published technique for speeding up Local Search algorithms, is analyzed and an efficient implementation is suggested. We describe several changes that significantly improve the performance of an SMD-based Local Search algorithm. The result is an efficient and flexible technique that can easily be adapted to different metaheuristics and can be combined with other complexity reduction strategies.

KW - Efficient local search

KW - Heuristic priority queue

KW - Static move descriptors

KW - Vehicle routing

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

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

M3 - Conference contribution

SN - 9789898565402

SP - 277

EP - 282

BT - ICORES 2013 - Proceedings of the 2nd International Conference on Operations Research and Enterprise Systems

ER -

Beek O, Raa B, Dullaert W. An efficient implementation of a static move descriptor-based local search heuristic. In ICORES 2013 - Proceedings of the 2nd International Conference on Operations Research and Enterprise Systems. 2013. p. 277-282