Traveling salesman
19 methods in the atlas attack this one problem. They are rivals: each wins something the others do not.
Phrasings that mean this problem
Exact traveling salesmanTraveling salesman exactTraveling-salesman problemExact TSPAsymmetric TSPTSP boundingTraveling salesman heuristicTSP constructionTraveling-salesman toursMetric TSP approximationTour improvementTour constructionTour evolution
approximation
- ChristofidesMatching plus Euler tourcanonapproximation
- Double-tree TSPMST shortcuttingstandardapproximation
backtracking-cp
- Branch and bound1-tree boundstandardbacktracking-cp
- Branch and boundReduced-cost matrix boundspecialistbacktracking-cp
dynamic-programming
- Bitmask DPSubset enumerationcanondynamic-programming
- Held-KarpBitmask subset statescanonfull lesson ▸dynamic-programming
metaheuristics
- Simulated annealingGeometric cooling schedulecanonfull lesson ▸metaheuristics
- Genetic algorithmEdge recombination crossoverspecialistmetaheuristics
- Ant Colony SystemPseudorandom proportional rulestandardmetaheuristics
scheduling-operations
- Lin-KernighanSequential edge exchangescanonscheduling-operations
- Lin-Kernighan-Helsgaun5-opt candidate movesstandardscheduling-operations
- Or-optSegment relocationstandardscheduling-operations
- 2-optEdge-uncrossing swapscanonscheduling-operations
- 3-optstandalonestandardscheduling-operations
- Nearest neighbor tourstandalonestandardscheduling-operations
- Greedy edge tourstandalonespecialistscheduling-operations
- Savings-based constructionstandalonespecialistscheduling-operations
- Held-Karp lower boundLagrangian 1-treespecialistscheduling-operations
- Concorde branch and cutstandalonespecialistscheduling-operations