无人机协同送货,优化路径与取货时机,提升运输效率与利润。
Drive, Pack, Fly: The Travelling Thief Problem with Drone
- 联合优化选货、车行路线与无人机飞行同步,减少时间成本。
- 无人机可缩短总时长,使大件货物运输效率提升20%以上。
- 适合物流调度、无人机配送等需动态协调的场景研究者参考。
在收集作业中,随着载重增加,车辆速度下降,导致路径效率持续降低。车载无人机可通过取回偏远物品来缓解这一问题,从而缩短完成时间并提高运营收益。然而,行驶时间仍受负载影响,地面车每收集一件物品都会改变无人机起飞和会合的时间点。本文提出旅行窃贼问题带无人机(TTP-D),通过联合优化物品选择、车辆路径与飞行同步,在扣除基于时间的租赁费用后最大化净收益。我们构建了混合整数线性规划模型求解小规模实例至最优,并设计了元启发式算法与基于注意力机制的深度强化学习(DRL)策略以应对大规模实例。进一步提出一种学习初始化的混合求解器:由DRL策略生成初始解,再经短时模拟退火优化。在两个基准数据集上,该混合方法以极低计算开销达到元启发式基线近90%的性能,但最大规模实例仍需全预算基线。敏感性分析表明,租赁费率是利润的主要决定因素,而车队参数仅边际影响收益。
原文摘要 · Abstract (English)
In collection operations, accumulating payload progressively slows the vehicle, imposing a cumulative penalty on routing efficiency. An onboard drone can offset this penalty by retrieving outlying items, thereby shortening the makespan and increasing operational profit. However, travel time remains load-dependent, and each item collected by the ground vehicle shifts the arrival times that govern the drone's launch and rendezvous points. This paper introduces the Travelling Thief Problem with Drone (TTP-D), which maximises the collected profit, net of a time-based rental cost, by jointly optimising item selection, vehicle routing, and flight synchronisation. We formulate a mixed-integer linear program that solves small instances to optimality, and develop both metaheuristics and an attention-based Deep Reinforcement Learning (DRL) policy for larger instances. We further propose a learner-initialised hybrid solver, in which the DRL policy constructs an initial solution that a short annealing run subsequently refines. On two benchmark sets, this hybrid recovers most of the metaheuristic baseline's quality at a fraction of its computational budget, although the largest instances still require the baseline at its full budget. Finally, a sensitivity analysis reveals that the rental ratio is the primary driver of profitability, whereas the fleet parameters affect profit only at the margin.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。