Academic Bibliography

 Search 200 years of publications by Ghent University researchers.
Advanced search
1 file | 662.59 KB
Add to list
  1. Search results
  2. An efficient implementation of a stat...

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

Onne Beek (UGent) , Birger Raa (UGent) , Wout Dullaert and Daniele Vigo
(2018) COMPUTERS & OPERATIONS RESEARCH. 94. p.1-10
Author
Organization
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, Vehicle Routing, Static Move Descriptors, Heuristic Priority Queue

Downloads

  • Download
    (...).pdf
    • full text
    • |
    • UGent only
    • |
    • PDF
    • |
    • 662.59 KB

Citation

Please use this url to cite or link to this publication:

MLA
Beek, Onne, et al. “An Efficient Implementation of a Static Move Descriptor-Based Local Search Heuristic.” COMPUTERS & OPERATIONS RESEARCH, vol. 94, Elsevier BV, 2018, pp. 1–10, doi:10.1016/j.cor.2018.01.006.
APA
Beek, O., Raa, B., Dullaert, W., & Vigo, D. (2018). An efficient implementation of a static move descriptor-based local search heuristic. COMPUTERS & OPERATIONS RESEARCH, 94, 1–10. https://doi.org/10.1016/j.cor.2018.01.006
Chicago author-date
Beek, Onne, Birger Raa, Wout Dullaert, and Daniele Vigo. 2018. “An Efficient Implementation of a Static Move Descriptor-Based Local Search Heuristic.” COMPUTERS & OPERATIONS RESEARCH 94: 1–10. https://doi.org/10.1016/j.cor.2018.01.006.
Chicago author-date (all authors)
Beek, Onne, Birger Raa, Wout Dullaert, and Daniele Vigo. 2018. “An Efficient Implementation of a Static Move Descriptor-Based Local Search Heuristic.” COMPUTERS & OPERATIONS RESEARCH 94: 1–10. doi:10.1016/j.cor.2018.01.006.
Vancouver
1.
Beek O, Raa B, Dullaert W, Vigo D. An efficient implementation of a static move descriptor-based local search heuristic. COMPUTERS & OPERATIONS RESEARCH. 2018;94:1–10.
IEEE
[1]
O. Beek, B. Raa, W. Dullaert, and D. Vigo, “An efficient implementation of a static move descriptor-based local search heuristic,” COMPUTERS & OPERATIONS RESEARCH, vol. 94, pp. 1–10, 2018.
@article{8559163,
  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.}},
  author       = {{Beek, Onne and Raa, Birger and Dullaert, Wout and Vigo, Daniele}},
  issn         = {{0305-0548}},
  journal      = {{COMPUTERS & OPERATIONS RESEARCH}},
  keywords     = {{Efficient Local Search,Vehicle Routing,Static Move Descriptors,Heuristic Priority Queue}},
  language     = {{eng}},
  pages        = {{1--10}},
  publisher    = {{Elsevier BV}},
  title        = {{An efficient implementation of a static move descriptor-based local search heuristic}},
  url          = {{http://doi.org/10.1016/j.cor.2018.01.006}},
  volume       = {{94}},
  year         = {{2018}},
}
Altmetric
View in Altmetric
Web of Science
Times cited: