面向农村物流需求波动的公交货运调度：随机情景驱动的优化建模方法
城乡公交闲置运力也能变身快递专线？
农村物流成本高、快递难下沉，而城乡公交却常常“空车运行”。 一边是物流缺口，一边是闲置运力 ——能否让改装后的公交车顺便送货？难点在于 班次改造是长期决策，但每日货运需求高度不确定 。
在需求高度不确定的农村场景中，怎样选择提供货运服务的公交班次，并在每天的随机需求下高效分配订单？模型如何在大规模场景下求解？
论文摘要
城市–农村公交由于客流稀疏、路线长且基础设施薄弱，存在大量闲置运力。本研究针对通过改装城乡公交车（车厢分割出货物仓）开展“公交货运”服务的调度问题，考虑了短期货运需求不确定性。作者提出两阶段随机规划模型：第一阶段决定哪些公交班次提供货运服务，第二阶段在每个场景下根据需求将订单分配到具体班次或弃运。为应对大量场景带来的计算瓶颈，研究设计了CPU‑GPU异构算法：外层利用 禁忌搜索（TS） 优化战略决策，内层利用 自适应大邻域搜索（ALNS） 并借助GPU并行加速求解每个场景下的订单分配。
实证基于山东东明县城乡公交系统数据，算法在四组实例上相较纯CPU实现获得26.5–246倍的加速，解决时间从数小时降至数分钟甚至数秒。敏感性分析显示，需求波动范围缩小能显著降低总成本并提高订单满足率。
一、研究背景与问题
1.1 城乡公交与货运整合的必要性
城乡客运运力闲置与物流缺口共存：农村地区人口稀疏导致公交运力利用率低，而电商快速增长又使农村物流成本高昂、企业积极性低。2019年中国交通运输部批准城乡公交开展货运服务，2024年发布试行指南，鼓励客货邮融合。 改装公交兼运货物的新模式：将公交车改装为乘客区和货运区，使闲置运力用于短途货运，可为公交企业增加收入、降低快递公司成本、促进农村商品流通。 调度决策复杂：应选择部分班次提供货运，以平衡改装投入与货运需求；同时货物装卸会增加停站时间并可能影响乘客体验。
1.2 现有研究与挑战
单阶段确定性模型的局限性：目前客货融合调度多采用混合整数规划或启发式算法，但大多假设需求确定，不足以描述农村货运需求的波动。 两阶段随机规划的必要性：城乡公交货运需要在长期战略决策（选择班次）和短期运营决策（订单分配）之间权衡，因此采用两阶段随机规划模型，并使用大量场景刻画不确定性。 计算复杂性高：第一阶段决策变量的组合复杂度为，第二阶段订单分配问题是NP难背包问题扩展，两者乘积使模型难以通过传统商用求解器在合理时间内求解。
二、模型构建
2.1 符号与决策变量
文中以拉丁字母表示参数，以希腊字母表示决策变量。核心符号如下：
集合与索引： 为所有停靠点，为公交线路集合， 为班次集合， 为订单集合， 为情景集合。 主要参数： 表示班次 到达站点 的时间， 为班次可承载货物容量， 为班次固定运营成本， 为历史各站每日订单量范围， 和 分别为未满足和延迟订单的惩罚成本， 分别为场景 下订单货量、目的站和截止时间。 决策变量：第一阶段变量 指示班次 是否改造为货运班次；第二阶段变量 表示订单 在场景 是否分配至班次 ， 表示订单 在场景 是否未服务。
2.2 第一阶段模型 M1：战略决策
目标是最小化改装班次的固定成本与第二阶段期望惩罚成本之和：
约束包括：
每条线路至少有一班被改造。 改造班次总容量应覆盖历史订单量范围。 决策变量为二元变量。
第一阶段决策决定货运班次集合，并通过 与第二阶段相连。
2.3 第二阶段模型 M2：运营决策
在给定第一阶段决策 和特定场景 下，第二阶段决定订单分配，目标最小化期望延迟和未服务惩罚：
关键约束：
订单只能分配给同线路的货运班次。 每个订单必须被配送或弃运。 班次货物总量不能超过容量。 为二元变量。
未服务和延迟惩罚被设定为与订单货量和滞后时间相关的线性函数。
2.4 模型难点与简化
由于 与 相互耦合，且场景数量大，模型求解复杂度高。文中通过引入虚拟班次处理未服务订单，以避免 GPU 并行中 if–else 分支；同时使用张量化结构表示订单分配，提高并行效率。
三、求解方法：两层CPU‑GPU异构算法
该算法由 外层禁忌搜索（TS） 和 内层GPU‑ALNS 组成，整体框架如图所示。
3.1 外层禁忌搜索：战略层优化
外层算法在CPU上运行，对第一阶段决策进行探索：
初始化：基于历史平均数据快速构造初始可行解，并设置禁忌表。 邻域生成：采用三种邻域操作生成新解：①单班次取反；②同线路内交换改造与未改造班次；③不同线路间交换。 可行性检查：检查新解是否违反容量区间约束并排除禁忌表中的重复解。 调用内层求解：对每个候选决策调用GPU‑ALNS求解第二阶段模型，并计算综合目标值。 更新：若新解优于当前最优，则更新最优解和禁忌表；迭代终止后输出结果。
3.2 内层 GPU‑ALNS：场景并行求解
内层算法针对每个场景并行求解订单分配问题，其核心特点：
自适应大邻域搜索框架：在模拟退火机制驱动下，交替选择移除和插入算子生成邻域解，动态调整算子权重。 移除算子：包括随机移除、相关移除和最差移除三类；其中相关移除根据订单目的站相似性衡量相关性并并行计算相似度矩阵。 插入算子：包括贪婪插入和二次后悔插入；贪婪插入将每个未分配订单分配至最小成本班次，适合GPU并行。 GPU并行实现细节：每个场景由一个GPU block处理；线程0负责加载数据和串行操作，其他线程并行完成相似度计算、插入成本矩阵生成、求最优插入等任务。 Greedy Insertion流程：下图展示了贪婪插入算子在GPU上的实现流程。
这种异构算法利用 CPU 处理战略层的组合决策，GPU 并行处理大量场景下的订单分配，大幅降低计算时间。
四、数值试验与分析
4.1 实例与实验设置
作者利用山东省东明县城乡公交系统的真实数据生成测试实例并随机生成订单场景，使用英特尔 Xeon 5218R CPU、NVIDIA RTX A2000/4060Ti/V100 GPU 进行测试。场景数量和实例规模分为四个分组，每组实例规模逐渐增大。
4.2 算法效率比较
与 Gurobi 在 3600秒 时间限制内求解相比，CPU‑GPU算法实现了数量级的加速，四个实例组的平均加速比分别约为 26.5、50.7、166.5、246.1。为了研究 GPU 型号对性能的影响，文中测试了 A2000、4060Ti 和 V100 三种 GPU。下图显示了不同实例规模下三种 GPU 的平均求解时间，可以看到随着问题规模增加，V100 的优势更加明显：
4.3 敏感性分析与管理启示
需求波动范围：缩小订单量波动范围会降低总成本并提高订单满足率；建立稳定的货运联盟能减少需求不确定性，从而降低闲置或不足的风险。 固定成本结构：将固定成本改为考虑班次容量、出发时间和乘客空间三因素的组合，能避免模型偏向高峰班次并取得更平衡的排班结果。 提升订单满足率：调整延迟惩罚系数或增加车厢容量会提高平均订单满足率，但固定成本增加较大；运营者需在服务水平与改装投入之间权衡。
五、创新点与亮点
两阶段随机规划框架：首次针对公交货运调度问题构建含场景的大规模随机规划模型，兼顾长期战略决策与短期运营决策。 CPU‑GPU 异构求解策略：设计外层禁忌搜索与内层 GPU‑ALNS 相结合的两层算法，充分利用 GPU 并行加速大规模场景求解，显著提升计算效率。 GPU 友好型解表示与算子实现：引入虚拟班次与张量化表示避免条件分支，引入贪婪和二次后悔插入算子，详细设计 GPU 线程协调与共享内存结构。 实证与敏感性分析：结合东明县实测数据构建实例，通过多 GPU 实验验证算法效率，进一步分析需求波动、固定成本结构和订单满足率对策略的影响，提供实际运营建议。
六、结论与展望
该研究指出，利用城乡公交闲置运力开展货运服务具有显著的经济与社会效益，但调度决策面临需求不确定和计算复杂性双重挑战。通过构建两阶段随机规划模型并采用 CPU‑GPU 异构算法，能够在合理时间内求解大规模调度问题，并提供具有实用价值的管理建议。未来研究可考虑引入更细致的运价和服务质量差异、动态需求预测以及多客运运营商的协同行为，进一步提高公交货运模式的实用性与效率。
文章须知
推文编辑：单子叶
责任编辑：张仁义
原文链接：https://doi.org/10.1016/j.tre.2025.104508
