LLM-based automatic heuristic design for vehicle-drone collaborative routing problems

Vehicle-drone collaborative routing problems (VDCRPs) have attracted increasing attention due to their potential to enhance logistics efficiency. However, designing effective algorithms remains challenging due to their structural complexity and the diversity of variants. This study presents a novel automatic heuristic design framework, termed LLM-VD, which integrates the text generation capabilities of LLMs with an evolutionary computation framework. Through structured prompting strategies, the framework efficiently generates, evolves, and evaluates VDCRP heuristics. A key innovation of LLM-VD is the integration of two complementary self-debugging mechanisms. The first incorporates structured failure feedback into subsequent prompts to prevent recurring errors, while the second employs repair prompts that pair failed heuristics with their feedback to guide reflective algorithmic correction. Experiments on three VDCRP variants show that LLM-VD can generate high-quality heuristics that outperform the baseline heuristic and generalize well across various LLMs. The two self-debugging mechanisms significantly enhance the success rate, achieving nearly a fourfold improvement for the most complex problem variant. These findings underscore the potential of evolutionary computation and self-debugging mechanisms in improving the robustness and adaptability of automatic heuristic design frameworks. LLM-VD provides a promising approach for VDCRPs and can be extended to other complex combinatorial optimization problems.