We need to visit 6 cities by using as minimum number of vehicles as possible. We identify 10 feasible paths as follows:

We have the following data:

U ={1,2,3,4,5,6,7,8,9,10}

S1={5,6}

S2={3,5,6}

S3={1,4}

S4={2,3,4,6}

S5={1,2}

S6={2,6}

S7={5}

S8={3,4,6}

S9={3,5}

S10={4}

Transportation costs are as follows:

S1 S2 S3 S4 S5 S6 S7 S8 S9 S10

C = [18,22,14,36,17,14,8,24,14,71]

By assuming that each path can once only:

a. Formulate the problem according to set partitioning problem.

b. determine how many vehicles is needed at the transportation costs of the solution.