A Universal Framework for Vehicle Routing Problems with Large Language Models

Expand
  • 1 School of Computer Science and Technology, University of Chinese Academy of Sciences, Beijing 100049, China;
    2 School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China;
    3 College of Computer Science, Beijing University of Technology, Beijing 100124, China;
    4 Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China

Received date: 2025-05-28

  Revised date: 2026-03-11

  Accepted date: 2026-03-16

  Online published: 2026-10-15

Supported by

Rui-Bin Zeng, Mo-Xuan Yang, and Ming-Long Lei contributed equally to this work. This research was supported in part by the National Natural Science Foundation of China (Nos. 12271503 and 11991021), and in part by the Strategic Priority Research Program of Chinese Academy of Sciences (No. XDA27010101).

Abstract

Vehicle routing problems (VRP) are typical NP-hard combinatorial optimization problems that have great significance in real-world applications. Recently, neural methods have shown promising abilities to solve VRP with superior quality while maintaining high efficiency. Existing neural methods still have limitations in terms of data requirements, especially for VRP variants. Furthermore, it is difficult to generalize across different types of VRPs with a unified learning framework without extensive retraining. Notably, the large language models (LLMs) have shown potential to assist in solving VRP problems. Therefore, this paper proposes a universal framework for VRP based on LLMs. This framework captures the essential characteristics of different VRPs in a unified manner and adapts to various problem specifications with less data reliance. Concretely, the core architecture is built on pre-training and fine-tuning. Low-rank adaptation and the mixture of experts are further integrated to improve the adaptation ability. Experimental results demonstrate that on multiple vehicle routing problems, such as the traveling salesman problem and the capacitated vehicle routing problem, our framework achieves promising solution quality and computational efficiency.

Cite this article

Rui-Bin Zeng, Mo-Xuan Yang, Ming-Long Lei, Ling-Feng Niu, Yu-Hong Dai . A Universal Framework for Vehicle Routing Problems with Large Language Models[J]. Journal of the Operations Research Society of China, 2026 , 14(3) : 753 -783 . DOI: 10.1007/s40305-026-00692-6

References

[1] Baker, B.M., Ayechew, M.: A genetic algorithm for the vehicle routing problem. Comput. Oper. Res. 30(5), 787-800(2003)
[2] Baldacci, R., Christofides, N., Mingozzi, A.: An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Math. Program. 115, 351-385(2008)
[3] Bello, I., Pham, H., Le, Q.V., Norouzi, M., Bengio, S.: Neural combinatorial optimization with reinforcement learning (2016). arXiv:1611.09940
[4] Berto, F., Hua, C., Park, J., Luttmann, L., Ma, Y., Bu, F., Wang, J., Ye, H., Kim, M., Choi, S., et al.: Rl4co: an extensive reinforcement learning for combinatorial optimization benchmark. In: Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. 2, pp. 5278-5289(2025)
[5] Bi, J., Ma, Y., Wang, J., Cao, Z., Chen, J., Sun, Y., Chee, Y.M.: Learning generalizable models for vehicle routing problems via knowledge distillation. Adv. Neural. Inf. Process. Syst. 35, 31226-31238(2022)
[6] Chen, X., Tian, Y.: Learning to perform local rewriting for combinatorial optimization. Adv. Neural. Inf. Process. Syst. 32, 6281-6292(2019)
[7] Choo, J., Kwon, Y.-D., Kim, J., Jae, J., Hottung, A., Tierney, K., Gwon, Y.: Simulation-guided beam search for neural combinatorial optimization. Adv. Neural. Inf. Process. Syst. 35, 8760-8772(2022)
[8] Dorigo, M.: Optimization, learning and natural algorithms. Ph. D. Thesis, Politecnico di Milano (1992)
[9] Fang, H., Song, Z., Weng, P., Ban, Y.: Invit: a generalizable routing problem solver with invariant nested view transformer. In: Proceedings of the 41st International Conference on Machine Learning, pp. 12973-12992(2024)
[10] Fedus, W., Zoph, B., Shazeer, N.: Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity. J. Mach. Learn. Res. 23(120), 1-39(2022)
[11] Gendreau, M., Hertz, A., Laporte, G.: A tabu search heuristic for the vehicle routing problem. Manage. Sci. 40(10), 1276-1290(1994)
[12] Helsgaun, K.: An extension of the lin-kernighan-helsgaun tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde Univ. 12, 966-980(2017)
[13] Hopfield, J.J.: Neural networks and physical systems with emergent collective computational abilities. Proc. Natl. Acad. Sci. 79(8), 2554-2558(1982)
[14] Hottung, A., Kwon, Y.-D., Tierney, K.: Efficient active search for combinatorial optimization problems. In: International Conference on Learning Representations (2022)
[15] Hottung, A., Tierney, K.: Neural large neighborhood search for the capacitated vehicle routing problem (2019). arXiv:1911.09539
[16] Hu, E.J., Shen, Y., Wallis, P., Allen-Zhu, Z., Li, Y., Wang, S., Wang, L., Chen, W., et al.: Lora: Low-rank adaptation of large language models. ICLR. 1(2), 3(2022)
[17] Huang, Z., Shi, G., Sukhatme, G.S.: From words to routes: Applying large language models to vehicle routing (2024). arXiv:2403.10795
[18] Jiang, S., Xie, M., Luo, J.: Large language models for combinatorial optimization of design structure matrix. Proc. Des. Soc. 5, 2201-2210(2025)
[19] Jiang, X., Wu, Y., Wang, Y., Zhang, Y.: Unco: towards unifying neural combinatorial optimization through large language model (2024). arXiv:2408.12214
[20] Jiang, Y., Wu, Y., Cao, Z., Zhang, J.: Learning to solve routing problems via distributionally robust optimization. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 36, pp. 9786- 9794(2022)
[21] Kalantari, B., Hill, A.V., Arora, S.R.: An algorithm for the traveling salesman problem with pickup and delivery customers. Eur. J. Oper. Res. 22(3), 377-386(1985)
[22] Kim, M., Park, J., et al.: Learning collaborative policies to solve np-hard routing problems. Adv. Neural. Inf. Process. Syst. 34, 10418-10430(2021)
[23] Kim, M., Choi, S., Kim, H., Son, J., Park, J., Bengio, Y.: Ant colony sampling with GFlownets for combinatorial optimization. In: The 28th International Conference on Artificial Intelligence and Statistics (2025)
[24] Kim, M., Park, J., Park, J.: Sym-nco: leveraging symmetricity for neural combinatorial optimization. Adv. Neural. Inf. Process. Syst. 35, 1936-1949(2022)
[25] Kool, W., Van Hoof, H., Welling, M.: Attention, learn to solve routing problems! International Conference on Learning Representations. (2019)
[26] Kool, W., Hoof, H., Gromicho, J., Welling, M.: Deep policy dynamic programming for vehicle routing problems. In: International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pp. 190-213(2022)
[27] Kwon, Y.-D., Choo, J., Kim, B., Yoon, I., Gwon, Y., Min, S.: Pomo: policy optimization with multiple optima for reinforcement learning. Adv. Neural. Inf. Process. Syst. 33, 21188-21198(2020)
[28] Laporte, G.: Fifty years of vehicle routing. Transp. Sci. 43(4), 408-416(2009)
[29] Laporte, G., Nobert, Y.: A branch and bound algorithm for the capacitated vehicle routing problem. Operations-Research-Spektrum. 5, 77-85(1983)
[30] Lenstra, J.K., Kan, A.R.: Complexity of vehicle routing and scheduling problems. Networks. 11(2), 221-227(1981)
[31] Li, S., Yan, Z., Wu, C.: Learning to delegate for large-scale vehicle routing. Adv. Neural. Inf. Process. Syst. 34, 26198-26211(2021)
[32] Lin, Z., Wu, Y., Zhou, B., Cao, Z., Song, W., Zhang, Y., Senthilnath, J.: Cross-problem learning for solving vehicle routing problems. In: The 33rd International Joint Conference on Artificial Intelligence (2024)
[33] Luo, F., Lin, X., Wu, Y., Wang, Z., Xialiang, T., Yuan, M., Zhang, Q.: Boosting neural combinatorial optimization for large-scale vehicle routing problems. In: The Thirteenth International Conference on Learning Representations (2025)
[34] O Costa, P.R., Rhuggenaath, J., Zhang, Y., Akcay, A.: Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In: Asian Conference on Machine Learning, pp. 465-480(2020)
[35] Padberg, M., Rinaldi, G.: A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev. 33(1), 60-100(1991)
[36] Pan, W., Xiong, H., Ma, J., Zhao, W., Li, Y., Yan, J.: UniCO: On unified combinatorial optimization via problem reduction to matrix-encoded general TSP. In: The Thirteenth International Conference on Learning Representations (2025)
[37] Romera-Paredes, B., Barekatain, M., Novikov, A., Balog, M., Kumar, M.P., Dupont, E., Ruiz, F.J., Ellenberg, J.S., Wang, P., Fawzi, O., et al.: Mathematical discoveries from program search with large language models. Nature 625(7995), 468-475(2024)
[38] Savelsbergh, M.W., Sol, M.: The general pickup and delivery problem. Transp. Sci. 29(1), 17-29(1995)
[39] Shi Ruiyang, D.Y.-H., et al.: Niu Lingfeng: capsule aggregated attention for vehicle routing problems. SCIENTIA SINICA Math. 55(4), 849-874(2025)
[40] Solomon, M.M.: Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35(2), 254-265(1987)
[41] Son, J., Kim, M., Kim, H., Park, J.: Meta-sage: Scale meta-learning scheduled adaptation with guided exploration for mitigating scale shift on combinatorial optimization. In: International Conference on Machine Learning, pp. 32194-32210(2023)
[42] Toth, P., Vigo, D.: The vehicle routing problem. SIAM (2002)
[43] Vinyals, O., Fortunato, M., Jaitly, N.: Pointer networks. Adv. Neural. Inf. Process. Syst. 28, 2692-2700(2015)
[44] Wu, Y., Song, W., Cao, Z., Zhang, J., Lim, A.: Learning improvement heuristics for solving routing problems. IEEE Trans. Neural Netw. Learn. Syst. 33(9), 5057-5069(2021)
[45] Ye, H., Wang, J., Cao, Z., Berto, F., Hua, C., Kim, H., Park, J., Song, G.: Reevo: large language models as hyper-heuristics with reflective evolution. Adv. Neural. Inf. Process. Syst. 37, 43571-43608(2024)
[46] Zhou, J., Wu, Y., Song, W., Cao, Z., Zhang, J.: Towards omni-generalizable neural methods for vehicle routing problems. In: International Conference on Machine Learning, pp. 42769-42789(2023)
Options
Outlines

/

〈 〉