Travelling Salesman Problems (AS)

Travelling Salesman Problems (AS)

Understanding the Problem

• Become familiar with the problem before proceeding to establish a solution.
• Define the problem accurately to avoid redundant steps.

Constructive Heuristics

• Understand Nearest Neighbour: Start from a city and then go to the nearest city until all cities have been visited.
• Note the importance of constructing a graph, where vertices represent cities and edges represent paths between cities.

Lower Bound 1

• Consider that a Traveling Salesman Problem (TSP) solution would always be greater than the cost of a minimum spanning tree.
• Determine the cost of a minimum spanning tree as a lower bound for TSP.

Lower Bound 2

• Observe that a TSP solution would always be greater than the cost of a twice repeated minimum weighted edge.
• Calculate a twice repeated minimum weighted edge as another lower bound for TSP.

The 2-opt Heuristic

• Implement the 2-opt heuristic to find a local optimum solution for TSP.
• Utilize the 2-opt heuristic when a solution is required quickly and exactness is not crucial.

The 3-opt Heuristic

• Study the 3-opt heuristic as an improved version of the 2-opt heuristic.
• Apply the 3-opt heuristic to uncover better and efficient solutions.

Solving TSP with Linear Programming

• Explore solving TSP using Linear Programming (LP).
• Remember to add subtour elimination constraints when formulating the LP problem.

Upper Bounds

• Recognize that the cost of any TSP tour can be an upper bound for the TSP.
• Estimate upper bounds to narrow down the optimal solution’s possibilities.

Iterative Improvement Heuristics

• Acknowledge heuristic solutions can often be improved by altering some decisions.
• Practice applying iterative improvement heuristics to achieve better solutions.