Skip to main content

Module tsp_grasp

simular::demos

Module tsp_grasp 

Source
Expand description

Demo 6: TSP Randomized Greedy Start with 2-Opt

Demonstrates the GRASP (Greedy Randomized Adaptive Search Procedure) methodology for the Traveling Salesman Problem.

§Governing Equations

Tour Length:           L(π) = Σᵢ d(π(i), π(i+1)) + d(π(n), π(1))
2-Opt Improvement:     Δ = d(i,i+1) + d(j,j+1) - d(i,j) - d(i+1,j+1)
Expected Greedy Tour:  E[L_greedy] ≈ 0.7124·√(n·A)  [BHH 1959]
1-Tree Lower Bound:    L* ≥ MST(G\{v₀}) + 2·min_edges(v₀)  [Held-Karp 1970]

§EDD Cycle

  1. Equation: Greedy + 2-opt achieves tours within ~5% of optimal [JM 1997]
  2. Failing Test: Assert tour_length / lower_bound < 1.10 (10% optimality gap)
  3. Implementation: Randomized nearest-neighbor + exhaustive 2-opt local search
  4. Verification: Multiple random starts converge to similar tour lengths
  5. Falsification: Pure random start (no greedy) yields significantly worse results

§Toyota Production System Compliance

  • Jidoka: Edge crossing detection (Lin-Kernighan 1973: Euclidean TSP optimal has 0 crossings)
  • Muda: Stagnation detection eliminates restart waste (early termination)
  • Heijunka: Adaptive tick rate based on convergence status
  • Poka-Yoke: RCL size clamping, input validation

§References (IEEE Style)

  • [51] Feo & Resende (1995). GRASP. J. Global Optimization, 6(2), 109-133.
  • [52] Lin & Kernighan (1973). TSP Heuristics. Operations Research, 21(2), 498-516.
  • [53] Johnson & McGeoch (1997). TSP Case Study. Local Search in Comb. Opt.
  • [54] Christofides (1976). TSP Heuristic. CMU Report 388.
  • [55] Beardwood, Halton & Hammersley (1959). Shortest Path. Proc. Cambridge, 55, 299-327.
  • [56] Held & Karp (1970). TSP and MST. Operations Research, 18(6), 1138-1162.

Structs§

City
A 2D point representing a city.
TspGraspDemo
TSP GRASP Demo state.

Enums§

ConstructionMethod
Construction method for initial tour.