Q1. (1596) Consider an instance of the vehicle routing problem (VRP) with the following parameters: number of customers = 6 (each customer has unit demand) number of vehicles available = 2 vehicle capacity = 5 and with the following distance matrix where node O is the origin. 0 1 2 3 4 5 6 o o 225303324204272349 1228 o 101123 62 113209 2306212 0 174176150351 3320123145 O 1411 15167 4211 60 124145 0 71160 5273 107153113710 110 6355195263161149 94 0 You are asked to employ a cluster-first-route-second (CFRS) procedure to find a feasible solution to the above VRP instance. Recall that the first step of a CFRS procedure is to partition the customers into a number of clusters. In the second step, for each cluster, a feasible traveling salesperson problem (TSP) tour is constructed over the customer nodes in the cluster and the specified origin. (a) (696) In how many different ways can you partition the customers into two clusters so that the number of customers in each cluster does not exceed the vehicle capacity of 5 units? (DO NOT enumerate and list all possible clusters, just show your calculations). (b) (396) Specify any two clusters that would yield a feasible VRP solution. () (696) Considering the clusters you specified in part (b), construct a feasible VRP solution using the nearest neighbor algorithm, and report its total length. Q1. (1596) Consider an instance of the vehicle routing problem (VRP) with the following parameters: number of customers = 6 (each customer has unit demand) number of vehicles available = 2 vehicle capacity = 5 and with the following distance matrix where node O is the origin. 0 1 2 3 4 5 6 o o 225303324204272349 1228 o 101123 62 113209 2306212 0 174176150351 3320123145 O 1411 15167 4211 60 124145 0 71160 5273 107153113710 110 6355195263161149 94 0 You are asked to employ a cluster-first-route-second (CFRS) procedure to find a feasible solution to the above VRP instance. Recall that the first step of a CFRS procedure is to partition the customers into a number of clusters. In the second step, for each cluster, a feasible traveling salesperson problem (TSP) tour is constructed over the customer nodes in the cluster and the specified origin. (a) (696) In how many different ways can you partition the customers into two clusters so that the number of customers in each cluster does not exceed the vehicle capacity of 5 units? (DO NOT enumerate and list all possible clusters, just show your calculations). (b) (396) Specify any two clusters that would yield a feasible VRP solution. () (696) Considering the clusters you specified in part (b), construct a feasible VRP solution using the nearest neighbor algorithm, and report its total length