Simulated Annealing (SA)

The core 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 based on the Metropolis-Hastings algorithm:

• Probability Formula: P(accept) = exp(-ΔE / T)
• ΔE: The difference in objective function value (new_cost - current_cost).
• T: The current temperature parameter. This probabilistic acceptance is what allows the algorithm to climb out of local optima, especially at high temperatures.

The cooling schedule dictates the rate at which the temperature parameter T decreases over time. It is the most critical factor in balancing exploration versus exploitation:

• Exploration Phase: At high initial temperatures, the algorithm behaves like a random walk, accepting almost all moves to broadly sample the search space.
• Exploitation Phase: As T approaches zero, the algorithm becomes a strict hill-climber, accepting only improving moves.
• Common Schedules: Geometric decay (T_k = α * T_{k-1}), logarithmic, and linear schedules. An improper schedule can cause premature convergence or infinite runtime.

A problem-specific heuristic that defines how to move from the current solution to a new candidate. The structure of the neighborhood directly impacts the algorithm's efficiency:

• VRP/TSP Context: Common operators include 2-opt (reversing a segment), Or-opt (relocating a segment), and swap (exchanging two nodes).
• Granularity: The perturbation size must be tuned. Too small a change leads to slow convergence; too large a change reduces the search to random sampling.
• Feasibility: The function must ensure that generated neighbors respect hard constraints, such as vehicle capacity in a Capacitated VRP.

Simulated Annealing is theoretically guaranteed to converge to the global optimum under specific conditions, a property known as asymptotic convergence:

• Condition: The cooling schedule must be logarithmic (T_k = C / log(k+1)), which is computationally impractical for most real-world problems.
• Practical Use: In practice, geometric cooling is used, which sacrifices the mathematical guarantee for finite-time execution. The final solution is a high-quality approximation, not a proven global optimum.
• Comparison: Unlike deterministic methods like Mixed Integer Programming (MIP), SA does not provide an optimality gap, but it can find near-optimal solutions for large-scale, non-linear problems where MIP fails to terminate.

The starting temperature T_0 must be set high enough to ensure the search space is sufficiently explored. A standard heuristic is to set T_0 such that a defined percentage of worsening moves are initially accepted:

• Method: Perform a preliminary random walk and calculate the average increase in cost ΔE_avg for worsening moves.
• Calculation: Set T_0 = -ΔE_avg / ln(χ), where χ is the desired initial acceptance ratio (typically 0.8 to 0.95).
• Impact: A T_0 that is too low traps the search in the nearest local basin; a T_0 that is too high wastes computation on a pure random walk.

To mitigate the risk of premature convergence due to an overly aggressive cooling schedule, modern implementations often employ restart strategies:

• Fixed Restart: The algorithm resets to the best-known solution and re-heats the temperature after a set number of non-improving iterations.
• Adaptive Restart: The system monitors the search trajectory and triggers a restart when it detects stagnation in a local basin.
• Benefit: This hybrid approach combines the global search properties of SA with the memory of Tabu Search, ensuring the best-found solution is never lost during the final exploitation phase.

In last-mile routing, the solution space is rugged with many local minima. A greedy algorithm might settle on a suboptimal route cluster. Simulated Annealing avoids this by probabilistically accepting a worse route permutation. The acceptance probability is governed by the Metropolis criterion: P = exp(-ΔE / T). Early in the schedule, when the temperature (T) is high, the algorithm freely explores the solution space, accepting cost-increasing moves like crossing routes or adding detours. As T cools, it converges on a highly optimized, low-cost delivery sequence.

SA is highly effective for the Vehicle Routing Problem with Time Windows (VRPTW) . The objective function penalizes early arrivals and late deliveries. The cooling schedule is tuned to first resolve capacity violations, then tighten time-window adherence. Key implementation details:

• Neighborhood operators: Relocate, 2-opt*, and Or-opt moves.
• Penalty functions: Soft time windows allow violations at a cost, guiding the search toward feasibility.
• Reheating: Strategic temperature increases prevent premature convergence when the search stagnates.

Last-mile delivery involves conflicting objectives: minimizing total distance traveled, minimizing fleet size, and maximizing on-time percentage. SA handles this through a weighted-sum objective function or by exploring the Pareto frontier directly. The algorithm can dynamically adjust weights during the annealing process. For example, a logistics provider might prioritize distance reduction at high temperatures and shift to time-window adherence as the system cools, producing a set of non-dominated trade-off solutions for the dispatcher.

When a disruption occurs—such as a traffic jam or a failed delivery—the existing route plan must be updated in seconds. SA is well-suited for this because it can start from the current, partially executed solution as a warm start. The initial temperature is set low to perform a localized search around the disrupted route segment. The algorithm rapidly evaluates a limited set of neighborhood moves:

• Inserting a new pickup order into the existing sequence.
• Swapping two remaining stops to avoid a congested zone.
• Re-assigning a failed delivery to a different vehicle.

The cooling schedule dictates how the temperature parameter decreases, directly controlling the exploration-exploitation balance. Common schedules in logistics applications:

• Geometric cooling: T_k = α * T_{k-1} where α is typically 0.95–0.99. Simple and predictable.
• Logarithmic cooling: Guarantees convergence to the global optimum but is impractically slow for real-time use.
• Adaptive cooling: Monitors the acceptance ratio and adjusts the cooling rate dynamically. If too many moves are rejected, the temperature plateaus to allow more exploration.

Pure SA can be slow to fine-tune a solution near the global optimum. In practice, it is often hybridized with a deterministic local search (e.g., 2-opt or Or-opt) at each temperature step. This creates a Simulated Annealing with Local Search (SALS) approach:

• SA provides the global diversification to jump between basins of attraction.
• Local search provides the intensification to rapidly descend to the bottom of each basin.
• This combination significantly accelerates convergence on large-scale instances with 500+ stops.