联系我们

论文查询结果	返回搜索

论文编号：	16104
作者编号：	2120243798
上传时间：	2026/6/7 17:46:57
中文题目：	车无人机协同调度的Transformer改进ALNS算法研究
英文题目：	A Transformer-Enhanced Adaptive Large Neighborhood Search Algorithm for Truck–Drone Cooperative Scheduling
指导老师：	张建勇
中文关键字：	卡车无人机协同调度；Transformer架构；强化学习；ALNS算法
英文关键字：	truck–drone cooperative routing; Transformer architecture; reinforcement learning; adaptive large neighborhood search (ALNS)
中文摘要：	作为车辆调度问题重要分支的卡车无人机问题在理论研究层面自提出以来已有长足的发展，许多精确式、启发式、元启发式算法已经为该问题提供了一些高质量的求解方法。而近年来，在中国从国家层面大力发展低空经济的背景下，随着首批低空经济试点城市的敲定，卡车无人机在社会层面展现出更强的实用价值。随着技术的进步，机器学习方法在许多领域带来了新的思路和成果，特别是Transformer架构在自然语言处理和计算机视觉有关领域大放异彩，证明了这一机器学习框架的高质量与可靠性。一个自然的思路就是将Transformer架构迁移到卡车无人机问题中，使用机器学习的方法改进原有的元启发式框架，保持现有高质量求解能力的基础上用机器学习的方法更进一步以取得具有优势的求解质量。 本研究选择元启发式算法中应用广泛且效果优秀的自适应大邻域搜索算法（Adaptive Large Neighborhood Search，ALNS），提出了使用基于Transformer架构的机器学习模型来替代ALNS中的自适应选择机制，实现兼容各种破坏和修复算子的同时提高了模型框架的性能。具体来说，研究使用Graphormer编码器处理问题的整体图景和当前解的背景信息，使用Transformer解码器处理ALNS框架迭代的历史动作和动作的结果，使用全连接层综合以上信息输出算子和破坏规模的选择，使模型可以根据迭代进程的变化、之前动作的结果和当前解的信息选择更合适的算子和破坏规模。研究利用机器学习的动作空间优势将更多有效信息纳入模型决策考量并将破坏规模交与模型控制。通过以上的策略改进，该框架在小规模问题成功改进标准的ALNS算法并取得了接近精确解的求解质量，在大规模问题上改进了Mara等（2022）提出的一种基于ALNS框架的算法并取得了更优的求解质量。 综上，本研究的主要贡献如下：首先，设计了破坏算子与修复算子的联合选择机制，提升了搜索策略的协同性与稳定性，提升了ALNS框架的性能。此外，引入基于Transformer架构的算子选择模型，实现对复杂算子空间的高效建模与决策，显著优于传统自适应权重更新方法并解决了原有自适应选择机制随算子集扩大而劣化的问题。最后，提出可控破坏规模的联合学习策略，使模型能够根据搜索状态动态调节邻域规模，在局部优化与全局探索之间取得更优平衡。大量消融实验与对比实验结果表明，所提出方法在不同规模问题及扩展场景下均显著提升了解的质量与算法的泛化能力。
英文摘要：	As an important branch of the vehicle routing problem, the truck–drone cooperative routing problem has achieved substantial progress at the theoretical level since its inception. A variety of exact, heuristic, and metaheuristic algorithms have been developed, providing high-quality solution approaches. In recent years, under the national strategic push for the development of the low-altitude economy in China and the designation of pilot cities, the practical value of truck–drone systems has become increasingly prominent. Meanwhile, advances in machine learning have introduced new perspectives across many fields. In particular, the Transformer architecture has demonstrated remarkable success in natural language processing and computer vision, highlighting its effectiveness and robustness. A natural direction is therefore to transfer the Transformer architecture to the truck–drone problem and integrate machine learning techniques into existing metaheuristic frameworks to further enhance solution quality while preserving their strong optimization capabilities. In this study, we adopt the Adaptive Large Neighborhood Search (ALNS), a widely used and effective metaheuristic framework, and propose a Transformer-based learning approach to replace the adaptive operator selection mechanism in ALNS. The proposed framework is compatible with various destroy and repair operators while improving overall performance. Specifically, a Graphormer-based encoder is employed to capture the global structure of the problem and the contextual information of the current solution, while a Transformer decoder processes the historical sequence of actions and their outcomes during the ALNS iterations. A fully connected layer integrates these features to output both operator selection and destruction size decisions. This design enables the model to adaptively choose appropriate operators and neighborhood sizes based on the search progress, past performance, and current solution state. By leveraging the expressive power of machine learning, the framework incorporates richer information into decision-making and allows dynamic control of the destruction scale. Through these enhancements, the proposed method improves the standard ALNS algorithm on small-scale instances, achieving solution quality close to exact methods. On large-scale instances, it outperforms the ALNS-based approach proposed by Mara et al. (2022), yielding superior solution quality. The main contributions of this study are summarized as follows. First, a joint selection mechanism for destroy and repair operators is designed, enhancing the coordination and stability of the search process and improving the performance of the ALNS framework. Second, a Transformer-based operator selection model is introduced to efficiently model and optimize decisions in a complex operator space, significantly outperforming traditional adaptive weight updating methods and addressing their performance degradation as the operator set grows. Third, a jointly learned, controllable destruction-scale strategy is proposed, enabling the model to dynamically adjust neighborhood sizes and achieve a better balance between local exploitation and global exploration. Extensive ablation and comparative experiments demonstrate that the proposed approach significantly improves solution quality and generalization ability across different problem scales and extended scenarios.
查看全文：	预览  下载(下载需要进行登录)