Local Search and Simulated Annealing › Practical Implications

Local search and simulated annealing are appropriate when the decision variable is a discrete arrangement, the objective is cheap to evaluate or can be updated incrementally, and a good feasible solution is more useful than a proof of optimality. Routing, scheduling, packing, and assignment are natural fits because a small structural edit (reversing a segment, swapping two jobs, moving an item) produces a candidate that can be scored directly. If an exact method can handle the instance, include it as a reference, as we do by enumerating these 40,320 permutations. A disconnected neighborhood or a budget too small for a meaningful scan also limits the heuristic. In those settings the heuristic may still produce a useful answer, but the comparison should be framed as baseline improvement under a fixed budget, not as a claim of global optimality.

The representation, decoder, and neighborhood jointly determine which candidate changes the algorithm can explore. In this chapter the permutation, the fixed four-customer split, and inclusive reversals work together because adjacent reversals generate all permutations, so the state graph is connected, while wider reversals can cross the route boundary and reassign customers between vehicles. Restricting moves to within-route reversals would silently forbid that reassignment and could leave the search stuck on a solution that is poor only because a customer is on the wrong vehicle. The practical test is to ask whether the move set can express the changes the objective rewards, and whether repeated application can reach every feasible solution. Symmetric within-route reversals give routing a geometric neighborhood, but arbitrary reversals need not improve a route. Scheduling and packing require moves suited to their own decisions and constraints.

Data requirements are modest but not zero. The instance must supply the coordinates, demands, capacities, time windows, service times, and depot information needed by the decoder, and the distance matrix should be computed once and reused rather than recalculated at every proposal. A feasibility checker is part of the data pipeline, not an afterthought: it should be called on every reported final solution, and in this chapter the experiment checks the required permutation, feasibility, objective equality, and monotone incumbent traces. Unlike feature-based models, local search does not require feature scaling or missing-value imputation in the usual sense, but inconsistent units, asymmetric distances, or an infeasible warm start can dominate the outcome. When several objectives are combined, state their units, scaling, and policy weights before scalarizing; equal numerical scales alone do not determine appropriate priorities.

Check experimental comparisons at the level of scored candidates. Reporting only a successful seed hides run-to-run variation. Counting only accepted moves understates cost, because rejected proposals, restarts, and initialization all consume evaluations. Equal evaluation counts should be accompanied by runtime measurements if computational cost is the comparison target: scoring a permutation traverses every arc in both tours, while a nearest-neighbor scan examines candidate arcs more cheaply. Inspect uphill acceptance separately from ties and improvements. A high total acceptance rate can reflect equal-cost or improving proposals; it does not alone prove that temperature is too high. Very few accepted worsening moves may reflect low temperature or the proposed objective changes. Hill climbing should be paired with restarts or perturbation, and annealing should be monitored rather than tuned by a single final number.

Computational cost is governed by how often the objective is evaluated and how expensive each evaluation is. A full scan here examines 28 reversals, so the 300-evaluation budget supports roughly ten scans, enough to reveal plateaus but not enough to certify optimality. For a symmetric within-route 2-opt reversal, the distance delta uses two removed and two replacement boundary edges and can be computed in $O(1)$ distance lookups. Cross-split moves require the correct decoder-specific depot accounting, and time-window feasibility can still need a route scan. This implementation deliberately uses full $O(n)$ candidate scoring and copies permutations; its distance matrix uses $O(n^2)$ storage, each budget trace uses $O(K)$ storage, and the repeated-run experiment retains all traces. Independent seeds can be run separately. If the neighborhood grows quadratically with the number of customers, candidate lists or first-improvement scans may be necessary to keep each iteration affordable; the general principle is to preserve the evaluation accounting while making each evaluation as light as the problem structure allows.

Performance should be reported as a distribution, not a point. Across 20 seeds with the same 300-evaluation budget, report the mean, standard deviation, minimum, maximum, and incumbent traces for each method, and compare against both a construction heuristic and a random baseline. On small instances, full enumeration supplies an exact reference; on larger ones, use the best known solution or a lower bound. In deployment, log the acceptance rate, the incumbent improvement, and the feasibility rate to help diagnose poor schedule behavior. Inspect uphill acceptance separately from ties and improvements; these logs do not guarantee a unique diagnosis or detection before quality degrades. Re-run the search when the instance changes, keep the seed ensemble as part of the evaluation protocol, and treat the method as a budgeted improvement procedure rather than a source of guaranteed optima. That framing also sets up the next chapter, where population-based methods reuse this instance, decoder, and evaluation accounting to ask whether a different search dynamic can spend the same evaluations more effectively.