针对无人机车队故障,提出两阶段拍卖框架,秒级重调度且保持高精度。
A Two-Stage Reactive Auction Framework for the Multi-Depot Rural Postman Problem with Dynamic Vehicle Failures
- 两阶段拍卖:先中心化快速生成可行解,再本地化优化修复。
- 实验显示平均调度时间从小时级降至秒级,提速超95%。
- 适合需要实时响应的无人机物流与巡检任务,尤其大规模场景。
尽管无人车车队在运输、物流和巡检中具有高效性,但其易发生故障,威胁任务连续性。本文研究带可充电可复用车辆的多起点乡村邮差问题(MD-RPP-RRV),其中部署于多个有容量限制的起点的无人车在服务弧段需求时可能失效。为应对运行中突发故障,提出两阶段实时重调度框架:第一阶段为集中式拍卖,快速生成可行解,并推导出理论上的加法界,提供最坏情况下的重调度惩罚保证;第二阶段为同侪拍卖,通过专用磁力场路由器进行局部调度修复,利用敏感性分析校准参数,确保计算量可控增长。在257种不同故障场景下对比模拟退火元启发式算法评估性能。结果表明,该框架平均运行时间相比基线减少超过95%,重调度时间从数小时缩短至秒级,同时保持高质量解。在大规模实例上,两阶段框架在近80%场景中优于集中拍卖,平均解质量提升超12%;在59%和28%的场景中分别优于模拟退火的均值和最优解,展现出实时任务连续性所需的优异速度-质量权衡。
原文摘要 · Abstract (English)
Although unmanned vehicle fleets offer efficiency in transportation, logistics and inspection, their susceptibility to failures poses a significant challenge to mission continuity. We study the Multi-Depot Rural Postman Problem with Rechargeable and Reusable Vehicles (MD-RPP-RRV) with vehicle failures, where unmanned rechargeable vehicles placed at multiple depots with capacity constraints may fail while serving arc-based demands. To address unexpected vehicle breakdowns during operation, we propose a two-stage real-time rescheduling framework. First, a centralized auction quickly generates a feasible rescheduling solution; for this stage, we derive a theoretical additive bound that establishes an analytical guarantee on the worst-case rescheduling penalty. Second, a peer auction refines this baseline through a problem-specific magnetic field router for local schedule repair, utilizing parameters calibrated via sensitivity analysis to ensure controlled computational growth. We benchmark this approach against a simulated annealing metaheuristic to evaluate solution quality and execution speed. Experimental results on 257 diverse failure scenarios demonstrate that the framework achieves an average runtime reduction of over 95\% relative to the metaheuristic baseline, cutting rescheduling times from hours to seconds while maintaining high solution quality. The two-stage framework excels on large-scale instances, surpassing the centralized auction in nearly 80\% of scenarios with an average solution improvement exceeding 12\%. Moreover, it outperforms the simulated annealing mean and best results in 59\% and 28\% of scenarios, respectively, offering the robust speed-quality trade-off required for real-time mission continuity.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。