Problem #$2$

Consider the following TSP distance data between six nodes. The goal is to find shortest closed tour.

$([,15,26,31,44,38],[19,47,53,39,27],[29,43,35,54,62],[34,51,36,22,19],[44,34,59,24,26],[31,27,65,11,29,])$

$($a$)$ Solve the problem using nearest neighbor heuristic.

$($b$)$ Solve the problem using reversal heuristic. Assume the starting tour is $1-2-3-4-5-6-1.$ Termination criteria: either encountering a local optimal solution, or reaching three iterations.

$($c$)$ Identify an upper bound of the TSP$.$

$($d$)$ Identify a lower bound for the TSP$.$

$($e$)$ Find the solution of TSP using B & B approach. At each node, solve the corresponding assignment problem using the Hungarian method ${?}^{}.$ Use the following strategy:

Node Selection: When there are several active nodes, select the node with best bound.

Branch Selection: When there are several open branches, pick the branch, whose variable corresponds to longest distance.

Subtour Selection: At a given node, if there are several subtours, pick the subtour with smallest cardinality. Break ties arbitrarily.