Q4

Consider the following graph which expresses the connections between places. Note that some of the edges are oriented. The numbers on the edges represent the travelling cost between the pairs of vertices. Let us solve the travelling salesman problem over this graph:

a) Find any feasible solution of the travelling salesman problem just from the picture, regardless the quality of the distance.
b) Construct the distance matrix (table). How many cells of the table will remain empty?
c) Solve the problem using Vogel’s approximation. What will be the largest difference in the first step of the method?
d) What is the objective function value if the problem is solved by Vogel’s approximation? Write the total distance.