NO - Chapter 13 (Modified). Construction heuristics for TSP

NO - TSP (Travelling Salesman Problem) Tour Construction

For the starting point we usually take a random city.

While for the selection criterion we have seen:

• Arbitrary Insertion (Random City)
• Nearest Neighbour

For the insertion criterion we have seen:

• NO - TSP (Travelling Salesman Problem) Nearest Addition
• NO - TSP (Travelling Salesman Problem) Farthest Addition
• NO - TSP (Travelling Salesman Problem) Nearest Merge

---

Also we have seen the Christofides’s algorithm, which creates a tour for the TSP (Travelling Salesman Problem), solving first a MST (Minimum Spanning Tree) problem.

Link to original

NO - TSP (Travelling Salesman Problem) Arbitrary Insertion

Link to original

NO - TSP (Travelling Salesman Problem) Nearest Neighbour

Link to original

NO - TSP (Travelling Salesman Problem) Nearest Addition

Link to original

NO - TSP (Travelling Salesman Problem) Farthest Addition

Link to original

NO - TSP (Travelling Salesman Problem) Nearest Merge

Link to original

NO - TSP (Travelling Salesman Problem) & MST (Minimum Spanning Tree)

---

See also: NO - Christofides’s algorithm

Link to original

NO - Christofides's algorithm

References:

• NO - Spanning Tree Graph

---

Link to original