Guided Local Search

Imagine you are hiking in fog and trying to find the lowest valley. You walk downhill until you can go no further — but the hollow you are standing in might not be the deepest one. You are stuck in a local optimum, and without information about the wider landscape you have no way to know.

Local search algorithms face exactly this problem. They tweak a candidate solution one step at a time, accepting changes only when they improve the objective. They are fast and practical — but they routinely stop at local optima that are far from the global best.

Guided Local Search (GLS), introduced by Christos Voudouris and Edward Tsang in 1995, adds a simple but powerful twist: every time the search gets stuck, it penalizes the features of the current solution. Penalized features carry an extra cost in future evaluations, so the optimum the algorithm was happy with a moment ago suddenly looks worse — and the search moves on.

The result is a meta-heuristic: a strategy that guides an underlying local search without knowing the problem's structure in advance. GLS has found near-optimal solutions for some of the hardest combinatorial problems we know, including the Travelling Salesman Problem.

The landscape below has several valleys. Plain local search drops into the nearest one and stops. Guided Local Search adds penalties to the features it keeps visiting — raising their effective cost and forcing the search out of a trap.

<!-- {{c_html_intro}} -->
<p class="hint">{{hint_para}}</p>
<div id="landscape-wrap">
  <canvas id="landscape" width="500" height="140"></canvas>
</div>
<div id="penalty-row">
  <span class="row-label">{{label_penalties}}</span>
  <div id="penalty-cells"></div>
</div>
<div id="pos-row">
  <span class="row-label">{{label_position}}</span>
  <span id="pos-display">—</span>
</div>
<div class="status" id="status">{{status_ready}}</div>
<div class="btns">
  <button id="btn-plain" type="button">{{btn_plain}}</button>
  <button id="btn-gls" type="button">{{btn_gls}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
#landscape-wrap { overflow-x: auto; margin-bottom: .4rem; }
canvas { display: block; max-width: 100%; border-radius: 8px; background: #f4f7fa; }
#penalty-row, #pos-row { display: flex; align-items: center; gap: .5rem; margin: .25rem 0; font-size: .85rem; }
.row-label { font-weight: 600; color: #555; min-width: 80px; }
#penalty-cells { display: flex; gap: 3px; flex-wrap: wrap; }
.pcell { width: 32px; height: 26px; display: flex; align-items: center; justify-content: center;
         font: 700 12px ui-monospace, monospace; border-radius: 5px;
         background: #e8eef3; border: 1px solid #cdd9e3; color: #1d3557; }
.pcell.active { background: #e63946; border-color: #c92f3c; color: #fff; }
#pos-display { font-weight: 700; font-size: .95rem; color: #1d3557; }
.status { font-size: .95rem; font-weight: 600; margin: .4rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: not-allowed; }

// Code not found

Click Run plain local search to see it stop at a local optimum. Then click Run guided local search to watch penalties accumulate (shown in the penalty row) and the search escape to a deeper valley. Each penalty increment raises the augmented cost of the current position, making a neighbor look better and causing a move.

GLS does not solve hard problems in polynomial time — it is a heuristic, not an exact algorithm. Its complexity picture has several layers:

• Each local search step runs in the time the underlying move evaluation takes — often $O(1)$ or $O(n)$ with incremental tricks, making individual steps very cheap.
• No guarantee of optimality. Because the search landscape for NP-hard problems like the Travelling Salesman Problem has exponentially many local optima, GLS cannot promise to find the global best. It can, however, escape many of the traps that plain local search cannot.
• The penalty function is the key. At each local optimum, GLS picks the feature $i$ that maximizes $\frac{c_i}{1 + p_i}$, where $c_i$ is the feature's original cost and $p_i$ its current penalty count. This utility measure favors features that are expensive and have been penalized least — intuitively, the ones most "worth" escaping. The augmented cost used by local search becomes $g(s) = f(s) + \lambda \sum_i p_i \cdot I_i(s)$, where $\lambda$ balances exploration against exploitation.
• Empirical near-optimality. On benchmark TSP instances with thousands of cities, GLS with Lin–Kernighan moves finds solutions within 1–2% of the known optimum — competitive with the best exact methods for practical purposes.
• Open questions. There is no general theorem about how many penalty steps GLS needs to escape all local optima on an arbitrary landscape. The interaction between the penalty parameter $\lambda$ and the problem instance is an active research question.

The broader takeaway: GLS is a practical answer to the limits of computation. When P vs NP tells us we cannot expect an efficient exact algorithm, penalty-guided search is one of our best tools for finding solutions that are good enough.

Guided Local Search is not a toy — it is used in real systems that need good solutions to NP-hard problems fast:

• Vehicle routing: GLS and its variants drive many state-of-the-art solvers for the Vehicle Routing Problem, which underlies delivery logistics for millions of packages a day.
• Job scheduling: penalizing bottleneck operations guides the search away from schedules that repeatedly overload the same machine.
• Network design: penalizing expensive or congested links helps find low-cost network topologies without exhaustive enumeration.
• Constraint satisfaction: penalty-based guidance is a natural fit for problems where violating constraints can be treated as costly features — the same idea as in SAT solvers that use clause-weight penalties.
• Combinatorial auctions: bidding configurations are solutions; GLS has been applied to winner-determination problems where exact algorithms are too slow.

Whenever you face a problem where local search gets stuck and exact methods are too slow, GLS is a strong first meta-heuristic to reach for — alongside simulated annealing and tabu search, which share the goal of escaping local optima but use different mechanisms.

Guided Local Search has a beautiful philosophy: instead of pretending a local optimum is good enough, penalize it. Every trap the algorithm falls into leaves a mark — a small increment to the cost of the features that defined that trap — and those marks collectively reshape the landscape so the next search runs differently.

No theorem guarantees this works in the worst case. But for the hard combinatorial problems that matter in practice — routing, scheduling, network design — GLS consistently finds solutions that are within a few percent of the best known, orders of magnitude faster than any exact algorithm could.

That is the pragmatic lesson when P vs NP blocks the door to efficient exact solutions: accumulate knowledge about where you have been, penalize the features that kept you there, and let the augmented landscape guide you somewhere better.