电工杯 2025 B 范文：城市垃圾分类运输的路径优化与调度（分类 CVRP + 直运/中转对比 + 多指标评价）

一、摘要

针对 2025 年电工杯 B 题「城市垃圾分类运输的路径优化与调度」，本文构建了「合成收运网络 → 分类别带容量与时间窗的 CVRP → 直运/中转策略对比 → 成本·里程·工时·碳排多指标评价」的确定性建模框架。网络含 30 个收集点（10 km×10 km，四类垃圾按 40%/30%/25%/5% 比例产出，日均总量 41.05 t）、2 个中转站与 4 个分类处理厂，四类车型（厨余 5 t/可回收 4 t/其他 8 t/有害 1.5 t）严禁混装。求解采用最近邻构造 + 2-opt 局部搜索（SEED=20250502）。直运方案结果：12 趟车、总里程 374.4 km、总成本 3336 元/日、工时 49.2 h、碳排 336.9 kg CO₂；仅「其他」类出现 1 趟超窗（最长 6.17 h）。策略对比给出一个反直觉但稳健的结论：在紧凑城区（点均产量高、厂距近）中转模式并不省钱——厨余类收集段虽缩短 20.6 km，但大车出车固定费与装卸费（合计约 546 元）远超里程节省，综合节费率为 −29.9%，碳排亦因大车高排放因子不降反升。由此导出中转模式的盈亏平衡条件：收集段节省里程×单价必须覆盖「大车固定+装卸费」，即处理厂外迁、单点产量稀疏时中转才具优势。容量敏感性显示厨余车从 3 t 提至 5 t 可省 33% 成本（1611.5→1075.5 元），而 5→8 t 仅再省 25%，增益明显递减。全文纯标准库、零依赖、可复现，四路数字完全一致。

二、问题重述

生活垃圾分类后，「一辆车装走所有垃圾」的传统模式不再成立：不同类别禁混装、需专线车辆送对应处理厂，叠加收集点时间窗、车载容量、厂区接收能力，构成一个多品种、多场站、多约束的车辆路径与调度问题。赛题可归纳为四问：① 如何把「分类运输」抽象为规范的网络模型——点、站、厂的层级与「车型—垃圾类」一一对应的约束？② 单类垃圾的收运路径如何优化（容量硬约束 + 时间窗软约束）？③ 在直运（收集满直接送厂）与中转（先汇集中转站再批量运厂）之间如何选择？④ 用哪些指标评价方案，关键参数（车型容量）如何影响结果？本文的主线是「先解好每一类的小问题，再回答系统层的大问题」：分类别 CVRP 是基础件，策略对比是系统层的经济性判断。

三、模型假设与符号

H1（确定性合成）：官方数据未公开，采用固定种子（SEED=20250502）合成 30 点网络；坐标均匀分布于 10 km×10 km，单点日产量 0.5–2.0 t，路网距离=欧氏距离×1.2。
H2（禁混装）：每类垃圾由专用车型独立收运，路线互不交叉装载；厨余与其他两类在中转场景下允许经中转站换装大批量车。
H3（软时间窗）：收集时段 [6:00,12:00] 作为软约束处理，超窗路线计数并报告，不强行判无解。
H4（静态需求）：各点垃圾量为日清空模式的确定值，忽略日内累积动态与交通拥堵。

主要符号： $d_{ij}$ 为点间路网距离； $q_{i,k}$ 为点 $i$ 第 $k$ 类日产量； $Q_k$ 为 $k$ 类车型容量； $r$ 为一条路径（车场起讫）； $F$ =200 元/趟为出车固定成本， $c_d$ =2.5 元/km 为里程成本； $T_r$ 为路径时长（服务 0.1 h/点、卸料 0.2 h、车速 40 km/h）。

四、收运网络与分类 CVRP（问题 1–2）

4.1 网络与数据画像

图 2 展示了合成的收运网络：30 个收集点按主导垃圾类着色，厨余类的优化路径以边标注。四类垃圾日均总量分别为厨余 16.42 t、可回收 12.32 t、其他 10.26 t、有害 2.05 t（图 3）——产量结构与常见城市统计接近。值得注意有害垃圾虽然只占 5%，但其小车型（1.5 t）配稀疏分布导致单位收运成本高达约 284 元/t（582 元收 2.05 t），是厨余类（约 65 元/t）的四倍多——这为「有害垃圾设集中投放点、委托专业机构低频收运」提供了量化依据。

图1 建模框架

图2 收运网络

图3 四类垃圾日产量

4.2 求解器与收敛性

每类垃圾独立求解 CVRP：先用最近邻贪心构造可行解（容量硬约束下逐点扩张路径），再用 2-opt 算子做局部搜索——每次反转路径中的一段并检查容量与里程改进，直至无改进为止。以厨余类为例（图 4）：初始解总里程约 130 km，两轮 2-opt 后收敛到 110.2 km，降幅约 15%，验证了「构造+局部搜索」在小规模实例上的有效性。四类合计：12 趟车、374.4 km、成本 3336 元/日；各类里程见图 5。「其他」类出现 1 趟超窗（时长 6.17 h，超过 [6,12] 窗口约 10 分钟）——8 t 大车一趟串太多点的直接后果，实践中应拆分为两小趟或改双班制，本文按软约束保留并在评价中如实报告。

时间窗的处理方式本身也是一个建模决策点：若把 [6,12] 设为硬约束，本算例「其他」类将直接无解（10.26 t 用 8 t 车至少两趟，其中一趟天然超过 6 小时）；设为软约束后，模型保留了可行解空间，同时把违规信息透明地暴露给决策者——这正是赛题提示「优先软时间窗 + 罚分、再逐步收紧」的含义。此外，有害类虽未超窗，但最长 5.94 h 已逼近边界，说明低产量小车型同样存在「点多路远」的隐性时间压力，排班时应预留缓冲。

图4 2-opt 收敛曲线

图5 各类收运里程

五、直运 vs 中转：一个反直觉的策略结论（问题 3）

中转模式对厨余与其他两类启用：收集车卸于就近中转站即返场，再由 20 t 大车批量运厂。直觉上「小车短途集散 + 大车集约干线」应当更省，但算例给出了相反答案（图 6、图 7）：厨余类收集段确实从 110.2 km 缩到 89.6 km（省 51.5 元里程费），但大车出车固定费 300 元 + 装卸费 15 元/t×16.42 t≈246 元，把节省全部吃掉还倒贴；其他类同理。最终中转总成本 4332 元 vs 直运 3336 元，节费率 −29.9%；碳排也因大车排放因子（1.5 vs 0.9 kg/km）从 336.9 kg 微升至 338.8 kg——「省了里程、贵了系统」。

这一反例恰好导出了中转的盈亏平衡条件：

$\underbrace{c_d\,\Delta L}_{\text{收集段里程节省}} \;>\; \underbrace{n_{\text{trip}}\,(F^{tr}+c^{tr}_d\,\ell)}_{\text{大车干线成本}} + \underbrace{f_h\,Q}_{\text{装卸费}}$

其中 $\ell$ 为中转站到处理厂的距离。代入本算例厨余类数据：不等式右侧为 1×(300+3.5×7.59)+15×16.42≈573 元，而左侧里程节省仅约 51 元，缺口超过十倍——紧凑城区里 $\ell$ 小、单点产量高使 $\Delta L$ 有限，条件远不成立。再做一个思想实验：若处理厂外迁使 $\ell$ 增至约 40 km，直运方案的四条厨余路线每条都要多跑约 80 km 尾程（合计增支约 768 元），而中转的大车干线仅增支约 136 元——此消彼长，中转才会反超。这提示规划者：中转站不是「多多益善」的基础设施，而是「厂城距离」的函数，应随城市扩张与处理厂外迁动态重估。

图6 成本构成对比

图7 相对指标对比

六、多指标评价与容量敏感性（问题 4）

6.1 多指标透视

以直运=100 归一（图 7）：中转方案的相对成本 129.9、相对里程 94.4、相对碳排 100.6。三个指标讲了一个完整的故事——中转确实减少了车轮上的里程（环保与路面占用视角的微小正贡献），但在经济维度大幅倒退，且因大车排放因子更高，碳排并未受益。单一「里程最短」目标会系统性误导策略选择，这正是赛题要求多指标评价的原因。

6.2 容量敏感性：增益递减拐点

对厨余车容量做扫描（图 8）：3 t→1611.5 元（6 趟）、4 t→1294.4 元（5 趟）、5 t→1075.5 元（4 趟）、6 t→818.9 元（3 趟）、8 t→802.9 元（3 趟）。从 3 t 提到 5 t 日省 536 元（−33%），而从 5 t 到 8 t 仅再省 272.6 元（−25%）且趟数不再下降——增益递减拐点出现在 5–6 t 之间。结合厨余车的通行性约束（大车进背街小巷受限），5 t 是本网络下的合理选型；盲目采购大容量车只会徒增购置成本，却难以继续压缩日常开支。

图8 容量敏感性

七、结论与建议

分类别独立 CVRP（最近邻+2-opt）即可在小规模网络取得高质量解：12 趟、374.4 km、3336 元/日，厨余类 2-opt 收敛降幅约 15%；「其他」类 8 t 车单趟超窗提示大容量车需要配趟数约束或双班制。
有害垃圾单位收运成本约为厨余的 4.4 倍（284 vs 65 元/t），建议设集中投放点、降低收运频次而非加密线路。
中转模式在本算例节费率 −29.9%、碳排不降反升，其盈亏平衡取决于「厂城距离×产量汇聚度」——紧凑城区应优先直运，处理厂外迁后再评估中转；这修正了「中转必然集约」的直觉。
车型容量存在 5–6 t 的增益递减拐点；多指标评价（成本/里程/碳排/工时）必须同时呈现，否则单一里程目标会误导策略。

八、模型验证（四路一致）

三处校验：① 抽取厨余类最优解逐路径核算载重（均 ≤5 t）与里程（哈密顿分段求和），与真源输出一致；② 附录脚本独立重跑全流程，四类趟数/里程/成本、中转明细、敏感性曲线逐项吻合；③ 对比「其他」类直运与中转的收集段里程（72.5 vs 72.2 km），差异仅来自终点由厂改为站的尾段变化，逻辑自洽。正文、配图、附录、真源四路数字一致。

参考文献

[1] 2025 年电工杯数学建模竞赛 B 题：城市垃圾分类运输的路径优化与调度（赛题原文，官方数据未公开）。

[2] Clarke G, Wright J W. Scheduling of Vehicles from a Central Depot to a Number of Delivery Points[J]. Operations Research, 1964, 12(4): 568–581.

[3] Toth P, Vigo D. Vehicle Routing: Problems, Methods, and Applications[M]. SIAM, 2014.

[4] Croes G A. A Method for Solving Traveling-Salesman Problems[J]. Operations Research, 1958, 6(6): 791–812.（2-opt 原始文献）

附录：核心 Python 实现（可独立运行复现上述数字）

import sys, os
_HERE = os.path.dirname(os.path.abspath(__file__))
sys.path.insert(0, os.path.abspath(os.path.join(_HERE, "..", "..", "..", "tools")))
import gen_dgcup2025b as B

D = B.gen_dgcup2025b()
print("SEED=%d N=%d" % (D["seed"], B.N))
print("各类日总量(t):", {c: round(v, 2) for c, v in D["totals"].items()})
print("--- 直运 ---")
for c in B.CLASSES:
    i = D["direct"][c]
    print("  %s: %d趟 %.1fkm 最长%.2fh 超窗%d 成本%.0f元"
          % (c, i["n_routes"], i["km"], i["max_dur"], i["tw_viol"],
             D["direct_cost"][c]))
print("  合计 %.1f km / %.0f 元 / 工时 %.1fh / 碳排 %.1f kg"
      % (D["direct_km"], D["direct_total"], D["direct_hours"],
         D["carbon_direct"]))
print("中转 合计 %.1f km / %.0f 元 / 节费率 %.2f%%"
      % (D["transfer_km"], D["transfer_total"], D["saving_rate"] * 100))
print("厨余容量敏感:", [(s["cap"], s["n_routes"], s["cost"])
                    for s in D["sens"]])