Vehicle routing problems (VRPs) are significant combinatorial optimization problems (COPs) holding substantial practical importance. Recently, neural combinatorial optimization (NCO), which involves training deep learning models on extensive data to learn vehicle routing heuristics, has emerged as a promising approach due to its efficiency and the reduced need for manual algorithm design. However, applying NCO across diverse real-world scenarios with various constraints necessitates cross-problem capabilities. Current cross-problem NCO methods for VRPs typically employ a constraint-unaware model, limiting their cross-problem performance. Furthermore, they rely solely on global connectivity, which fails to focus on key nodes and leads to inefficient representation learning. This paper introduces a Constraint-Aware Dual-Attention Model (CaDA), designed to address these limitations. CaDA incorporates a constraint prompt that efficiently represents different problem variants. Additionally, it features a dual-attention mechanism with a global branch for capturing broader graph-wide information and a sparse branch that selectively focuses on the key node connections. We comprehensively evaluate our model on 16 different VRPs and compare its performance against existing cross-problem VRP solvers. CaDA achieves state-of-the-art results across all tested VRPs. Our ablation study confirms that each component contributes to its cross-problem learning performance. The source code for CaDA is publicly available at https://github.com/CIAM-Group/CaDA.

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.