邮局选址问题：从组合优化建模到遗传算法与模拟退火实战

1. 邮局选址问题到底在解决什么

第一次看到“邮局选址问题”这个题目，很多人会以为就是在地图上找个地方盖房子。但真正动手做过的人都知道，这其实是一类非常经典的组合优化问题，核心目标是在若干个候选点中选出固定数量的位置，使得所有需求点到最近服务点的总距离最小。它跟“快递站点选址”“基站布点”“仓储中心布局”在数学模型上几乎是同一个东西，只是换了个业务外壳。

我最早接触这个问题是在一个物流调度的项目里，当时客户要求在一个片区里选三个中转站，让所有配送点的总运输成本最低。乍一看很简单，但候选点一多、需求点一散，暴力枚举直接爆炸。后来才发现，这类问题的标准解法在运筹学和算法教材里早有成熟框架，邮局选址只是它最朴素的一个变体。

这个题目适合谁看？如果你是正在做课程设计的学生、准备算法面试的求职者，或者工作中需要做设施选址的工程师，这篇内容都能直接拿去用。我会从问题建模讲到代码实现，再到实际调参时踩过的坑，尽量把每一步的“为什么”说清楚，而不是只丢一段代码让你自己悟。

提示：邮局选址问题的英文标准叫法是 Post Office Location Problem，在部分教材里也归为 P-中位问题（P-median Problem）的特例，搜索资料时两个关键词都可以试。

2. 问题建模与核心思路拆解

2.1 从业务语言翻译成数学语言

任何选址问题，第一步都是把“选几个点、让谁离得近、总成本怎么算”这三件事用数学符号固定下来。邮局选址问题的标准定义是这样的：给定 n 个需求点（比如居民区），每个点有一个权重（比如人口数或信件量），再给定 m 个候选点（比如可建邮局的位置），要求从中选出 p 个候选点作为邮局，使得每个需求点到最近邮局的距离乘以权重之和最小。

用公式表达就是最小化：

Σ(i=1..n) w_i * min(j∈S) d(i, j)

其中 S 是选中的 p 个邮局的集合，w_i 是第 i 个需求点的权重，d(i, j) 是需求点 i 到候选点 j 的距离。这个公式看起来简单，但 min 操作让目标函数变成了非线性的，不能直接用线性规划求解，这也是它属于 NP-hard 问题的原因。

我第一次建模时犯过一个错误：把权重全设成 1，结果算出来的选址方案在人口密集区表现很差。后来才意识到，权重代表的是业务量，忽略它等于假设每个需求点同等重要，这在真实场景里几乎不成立。

2.2 为什么不能暴力枚举

假设候选点有 20 个，要选 3 个，组合数是 C(20,3) = 1140，还能接受。但如果候选点 100 个、选 10 个，组合数就是 C(100,10) ≈ 1.73 × 10^13，普通计算机跑一辈子也算不完。这就是组合爆炸，也是为什么必须用启发式算法或精确算法来剪枝。

我在实际项目里试过两种路线：小规模（候选点少于 30）直接用整数规划求解器，能拿到全局最优解；大规模就上启发式算法，牺牲一点最优性换速度。下面这张表是我总结的选型参考：

注意：不要一上来就写遗传算法。如果规模不大，整数规划求解器几行代码就能出最优解，何必折腾启发式。我见过太多人为了“显得高级”直接上遗传算法，结果调参调到怀疑人生。

2.3 距离度量方式的选择

距离怎么算，直接决定结果。最常见的三种：欧氏距离、曼哈顿距离、网络距离。欧氏距离适合平面选址，曼哈顿距离适合网格状城市道路，网络距离适合有实际路网的情况。

我在一个城市配送项目里用过曼哈顿距离，因为那个片区的道路基本是横平竖直的。但如果换成山区，道路蜿蜒，就必须用实际路网距离，否则算出来的方案根本没法落地。这一点在课程设计里经常被忽略，很多人默认用欧氏距离，结果答辩时被问“现实中邮局是直线飞过去送信吗”就答不上来。

3. 核心算法实现与实操要点

3.1 贪心算法：快速拿到一个能用的解

贪心算法的思路很直白：每次从候选点里选一个能让当前总成本下降最多的点，直到选满 p 个。它不保证全局最优，但速度快，适合做初始解。

import numpy as np def greedy_location(demand_points, weights, candidates, p): n = len(demand_points) m = len(candidates) # 计算距离矩阵 dist = np.zeros((n, m)) for i in range(n): for j in range(m): dist[i][j] = np.linalg.norm(demand_points[i] - candidates[j]) selected = [] current_cost = np.sum(weights * np.min(dist, axis=1)) for _ in range(p): best_gain = -1 best_idx = -1 for j in range(m): if j in selected: continue # 临时加入该点后的成本 temp_dist = np.minimum(np.min(dist[:, selected], axis=1) if selected else np.inf, dist[:, j]) new_cost = np.sum(weights * temp_dist) gain = current_cost - new_cost if gain > best_gain: best_gain = gain best_idx = j selected.append(best_idx) current_cost -= best_gain return selected, current_cost

这段代码里有个细节：np.min(dist[:, selected], axis=1) if selected else np.inf这一行处理了第一次迭代时 selected 为空的情况。我第一次写的时候忘了这个判断，直接报错，调试了半小时才发现。

贪心算法的问题在于它可能陷入局部最优。比如有两个点单独看收益都不大，但组合起来覆盖效果很好，贪心就会错过。解决办法是跑多次贪心，每次随机打乱候选点顺序，取最好的结果。我一般跑 50 次，基本能接近最优解。

3.2 遗传算法：大规模问题的实用选择

遗传算法的核心是模拟自然选择：每个个体是一个选址方案，适应度是总成本的倒数，通过交叉和变异产生下一代。它的优势是不依赖梯度信息，能跳出局部最优。

import random def genetic_location(demand_points, weights, candidates, p, pop_size=50, generations=200): n = len(demand_points) m = len(candidates) dist = np.zeros((n, m)) for i in range(n): for j in range(m): dist[i][j] = np.linalg.norm(demand_points[i] - candidates[j]) def fitness(individual): selected = [i for i, v in enumerate(individual) if v == 1] if len(selected) != p: return -1e9 cost = np.sum(weights * np.min(dist[:, selected], axis=1)) return -cost # 初始化种群 population = [] for _ in range(pop_size): individual = [0] * m for idx in random.sample(range(m), p): individual[idx] = 1 population.append(individual) for gen in range(generations): population.sort(key=fitness, reverse=True) # 保留前20%精英 elites = population[:pop_size // 5] new_pop = elites[:] while len(new_pop) < pop_size: # 锦标赛选择 p1 = max(random.sample(population[:pop_size//2], 2), key=fitness) p2 = max(random.sample(population[:pop_size//2], 2), key=fitness) # 单点交叉 cross_point = random.randint(1, m-1) child = p1[:cross_point] + p2[cross_point:] # 变异 if random.random() < 0.1: ones = [i for i, v in enumerate(child) if v == 1] zeros = [i for i, v in enumerate(child) if v == 0] if ones and zeros: child[random.choice(ones)] = 0 child[random.choice(zeros)] = 1 # 修复：确保恰好p个1 ones = [i for i, v in enumerate(child) if v == 1] if len(ones) > p: for idx in random.sample(ones, len(ones) - p): child[idx] = 0 elif len(ones) < p: zeros = [i for i, v in enumerate(child) if v == 0] for idx in random.sample(zeros, p - len(ones)): child[idx] = 1 new_pop.append(child) population = new_pop best = max(population, key=fitness) selected = [i for i, v in enumerate(best) if v == 1] return selected, -fitness(best)

遗传算法最容易出问题的地方是约束修复。交叉和变异之后，个体里 1 的个数可能不等于 p，必须强制修复。我试过用惩罚函数代替修复，结果收敛速度慢了一半，后来还是老老实实写修复逻辑。

另一个坑是种群多样性。如果初始种群太相似，几代之后就全是近亲繁殖，解的质量上不去。我的做法是初始化时用随机采样，保证每个个体都不一样，另外每 50 代注入 10% 的随机新个体。

3.3 模拟退火：调参少但需要耐心

模拟退火的思路是允许一定概率接受更差的解，随着温度降低，接受概率逐渐减小。它的参数比遗传算法少，主要是初始温度、降温系数和终止温度。

import math def simulated_annealing(demand_points, weights, candidates, p, T0=1000, alpha=0.95, T_end=1e-3): n = len(demand_points) m = len(candidates) dist = np.zeros((n, m)) for i in range(n): for j in range(m): dist[i][j] = np.linalg.norm(demand_points[i] - candidates[j]) def cost(selected): return np.sum(weights * np.min(dist[:, selected], axis=1)) current = random.sample(range(m), p) current_cost = cost(current) best = current[:] best_cost = current_cost T = T0 while T > T_end: # 邻域操作：替换一个选中的点 new = current[:] out_idx = random.choice(new) candidates_left = [i for i in range(m) if i not in new] if not candidates_left: break new.remove(out_idx) new.append(random.choice(candidates_left)) new_cost = cost(new) if new_cost < current_cost or random.random() < math.exp((current_cost - new_cost) / T): current = new current_cost = new_cost if current_cost < best_cost: best = current[:] best_cost = current_cost T *= alpha return best, best_cost

模拟退火的关键是降温系数。alpha 设成 0.95 意味着每轮温度降 5%，通常跑几百轮就到底了。如果设成 0.99，跑得久但解更好。我在一个 200 个候选点的项目里用 0.99，跑了大概 2000 轮，耗时 3 秒左右，结果比遗传算法稳定。

提示：模拟退火的初始温度可以用“初始解的平均成本变化量”来估计，不用手动试。具体做法是随机扰动几次，取成本变化的平均值作为 T0。

4. 完整实操流程与参数选择

4.1 数据准备与预处理

真实项目里，数据从来不是现成的。需求点坐标可能来自 Excel，候选点可能来自地图标注，权重可能是人口、订单量或历史业务量。我一般用 pandas 读进来，统一转成 numpy 数组。

import pandas as pd demand_df = pd.read_csv('demand_points.csv') candidate_df = pd.read_csv('candidates.csv') demand_points = demand_df[['x', 'y']].values weights = demand_df['weight'].values candidates = candidate_df[['x', 'y']].values

预处理阶段要做三件事：去重（候选点可能有重复坐标）、归一化（如果 x 和 y 量纲差异大）、异常值处理（坐标明显偏离的点要检查）。我有一次没做去重，结果算法选了两个坐标几乎一样的点，方案完全没法用。

4.2 距离矩阵计算与内存优化

距离矩阵是 n×m 的，如果 n 和 m 都是几千，矩阵会占几百 MB。我一般用 float32 而不是 float64，内存直接减半。如果还是太大，就分块计算，不要一次性全算出来。

# 分块计算距离矩阵，避免内存溢出 def compute_dist_chunked(demand_points, candidates, chunk_size=1000): n = len(demand_points) m = len(candidates) dist = np.zeros((n, m), dtype=np.float32) for start in range(0, n, chunk_size): end = min(start + chunk_size, n) diff = demand_points[start:end, np.newaxis, :] - candidates[np.newaxis, :, :] dist[start:end] = np.sqrt(np.sum(diff ** 2, axis=2)) return dist

4.3 算法参数调优实录

参数调优没有万能公式，但有一些经验规律。遗传算法的种群大小一般取候选点数量的 2-5 倍，迭代次数 100-500 代。模拟退火的初始温度取 100-1000，降温系数 0.9-0.99。

我在一个 150 个候选点的项目里做过对比实验，结果如下：

可以看到，模拟退火在这个规模下性价比最高，整数规划虽然最优但耗时太长。实际项目中，如果对最优性要求不是极端严格，模拟退火完全够用。

4.4 结果可视化与验证

算完之后一定要画图验证。我一般用 matplotlib 把需求点、候选点、选中的点画出来，需求点用散点表示，大小代表权重，选中的邮局用红色星号标记。

import matplotlib.pyplot as plt plt.figure(figsize=(10, 8)) plt.scatter(demand_points[:, 0], demand_points[:, 1], s=weights*10, alpha=0.5, label='需求点') plt.scatter(candidates[:, 0], candidates[:, 1], c='gray', marker='s', label='候选点') selected_points = candidates[selected] plt.scatter(selected_points[:, 0], selected_points[:, 1], c='red', marker='*', s=300, label='选中邮局') plt.legend() plt.title('邮局选址方案') plt.show()

可视化能发现很多数值上看不出来的问题。比如有一次算法选了一个点，图上显示它周围几乎没有需求点，检查后发现那个候选点的坐标输错了，多了一个零。这种错误光看成本数字是发现不了的。

5. 常见问题与排查技巧实录

5.1 算法结果不稳定怎么办

启发式算法每次跑结果不一样是正常的，但如果波动太大，说明参数有问题。我遇到过一次遗传算法结果在 12000 到 15000 之间跳，后来发现是变异率设成了 0.5，太高了，种群一直在乱跳。把变异率降到 0.05 之后，结果稳定在 12400 左右。

另一个原因是随机种子没固定。做对比实验时一定要设random.seed(42)和np.random.seed(42)，否则没法复现。

5.2 选中的点明显不合理怎么排查

先检查距离矩阵。我有一次算出来的方案把所有邮局都选在了角落，排查后发现距离矩阵计算时用了np.linalg.norm但没指定 axis，结果算出来的是整个矩阵的范数，不是逐行逐列的。这种错误很隐蔽，因为代码不报错，只是结果离谱。

再检查权重。如果权重里有负数或零，目标函数就失去意义了。我一般会加一行assert np.all(weights > 0)做防御性编程。

5.3 大规模问题跑不动怎么优化

候选点超过 500 个时，距离矩阵计算本身就很慢。我的做法是先用 K-Means 把需求点聚成 50-100 个簇，用簇中心代替原始需求点，权重用簇内权重之和。这样问题规模直接降一个数量级，解的质量损失很小。

另一个技巧是候选点预筛选。如果某个候选点周围 5 公里内没有任何需求点，直接排除，不用参与计算。这个筛选能砍掉 30%-50% 的候选点，效果立竿见影。

5.4 常见问题速查表

提示：调试时先用小规模数据（10个需求点、5个候选点）跑通，确认逻辑正确后再上大规模数据。我见过太多人直接拿几千个点调试，出了问题根本不知道是算法错还是数据错。

6. 实际项目中的经验与扩展思路

邮局选址问题看起来是个学术题目，但实际用起来变体很多。我做过的一个项目里，客户要求每个邮局有容量上限，不能无限接收需求。这就变成了带容量约束的选址问题，需要在目标函数里加惩罚项，或者用拉格朗日松弛处理。

另一个变体是多目标选址，既要总距离小，又要每个邮局的服务范围均衡。这时候可以用加权求和把多目标转成单目标，或者用 NSGA-II 这类多目标遗传算法直接求 Pareto 前沿。

还有一个容易被忽略的点是动态选址。需求点不是一成不变的，每年可能新增或减少。我一般会留 10%-20% 的预算做后续调整，而不是一次性把 p 个点全定死。具体做法是先选 p-1 个核心点，留一个机动点，根据后续数据再决定。

代码实现上，我建议把距离计算、成本评估、算法主循环拆成独立函数，方便替换和测试。我自己的项目里，距离计算模块换过三次（欧氏→曼哈顿→路网），因为接口统一，换起来只改了一个函数，其他代码一行没动。

最后分享一个调试技巧：把每次迭代的最优成本打印出来，画成折线图。如果曲线早早平了，说明算法陷入局部最优，需要增大变异率或提高初始温度；如果曲线一直下降但很慢，说明降温系数太大，可以适当调小。这个图比任何日志都直观，我每次调参都靠它。