D1, C5 - The Travelling Salesman Problem

Question 1

What is the Travelling Salesman problem

Answer 1

Visiting every vertex / node in a network, starting and finishing at the same vertex

Question 2

How is the Travelling Salesman problem different to route inspection / the Chinese Postman problem

Answer 2

Travelling Salesman - visit every vertex and finish at start
Chinese Postman - traverse every arc

Question 3

What is the Classical Travelling Salesman problem

Answer 3

Each vertex is visited only once

Question 4

What is the Practical Travelling Salesman problem

Answer 4

Each vertex is visited at least once

Question 5

What is a walk

Answer 5

Begins at a vertex, traverses arcs and ends at a vertex

Question 6

What is a tour

Answer 6

Visits every vertex (could be more than once) and returns to the starting vertex

Question 7

What type of tour visits every vertex once

Answer 7

Hamiltonian Cycle

Question 8

Why do we use upper / lower bounds for travelling salesman problems

Answer 8

There is no efficient algorithm to solve the problems so you want to know how ‘good’ our solution is

Question 9

What does it mean if you solution to a travelling salesman problem equals the lower bound

Answer 9

It is an optimal solution

Question 10

What is a table of least distances

Answer 10

A table of the shortest distances between vertices

Question 11

How do you know the values for a table of least distances

Answer 11

Inspection

Question 12

How would you find the minimum spanning tree when given a network

Answer 12

Prim’s algorithm
OR
Kruskal’s algorithm

Question 13

How would you find the minimum spanning tree when given a (least) distance table

Answer 13

Prim’s algorithm

Question 14

How do you find the upper bound for the travelling salesman problem

Answer 14

Weight of upper bound x 2

Question 15

How do you find better solutions than the upper bound of the travelling salesman problem

Answer 15

Look for shortcuts

Question 16

What are the steps to find the lower bound using a minimum spanning tree

Answer 16

1) Remove a vertex
2) Find the residual minimum spanning tree
3) Add back the removed vertex by using the two shortest arcs
4) OPTIONAL, you can: Repeat steps 1-3, removing different vertices and pick the solution with the highest weight. If the solution is a Hamiltonian Cycle (or UB = LB), then have found an optimal solution

Question 17

What is a residual minimum spanning tree

Answer 17

A spanning tree of the remaining vertices when one is removed

Question 18

You have found two lower bounds, 678m and 712m, which is the better lower bound and why

Answer 18

712m is the better lower bound since we want the optimal solution interval (LB to UB) to be as small as possible
(712 is the biggest)

Question 19

The lower bound is 712m and does not form a Hamiltonian Cycle while the upper bound is 1093m, what is the smallest interval that must contain the optimal route

Answer 19

712 < optimal solution <= 1093
The optimal solution can ONLY equal the lower bound if the LB is a Hamiltonian Cycle

Question 20

When can the optimal solution = the LB

Answer 20

When the LB forms a Hamiltonian Cycle

Question 21

What does the nearest neighbour algorithm do

Answer 21

Finds an upper bound

Question 22

What are the steps for the nearest neighbour algorithm

Answer 22

1) Start with any vertex
2) Select the nearest vertex that has not yet been visited
3) Repeat until all vertices have been visited and make sure you return to starting vertex
4) Choose a different starting vertex and repeat steps 2-3
5) When all vertices have been selected as starting vertices, choose the tour with the lowest weight as an upper bound

Question 23

Why do we use the nearest neighbour algorithm instead of the minimum spanning tree method

Answer 23

For very large networks, the MST would take ages

Question 24

When performing the nearest neighbour algorithm (similar to Prim’s), why don’t you cross out the row for the starting vertex

Answer 24

Because you need to get back to the start

Question 25

You have found upper bounds of 1250m, 1237m, and 1233m, which should you pick for the upper bound for the optimal solution interval and why

Answer 25

LB < optimal solution <= 1233m
Because we want the optimal solution interval as small as possible (smallest UP)