Please enable JavaScript.
Coggle requires JavaScript to display documents.
Main Optimization Methods for TSP Made by KAJJI ANASS - Coggle Diagram
Main Optimization Methods for TSP Made by KAJJI ANASS
Dynamic Programming O(n2^n)
Branch and Bound Methods
Heuristics
construction heuristics
Nearest neighbor heuristic
we have an upper bound on the solution quality l(T)/l(Topt) ≤ (log2 n)/2
Nearest insertion heuristic
We have a worst-case performance ratio of l(T)/l(Topt) ≤ 2
Cheapest insertion heuristic
The bound on the solution quality is l(T)/l(Topt) ≤ log2 n
Furthest insertion heuristic
The worst-case performance ratio is l(T)/l(Topt)≤log2 n
improvement heuristics
Two-opt heuristic
k-opt heuristic
Lin-Kernighan heuristic
Approximation Algorithms
The Christofides heuristic
constant-factor approximation with an approximation ratio of ρ(n)=3/2. Its running time is O(n^3)
Metaheuristics
Tabu search
Simulated annealing
Genetic algorithm
Memetic Algorithm
Ant Colony Optimization Algorithm
Firefly Algorithm
Cuckoo- Search Algorithm
Data-Driven Metaheuristics