Travelling salesman problem

Question 1

Describe the travelling salesman problem.

Answer 1

You’re givn a graph of n cities with weighted, undirected edges. What is the shortest Hamiltonian cycle in the graph?

A Hamiltonian cycle is a graph cycle which starts in one city, travels through each other city exactly once, then finishes at the starting city.

Question 2

What is the random construction method?

Answer 2

The random construction method is one where we generate a random permutation of all cities.

Question 3

What is the iterative random construction method? How many times do we run it?

Answer 3

The iterative random method is one where we run the random method several times, then choose the best result.

It’s usually run 5 times, according to Nourddine.

Question 4

What is the greedy construction method?

Answer 4

The greedy construction method is one where we start in a random city. At each step, we move to the next node with has the cheapest transition cost.

Question 5

What is the random insertion method?

Answer 5

During each step in the random insertion method, we select a random city. We then try putting this in-between each other city in our current tour, to find out where it would cause the lowest increase in tour length.

Question 6

What is the cheapest insertion method?

Answer 6

During each iteration:

1) Look at each unvisited city.
2) Try to insert it at any point in our current tour.
3) Select to keep the tour with the shortest length after doing this for all cities.

Question 7

Describe the greedy improvement heuristic.

Answer 7

The greedy improvement heuristic takes some tour and tries to improve it by swapping cities pairwise. If the swap lowers the overall tour length, it’s accepted, otherwise it’s rejected.

The heuristic is run until some stopping criteria are met, and is usually bounded by:

• Time
• Number of iterations
• Rate of improvement over some window