Question 2. Consider an 5-node network (with 0 as the depot vertex and 4 other vertices)...

 

Transcribed Image Text:

Question 2. Consider an 5-node network (with 0 as the depot vertex and 4 other vertices) where the travel cost matrix and the demands are as follows: 0 1 2 3 4 1 2 279 420 0 0 279 0 420 256 0 288 349 565 341 216 122 3 565 256 288 349 0 444 4 341 216 122 444 0 a) Find the TSP solution using the Nearest Neighbor heuristic. b) Find the TSP solution using the Insertion heuristic. c) Find the TSP solution using the Clarke & Wright Savings heuristic. d) Using an exchange-neighborhood type algorithm where you exchange two vertices, try to improve your solution in (a) or show that it may not be improved. Question 2. Consider an 5-node network (with 0 as the depot vertex and 4 other vertices) where the travel cost matrix and the demands are as follows: 0 1 2 3 4 1 2 279 420 0 0 279 0 420 256 0 288 349 565 341 216 122 3 565 256 288 349 0 444 4 341 216 122 444 0 a) Find the TSP solution using the Nearest Neighbor heuristic. b) Find the TSP solution using the Insertion heuristic. c) Find the TSP solution using the Clarke & Wright Savings heuristic. d) Using an exchange-neighborhood type algorithm where you exchange two vertices, try to improve your solution in (a) or show that it may not be improved.

Answer rating: 100% (QA)

SOLUTION a Nearest Neighbor heuristic Start from depot 0 Next nearest is 1 cost 279 From 1 next near... View the full answer