How to Maximize Mobile Coverage with Limited Tower Budgets: An Optimization Model

Problem Background

Over the past decade, smartphones have dramatically changed daily life, with more than 2 billion people worldwide using them for a wide range of activities beyond basic communication. Cellular networks connect each phone to the telephone system via radio waves from local cell‑site antennas.

A critical issue is the placement of mobile signal towers to provide coverage for the largest possible number of users.

Problem Description

A telecom company plans to build a set of cellular towers to cover residents of a specific city. Several potential tower sites have been identified, each with a fixed coverage radius. Due to budget limits, only a limited number of towers can be constructed. The goal is to choose tower locations that maximize the proportion of the population covered. The city is divided into regions, each with a known population.

Mathematical Model

Sets and Indices

I : index set of candidate tower sites

J : index set of regions

E : bipartite graph defining which towers can cover which regions; an edge (i, j) ∈ E indicates that tower i can cover region j.

Parameters

c_i : construction cost of tower i

p_j : population of region j

Decision Variables

x_j : equals 1 if region j is covered, otherwise 0.

y_i : equals 1 if a tower is built at site i, otherwise 0.

Objective Function

Maximize covered population : maximize the total population of covered regions, i.e., maximize \(\sum_{j\in J} p_j x_j\).

Constraints

Coverage : for each region j, at least one selected tower that can cover it must be built, i.e., \(x_j \le \sum_{i:(i,j)\in E} y_i\) for all j ∈ J.

Budget : the total construction cost cannot exceed the available budget B, i.e., \(\sum_{i\in I} c_i y_i \le B\).

References

[1] Richard Church and Charles R. Velle. "The Maximal Covering Location Problem". Papers in Regional Science, 1974, vol. 32, issue 1, 101‑118.

[2] Tail Assignment Problem. https://www.gurobi.com/case_study/air-france-tail-assignment-optimization/