Consider a furniture shop that delivers daily the orders of their customers with their 3 capacitated vehicles. At the beginning of each day, the shop determines which customers need to be visited that day, and construct 3 sets of customers by taking into account the furnitures that are ordered by the customers and the capacity of the vehicles. Once these sets of customers are determined by the shop, then the driver of each vehicle needs to leave the shop in the morning, deliver the orders by visiting the set of customers assigned to her/him, and come back to the shop to complete its tour.

To determine a feasible Vehicle Routing Problem (VRP) solution of these 3 vehicles on a specific day with 12 customers, the shop determines the customer clusters corresponding to each vehicle as follows (i.e. vehicle 1 serves the first cluster, vehicle 2 serves the second cluster, etc.):

1. Cluster1 = {3,5,6,8}

2. Cluster2 = {1,4,9,11}

3. Cluster3 = {2,7,10,12}

Below, you can find the distance matrix including the distance information between every node pair, where node 0 represents the furniture shop, and nodes 1-12 correspond to the customers.

0 1 2 3 4 5 6 7 8 9 10 11 12 0 0 95.1 40.6 78.6 71.3 79.2 43.9 73.8 92.1 35.3 24.2 26.6 54.7 1 73.7 0 40.9 67.2 76.8 55.9 97.4 39.1 90.3 47.3 73 70 96.6 2 61.5 65.2 0 77.6 90.1 45.4 45.9 79.5 90.8 30 77.5 40.1 76.1 3 41.6 22.6 22.2 0 25.2 88.9 83.5 95.5 84.2 39.2 84.4 20.6 28.6 4 60.7 78.8 81.4 84.6 0 94.4 52.3 85.9 24.3 87.9 37.7 64.1 36.9 5 32.8 34.7 93 97.7 56.8 0 40 24.4 29.6 56.7 22.8 21.5 54.6 6 35.9 60.8 57.6 50.6 24.9 45.6 0 54.4 32.1 99 67.9 74.5 79.4 7 61.4 82.6 69.5 25.5 43.5 51.1 66.3 0 87.3 66.2 84.6 33.6 71.7 8 73.3 47.7 83.5 57.8 81.5 40.8 28.6 45.6 0 59.9 35.6 95.5 42.6 9 27 38.1 87.2 97.1 37.3 93.7 62.1 74.3 27.5 0 82.6 89.9 48 10 94.9 89 74.4 43.9 50.9 88.5 32.7 80.1 39.2 32.7 0 95.2 63 11 25.5 29.8 42.4 22.8 96.1 64.7 26.2 67.4 85.5 45.2 89.5 0 43.7 12 35.7 44.2 48.7 98.3 90.1 82.4 76 71.1 96.3 59.2 51.1 48.2 0

(5%) Find a feasible TSP tour for the first vehicle using the nearest-neighbor algorithm. Report the distance of the resulting tour. (10%) Alternatively for the first vehicle, a feasible TSP tour is suggested by the driver of that vehicle as [0,8,5,3,6,0]. However, the shop aims to see whether this suggested tour can be improved in terms of the distances travelled. For this purpose, evaluate the 2-opt swap operation between node 5 and node 6. Report the resulting TSP tour with its distance after the swap operation, and determine whether this swap operation should be conducted. (15%) For the second and third vehicles, the shop first determines the tours of these vehicles as Tour2 = [0,9,11,4,1,0] and Tour3 = [0,2,12,10,7,0]. Since each of the customers in the sets of Cluster2 and Cluster3 have the same furniture order, the shop considers evaluating 2-opt swap operations between the tours as the swap operation will not violate the capacity restriction of the vehicles. For this purpose, evaluate the 2-opt swap operation between node 4 in Tour2 and node 12 in Tour3. Report the resulting TSP tour with its distance after the swap operation, and determine whether this swap operation should be conducted.