基于LLM（法律硕士）的自动启发式设计方法，用于车辆与无人机协同路由问题

《TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW》：LLM-based automatic heuristic design for vehicle-drone collaborative routing problems

车辆-无人机协作路由问题（VDCRPs）因提升物流效率潜力大而受关注，但存在结构复杂、变体多样等挑战。本研究提出LLM-VD框架，整合大语言模型（LLM）与进化计算，通过结构化提示生成、优化启发式算法，并设计两种自调试机制：反馈修正防止重复错误，代码级修复优化可行解。实验表明LLM-VD在三个VDCRP变体中生成的启发式算法性能优于基线，成功率达四倍提升，且泛化性强。

　　

海阳 施| 陆臻

上海大学管理学院，上海上大路99号，200444，中国

摘要

车辆-无人机协同路由问题（VDCRPs）由于具有提高物流效率的潜力而受到越来越多的关注。然而，由于它们的结构复杂性和变体的多样性，设计有效的算法仍然具有挑战性。本研究提出了一个新颖的自动启发式设计框架，称为LLM-VD，该框架将大型语言模型（LLMs）的文本生成能力与进化计算框架相结合。通过结构化的提示策略，该框架能够高效地生成、演化和评估VDCRP启发式方法。LLM-VD的一个关键创新是整合了两种互补的自我调试机制。第一种机制将结构化的失败反馈纳入后续提示中，以防止重复错误；第二种机制使用修复提示，将失败的启发式方法与其反馈配对，以指导算法的反思性修正。在三种VDCRP变体上的实验表明，LLM-VD能够生成高质量的启发式方法，其性能优于基线启发式方法，并且在不同的LLMs之间具有良好的泛化能力。这两种自我调试机制显著提高了成功率，对于最复杂的问题变体，成功率提高了近四倍。这些发现强调了进化计算和自我调试机制在提高自动启发式设计框架的鲁棒性和适应性方面的潜力。LLM-VD为VDCRPs提供了一种有前景的方法，并可以扩展到其他复杂的组合优化问题。

引言

随着低空飞行技术的快速发展，无人机（UAVs）在物流、军事行动、农业生产和服务领域得到了越来越广泛的应用，展现了前所未有的灵活性和响应能力。特别是在物流领域（Moshref-Javadi和Winkenbach，2021；Wu等人，2023），车辆-无人机协同配送模型利用了地面车辆的耐力和载重能力以及无人机的敏捷性和速度，能够在无需额外基础设施的情况下快速响应客户需求。例如，在人口密集的城市地区，无人机可以减少交通拥堵造成的延误（Paul等人，2025；Zhen等人，2025）。相反，在农村地区或灾区，无人机可以克服地形和道路限制，即使在基础设施受损或资源稀缺的情况下也能快速交付紧急物资（Lu等人，2025；Yin等人，2023）。这些优势促使车辆-无人机协作在实践中得到越来越多的应用，从而确立了VDCRPs作为一个新兴且有前景的研究领域。然而，由于应用环境的高度动态性和路由问题的NP难度，为VDCRPs定制建模和高效解决方法仍然是一个巨大的挑战。

在现实世界场景中，随着问题规模的扩大和特定场景约束的增加，车辆-无人机协调的复杂性急剧增加。解决方案空间的指数级增长使得商业求解器变得不足。因此，目前的VDCRPs解决方法主要依赖于手工设计，包括精确算法、元启发式方法和基于学习的方法。精确方法，如分支定价切割（Schmidt等人，2025；Yang和Zhen，2025），可以提供最优解，但仅适用于小规模问题。元启发式方法，包括变邻域搜索（De Freitas和Penna，2020）、粒子群优化（Li等人，2024）和大邻域搜索（Sacramento等人，2019），虽然具有实际效果，但缺乏特定问题的策略，并且局部利用能力有限。基于学习的方法，如深度强化学习（Bi等人，2023），部分减轻了对人工设计的依赖，但通常需要大规模的预训练，并且泛化能力有限。总体而言，现有方法未能提供一个统一的、独立于专家的框架，能够自动开发适用于不同VDCRP变体的启发式方法。

大型语言模型（LLMs）的出现为解决这一挑战提供了新的机会。凭借其强大的上下文理解和全局推理能力，LLMs可以通过结构化的提示策略将复杂的优化问题转换为可解释的自然语言格式，并自动生成相应的启发式方法。因此，LLMs作为复杂和动态决策场景的适应性强的启发式设计工具具有巨大潜力。最近的研究主要探索了将LLMs与进化计算（EC）相结合的方法，其中LLMs用作启发式生成器，EC作为选择和优化机制。代表性的框架包括Liu等人（2023a）提出的启发式进化（EoH）和Romera-Paredes等人（2024）提出的FunSearch。EoH和FunSearch开创了直接进化启发式方法或程序逻辑的想法，而不是优化候选解决方案，从而为自动算法发现开辟了新的方向。然而，现有框架主要依赖于基于消除的策略，在每次迭代中简单地丢弃失败的启发式方法。这种设计隐含地假设可以通过群体级过滤来确保LLM生成的启发式方法的可靠性。实际上，由于LLMs在处理执行级约束和算法正确性方面的固有局限性，很大比例生成的启发式方法是不可行的或有错误的，尤其是在涉及多种约束和协调机制的复杂路由问题（如VDCRPs）中。丢弃这些失败的启发式方法导致知识利用率低和启发式设计成本高。

为了提高基于LLM的启发式生成的可靠性和效率，我们在EoH框架中加入了自我调试机制。该方法不仅简单地丢弃失败的启发式方法，还从评估失败中提取结构化的调试信息，并将这些反馈反馈给LLM。在这些信号的指导下，LLM可以修复无效的启发式方法，并在后续生成中避免类似的错误。这种自我调试机制使得之前生成的启发式方法得到更有效的利用，增强了约束意识，并提高了生成启发式方法的鲁棒性，从而使提出的LLM-VD框架更适合复杂和现实的VDCRPs。总之，本研究的主要贡献总结如下：

1)

本文介绍了LLM-VD，这是第一个专为VDCRPs设计的基于LLM的自动启发式设计框架，它能够在不依赖传统算法设计或领域专家的情况下高效生成启发式方法。

2)

为启发式生成和演化过程设计了结构化的提示策略和严格的评估器，指导LLM生成适应不同VDCRP变体的启发式方法。

3)

提出了两种自我调试机制来提高启发式生成的成功率：一种在演化过程中整合失败反馈以防止重复错误，另一种使用代码级修复提示来纠正接近可行的启发式方法。

4)

实验结果表明，LLM-VD能够生成高质量的启发式方法，并在不同LLMs之间具有良好的泛化能力。此外，自我调试机制显著提高了启发式生成的成功率，特别是在更复杂的VDCRP变体中。

本文的其余部分组织如下。第2节回顾了相关工作，第3节提供了VDCRPs的问题规范。第4节详细介绍了我们提出的VDCRPs自动启发式设计方法。第5节展示了数值实验，最后第6节总结了本文并讨论了未来的研究方向。

节选

相关工作

在本节中，我们主要回顾了分为两个主要研究流的相关文献。第一个流涉及VDCRPs，第二个流回顾了由LLMs驱动的自动启发式设计。

问题规范

本节提供了支持所提出的LLM-VD框架的问题规范。我们不是将数学模型视为一个独立的问题定义或直接解决的目标，而是用它来正式指定优化目标、可行性条件和评估标准，这些标准指导启发式方法的生成。从这个意义上说，问题规范是一个规范参考，定义了什么是有效和高质量的解决方案。

方法论：LLM-VD

本节介绍了专为VDCRPs设计的自动启发式设计的LLM-VD方法论。基于EoH范式，LLM-VD在统一的接口下演化可执行的启发式方法，并利用评估驱动的反馈来提高各代的可行性和性能。我们首先在第4.1节介绍了LLM-VD的整体工作流程。然后我们在第4.2节描述了集成的启发式评估和自我调试模块，包括如何处理失败反馈

数值实验

为了评估所提出的LLM-VD框架在生成VDCRPs启发式方法方面的有效性，我们在本节进行了一系列数值实验。我们首先介绍了用于测试所提出的LLM-VD框架的实例和参数设置。实验包括三个主要部分。首先，我们报告了LLM-VD在三种类型的VDCRPs上获得的最佳性能启发式方法及其对应结果，并进一步将LLM-VD与基线启发式方法进行了比较。

结论

在这项研究中，我们提出了LLM-VD，这是一个由LLM驱动的VDCRPs自动启发式设计框架。LLM-VD利用结构化的提示策略将复杂的VDCRP实例转换为LLM可解释的自然语言表示，从而实现启发式方法的自动生成和进化优化。本研究的关键创新在于在LLM-VD框架中引入了两种自我调试机制。这些机制从失败的启发式方法中收集反馈

CRediT作者贡献声明

海阳 施：撰写——原始草稿、可视化、验证、软件、方法论、调查、形式分析、数据整理。陆臻：撰写——审稿与编辑、监督、资源管理、项目管理、方法论、调查、资金获取、概念化。

利益冲突声明

作者声明他们没有已知的竞争性财务利益或个人关系可能会影响本文报告的工作。

致谢

本研究得到了国家自然科学基金（资助编号72394360、72394362和72361137001）、上海市科学技术委员会（23JC1402200）和中国博士后科学基金会（2025M780758）的支持。