Notice: Trying to get property of non-object in /var/www/examples/cell-tower-coverage/index.php on line 51

Notice: Trying to get property of non-object in /var/www/examples/cell-tower-coverage/index.php on line 80

Notice: Trying to get property of non-object in /var/www/examples/cell-tower-coverage/index.php on line 94

Cell Tower Coverage

with integer programming and Gurobi

In this example we'll solve a simple covering problem: how to build cell towers to provide signal to the largest number of people.

We'll construct a mathematical model of the business problem, implement this model in Gurobi's Python interface, and compute and visualize an optimal solution.

Although your own business may not involve operating a telecommunications network, the same basic techniques used in this example can be used for many other applications.

Problem Description

A cell tower is a site where antennae and electronic equipment for communications are placed.

In this example, a telecom company needs to build a set of cell towers to provide signal for inhabitants on Cape Cod. A number of potential locations for building the towers have been determined. The choice of these locations is based on several factors, including how well the tower blends in to the surrounding environment and the height of the terrain.

The towers have a fixed range, and due to budget constraints only a limited number of them can be built. Given these restrictions, the company wishes to provide coverage to as large a fraction of the population as possible.

To simplify the problem, the company has split the area it wishes to cover into a set of regions, each of which has a known population.

The goal is then to choose at which of the potential locations the company should build cell towers to provide coverage to as many people as possible.

Mathematical Model

Our example is an instance of the Maximal Covering Location Problem. It is also related to the Set Cover Problem. Covering problems occur in many different fields. We'll describe the mathematical model for this business problem in terms of cell towers, but it's important to remember that the techniques used here can be applied to a large set of problems.

First, let $R$ be the set of regions. For each of these regions we associate a binary variable: $r_j = \left\{\begin{array}{ll} 1 & \text{if region j is covered}\\ 0 & \mathrm{otherwise.} \end{array}\right.$ The population in region $j$ is denoted by $p_j$.

Secondly, we let $T$ denote the set of potential sites where we can build the towers. We associate a binary variable with each of these sites: $t_i = \left\{\begin{array}{ll} 1 & \text{if tower i is built}\\ 0 & \mathrm{otherwise} \end{array}\right.$ The cost of setting up the tower at site $i$ is denoted by $c_i$.

We then create a bipartite graph $G(T, R, E)$ and place an edge $(i,j)$ in $E$ if region $j$ is covered by tower $i$. An example of a bipartite graph for 3 towers and 8 regions is shown below. Hover over the different towers and regions to see how they are covered. For example, tower 1 (in the top left) covers regions 1, 3, 6 and 7. And region 3 is covered by towers 1 and 3.

At least one tower that covers a region must be selected, for that region to be covered. This yields a constraint $\sum_{(i, j) \in E} t_{i} \geq r_j$ for each region $j \in R$.

In addition, we cannot exceed the allocated budget. So we have the constraint $\sum_{i \in T} c_{i} t_{i} \leq \text{budget}$

We seek to maximize the total population covered by the towers, so the optimization model is given by: $\begin{array}{ll} \text{maximize} & \sum_{j \in R} p_j r_j} \\ \text{subject to} & \sum_{(i, j) \in E} t_{i}} \geq r_j \quad \forall r_j \in R\\ & \sum_{i \in T} c_{i} t_{i}} \leq \text{budget} \\ & t_i \in \{ 0, 1 \} \\ & r_j \in \{ 0, 1 \}. \end{array}$

Implementation

Below is the full implementation of the model (and the associated data) in Gurobi's Python interface:

from gurobipy import * # Problem Data # Population in each region pop = [523, 690, 420, 1010, 1200, 850, 400, 1008, 950] # Regions covered by each tower sites = [[0,1,5], [0,7,8], [2,3,4,6], [2,5,6], [0,2,6,7,8], [3,4,8]] # Cost to build tower (in millions of dollars) cost = [4.2, 6.1, 5.2, 5.5, 4.8, 9.2] # Allocated budget (in millions of dollars) budget = 20 numR = len(pop) # Number of regions numT = len(sites) # Number of sites for towers m = Model() t = {} # Binary variables for each tower r = {} # Binary variable for each region for i in range(numT): t[i] = m.addVar(vtype=GRB.BINARY, name="t%d" % i) for j in range(numR): r[j] = m.addVar(vtype=GRB.BINARY, name="r%d" % j) m.update() for j in range(numR): m.addConstr(quicksum(t[i] for i in range(numT) if j in sites[i]) >= r[j]) m.addConstr(quicksum( cost[i]*t[i] for i in range(numT) ) <= budget) m.setObjective(quicksum( pop[j]*r[j] for j in range(numR) ), GRB.MAXIMIZE) m.optimize()

Live Demo

Below is a visualization of the example we have discussed.

We have divided Cape Cod into several regions. The population of each region has been determined using US Census data. The larger the population of the region, the darker its color.

You can add potential cell tower locations by clicking the map. They are represented by:

The coverage radius of the towers (8 miles) is also shown.

Click "Compute" to determine the location of cell towers which maximizes the population that has signal. If the tower is built, the cell tower location and the regions that are covered will turn yellow. Note that a region is considered to be covered only if it is entirely covered by a single cell tower.

Click "Restart" if you wish to remove your current choice of cell tower locations.

The budget currently allows for the construction of 4 towers, but you can increase the budget by using the slider below.

4 Towers