Consider the Traveling Salesman Problem in the following network. Assume that the warehouse is located at node $1.$

a$)$ Solve the problem using the patching heuristic algorithm $($Reminder: First, solve the assignment problem and combine any sub$-$tours with the patching algorithm$).$

b$)$ Solve the problem with the Christofides algorithm.

c$)$ Find a high lower bound for the problem by solving MSrTP problems. Use this lower bound to comment on the quality of the solutions found in the previous option.

d$)$ Try to improve the solutions in parts a and b through $2-$neighborhood.