LLM based method improves heuristics for diverse optimization problems
Multi-Task Evolution for Zero-Shot Cross-Problem Generalization using LLMs
Artificial Intelligence
Summary
Finding good shortcuts to solve tricky scheduling or routing problems usually needs lots of expert trial and error. This paper introduces MECo, a method that uses large language models to evolve and mix these shortcuts across different kinds of problems. MECo can combine knowledge from one set of tasks to solve new tasks without extra searching or tweaking. Tests showed MECo often finds better solutions than existing automated methods across many problem types, including vehicle routing and job scheduling.
What this means in practice
- •For logistics planners: Produce efficient routing plans for new logistics challenges without extra tuning using MECo’s multi-task heuristic selection.
- •For manufacturing schedulers: Generate robust scheduling heuristics that adapt to new production problems without additional search or adjustments.
Authors
Zhouliang Xie, Changliang Zhou, Genghui Li, Zhenkun Wang
Abstract
Designing effective heuristics for diverse combinatorial optimization problems requires substantial expertise and repeated search. Large language models (LLMs) automate heuristic generation and refinement, but heuristic search typically depends on evaluation feedback from the problem being optimized. Generalizing to new problem definitions using only source-task feedback therefore remains a central challenge. We introduce MECo, an LLM-driven multi-task evolutionary framework for zero-shot cross-problem generalization. MECo maintains task-conditioned heuristic populations and uses a transfer gap based on cross-task population performance to guide their interactions. These interactions enable the transfer and recombination of heuristics. A complementary selection criterion then constructs a compact heuristic set by rewarding each member's additional coverage of source combinations. The selected set is applied to target problems without further search or adaptation. Experiments on 32 problem variants across vehicle routing (VRP) and flexible job-shop scheduling (FJSP) show that MECo achieves the lowest mean costs compared with eight automated heuristic design (AHD) baselines under the same budgets. On out-of-domain problems, it outperforms the strongest baseline in each family. Moreover, integrating the framework of MECo with different AHD methods improves their ID and OOD performance in both families, supporting its effectiveness across different methods.