variable-neighborhood-search

Variable Neighborhood Search

You are an expert in variable neighborhood search (VNS), the metaheuristic family built on systematic change of neighborhood structures: variable neighborhood descent (VND), reduced VNS (RVNS), basic VNS (BVNS), general VNS (GVNS), skewed VNS (SVNS), and variable neighborhood decomposition search (VNDS). This skill covers neighborhood ordering, shaking design, neighborhood-change rules, and complete worked implementations on the p-median problem and the capacitated vehicle routing problem (CVRP). Use the framework below to pick the right family member, assemble it from reusable components, and validate the result.

Initial Assessment

Establish the following before designing or coding any VNS:

• Representation. Permutation, subset selection, partition into routes, or assignment? The representation fixes which neighborhood structures exist at all. If the representation itself is open, settle it first (see solution-encodings in this repository's operator skills).
• Move inventory. List every candidate move type (swap, relocate, 2-opt, k-interchange, segment exchange), its neighborhood size, and the cost of evaluating one move. VNS pays off only when at least two genuinely different move types are available; with a single strong move type, iterated-local-search is the simpler design.
• Delta evaluation. Determine for each move whether the objective change is computable in O(1) or O(n) without re-evaluating the whole solution. A VND scanning O(n^2) moves with full O(n) re-evaluation per move is unusable beyond toy sizes; see local-search-and-neighborhoods for delta-evaluation patterns.
• Constraint structure. Which constraints are hard? Can shaking and descent stay feasible by construction (capacity-checked insertions), or is a repair step or penalty needed? Feasible-by-construction is strongly preferred inside VNS because the neighborhood-change logic assumes comparable objective values.
• Instance size and time budget. Number of decision elements (clients, customers, jobs), wall-clock budget per run, and number of runs (tuning plus final experiments). This decides best- vs first-improvement, candidate lists, and whether VNDS is needed.
• Quality target. Gap to best-known solutions, gap to an exact bound, or simply "beat the current heuristic under equal budget"? The target determines how much engineering (candidate lists, caching) is justified.
• Baseline. Confirm what already exists: a construction heuristic, a plain local search, an ILS. VNS must be compared against the strongest of these under the same time budget, with the same underlying moves.
• Exact reference for validation. On small instances, an exact model (Gurobi, HiGHS) or exhaustive enumeration should confirm that the VNS reaches the optimum. Plan this check before scaling up.
• Reproducibility requirements. Seeded np.random.default_rng, and a stopping rule that is reproducible (shake budget) versus one that is fair across machines (wall clock). Decide which the deliverable needs; record both.
• Data format. Coordinates versus explicit distance matrix; symmetric or asymmetric costs; integer or float objective (sets the improvement tolerance).
• Output expectations. One good solution, or a statistical comparison across seeds and instances with convergence evidence? This changes how much instrumentation the implementation needs from the start.