Traveling-Salesperson-Problem-TSP-

Solving the TSP using Construction Heuristics and 2-Opt Improvement Heuristic

In this homework, you are going to solve the TSP for three data sets. They are called eil51.dat, eil76.dat, and eil101.dat, and consist of 51, 76, and 101 customer locations, respectively. Each data set includes the x-coordinates and y-coordinates of customers. The distances between customer locations are measured via Euclidean distance rounded to two digits after the decimal point. You can also compute the optimal tour length by considering the sequence given in the xxxopt.dat files.

1. Solve each instance using the one-sided nearest neighbor heuristic starting at cities 10, 20, and 30. This means that you will obtain nine tours. Provide the tour length of each one using the table below.
   
2. Solve each instance using the two-sided nearest neighbor heuristic starting at cities 10, 20, and 30. This means that you will obtain nine tours. Provide the tour length of each one using the table below.
   
3. Solve each instance using the nearest insertion heuristic starting at cities 10, 20, and 30. This means that you will obtain nine tours. Provide the tour length of each one using the table below.
   
4. Solve each instance using the farthest insertion heuristic starting at cities 10, 20, and 30. This means that you will obtain nine tours. Provide the tour length of each one using the table below.
   
5. For each tour obtained so far, apply the 2-opt improvement heuristic, and give the tour length using the table below.