Adaptive Large Neighborhood Search (ALNS)

The core learning mechanism of ALNS. Each destroy and repair heuristic is assigned a weight that reflects its historical performance. After a segment of iterations, weights are updated based on a scoring system that rewards heuristics for finding new global best solutions, improving the current solution, or enabling escape from local optima. A roulette-wheel selection principle then biases the choice of heuristics toward those with higher weights, ensuring the search strategy self-tunes to the specific problem instance.

These heuristics partially dismantle a feasible solution by removing a subset of its components—such as customer visits in a routing context. The degree of destruction is typically controlled by a parameter defining the percentage of the solution to remove. Common destroy operators include:

• Random Removal: Randomly selects components to remove, promoting diversification.
• Worst Removal: Removes components with the highest contribution to the objective function cost, focusing the repair on inefficient parts of the solution.
• Shaw Removal: Removes components that are related based on a similarity metric (e.g., proximity, demand), creating a correlated sub-problem for the repair phase.

These heuristics reconstruct a complete, feasible solution by reinserting the removed components. The repair strategy is critical for intensification, as it seeks to place the removed elements in positions that improve the overall objective. Common repair operators include:

• Greedy Insertion: Iteratively inserts each removed component into the position that minimizes the marginal increase in cost.
• Regret-k Insertion: A look-ahead heuristic that calculates the difference in cost between the best and k-th best insertion positions, prioritizing components with high regret values to avoid myopic decisions.

ALNS typically uses a Simulated Annealing (SA) master framework to decide whether a newly generated solution is accepted. The SA criterion accepts all improving solutions and, with a probability determined by a decreasing temperature parameter, accepts worse solutions. This mechanism allows the search to escape local optima early in the process while converging to a high-quality solution as the temperature cools. The initial temperature and cooling rate are critical hyperparameters that control the exploration-exploitation balance.

The adaptive layer operates in discrete segments of iterations. Within a segment, heuristics accumulate scores based on their performance. A typical scoring scheme awards:

• σ₁: High reward for finding a new global best solution.
• σ₂: Moderate reward for improving the current solution.
• σ₃: Low reward for accepting a worse solution that diversifies the search. At the end of a segment, new weights are calculated using a reaction factor that controls how quickly the algorithm adapts to recent performance, balancing historical weight with the new segment score.

To prevent the search from becoming overly deterministic and converging prematurely, ALNS often injects controlled noise into the objective function evaluation during repair. When calculating insertion costs, a random noise term is added, temporarily distorting the objective landscape. This technique, known as blinkered evaluation, encourages the exploration of structurally different solutions that might otherwise be ignored by a purely greedy repair operator, ultimately leading to more robust final solutions.

ALNS is a prime example of a metaheuristic—a high-level, problem-independent algorithmic framework designed to guide subordinate heuristics. Unlike exact methods, metaheuristics trade guaranteed optimality for the ability to find high-quality solutions to NP-hard problems like the Vehicle Routing Problem (VRP) in a practical timeframe. They orchestrate the interplay between exploration (searching new regions of the solution space) and exploitation (refining known good solutions).

The acceptance criterion most commonly paired with ALNS. Simulated Annealing is a probabilistic technique that accepts a worse solution with a probability that decreases over time, mimicking the cooling of metal. This allows ALNS to escape local optima early in the search. The temperature schedule—controlling how quickly the algorithm becomes greedy—is a critical hyperparameter that balances exploration and exploitation.

Real-world logistics rarely optimize a single metric. ALNS can be extended to handle multi-objective optimization, simultaneously minimizing cost, maximizing service level, and reducing carbon emissions. This is often achieved by using a weighted sum of objectives in the acceptance criterion or by maintaining an archive of non-dominated solutions that form the Pareto Frontier, allowing a dispatcher to choose the ideal trade-off.

A declarative paradigm often used in conjunction with ALNS. While ALNS provides the high-level search strategy, Constraint Programming can act as a powerful feasibility checker or repair engine. When an ALNS destroy operator removes a set of visits, a CP solver can be invoked to re-insert them while guaranteeing that all complex temporal and capacity constraints are satisfied, combining the strengths of both approaches.