# LLM-Driven Co-Evolutionary Automated Heuristic Design for Bi-Component Coupled Combinatorial Optimization

arXiv: https://arxiv.org/abs/2606.00718 · HTML: https://mlsanity.com/paper/2606.00718/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 30 references that are in the map.
- First posted on arXiv 30 May 2026.

## Builds on (most cited first, 13 of 13)

- [Large Language Models as Optimizers](https://mlsanity.com/paper/2309.03409/) (2023)
- [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024)
- [Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model](https://mlsanity.com/paper/2401.02051/) (2024)
- [Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design](https://mlsanity.com/paper/2501.08603/) (2025)
- [HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMs](https://mlsanity.com/paper/2412.14995/) (2024)
- [Multi-objective Evolution of Heuristic Using Large Language Model](https://mlsanity.com/paper/2409.16867/) (2024)
- [EoH-S: Evolution of Heuristic Set using LLMs for Automated Heuristic Design](https://mlsanity.com/paper/2508.03082/) (2025)
- [MOTIF: Multi-strategy Optimization via Turn-based Interactive Framework](https://mlsanity.com/paper/2508.03929/) (2025)
- [G-LNS: Generative Large Neighborhood Search for LLM-Based Automatic Heuristic Design](https://mlsanity.com/paper/2602.08253/) (2026)
- [Exact Approaches for the Travelling Thief Problem](https://mlsanity.com/paper/1708.00331/) (2017)
- [Evolving Interdependent Operators with Large Language Models for Multi-Objective Combinatorial Optimization](https://mlsanity.com/paper/2601.17899/) (2026)
- [Solving Travelling Thief Problems using Coordination Based Methods](https://mlsanity.com/paper/2310.07156/) (2023)
- [Deep Reinforcement Learning for Traveling Purchaser Problems](https://mlsanity.com/paper/2404.02476/) (2024)

## Built on by (most cited first, 2 of 2)

- [MuEvo: LLM-Driven Evolution of Multi-Heuristic Ensemble](https://mlsanity.com/paper/2608.03636/) (2026)
- [HeurEvo: Agentic Evolution of Hybrid Solver-Augmented Heuristics for Time-Critical Mathematical Optimization](https://mlsanity.com/paper/2609.36303/) (2026)

## Abstract (arXiv)

While Large Language Models (LLMs) have recently shown promise in Automated Heuristic Design (AHD), existing methods typically generate and evolve heuristics as a single operator or search strategy, limiting their ability to model strong coupling among multiple decision substructures in problems such as the Traveling Thief Problem (TTP) and the Traveling Purchaser Problem (TPP). In this work, we propose CoEvo-AHD, an LLM-driven dual-population co-evolutionary framework for automated heuristic design in coupled combinatorial optimization. Unlike prior methods that evolve individual heuristics in isolation, CoEvo-AHD leverages LLMs to co-evolve two closely related operator populations. A cooperative evaluation mechanism explicitly captures interactions between route and selection operators, while pairwise scoring and synergistic joint crossover help discover complementary operator logic for joint improvement across coupled decision subspaces. We further design a tool-invocation environment library that encapsulates frequently used core operations, such as local-search delta computation, into callable functions, enabling LLM-generated operators to use standardized interfaces instead of reimplementing inefficient and error-prone problem-specific loops. Experiments on TTP and TPP show that CoEvo-AHD automatically discovers cooperative heuristic combinations and achieves competitive solution quality against traditional heuristics.