Problem 1. [50 points] Consider the following list of node locations, where node 0 represents a...

Transcribed Image Text:

Problem 1. [50 points] Consider the following list of node locations, where node 0 represents a depot and all other locations represent customer. Node x-coordinate y-coordinate 1 50 50 1 11 43 2 56 22 3 50 7 4 28 48 5 96 18 6 0 11 7 68 98 8 25 93 9 10 78 10 11 19 11 94 2 12 89 15 13 78 52 14 28 28 15 18 39 16 13 23 17 4 13 18 9 38 19 18 21 20 90 70 21 36 99 22 34 36 23 22 89 24 67 18 Suppose the cost to travel between any pair of locations is given by the Manhattan metric, that is, the rectilinear distance between them. (This is the sum of the horizontal and vertical distances between the points, and is used in urban logistics to model travel time between locations in a city.) 1.1 (20 points) Run the Nearest Neighbor heuristics using the depot as a starting point; report the heuristics' partial solution after every iteration, and the final solution. Hint: use the following format: Problem 1. [50 points] Consider the following list of node locations, where node 0 represents a depot and all other locations represent customer. Node x-coordinate y-coordinate 1 50 50 1 11 43 2 56 22 3 50 7 4 28 48 5 96 18 6 0 11 7 68 98 8 25 93 9 10 78 10 11 19 11 94 2 12 89 15 13 78 52 14 28 28 15 18 39 16 13 23 17 4 13 18 9 38 19 18 21 20 90 70 21 36 99 22 34 36 23 22 89 24 67 18 Suppose the cost to travel between any pair of locations is given by the Manhattan metric, that is, the rectilinear distance between them. (This is the sum of the horizontal and vertical distances between the points, and is used in urban logistics to model travel time between locations in a city.) 1.1 (20 points) Run the Nearest Neighbor heuristics using the depot as a starting point; report the heuristics' partial solution after every iteration, and the final solution. Hint: use the following format: