Part B. Is the algorithm run in exponential or polynomial time and why?

2. Consider the Clark and Wright algorithm for the Vehicle Routing Problem. (15 Points) What is the complexity of the algorithm? The steps are provided below. Clearly explain/demonstrate your logic to receive credit, A. Clark and Wright Agorithm (Assume n customers) 1. Starting solution: each of the n vehicles serves one customer. 2. For all pairs of nodes (Lj), J, calculate the savings for joining the cycles using edge(WJ: sij = cio + coj-cij Sort the savings in decreasing order (assume an efficient algorithm of O(n) at this step) 3. 4. Take edge [ij] from the top of the savings list. Join two separate cycles with edge fiji, if a) the nodes belong to separate cycles b) the maximum capacity of the vehicle is not exceeded c) i and j are first or last customer on their cycles. Repeat 4 until the savings list is handled or the capacities don't allow more merging. 5. 2. Consider the Clark and Wright algorithm for the Vehicle Routing Problem. (15 Points) What is the complexity of the algorithm? The steps are provided below. Clearly explain/demonstrate your logic to receive credit, A. Clark and Wright Agorithm (Assume n customers) 1. Starting solution: each of the n vehicles serves one customer. 2. For all pairs of nodes (Lj), J, calculate the savings for joining the cycles using edge(WJ: sij = cio + coj-cij Sort the savings in decreasing order (assume an efficient algorithm of O(n) at this step) 3. 4. Take edge [ij] from the top of the savings list. Join two separate cycles with edge fiji, if a) the nodes belong to separate cycles b) the maximum capacity of the vehicle is not exceeded c) i and j are first or last customer on their cycles. Repeat 4 until the savings list is handled or the capacities don't allow more merging. 5