: COVERING PROBLEMS

Question $1$:

Consider the transportation network below. In this network, the numbers on the links indicate the travel times $(t_{ij})$ of the links.

In this network, set $N=\{1,2,5,8,9,10\}$ represent the customers and set $M=\{3,4,6,7\}$ demonstrate the potential facility locations.

a$)$ Create the covering matrix $A=[a_{ij}]$ for covering distance $T=5.$

$a_{ij}=\{\begin{array}{ccc}1,& if& t_{ij}T\\ 0,& \text{o}\text{t}\text{h}\text{e}\text{r}\text{w}\text{i}\text{s}\text{e}& \end{array}$

b$)$ In this network, we would like to locate facilities that cover everyone $($all customers$)$ with the minimum number of facilities. Find a solution to this problem using the greedy algorithm. List all alternative solutions that can be found using the greedy algorithm.

c$)$ Among the alternative solutions you found in the previous option, determine the one that minimizes the total transportation costs to customers.