摘要
车辆调度问题（VRP）及其变体是现代物流和城市出行中最重要的优化挑战之一。本研究针对一种动态在线变体，结合了VRP和定向问题（OP）的元素，在固定时间范围内，一组车辆需最大化收集的累积奖励，并在新任务到达时不断重新规划。
我们提出了一种动态多车分配的奖励密度启发式方法，称为效率启发式。我们在两个应用领域进行了评估：自主无人机任务分配和城市出租车调度，涉及多个车队规模和任务规模。所提方法与四种经典构造启发式和三种元启发式算法（自适应大邻域搜索、遗传算法和模拟退火）进行了比较，所有算法在相同条件下进行评估。
在所有测试配置中，效率启发式匹配了最佳元启发式算法的解决方案质量，同时所需的规划时间减少了两个到三个数量级，在奖励与计算的权衡上优于所有竞争方法。这些发现为实时分配和调度系统提供了实用设计原则：在动态、时间受限的路由环境中，精心设计的贪婪启发式方法可以以较低的计算成本匹配复杂搜索过程的输出，使其在在线部署中更具优势。
博主点评： 本文提出的效率启发式方法在动态调度领域展现出了极高的实用价值，尤其是在需要快速响应的场景中，其计算效率显著优于传统方法，值得在实际应用中推广。通过将贪婪策略与动态任务分配相结合，作者为解决复杂的调度问题提供了创新思路。