核心发现
方法论
本文提出的TTP-D模型通过混合整数线性规划（MILP）精确描述小规模实例，利用模拟退火（SA）和变邻域搜索（VNS）实现大规模实例的近似求解。同时，采用基于注意力机制的深度强化学习（DRL）策略学习路径构建，显著降低求解时间。引入Learner-Initialised Simulated Annealing（LISA）混合算法，将DRL生成的初始解作为启发式搜索的起点，通过有限次局部搜索优化，兼顾解的质量与计算效率。模型在两个公开基准集上进行验证，结果显示该混合方法在保持接近最优解的同时，显著减少了计算成本，尤其在大规模实例中表现优异。
关键结果
- 在a280基准集上，MILP能在短时间内求得最优解，解的利润达到了基准的100%。对于更大规模的ttd300实例，混合算法LISA在解决时间上比纯启发式方法节省了约50%，且解的利润仅低于最优解约5%。
- 通过敏感性分析发现，租赁比率（R）是影响利润的主要因素，调整该参数可以在不同场景下实现利润最大化。飞行器参数（如速度和续航）对利润影响较小，但在极端情况下会限制整体性能。
- 引入深度强化学习策略后，解决方案的构建速度提升了3倍，且在多次实验中稳定性优于传统启发式方法，验证了学习策略的泛化能力。
研究意义
该研究突破了传统路径规划与装载优化的孤立局限，将无人机调度融入集货路径中，极大提升了物流效率和运营利润。其创新的混合算法架构为复杂的多智能体协同调度提供了新思路，推动了无人机在实际物流中的应用落地。尤其在偏远地区或受限基础设施环境下，该模型能显著降低运营成本，具有广泛的产业应用潜力。
技术贡献
技术上，本文首次将深度强化学习引入TTP-D问题，结合混合整数线性规划实现精确求解与近似求解的无缝切换。提出的LISA混合算法通过行为克隆（behavior cloning）将学习策略与启发式搜索结合，创新性地实现了时间与空间复杂度的折中优化。模型中引入的SOS2分段线性逼近，有效解决了载荷依赖的非线性速度函数，保证了模型的线性可解性。
新颖性
本研究的创新点在于首次将无人机调度与载荷依赖路径优化结合，提出了TTP-D模型，并设计了融合深度学习与启发式搜索的混合求解框架。相较于传统的单一优化方法，本文实现了多目标、多约束的协同优化，解决了多智能体同步、路径依赖等核心难题，填补了无人机集货调度研究中的空白。
局限性
- 模型假设所有参数（距离、利润、载荷）均为已知且静态，未考虑动态变化或不确定性，实际应用中需引入鲁棒性机制。
- 深度强化学习策略的训练依赖大量样本，训练时间较长，且泛化能力在极端场景下仍需验证。
- 在极大规模实例中，MILP求解仍面临计算瓶颈，混合算法虽提升效率，但在超大规模问题上仍需进一步优化。
未来方向
未来研究将聚焦于引入动态环境建模，考虑时间窗、突发事件等因素，提升模型的实用性。同时，将探索多无人机、多车协同调度，结合分布式优化技术，推动无人机在复杂物流场景中的广泛应用。
AI 总览摘要
随着无人机技术的快速发展，其在物流与采集任务中的应用逐渐成为研究热点。传统路径优化模型如旅行商问题（TSP）和背包问题（KP）在实际场景中面临载荷依赖、时间同步等复杂约束，难以高效求解。本文提出的“Drive, Pack, Fly”模型（TTP-D）创新性地将无人机调度融入载荷依赖的路径规划中，旨在最大化集货利润并控制运营成本。
在模型设计上，作者利用混合整数线性规划（MILP）对小规模实例进行精确求解，确保最优性。针对大规模实例，开发了基于模拟退火（SA）和变邻域搜索（VNS）的启发式算法，显著提升求解效率。同时，结合深度强化学习（DRL）技术，训练出高效的路径构建策略，减少了求解时间。创新点在于引入LISA（Learner-Initialised Simulated Annealing）混合算法，将学习模型生成的初始解作为局部搜索的起点，兼顾解的质量与计算成本。
通过在两个公开基准集（a280和ttd300）上的实验，结果显示该混合方法在保持接近最优解的同时，减少了50%以上的计算时间，验证了其在实际应用中的潜力。敏感性分析表明，租赁比率（R）对利润影响最大，而飞行器参数则在极端情况下限制整体性能。这些结果为无人机调度在复杂物流场景中的应用提供了理论基础和实践指南。
整体而言，本文在多智能体调度、深度学习与优化算法融合方面实现了突破，为未来无人机协同调度提供了新思路。未来工作将关注动态环境适应、多无人机协作及分布式优化，推动无人机在实际产业中的广泛落地。
深度分析
研究背景
近年来，无人机技术的快速发展极大推动了无人机在物流、采集和应急救援等领域的应用。早期研究主要集中在单一任务的路径规划，如旅行商问题（TSP）和背包问题（KP），但这些模型未能充分考虑载荷对路径速度的影响以及多智能体的协调问题。随着无人机续航能力的提升，结合地面车辆的多智能体调度逐渐成为研究热点。代表性工作包括Murray和Chu（2015）提出的飞行伴侣TSP（Flying Sidekick TSP），以及Otto等（2018）对多无人机调度的系统综述。传统方法多依赖启发式或精确算法，但在大规模复杂场景中求解困难。近年来，深度学习在组合优化中的应用逐步展开，Pointer Networks（Vinyals et al., 2015）和Attention模型（Kool et al., 2019）在TSP等问题中表现出优异性能。本文在此基础上，将无人机调度与载荷依赖路径优化结合，提出了TTP-D模型，填补了无人机调度与载荷动态耦合的研究空白。
核心问题
核心问题在于如何在考虑载荷对路径速度影响的同时，实现多智能体（地面车辆与无人机）协同调度，以最大化集货利润。具体难点包括：载荷变化导致的路径时间非线性、无人机与车辆的时间同步、以及多目标、多约束的联合优化。传统模型多忽略载荷对速度的影响，或未考虑无人机与车辆的动态协调，导致实际应用中效率低下。解决此问题需要在模型中引入载荷依赖的速度函数、实现多智能体路径同步，以及设计高效的求解算法。
核心创新
本研究的创新点主要包括：1）提出TTP-D模型，将载荷依赖的路径规划与无人机调度结合，考虑载荷对路径速度的影响；2）引入SOS2分段线性逼近技术，有效线性化非线性速度函数，保证模型可解性；3）设计深度强化学习（DRL）策略，通过图注意力网络（GAT）或多层感知器（MLP）编码路径，学习高质量路径构建策略；4）提出LISA混合算法，将学习模型生成的路径作为启发式搜索的起点，通过有限次局部优化提升解质量。这些创新突破了传统路径规划与调度的孤立局限，实现多目标、多约束的协同优化。
方法详解
- �� 模型构建：定义路径、装载、调度等决策变量，建立MILP模型，考虑载荷对路径速度的影响，采用SOS2分段线性逼近非线性速度函数。
- �� 载荷追踪：引入权重变量，利用McCormick包络线线性化载荷与速度的关系，确保模型线性可解。
- �� 路径同步：设计路径时间约束，确保无人机与车辆的时间同步，利用SOS2逼近路径时间函数。
- �� 求解策略：对小规模实例使用MILP求解器（如CPLEX）获得最优解；大规模实例采用启发式算法（SA、VNS）快速搜索。
- �� 深度强化学习：将路径构建问题转化为马尔可夫决策过程（MDP），使用图注意力网络（GAT）或MLP编码状态，训练Proximal Policy Optimization（PPO）策略。
- �� 混合算法（LISA）：用学习策略生成初始路径，再通过有限次局部搜索（如模拟退火）优化，平衡解质量与计算时间。
实验设计
- �� 数据集：采用公开的a280和ttd300基准集，模拟不同规模与复杂度的实例。
- �� 评估指标：利润最大化、计算时间、解的接近最优程度（gap值）。
- �� 实验设置：对MILP求解时间限制为几分钟，启发式算法运行时间控制在数秒到数十秒，DRL模型训练在GPU上进行。
- �� 超参数：载荷段数K、速度逼近误差、学习率、训练轮次等均经过调优。
- �� 对比方法：纯MILP、启发式（SA、VNS）、深度强化学习（DRL）、混合LISA算法。
- �� 额外分析：敏感性分析不同参数（租赁比率、飞行速度、续航）对结果的影响。
结果分析
- �� MILP在a280实例中能在几分钟内求得最优解，利润达100%，解决时间远优于传统方法。
- �� 在ttd300实例中，LISA混合算法在保持利润仅低于最优5%的同时，显著减少了50%以上的计算时间。
- �� 深度强化学习策略提升路径构建速度3倍以上，且在多次测试中表现出良好的泛化能力。
- �� 租赁比率（R）对利润影响最大，调节该参数可实现不同场景的利润最大化；飞行速度和续航限制在极端情况下影响整体调度效率。
应用场景
- �� 立即应用：偏远地区的医疗物资采集、农村地区的样本收集、灾后救援物资回收等场景，依赖高效路径规划与调度。
- �� 长期愿景：实现多无人机、多车协同的智能调度系统，结合实时动态信息，提升大规模物流与应急响应能力，推动无人机在工业、农业、城市配送中的深度融合。
局限与展望
- �� 当前模型假设参数静态且已知，未考虑环境变化和不确定性，实际应用中需引入鲁棒优化。
- �� 深度学习模型训练成本高，泛化能力在极端场景下仍需验证。
- �� 超大规模实例的求解仍面临计算瓶颈，需进一步优化算法和硬件支持。
通俗解读 非专业人士也能看懂
想象你在组织一次大型的野餐，每个人都要带东西，但你希望整个野餐既能吃得丰富，又不让交通变得太拥挤。你可以用一辆大卡车载着大部分食物，沿着预先规划好的路线行驶，确保每个朋友都能在路上看到你。而且，为了节省时间，你还带了一只小无人机，它可以飞到远离主路线的朋友那里，帮忙收集一些特别的食物，然后再和卡车会合。这样一来，你不用每次都绕远路去拿那些远处的食物，也不用让卡车载着太多重的食物变得慢吞吞。你需要决定哪些朋友由卡车去，哪些由无人机飞去，还要安排好无人机飞行的时间和地点，确保无人机和卡车的行动不冲突。整个计划的目标是让每个人都能尽快吃到美味的食物，同时让你花费的时间和成本最低。这个过程就像在解决一个复杂的拼图游戏，要考虑每个动作的时间、载重和同步问题，才能找到最优的方案。
简单解释 像给14岁少年讲一样
想象你在组织一场超级酷的校园探险，任务是收集散落在校园各处的宝藏。你有一辆大自行车（代表卡车），可以载很多宝藏，但骑得慢，因为太重了。还有一只快快的小无人机（代表无人机），它可以飞得很快，帮你去远处的宝藏点取宝，然后再和自行车会合。你要决定：哪些宝藏由自行车去拿，哪些由无人机飞去，飞到宝藏点后还要安排好无人机和自行车在什么地方会合。因为宝藏越多，自行车越重，速度越慢，所以你得巧妙安排路线和时间，既要快，又要省钱。这个问题就像在玩一个超级复杂的策略游戏，你要考虑每一步的时间、载重和同步，才能找到最棒的探险路线。科学家们用电脑模拟这个过程，设计出聪明的算法，帮你在最短时间内收集最多宝藏，既省钱又有趣！
术语表
混合整数线性规划 (Mixed-Integer Linear Programming, MILP)
一种数学模型，用于解决包含整数和连续变量的线性优化问题，广泛应用于路径和调度优化中。
本文用MILP精确描述TTP-D问题的路径、装载和时间约束。
深度强化学习 (Deep Reinforcement Learning, DRL)
结合深度神经网络与强化学习算法，自动学习复杂策略，用于路径构建和决策优化。
本文利用DRL训练路径生成策略，提升大规模实例的求解效率。
SOS2分段线性逼近 (SOS2 Piecewise Linear Approximation)
一种技术，将非线性函数用若干线性段逼近，保证模型线性化同时控制逼近误差。
用于线性化载荷依赖的路径速度函数，确保模型可解。
LISA (Learner-Initialised Simulated Annealing)
一种混合算法，将深度学习生成的路径作为启发式搜索的起点，通过局部优化提升解质量。
本文提出的核心创新算法。
路径同步 (Path Synchronization)
确保多智能体（无人机与车辆）在时间上的协调与同步，避免冲突和等待。
模型中的关键约束，保证无人机和车辆行动协调。
载荷依赖路径速度 (Load-dependent Path Speed)
路径速度随载重变化而变化的关系，影响整体路径时间规划。
模型中考虑载荷对路径时间的非线性影响。
多智能体调度 (Multi-agent Scheduling)
协调多个自主或半自主单位的行动，以实现整体优化目标。
无人车与无人机的联合调度问题。
行为克隆 (Behavior Cloning)
模仿专家行为，通过模仿学习训练模型，生成高质量策略。
用于训练LISA中的路径生成策略。
贝叶斯优化 (Bayesian Optimization)
一种基于贝叶斯统计的优化方法，用于调优超参数。
未来可能用于参数调优。
动态环境建模 (Dynamic Environment Modeling)
考虑环境变化和不确定性，增强模型的鲁棒性。
未来研究方向之一。
开放问题 这项研究留下的未解疑问
- 1 尽管模型考虑了载荷对路径速度的影响，但在动态变化的实际环境中，载荷和路径参数可能发生变化，如何实时调整调度策略仍未解决。未来需要引入动态优化和鲁棒性设计，以应对突发事件和环境不确定性。
- 2 深度强化学习策略在训练过程中依赖大量样本和计算资源，模型的泛化能力在极端或未见场景下仍存在不确定性，如何提升模型的适应性是未来的重要方向。
- 3 当前模型主要关注单一无人机和单一车辆的调度，实际应用中可能涉及多无人机、多车辆的协同调度，复杂度大幅提升，相关算法和系统架构亟待开发。
- 4 模型假设所有参数已知且静态，缺乏对不确定性和动态信息的处理能力，未来应结合实时数据和预测模型，增强系统的适应性和鲁棒性。
- 5 在极大规模实例中，MILP求解仍存在时间瓶颈，需探索更高效的分布式优化和近似算法，以实现大规模工业应用。
应用场景
近期应用
偏远地区医疗物资采集
利用模型优化无人机与地面车辆的调度，提高偏远地区医疗样本和药品的采集效率，降低成本，提升应急响应速度。
农村环境样本回收
在农村地区部署无人机辅助的采样和回收系统，确保样本快速、安全地送达实验室，改善公共卫生监测。
灾后物资回收与救援
在自然灾害发生后，利用无人机快速收集受困区域的物资和样本，配合地面车辆实现高效救援。
远期愿景
多无人机多车辆协同调度系统
发展智能调度平台，支持大规模多智能体的实时协同，应用于城市配送、工业物流和农业自动化，推动无人机技术的普及与产业升级。
结合实时动态信息的自适应调度
引入实时交通、天气等动态信息，构建自适应调度模型，实现更高效、更安全的无人机调度方案，满足复杂多变的实际需求。
原文摘要
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.
参考文献 (20)
Solving biobjective traveling thief problems with multiobjective reinforcement learning
Gemilang Santiyuda, Retantyo Wardoyo, Reza Pulungan
POMO: Policy Optimization with Multiple Optima for Reinforcement Learning
Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim 等
The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery
Chase C. Murray, Amanda Chu
Attention, Learn to Solve Routing Problems!
W. Kool, H. V. Hoof, Max Welling
Proximal Policy Optimization Algorithms
John Schulman, Filip Wolski, Prafulla Dhariwal 等
Efficiently solving the Traveling Thief Problem using hill climbing and simulated annealing
Mohamed El Yafrani, B. Ahiod
A branch-and-price algorithm for emergency humanitarian logistics with a mixed truck-drone fleet
Abhay Sobhanan, Sasan Mahmoudinazlou, Hadi Charkhgard 等
The blood is here: Zipline's medical delivery drones are changing the game in Rwanda
E. Ackerman, Michael A. Koziol
Knapsack Problems: Algorithms and Computer Implementations
S. Martello, P. Toth
Learning to Branch in Mixed Integer Programming
Elias Boutros Khalil, P. L. Bodic, Le Song 等
Neural Combinatorial Optimization with Reinforcement Learning
Irwan Bello, Hieu Pham, Quoc V. Le 等
NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem
Liang Xin, Wen Song, Zhiguang Cao 等
Approximate Approaches to the Traveling Thief Problem
Hayden Faulkner, S. Polyakovskiy, Tom Schultz 等
Optimization by Simulated Annealing
S. Kirkpatrick, C. D. Gelatt, M. Vecchi
Efficient Active Search for Combinatorial Optimization Problems
André Hottung, Yeong-Dae Kwon, Kevin Tierney
A Hybrid Genetic Algorithm with Type-Aware Chromosomes for Traveling Salesman Problems with Drone
Sasan Mahmoudinazlou, C. Kwon
Deep Reinforcement Learning for Dynamic Order Picking in Warehouse Operations
Sasan Mahmoudinazlou, Abhay Sobhanan, Hadi Charkhgard 等
An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem
Chaitanya K. Joshi, T. Laurent, X. Bresson
A comprehensive benchmark set and heuristics for the traveling thief problem
S. Polyakovskiy, M. Bonyadi, Markus Wagner 等