Multipopulation Optimization With LLM-Driven Knowledge Discovery for Large-Scale HFVRP

Logistics transportation plays a critical role in real-world applications. The heterogeneous fleet vehicle routing problem (HFVRP), characterized by varying vehicle capacities and costs, are the key optimization challenges in many logistic scenarios. Despite its importance, it presents substantial challenges due to its NP-hard nature and large scale. Existing methods only study HFVRP instances of moderate size (i.e., about 300 nodes), which is insufficient for real-world application. In this article, we introduce large language model-multipopulation (MP-LLM), a novel MP optimization method with LLM-driven knowledge discovery. MP-LLM employs multiple populations with iterated local search (ILS) and dynamic updating to balance exploration and exploitation. An LLM-driven knowledge discovery is adopted to design a parameter adjustment strategy to pinpoint features specific to each instance, thereby facilitating a more effective dynamic parameter adjustment. We comprehensively evaluate MP-LLM on four benchmark test sets with 170 instances of diverse distributions and sizes. Our results show that when compared to stat-of-the-art methods, MP-LLM not only achieves superior solution quality but also significantly enhances efficiency. Notably, MP-LLM generates new best-known solutions on 18 out of 90 classic instances. It significantly expands HFVRP-solving capabilities from approximately 300 nodes to instances with up to 3000 nodes.