废弃物收运网络的中转站选址—分配优化

摘要：本文解决美赛 2019-B 的第二层问题——在成本与环境约束下优化收运网络。在现状两阶段网络基础上，引入 7 个候选中转站（单站固定投资 3000 $），决策"选哪些站开放 + 每个产生点分配给最近优设施"，目标最小化日总成本（固定 + 收运 + 处理）。采用**子集穷举（2⁷=128）+ 可分离分配**精确解法：对每个开放子集，每个产生点独立选取"吨成本最小"的服务设施（直送厂或经某中转站），满足中转站容量硬约束。结果：最优开放 **TS1、TS4、TS5** 三站，日总成本由现状 **61392.5 降至 55741.2$ **（节约 9.21%），CO₂ 由 201.6 降至 148.0 吨/日（削减 26.57%）；收运成本降 4706.8 $**、处理费降 **944.5$ （图1—图3）。中转站利用率 TS1 82.3%、TS4 91.3%、TS5 35.0%（图4—图5）；边际价值分析显示 TS4 最关键（停用成本增 5651 $）、TS1 次之（2770$ ）、TS5 较弱（591 $）（图6）。优化还显著均衡了厂间负荷（P2 由 217.3 降至 37.1 吨/日，P3 升至 272.4）（图7）。本文方法为城市固废收运的"建站—分配"决策提供了可落地的精确方案。

关键词：设施选址；分配问题；子集穷举；成本—排放协同；边际价值；负荷均衡

一、问题重述

给定产生点、处理厂与候选中转站，如何决定中转站的"建/不建"以及每个产生点的归属，使系统日总成本最小、同时降低环境影响？需形式化决策变量与目标、设计可求解算法、解释最优解结构，并说明各中转站的贡献与厂间负荷变化。

本问对应城市环卫的"压缩站选址"决策：在已建处理厂格局固定的前提下，何时该建压缩站、建几座、建在哪，直接决定收运成本与居民满意度。模型输出（开放 TS=[1,4,5]）即"建站清单"，可立即转化为工程立项依据；而边际价值分析则回答了"如果预算只够建两座，先建哪两座"这一最现实的资源约束问题。这是城市环卫规划中的核心运筹问题，兼具学术训练价值与真实工程意义。

二、模型假设

沿用第一问网络与距离、流量设定；
中转站候选 7 个，开放需投固定成本 $\text{FC}=3000$ $/站，单站容量 160 吨/日；
收运单价分层：直送 $c^{\text{tr}}=3.0$ 、本地短驳 $c^{\text{loc}}=1.2$ 、长途转运 $c^{\text{ts}}=1.0$ （整车大批量更省）；
排放因子同步分层： $\text{ef}^{\text{tr}}=0.012$ 、 $\text{ef}^{\text{loc}}=0.006$ 、 $\text{ef}^{\text{ts}}=0.004$ ；
每个产生点必须且只能归属一个开放设施（直送厂或经某开放中转站），中转站容量不可超；
目标为日总成本最小（不含已发生的处理厂沉没成本）。

三、符号说明

符号	含义	单位
$S\subseteq\{0..6\}$	开放中转站子集	—
$x_{ij}\in\{0,1\}$	点 $i$ 是否经站 $j$	—
$\text{FC}$	单站固定投资	$
$c^{\text{loc}},c^{\text{ts}}$	本地 / 长途转运单价	$/(吨·单位距离)
$U_j$	站 $j$ 日承接量 / 利用率	吨/日, %

四、模型的建立

4.1 优化问题形式化

$\min_{S,\,x} \ \text{FC}\cdot|S|+\sum_i w_i\Big(d^{\text{loc}}_i c^{\text{loc}}+d^{\text{ts}}_i c^{\text{ts}}+\text{pc}_{p(i)}\Big)$

s.t. 每个 $i$ 分配到唯一开放设施； $\sum_{i\in j} w_i\le 160$ （中转站容量）。其中本地短驳按产生点到其归属站距离计、长途转运按站到目标厂距离计，二者因"整车化"而单价低于直送。

该问题的可分离性源于目标对产生点的可加：给定开放子集 $S$ ，任意点 $i$ 的最优服务设施只取决于 $i$ 自身的几何与流量，与 $j\ne i$ 无关。于是"联合选址—分配"这一通常 NP-hard 的组合问题，在 $S$ 固定时被分解为 24 个独立的一维最小选择，总复杂度降至 $O(2^K\cdot N\cdot(M+K))$ 。穷举 $S\in[0,2^K]$ 后对每子集取最小即得全局最优——这是本解法精确且高效的核心。

4.2 精确解法：子集穷举 + 可分离分配

关键观察：给定开放子集 $S$ ，每个产生点的成本仅取决于其自身选择（本地 + 长途 + 处理费可加），故分配可分离——对每个点独立取吨成本最小选项即可。于是算法为：

枚举 $S$ 的 $2^7=128$ 个子集；
对每个子集，逐点计算"直送各厂"与"经各开放站"的吨成本，取最小并累计、累加站承接量；
剔除超容量的子集（加罚），取总成本最小者。

复杂度 $O(128\times 24\times 11)\approx 3.4\times10^4$ ，秒级精确求解，无近似误差（图8）。

图1 优化后分配：开放 TS=[1,4,5]，CP 按最优归属着色

图2 优化 vs 基线：总成本与 CO2 双下降

4.3 最优解结构

最优开放 TS1、TS4、TS5：TS1 衔接 P0、TS4 衔接 P3、TS5 衔接 P1（长途目标厂）。三站把原直送 P2 的大批流量改道至有余量的 P0/P1/P3，既缩短本地短驳、又以低价长途替代高价直送（图1、图3）。这种"一站衔接一厂"的清晰拓扑使运营调度极简——每辆收运车只需认知"本片区归属哪座站、该站送往哪座厂"两条规则，降低了管理复杂度，是方案可落地性的隐性加分。

图3 成本节约分解：收运与处理双降

五、模型求解与结果

最优方案：开放 TS = [1, 4, 5]，日总成本 55741.2 $（基线 61392.5，节约 9.21%）；
排放：148.0 吨CO₂/日（基线 201.6，削减 26.57%）；
成本分解：收运 43027.9→38321.1（−4706.8），处理 18364.6→17420.1（−944.5）；
中转站利用率：TS1 82.3%、TS4 91.3%、TS5 35.0%（图4—图5）；
厂间负荷再均衡（图7）：P2 217.3→37.1、P3 126.4→272.4、P0 142.6→176.7、P1 137.4→137.4，超载消除。

将节约结构拆开看：收运由 43027.9 降至 38321.1（−4706.8，占节约额 83.3%），处理由 18364.6 降至 17420.1（−944.5，占 16.7%）。收运主导节约，印证"降单价、缩长途"是降本主引擎；处理费下降则源于流量改道至单位处理费更低的 P3（26 $/吨）与 P0（30），优化在降收运的同时天然完成了"择优厂"的二次优化。成本与排放同步下降，说明本网络存在真实的"经济—环境共赢"区间。值得注意的是，优化在降成本的同时把 P2 超载流量改道，等价于"零额外成本"地完成了一次厂间负荷重平衡，这是单目标成本优化意外收获的系统弹性。

图4 开放中转站利用率 (占容量 %)

图5 各开放中转站承接垃圾量 (吨/日)

六、结果分析与灵敏度

中转站为何省钱：本地短驳（1.2）替代了高价直送（3.0）的长途段，且长途转运（1.0）比直送（3.0）低 67%，规模效应显著——节约主要来自收运（占总额 83%）。
边际价值排序（图6）：TS4（5651 $）> TS1（2770$ ）> TS5（591 $）> 其余（≈0）。TS4 地处流量密集区且衔接远厂 P3，停用则大量流量被迫高价直送；TS2/3/6 边际≈0，说明其区位无增量价值，不建反省投资。
容量利用不均：TS4 近满载（91.3%）而 TS5 仅 35%，提示若未来需求增长，应优先扩容 TS4 或在其附近补站，而非增设低效站。
负荷均衡收益：P2 超载解除是最优解的重要外部红利——说明"就近直送"忽视了容量，而优化在降成本同时顺带修复了失衡。
方法稳健性：128 子集精确枚举无局部最优陷阱；若候选站增至 12 个（4096 子集）仍可秒级求解，算法具扩展性。
节约的结构弹性：总额外节约 5651.3 $/日中，收运贡献 4706.8（占 83%），处理仅 944.5（17%）——未来进一步降本应聚焦"提升收集密度、缩短本地短驳"，而非压处理费。
投资回收期极短：三站固定投资合计 9000 $，按日节约 5651.3$ 计，年节约约 206 万 $，回收期不足 2 天，经济性极强；这意味着"建中转站"在几乎所有城市固废场景下都是稳赚的战略投资。
与真实规划的接口：本模型输出的是"战略层选址"，落地时尚需叠加车辆调度、收运频次、司机工时等运营约束；但战略层已锁定约 83% 的节约空间，运营优化只是锦上添花——先定对"建在哪"，再谈"怎么跑"。

图6 各中转站边际价值 (强制停用后成本增量 $)

图7 优化后各处理厂负荷占比 (吨/日)

七、模型评价

优点：(1) 可分离结构使 NP-hard 选址问题退化为精确可解的穷举，结果可信；(2) 成本—排放双降，且顺带均衡厂间负荷，综合效益显著；(3) 边际价值分析直指"该建哪几座、哪座最关键"，给出可操作决策依据；(4) 全参数确定性（种子 2019），最优解与所有派生指标可一键复现。

局限：(1) 固定投资 3000 $/站为合成值，真实决策需按征地/建设单价标定；(2) 容量约束为硬上限，未考虑适度超容的弹性；(3) 未建模车辆数、收运频次等运营细节，属战略层选址而非调度层；(4) 中转站长途目标厂按"最近厂"固定，未让"站—厂"配对参与联合优化。

八、结论

引入 3 座中转站（TS1/4/5）即可在日成本降 9.21%、排放降 26.57% 的同时消除厂间超载，投资回报显著。决策要点：优先建设高边际价值站（TS4、TS1），低价值候选（TS2/3/6）不建以省投资；TS4 近满载提示其为准瓶颈，应预留扩容。本精确选址—分配框架可直接迁移至快递分拨、公交场站等同类网络优化。

管理启示：(1) 投资回收期 < 2 天，故"建中转站"应作为城市固废网络的默认标配而非可选优化；(2) 资源向高边际价值站倾斜——TS4（衔接远厂 P3）是系统枢纽，其周边应优先保障用地与扩容；(3) 低价值候选（TS2/3/6）不建，避免沉没投资；(4) 厂间负荷再均衡是优化的"免费红利"，规划新厂时应与中转站布局联合决策，而非各自为政；(5) 优化结果应随垃圾量增长定期重算——因 TS4 已近满载（91.3%），增长将首先触及该瓶颈，届时应优先扩容 TS4 或在其附近新建备选站。

图8 优化求解流程

附录：核心 Python 实现

# 附录：核心 Python 实现（独立可运行，复现本文权威数字）
import os, sys
_HERE = os.path.dirname(os.path.abspath(__file__))
sys.path.insert(0, os.path.abspath(os.path.join(_HERE, "..", "..", "..", "tools")))
import gen_mcm2019b as G

D = G.gen_mcm2019b()
o, b = D["opt"], D["base"]
print("最优开放 TS =", o["open"])
print("最优: 成本=%.1f CO2=%.1f" % (o["cost"], o["co2"]))
print("基线: 成本=%.1f CO2=%.1f" % (b["cost"], b["co2"]))
print("成本节约 = %.2f%%  CO2削减 = %.2f%%" % (o["savings"]*100, o["co2_cut"]*100))
print("中转站利用率 =", {j: round(v[1]*100, 1) for j, v in D["ts_util"].items()})
# 复现优化后各厂负荷
cps, plants = D["cps"], D["plants"]
TS2P = {o["open"][p]: o["ts_plant"][p] for p in range(len(o["open"]))}
pl = [0.0]*len(plants)
for (i, k, t) in o["assign"]:
    w = cps[i][2]; pl[t if k == 'plant' else TS2P[t]] += w
print("优化后四厂负荷 =", [round(x, 1) for x in pl])