动态多车辆路径规划中的奖励密度启发式算法：性能与计算效率

# 奖励密度启发式在动态多车路径规划中的性能与计算效率
来源: https://arxiv.org/html/2607.06066

###### 摘要

车辆路径问题\(VRP\)及其变体是现代物流与城市交通中实践意义最突出的优化挑战之一。我们研究一种结合了VRP和定向问题\(OP\)元素的动态在线变体：一组车辆必须在固定时间范围内最大化累积奖励，同时在新任务到达时持续重新规划。我们提出并评估了一种用于动态多车分配的奖励密度启发式方法（即效率启发式），涵盖两个领域——自主无人机任务分配和城市出租车调度——并在多种车队规模下进行测试。该方法与四种构造启发式算法和三种元启发式算法（ALNS、GA、SA）在相同条件下进行比较。在所有测试配置中，效率启发式达到了最佳元启发式算法的解质量，但规划时间减少了两到三个数量级，在奖励与计算量的前沿曲线上建立了对所有竞争方法的帕累托优势。

## I. 引言

2018年，美国企业在运输成本上的支出占其收入的10.4%，而整体物流支出占GDP的8%[1 (https://arxiv.org/html/2607.06066#bib.bib1)]。Dantzig和Ramser在1959年首次形式化的车辆路径问题\(VRP\)[2 (https://arxiv.org/html/2607.06066#bib.bib2)]是组合优化中研究最深入的问题之一。VRP和旅行商问题\(TSP\)[3 (https://arxiv.org/html/2607.06066#bib.bib3)]都是NP-hard问题，这使得大规模场景下的精确解法难以处理[4 (https://arxiv.org/html/2607.06066#bib.bib4)]，并对燃料消耗、配送时间和碳排放产生广泛影响[5 (https://arxiv.org/html/2607.06066#bib.bib5)]。

一个特别具有挑战性的变体是动态VRP，其中任务在线到达，车辆需要持续重新规划[6 (https://arxiv.org/html/2607.06066#bib.bib6),7 (https://arxiv.org/html/2607.06066#bib.bib7)]。我们专注于一种结合了动态VRP与定向问题\(OP\)[8 (https://arxiv.org/html/2607.06066#bib.bib8)]的公式，其中车辆在固定时间范围内最大化累积奖励。这种结构出现在无人机任务分配[9 (https://arxiv.org/html/2607.06066#bib.bib9),10 (https://arxiv.org/html/2607.06066#bib.bib10)]和城市出租车调度[11 (https://arxiv.org/html/2607.06066#bib.bib11),12 (https://arxiv.org/html/2607.06066#bib.bib12)]中：在这两种场景中，任务是动态到达的，车辆根据当前位置分配，约束条件是时间预算。这使得我们的公式与奖励收集VRP[13 (https://arxiv.org/html/2607.06066#bib.bib13)]和OP[8 (https://arxiv.org/html/2607.06066#bib.bib8)]一致，其中选择性完成任务是核心，并且两个领域都需要在毫秒内做出分配决策。

这种场景下，一个自然的选择是贪婪的奖励密度启发式方法——根据奖励除以时间成本对每个候选任务进行评分[14 (https://arxiv.org/html/2607.06066#bib.bib14)]。这种规则不需要群体、迭代或收敛。这种简单性是否相对于元启发式算法以解质量的明显代价为代价，这是一个具有直接实际意义且尚未实证回答的问题。

本文通过在五个实验配置中评估这个问题。效率启发式在合成无人机环境和真实纽约出租车调度数据[15 (https://arxiv.org/html/2607.06066#bib.bib15)]中，始终匹配ALNS、GA和SA的表现，同时规划时间减少两到三个数量级。贡献：(1) 一个统一的动态奖励最大化VRP框架；(2) 两种奖励密度实例化——贪婪顺序和最优匈牙利匹配[16 (https://arxiv.org/html/2607.06066#bib.bib16)]；(3) 在五个配置中系统性地展示了帕累托最优性能。

## II. 相关工作

### II-A 构造启发式算法

最近邻 (Greedy-Nearest): 最近邻启发式[20 (https://arxiv.org/html/2607.06066#bib.bib20)]贪婪地选择最近的未访问节点，在多多项式时间内生成路径，并作为标准VRP基线[21 (https://arxiv.org/html/2607.06066#bib.bib21)]。

奖励贪婪 (Greedy-Reward): 奖励贪婪启发式优先考虑高价值目标，无论空间位置如何，是奖励收集和定向问题公式的自然选择[22 (https://arxiv.org/html/2607.06066#bib.bib22)]。它们被广泛应用于UAV任务分配[9 (https://arxiv.org/html/2607.06066#bib.bib9)]，尽管可能将车辆分配到远距离目标而忽略附近价值相当的目标。

匈牙利算法: 匈牙利算法最优地解决分配问题，时间复杂度为多项式[16 (https://arxiv.org/html/2607.06066#bib.bib16)]，并广泛应用于多机器人任务分配和在线调度[23 (https://arxiv.org/html/2607.06066#bib.bib23)]。我们评估了两种变体：最小化旅行时间 (Hungarian-Time) 和最大化原始奖励 (Hungarian-Reward)，均使用SciPy[18 (https://arxiv.org/html/2607.06066#bib.bib18)]实现。

### II-B 元启发式算法

遗传算法[24 (https://arxiv.org/html/2607.06066#bib.bib24)]通过选择和变异进化候选解，在给定足够时间的情况下可在静态实例上产生接近最优的解。模拟退火[25 (https://arxiv.org/html/2607.06066#bib.bib25)]通过温度依赖的接受准则逃离局部最优，成本低于基于种群的方法，使其适用于时间受限的场景。ALNS[26 (https://arxiv.org/html/2607.06066#bib.bib26)]维护一个破坏和修复操作符的组合，并自适应选择，在多种VRP变体上表现优异。由于分配格局随着每次任务完成而改变，所有元启发式规划器在每次重新规划事件时都会重新初始化。

### II-C 效率启发式算法

奖励密度原则源于OP，Tsiligirides[14 (https://arxiv.org/html/2607.06066#bib.bib14)]引入了期望度量A\(j\)=Sj/tlast,j (每单位旅行时间的奖励)，作为S算法和D算法的基础。这种结构也类似于分数背包松弛[27 (https://arxiv.org/html/2607.06066#bib.bib27)]——密度贪婪在分数情况下是最优的——并已出现在分数规划[28 (https://arxiv.org/html/2607.06066#bib.bib28)]和时间约束定向问题[29 (https://arxiv.org/html/2607.06066#bib.bib29)]中。对于UAV操作，[30 (https://arxiv.org/html/2607.06066#bib.bib30)]提出了一种贪婪的最佳通道启发式，通过最大奖励-成本比选择目标，这直接类似于我们的评分规则。在动态场景中，[6 (https://arxiv.org/html/2607.06066#bib.bib6)]确立了静态解在线到达时会退化，从而激发了快速反应性重新规划。本研究将其扩展到完全动态、多车场景，并在两个领域中进行系统的元启发式比较。

## III. 方法

TABLE I: 对于12、20和50架无人机机队，无人机调度算法在奖励和规划时间方面的比较。参考算法为Hungarian-Efficiency；相对于参考的统计显著性由ns（不显著）、*（p<0.05）、**（p<0.01）或***（p<0.001）表示。

### III-A 问题公式化与仿真

一个由VV辆车组成的车队从一个中央仓库出发。一组NN个目标分布在M×M地图上，每个目标ii具有位置(xi,yi)、奖励ri∼U(1,100)和服务时间si∼U[5,30]时间单位。车辆速度从{10,15,30}地图单位/时间单位中抽取。只有当旅行时间加上服务时间不超过其剩余预算时，车辆才能被分配目标ii。目标是最大化所有车辆在任务持续时间内获得的总奖励。

我们实现了一个事件驱动的仿真器，其中重新规划在任务完成时触发。只有刚刚完成任务的车辆会收到新分配；正在途中的车辆不会被中断。同时完成的任务被批处理为一次重新规划调用。一个共享的已声明集合防止重复分配。性能通过在相同环境（使用共享随机种子）上的15次独立运行（无人机）和10次运行（出租车）进行评估。

### III-B 实验配置

无人机: 三种配置——12/50、20/100、50/200（车辆/目标）——在5000×5000地图上运行200个时间单位，奖励从1-100均匀抽取。出租车: 车队规模为50和200辆车，运行120分钟，处理约7,600个来自NYC TLC Yellow Cab 2024数据集[15 (https://arxiv.org/html/2607.06066#bib.bib15)]的任务。车辆从下车点顺序进行乘客行程；收入使用实际的TLC票价数据。该数据集提供了现实的空间聚类、异质的行程长度和随机VRP设置中典型的经验到达模式[13 (https://arxiv.org/html/2607.06066#bib.bib13),31 (https://arxiv.org/html/2607.06066#bib.bib31)]。

参见图注 图1: 三种车队规模下多无人机任务分配算法的性能比较。(a–c) 模拟时间（0–200秒）内的累积奖励，显示平均轨迹及置信区间。(d–f) 平均总奖励与总规划时间（毫秒），说明奖励-效率权衡（GA因比例问题省略）。

### III-C 算法

构造启发式算法遵循一个贪婪框架：对每个可行目标进行评分，每个空闲车辆依次取评分最高且未被声明的目标，车辆按索引顺序处理。Greedy-Nearest按负距离评分；Greedy-Reward按奖励值评分；Hungarian-Time通过SciPy[18 (https://arxiv.org/html/2607.06066#bib.bib18)]求解最小化旅行时间的分配问题；Hungarian-Reward求解同一分配问题但最大化奖励。

元启发式算法 (GA, SA, ALNS) 将分配编码为对长度为V的优先级向量的优化。GA使用epoch = 100，种群大小 = 50（MealPy[17 (https://arxiv.org/html/2607.06066#bib.bib17)]）。SA使用种群大小 = 2，冷却因子 0.95，epoch = 100，初始温度校准为目标平均奖励的15%。ALNS[19 (https://arxiv.org/html/2607.06066#bib.bib19)]每次规划使用200次迭代（无人机）或100次（出租车）；破坏操作符为随机移除和最差50%移除（按奖励-时间比）；修复操作符为贪婪效率与后悔基；轮盘赌选择使用得分[5,3,1,0]且衰减0.8，冷启动时使用贪婪效率解。

奖励密度启发式算法。每个任务从车辆的固定预算中消耗旅行时间加上服务时间，类似于分数背包。候选目标τ的期望得分是:

η(τ)=R(τ)/(d(v,τ)+s(τ)) (1)

其中R(τ)是奖励，d(v,τ)是从车辆位置v到目标的旅行时间，s(τ)是服务时间。这通过合并服务时间将Tsiligirides[14 (https://arxiv.org/html/2607.06066#bib.bib14)]扩展到动态多车场景。Greedy-Efficiency顺序地为每个空闲车辆分配其评分最高的可行未声明目标。Hungarian-Efficiency使用-η(τ)作为成本矩阵求解分配问题，在奖励密度目标下找到全局最优分配[16 (https://arxiv.org/html/2607.06066#bib.bib16)]。

### III-D 统计分析

我们报告平均值±标准误。统计显著性使用经Bonferroni校正的Mann-Whitney U检验，与Hungarian-Efficiency比较: *p<0.05, **p<0.01, ***p<0.001；ns = 不显著。累积奖励曲线通过将每次运行的阶跃函数插值到500点时间网格上取平均得到。

## IV. 结果

我们评估了四种启发式方法（Greedy-Nearest, Greedy-Reward, Hungarian-Time, Hungarian-Reward）和三种元启发式规划器（GA, SA, ALNS）在两个动态资源分配问题上的表现：在线无人机任务分配和出租车调度。性能通过累积奖励（或收入）和规划成本衡量。所有结果代表：无人机实验15次独立运行的平均值，出租车实验10次运行的平均值，误差线表示平均值的标准误，箱线图显示四分位距及平均值±标准误。无人机仿真针对三组任务参数运行，出租车调度实验针对两组任务参数。

### IV-A 无人机调度

在所有测试的车队规模（12、20和50架无人机）中，效率优化算法在收入上始终优于简单启发式，同时保持计算可行性。Hungarian-Efficiency作为主要参考，在12、20和50架无人机时的平均奖励分别为1,811、3,485和8,306。Greedy-Efficiency算法在所有规模下均紧密匹配此性能。

较简单的贪婪方法——Greedy-Nearest和Greedy-Reward——在所有车队规模下均显著低于Hungarian-Efficiency（p<0.05 到 p<0.001），而Hungarian-Time和Hungarian-Reward类似地表现不佳，在所有规模下收入显著低于效率启发式（p<0.001）。

元启发式方法——ALNS、GA和SA——均获得统计上与效率启发式相当的奖励（所有规模下ns），但规划成本显著更高。在50架无人机时，SA需要约5,247毫秒，ALNS约42,654毫秒，GA超过110万毫秒，而Hungarian-Efficiency仅需约128毫秒。这相当于规划开销分别约为40倍、330倍和8,600倍，使得这些方法在大规模实时调度中不可行。

出租车领域的结果在很大程度上复制了无人机发现，效率基方法在收入与速度权衡上占优。在50辆和200辆出租车两种情况下，Hungarian-Efficiency和Greedy-Efficiency取得了统计上等效的收入（ns），并显著高于其他启发式（p<0.001）。三种元启发式（ALNS, GA, SA）产生的收入统计上与Hungarian-Efficiency和Greedy-Efficiency无法区分，但产生了禁止性的规划时间。在200辆出租车时，GA每个规划周期需要约458万毫秒，SA约96,660毫秒，ALNS约236,765毫秒——而Hungarian-Efficiency仅需363毫秒。这些成本使这三种方法对于运营调度变得不切实际。

参见图注 图2: 两种车队规模下出租车调度算法的性能比较。(a–b) 模拟时间内的累积奖励。(c–d) 平均总奖励与总规划时间（毫秒）。误差线表示试验间的标准差（GA因比例问题省略）。

TABLE II: 对于50和200辆出租车车队规模，出租车调度算法在收入和规划时间方面的比较。数值报告为平均值±标准差。相对于参考方法（Hungarian-Efficiency）的统计显著性由ns（不显著）或***（p<0.001）表示。

综合来看，效率启发式在解质量上匹配了最先进的元启发式算法，同时计算时间减少了几个数量级。这使得它们特别适合需要实时重新规划的动态环境。这些结果在两个领域和多种车队规模中都是一致的，表明奖励密度原则是动态VRP任务中一种稳健且实用的方法。未来的工作可以探索自适应评分机制、时间相关reward以及异构车辆能力，以进一步扩展这一方法的适用性。