A small parcel delivery company has its terminal (depot) in downtown Des Moines (node 3) and has sixpackage deliveries to make on a given day (nodes 1, 2, 4, 5, 6, and 7). The Excel template shows the table of distances between all pairs of nodes (in miles).The
company wants to find the best route, or the optimal sequence of
visiting customer nodes, that minimizes the travel distance of the
delivery truck. Your task is to help the company come up with this route
by answering the following questions.Question 7How many possible routes are there for this problem?Is this problem symmetric or asymmetric?Question 8Currently the driver has been using the route 3-1-2-4-5-6-7-3. What is the distance for this tour?Question 9What is the nearest-neighbor heuristic solution to this problem? Note: when you have a tie, choose the node with the smaller node number (for example, if node 1 and node 5 are tie, choose node 1).Question 10Determine the optimal traveling salesman tour using the LP method you studied in class. Make sure that you fill the table “Sub-tour elimination constraints” as you solve a series of LPs (follow the example shown in the table, which contain fake data).