Simulated Annealing

The core probabilistic decision rule that determines whether a new candidate solution is accepted. If the new solution is better, it is always accepted. If it is worse, it is accepted with a probability of exp(-ΔE / T), where ΔE is the magnitude of the objective function degradation and T is the current temperature. This allows the algorithm to climb out of local minima early in the search when T is high.

The function controlling the rate at which the temperature parameter T decreases over iterations. Common schedules include:

• Exponential decay: T_k = α * T_{k-1}, where α is typically between 0.8 and 0.99
• Logarithmic cooling: T_k = T_0 / log(1 + k), which guarantees convergence to the global optimum but is impractically slow
• Linear decay: T_k = T_0 - η * k The schedule directly balances exploration (high T) against exploitation (low T).

A problem-specific perturbation function that generates a new candidate solution from the current state. In the context of the Vehicle Routing Problem, common neighborhood operators include:

• 2-opt: Reversing a segment of a route to eliminate crossing edges
• Or-opt: Relocating a short segment of consecutive customers to a different position
• Cross-exchange: Swapping segments between two distinct routes The efficiency of the search depends heavily on the design of this operator.

Under a logarithmic cooling schedule, simulated annealing is proven to converge asymptotically to the global optimum with probability 1, a property derived from the theory of inhomogeneous Markov chains. In practice, faster cooling schedules are used, trading the theoretical guarantee for computational feasibility. The algorithm is particularly effective on problems with a rugged fitness landscape containing many local optima, such as VLSI circuit placement and complex scheduling.

Critical hyperparameters that must be calibrated for effective performance:

• Initial temperature (T_0): Set high enough that approximately 80% of worse moves are initially accepted, ensuring sufficient exploration
• Final temperature (T_f): A stopping threshold where the system is considered frozen
• Iterations per temperature level: The number of neighborhood moves attempted before reducing T, often set proportional to the problem size
• Restart strategies: Reheating the system to escape deep local minima if no improvement is found after a set number of iterations

Simulated annealing is distinguished from related approaches by its single-solution trajectory and explicit temperature mechanism:

• vs. Tabu Search: SA uses stochastic acceptance of worse moves, while Tabu Search uses deterministic memory structures to forbid recently visited solutions
• vs. Genetic Algorithms: SA maintains and iterates on a single solution rather than a population, making it more memory-efficient but lacking implicit parallelism
• vs. ALNS: Adaptive Large Neighborhood Search uses a destroy-and-repair paradigm with adaptive weight adjustment, while SA relies purely on perturbation and the Metropolis criterion

A high-level, problem-independent algorithmic framework that guides subordinate heuristics to efficiently explore a search space. Simulated Annealing is a classic single-solution trajectory-based metaheuristic, contrasting with population-based methods like Genetic Algorithms. Metaheuristics trade guaranteed optimality for computational speed, making them essential for NP-hard routing problems where exact solvers fail to converge within operational time limits.

A population-based metaheuristic inspired by natural selection. Unlike Simulated Annealing's single-solution trajectory, Genetic Algorithms maintain a population of candidate routes, combining them via crossover and mutation operators.

• Exploration: Genetic Algorithms explore the search space more broadly through population diversity.
• Exploitation: Simulated Annealing's cooling schedule provides a more controlled convergence.
• Hybridization: Modern solvers often embed Simulated Annealing as a local search operator within a Genetic Algorithm framework.

A deterministic metaheuristic that uses adaptive memory structures to avoid cycling back to previously visited solutions. Unlike Simulated Annealing's probabilistic acceptance of worse solutions, Tabu Search systematically prohibits recently explored moves.

• Tabu List: A short-term memory that records forbidden transitions.
• Aspiration Criteria: Overrides tabu status if a move leads to a new global best.
• Contrast: Simulated Annealing relies on stochastic escape from local optima; Tabu Search uses explicit memory to force exploration.

An iterative metaheuristic that repeatedly destroys and repairs parts of a solution. ALNS is particularly effective for complex Vehicle Routing Problems with many constraints.

• Destroy Operators: Remove a subset of stops from a route (e.g., random removal, worst-cost removal).
• Repair Operators: Reinsert removed stops using greedy or regret-based heuristics.
• Adaptive Layer: Tracks operator performance and selects the most effective destroy/repair pairs based on historical success.
• Synergy: Simulated Annealing is often used as the acceptance criterion within ALNS, deciding whether to keep a newly repaired solution.

An exact optimization model with a linear objective and linear constraints where some variables are restricted to integer values. Solved using algorithms like Branch and Bound.

• Guarantee: MILP solvers like Gurobi and CPLEX provide provably optimal solutions or a certified optimality gap.
• Limitation: For large-scale, real-time routing instances, MILP may fail to find a feasible solution within seconds.
• Complement: Simulated Annealing provides fast, near-optimal solutions when MILP is computationally intractable, often serving as a warm-start for exact solvers.

The process of simultaneously optimizing conflicting objectives, such as minimizing cost while maximizing service level. Simulated Annealing can be extended to multi-objective problems through several strategies:

• Weighted Sum: Combine objectives into a single scalar function with user-defined weights.
• Pareto Simulated Annealing: Maintain an archive of non-dominated solutions and use dominance-based acceptance criteria.
• Pareto Frontier: The resulting set of trade-off solutions where improving one objective degrades another, enabling decision-makers to select the optimal balance.