Problem $1.$ Consider the following list of node locations, where node $0$ represents a depot and

all other locations represent customers.

i$.$ 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, used in urban logistics to model travel time

between locations in a city.$)$ Run the Nearest Neighbor and Cheapest Insertion heuristics

using the depot as a starting point; report the heuristics' partial solution after every

iteration, the final solutions, and compare their costs.

ii$.$ For both solutions, identify a $2-$opt improvement and state the change in cost$,$ or verify

that no such improvement exists.