computer science//algorithms//local search

2026-02-21

Local search is an optimization method that starts from a complete solution and keeps improving it by small changes, accepting a change when it lowers the cost, and it is used to polish the fast answer of a greedy algorithm in task assignment, vehicle routing and production scheduling. The change is problem-specific: swap the tasks of two robots, move one drone from one fire to another, reverse a stretch of a delivery route (the **2-opt** move of routing).

Take a dispatcher that has just assigned forty warehouse robots to sixty orders by giving each robot its nearest free order. Local search then tries every pair of robots: would swapping their orders shorten the total distance? Each improving swap is applied, and the loop repeats until no swap helps. Every intermediate assignment is valid, so the dispatcher can send the current one whenever the next cycle starts, which makes greedy followed by local search a natural anytime algorithm; most of the improvement tends to come in the first few passes.

It stops at a local optimum, a solution no single change can improve even though a better one exists several changes away. Metaheuristics such as simulated annealing or tabu search accept some worsening moves to escape, and routing libraries such as Google's OR-Tools combine them with local search; none of them guarantees the optimum.

It needs nothing but a way to evaluate the cost, which makes it the tool of choice for NP-hard problems with messy costs, such as weapon-target assignment in real time. When the problem has structure an exact solver can exploit (the one-to-one assignment problem), the exact solver is faster and certain.

Gradient descent is local search over continuous parameters, with the gradient choosing the move; on a discrete set there is no gradient, only neighbours to try.