**Go to ..... **Main** | **Set Covering Example** | **Transportation Example** | **Core Set Covering** | **Core Transportation

In this problem, we will integrate the set covering and transportation problems to solve the optimal flight plan problem. We are given an area to search as shown in the figure below. The entire area is divided into 11 smaller regions. We need to model the figure as a set covering problem to find which regions the plane should be so that the camera can cover the whole area. Then, we take the optimal solution and find the best route to travel within those regions.

Model the graph below as a set covering problem to find the optimal area where the plane should be. Assume that the camera is moving at 360^{0} and cover the area below it and the surrounding areas. For example, if the camera is above 3, it can scan all the areas 1, 2, 3, 4, 5, 6.

Model

Sets |
i - small areas numbered 1 to 11 |

Variables |
X X |

Objective Function |
Z = S X |

Solution Summary

The optimal value is Z = 3

The optimal solution is X_{3} = 1, X_{8} = 1, X_{9} = 1, X_{i} = 0 where i = 1,2,4,5,6,7,10,11

This implies that if the plane is above area 3, area 8, and area 9, it will cover the whole searched area.

Back to Top

Given the optimal solution from the set covering model, the objective of this problem is to find the optimal flight plan ( ie minimum cost flight plan) to each of the nodes designated by the set covering model.

Model

Sets |
I - areas from which we travel to next area to be searched {3o, 5o, 6o, 8o, 9o} J - areas to be searched {3d, 5d, 6d, 8d, 9d} |

Variables |
X(I,J) - represents travelling on path i-j Z - total search cost in dollars |

Objective Function |
min S |

Solution Summary

The objective value is 13.

Pictorial Optimal Flight Plan:

Back to Top

by Breonda Carrigan, Cari McRae & Queenie Li