问题背景

在过去的十年里，智能手机已经彻底改变了我们的生活，其方式远远超出了我们的沟通方式。除了打电话、发短信和发电子邮件之外，现在全世界有超过20亿人使用这些设备来预订出租车、比较产品评论和价格、关注新闻、看电影、听音乐、玩视频游戏、拍照、参与社交媒体以及许多其他应用程序。

蜂窝网络是一种手持智能手机网络，其中每一部手机通过蜂窝基站(蜂窝基站)的本地天线通过无线电波与电话网络进行通信。一个重要的问题是手机信号塔的位置，以便为最多的人提供信号覆盖。

问题描述

一家电信公司需要建造一套手机信号塔来为特定城市的居民提供信号覆盖。目前已经确定了几个可能建造信号塔的地点。这些塔有固定的范围，而且由于预算限制，只能建造有限数量的塔。鉴于这些限制，该公司希望尽可能为最大比例的人口提供覆盖。为了简化这个问题，该公司将其希望覆盖的地区划分为一系列区域，每个区域都有已知的人口。接下来的目标是选择公司应该在哪些潜在地点建立手机信号塔，以便为尽可能多的人提供信号覆盖。

数学模型

集合和索引

• $i \in T$: 备选信号塔的索引
• $j \in R$: 区域索引
• $G(T,R,E)$: 定义信号塔 $T$ 与区域 $R$ 匹配的二分图, $E$ 是边的集合， $(i,j) \in E$ 表示区域$j \in R$ 能被信号塔 $i \in T$覆盖.

参数

• $c_{i} \in \mathbb{R}^+$: 建造信号塔 $i$的费用.
• $p_{j} \in \mathbb{N}$: 区域 $j$的人口.

决策变量

$covered_{j} \in \{0, 1 \}$: This variable is equal to 1 if region $j$ is covered; and 0 otherwise.

$build_{i} \in \{0, 1 \}$: This variable is equal to 1 if tower $i$ is built; and 0 otherwise.

目标函数

• 覆盖人口.我们希望找到最大的信号塔覆盖的人群 $$ \begin{equation} \text{Max} \quad Z = \sum_{j \in R} p_{j} \cdot covered_{j} \tag{0} \end{equation} $$

约束条件

• 覆盖. 对于区域 $j \in R$ 要确保最少有一个信号塔可以覆盖 $$ \begin{equation} \sum_{(i,j) \in E} build_{i} \geq covered_{j} \quad \forall j \in R \tag{1} \end{equation} $$

• 预算. 建设塔的费用不能超出预算

$$ \begin{equation} \sum_{i \in T} c_{i} \cdot build_{i} \leq \text{budget} \tag{2} \end{equation} $$

数据

信号塔的覆盖情况

	Region 0	Region 1	Region 2	Region 3	Region 4	Region 5	Region 6	Region 7	Region 8
Tower 0	1	1	-	-	-	1	-	-	-
Tower 1	1	-	-	-	-	-	-	1	1
Tower 2	-	-	1	1	1	-	1	-	-
Tower 3	-	-	1	-	-	1	1	-	-
Tower 4	1	-	1	-	-	-	1	1	1
Tower 5	-	-	-	1	1	-	-	-	1

每个区域的人口

	Region 0	Region 1	Region 2	Region 3	Region 4	Region 5	Region 6	Region 7	Region 8
Population	523	690	420	1010	1200	850	400	1008	950

信号塔的建设费用

	Cost (millions of USD)
Tower 0	4.2
Tower 1	6.1
Tower 2	5.2
Tower 3	5.5
Tower 4	4.8
Tower 5	9.2

预算 $\$20,000,000$.

参考资料： [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/

import pulp as lp

# 参数
budget = 20
regions = range(0,9) # 区域
# 人口
population = {
    0: 523, 1: 690, 2: 420,
    3: 1010, 4: 1200, 5: 850,
    6: 400, 7: 1008, 8: 950
}

sites = range(0,6) # 信号塔
# 覆盖
coverage = {
    0: {0,1,5},
    1: {0,7,8}, 
    2: {2,3,4,6},
    3: {2,5,6},
    4: {0,2,6,7,8},
    5: {3,4,8}
}
# 费用
cost = {
    0: 4.2,
    1: 6.1,
    2: 5.2,
    3: 5.5,
    4: 4.8,
    5: 9.2
}

# 模型构建
m = lp.LpProblem(name="cell_tower",sense=lp.LpMaximize)

build = lp.LpVariable.dicts(name="Build",indexs=sites,cat='Binary' )
is_covered = lp.LpVariable.dicts(name="Is_covered",indexs=regions,cat='Binary')

obj = lp.lpSum(is_covered[r]*population[r] for r in regions)
m += obj

for r in regions:
    m += lp.lpSum(build[t] for t in sites if r in coverage[t]) >= is_covered[r]

m += lp.lpSum(build[t]*cost[t] for t in sites) <= budget, "budget"

m.solve()

1

for t in sites:
    print(build[t],lp.value(build[t]))

Build_0 1.0
Build_1 0.0
Build_2 0.0
Build_3 0.0
Build_4 1.0
Build_5 1.0

---