A Universal Framework for Vehicle Routing Problems with Large Language Models

doi:10.1007/s40305-026-00692-6

Abstract

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.

Key words: Efficient fine-tuning, Vehicle routing problems, Large language models, Combinatorial optimization

CLC Number:

90C27·68T07·68T20

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.

TrendMD

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.jorsc.shu.edu.cn/EN/10.1007/s40305-026-00692-6

https://www.jorsc.shu.edu.cn/EN/Y2026/V14/I3/753

[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)

A Universal Framework for Vehicle Routing Problems with Large Language Models

Knowledge

Abstract

Cite this article

share this article

Related Articles 6

Recommended Articles

Metrics

Comments

[1]	Peng-Xiang Pan, Jun-Ran Lichen, Wen-Cheng Wang, Li-Jian Cai, Jian-Ping Li. Approximation Algorithms for Solving the k-Chinese Postman Problem Under Interdiction Budget Constraints [J]. Journal of the Operations Research Society of China, 2025, 13(2): 535-554.
[2]	Jian-Ping Li, Wen-Cheng Wang, Jun-Ran Lichen, Yu-Jie Zheng. Approximation Algorithms for Constructing Steiner Trees in the Euclidean Plane R² Using Stock Pieces of Materials with Fixed Length [J]. Journal of the Operations Research Society of China, 2024, 12(4): 996-1021.
[3]	Esmaeil Afrashteh, Behrooz Alizadeh, Fahimeh Baroughi. Optimal Algorithms for Integer Inverse Undesirable p-Median Location Problems on Weighted Extended Star Networks [J]. Journal of the Operations Research Society of China, 2021, 9(1): 99-117.
[4]	Yue Li, Rui-Yun Tang, Li-Wen MuRong, Qian Sun. Collaborative Optimization of Dock Door Assignment and Vehicle Scheduling in Cross-Docking [J]. Journal of the Operations Research Society of China, 2020, 8(3): 493-514.
[5]	Roghayeh Etemad · Behrooz Alizadeh. Combinatorial Algorithms for Reverse Selective Undesirable Center Location Problems on Cycle Graphs [J]. Journal of the Operations Research Society of China, 2017, 5(3): 347-361.
[6]	Jian Li· Yu Liu. Approximation Algorithms for Stochastic Combinatorial Optimization Problems [J]. Journal of the Operations Research Society of China, 2016, 4(1): 1-.