Question $1(50$ pts$)$

A logistics company needs to deliver packages to $10$ different locations using a fleet of identical $4$ vehicles. Each vehicle has a maximum capacity of $15$ units. The demand $($in units$)$ for each location and the distances between each pair of locations are given in the tables below. The objective is to determine the optimal set of routes for the vehicles that minimizes the total distance traveled while ensuring that the total demand on any route does not exceed the vehicle capacity and each demand point is served exactly by one of the vehicles.

$\backslash$table$[[$Location$,1,2,3,4,5,6,7,8,9,10],[$Demand$,3,4,2,5,6,7,3,8,4,5]]$

$\backslash$table$[[$From$/$To$,0,1,2,3,4,5,6,7,8,9,10],[0,0,10,15,20,10,15,25,30,35,40,45],[1,10,0,12,25,25,30,35,25,30,45,50],[2,15,12,0,14,20,15,20,25,30,35,40],[3,20,25,14,0,10,25,30,35,40,45,50],[4,10,25,20,10,0,20,25,30,35,40,45],[5,15,30,15,25,20,0,10,20,25,30,35],[6,25,35,20,30,25,10,0,10,20,25,30],[7,30,25,25,35,30,20,10,0,15,20,25],[8,35,30,30,40,35,25,20,15,0,10,15],[9,40,45,35,45,40,30,25,20,10,0,10],[10,45,50,40,50,45,35,30,25,15,10,0]]$

a$.(30$ pts$)$ Formulate the problem as a Capacitated Vehicle Routing Problem. Use the following decision variables:

Let xij: a binary variable denoting whether city $j$ is visited just after city $i$ or not.

Let yi : the load of vehicle after serving location i$.$

b$.(20$ pts$)$ The transportation company, faced with a reduced fleet size of $3$ vehicles, seeks to optimize its delivery routes while considering the possibility of increasing vehicle capacity through modifications. However, each unit increase in capacity incurs a penalty cost of $M$.$ The objective is to identify a feasible route with the minimum possible penalty while minimizing the total distance traveled. Modify the formulation you developed in part a$.($Hint: Consider adding a new decision variable$)$