Early Warning Radar Network
Maximal Covering Location Problem (MCLP)
Deploy radar stations to maximize detection coverage of incoming alien approach corridors. Given 5 candidate sites, 8 demand corridors with importance weights, and a fixed detection radius, choose p=2 sites to open that cover the maximum total weighted demand.
The Scenario
Detection Coverage
Earth's perimeter defense requires early warning radar stations positioned to detect incoming alien vessels along 8 approach corridors. Each corridor has an importance weight reflecting the threat level. 5 candidate sites are available, each with a fixed detection radius. The budget allows deploying only p = 2 radars. Which 2 sites maximize total weighted detection coverage?
| Defense Domain | OR Element | Symbol | Example |
|---|---|---|---|
| Radar station site | Candidate facility | i ∈ I | Radar-A |
| Approach corridor | Demand point | j ∈ J | Corridor-3 |
| Corridor importance | Demand weight | dˇ | 18 |
| Detection range | Coverage radius | r = 25 | 25 km |
| Number of radars | Facilities to open | p = 2 | 2 radars |
| Build radar here? | Location variable | xᵢ ∈ {0,1} | 0 or 1 |
| Corridor detected? | Coverage variable | yˇ ∈ {0,1} | 0 or 1 |
MAXIMIZE Σj∈J dˇ · yˇ
subject to:
yˇ ≤ Σi∈Nˇ xᵢ ∀ j ∈ J // covered only if facility in Nˇ open
Σi∈I xᵢ = p // open exactly p facilities
xᵢ ∈ {0,1} ∀ i ∈ I
yˇ ∈ {0,1} ∀ j ∈ J
// Nˇ = {i ∈ I : dist(i,j) ≤ r} (candidates within radius)
// NP-hard in general (Church & ReVelle, 1974)
// For p≤3 and |I|≤10: exact enumeration of C(|I|,p) subsets is feasible
Interactive Solver
Coverage Optimizer
★★★ Exact (enumeration)
★★☆ Greedy
5 Candidates · 8 Corridors · r=25 · p=2
References
Published Church, R. & ReVelle, C. (1974). “The maximal covering location problem.” Papers of the Regional Science Association, 32, 101–118. — Original MCLP formulation.
Published Daskin, M.S. (1995). Network and Discrete Location: Models, Algorithms, and Applications. Wiley. — Comprehensive treatment of covering and median problems.
Preparing for First Contact
We do recommend the Hungarian algorithm. It works on any planet.
Educational Fiction Disclaimer
This is a fictional educational scenario.
- All data and parameters are entirely fictional
- No military applications intended
- The author advocates for peace