Page 157 - 《软件学报》2026年第5期

2036 软件学报 2026 年第 37 卷第 5 期

前向传播开销.
总体而言, TB-Match 的推理复杂度主要由待分配货车和运单的规模决定, 约为 O(|D||O|), 与贪心算法 (greedy
matching, GM) 在同一数量级, 但具有更大的常数因子. 然而, 它远优于需要构建和求解二分图的匈牙利算法 (Hun-
( )
3
garian algorithm, HA), 后者的复杂度为 O max(|D|,|O|) . 在实际应用中, 可以通过引入候选集生成等剪枝策略 (例
( )
¯
¯
如, 仅考虑地理上邻近的司机-订单对), 将复杂度从 O(|D||O|) 降低到 O |D|·k , 其中 k 是每个司机的平均候选订
单数, 以更高效地处理大规模的实时运单分配任务.
4 实 验
本实验部分将解决以下问题.
RQ1: 我们提出的模型与其他现有模型相比表现如何?
RQ2: 不同模型组件的效果如何?
RQ3: 超参数如何影响模型性能?
RQ4: 我们提出的模型在鲁棒性指标方面的表现如何?
4.1 实验设置
4.1.1 实验数据集描述
● RS 数据集. 该数据集由一家钢铁公司提供, 包含货运账单和司机信息. 整个数据集包含 173 000 条运输任务
记录, 涉及 1 200 多名司机的信息, 时间跨度为两个月 (2020 年 7–8 月). 在实际实验中, 平均每日运单数量为
2 883 条, 每 15 min 划分为一个批次, 平均每批次分配涉及 150 个运单与 80 名可用司机. 每条记录包括执行运输
任务的司机 ID、运输目的地 (经度、纬度及其所属行政区域)、运输开始和结束的日期与时间、完成运输所需的
时间以及运输距离. 该数据集中的运输任务都具有相同的出发点, 我们将使用该数据集测试模型在只有一个出发
点时的性能.
● DT-CARGO 数据集 [27] . DT-CARGO 是慕尼黑工业大学于 2021 年秋季至 2022 年春季从 54 辆货车收集的
开源数据集. 由于该数据集不包含具体的任务信息, 我们将货车从驶离工业区到下一个工业区的行程视为一次运
输任务, 并为每次运输任务随机分配运输重量. 每次行程的第 1 个和最后一个标记分别被标记为运输的出发点和
目的地.
4.1.2 基线模型设置
为全面评估所提出 TB-Match 框架的有效性与先进性, 本文选取了 6 种具有代表性的基线方法进行对比实验,
涵盖了传统启发式、经典组合优化、元启发式算法、图神经网络及强化学习等不同技术范式. 具体如下.
● 贪婪匹配 (GM): 作为运单分配领域的经典启发式算法, GM 采用局部最优策略, 在每个决策时刻将待分配
运单优先分配给当前接单概率最高的可用司机.
● 匈牙利算法 (HA): 作为二分图最大权匹配的经典组合优化算法, HA 通过构建司机-运单二分图并求解最大
权重匹配, 能够在静态假设下保证全局最优解.
● 遗传算法 (genetic algorithm, GA) [28] : 作为元启发式优化方法的代表, GA 通过模拟生物进化过程求解带时间
约束的任务分配问题. 该方法采用染色体编码表示分配方案, 通过选择、交叉、变异等遗传操作在解空间中进行
全局搜索.
[3]
● 时间加权偏好感知任务分配 (temporal-weighted preference-aware task assignment, TPTA) : TPTA 基于协同
过滤理论构建工作者偏好模型, 通过分析历史交互数据挖掘工作者的任务偏好模式, 并结合时间衰减因子捕捉偏
好的动态演化特征.
● 融合用户偏好学习任务分配 (fused user preference learning for task assignment, FUPTA) [29] : FUPTA 采用图神
经网络架构建模工作者-任务交互关系, 通过图卷积操作聚合邻域信息学习工作者的深层偏好表征.
● 偏好强化学习 (multi-agent preference Transformer, MAPT) [11] : MAPT 是一个多智能体偏好学习框架, 利用级