Adaptive LNS (ALNS)

Unlike static LNS, ALNS maintains a weighted portfolio of multiple destroy and repair heuristics. After each iteration, the algorithm updates the probability of selecting each operator based on a scoring system. Operators that discover new global best solutions receive higher scores, while those that fail to improve the incumbent are penalized. This roulette-wheel selection mechanism ensures the search automatically biases itself toward the most effective heuristics for the specific problem instance.

ALNS employs diverse destruction heuristics to remove a subset of customer visits from a route, creating a partial solution. Common operators include:

• Random Removal: Randomly selects nodes to remove, promoting diversification.
• Worst Removal: Removes nodes with the highest contribution to total cost, focusing on local optimization.
• Shaw Removal: Removes nodes that are similar in terms of location, demand, or time window, creating structured, easier-to-repair gaps.
• Cluster Removal: Divides the route into spatial clusters and removes an entire cluster.

Repair heuristics reinsert the removed nodes back into the partial solution to create a new, feasible candidate. The portfolio typically includes:

• Greedy Insertion: Inserts each node at the position that minimizes the marginal cost increase.
• Regret-k Insertion: Considers not just the best insertion cost, but the difference between the best and k-th best insertion positions, prioritizing nodes with high regret to avoid myopic decisions.
• Noise Injection: Adds a randomized perturbation to insertion costs to prevent the search from becoming overly deterministic.

ALNS typically uses a Simulated Annealing (SA) framework to decide whether to accept a new candidate solution. If the new solution is better than the current one, it is always accepted. If it is worse, it is accepted with a probability that depends on the degree of deterioration and a temperature parameter that decreases over time. This mechanism allows the search to escape local optima early on while converging to a high-quality solution as the system cools.

The search is divided into segments of consecutive iterations. During a segment, operators accumulate scores based on their performance. At the end of each segment, the weights are updated using a reaction factor that controls how quickly the algorithm adapts to recent performance. A high reaction factor makes the search highly responsive to the latest operator success, while a low factor provides more stability and prevents a single lucky improvement from dominating the selection.

ALNS is highly effective for complex Vehicle Routing Problem (VRP) variants common in last-mile delivery. It handles time windows, heterogeneous fleets, and pickup-and-delivery constraints naturally through specialized operators. For example, a Shaw removal operator can be designed to remove customers with overlapping time windows, while a regret-3 insertion operator ensures that urgent deliveries are prioritized. This flexibility makes ALNS the algorithm of choice for solving large-scale, real-world routing instances with thousands of stops.

The foundational framework that ALNS extends. LNS iteratively improves a solution by applying a destroy operator to remove a large portion of the solution and a repair operator to reconstruct it. This allows the search to escape local optima by making substantial structural changes in each iteration. Unlike local search methods that make small, incremental moves, LNS explores a much wider neighborhood.

The two fundamental components manipulated by ALNS. Destroy operators remove elements from the current solution—common examples include:

• Random Removal: Deletes elements arbitrarily
• Worst Removal: Eliminates elements with the highest cost contribution
• Shaw Removal: Removes elements that are similar to each other based on a relatedness metric

Repair operators reinsert the removed elements, typically using greedy or regret-based heuristics that minimize insertion cost.

The defining mechanism that distinguishes ALNS from standard LNS. Each operator is assigned a weight that determines its selection probability. After each iteration, the weight is updated based on a scoring system:

• High reward for finding a new global best solution
• Medium reward for improving the current solution
• Low reward for accepting a worse solution (diversification)
• No reward for rejected solutions

This creates a self-tuning search that automatically favors effective operators.

ALNS typically uses a simulated annealing (SA) acceptance criterion to decide whether to keep a new solution. The probability of accepting a worse solution is governed by the formula exp(-(f(s') - f(s)) / T), where T is the current temperature. The temperature starts high (accepting many worse solutions for exploration) and gradually cools (becoming more selective). This balances exploration early in the search with exploitation later.

The philosophical foundation of ALNS, introduced by Schrimpf et al. (2000). The core insight is that partially destroying a good solution and rebuilding it often yields better results than incremental improvement. This principle is particularly effective for highly constrained combinatorial problems where feasible solutions are sparse. The 'ruin' phase creates space for structural innovation, while the 'recreate' phase leverages problem-specific heuristics to restore feasibility.