Earth’s Fleet Assignment¶
Problem Definition¶
In the year 2357, tensions between Earth, Mars, and the Belt are at an all-time high. The United Nations Navy (UNN) must deploy vessels to ensure the statibility in earth’s colony and provide security to supply chain operations across the solar system.
More specifically, Earth needs to assign five available warships (UNN Agatha King, to secure five colonies in need of military assistance: Ceres, Ganymede, Europa, Io, and Callisto.
Each vessel as an associated cost for each mission, that depends on factors such as suitability, operational range, and efficiency. The costs are provided in the table below in M€:
Vessel / Colony |
Ceres |
Ganymede |
Io |
Europa |
Callisto |
|---|---|---|---|---|---|
UNN Agatha King |
12 |
18 |
25 |
30 |
14 |
UNN Nathan Hale |
20 |
14 |
22 |
24 |
18 |
UNN Donnager |
30 |
12 |
18 |
16 |
10 |
UNN Rocinante |
15 |
22 |
28 |
12 |
20 |
UNN Behemoth |
18 |
20 |
30 |
14 |
12 |
Formulate an Integer Programming model to minimize the total cost of vessel assignments while ensuring every colony gets a vessel.
Draw a graph to solve the problem using graph algorithms.
Describe a strategy to design a greedy algorithm to solve the problem.