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 language | English |
---|---|
Pages (from-to) | 1-10 |
Number of pages | 10 |
Journal | Computers and Operations Research |
Volume | 94 |
Early online date | 13 Feb 2018 |
DOIs | |
Publication status | Published - 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.
Funders | Funder number |
---|---|
Air Force Office of Scientific Research | FA9550-17-1-0234 |
Keywords
- Efficient Local Search
- Heuristic Priority Queue
- Static Move Descriptors
- Vehicle Routing