Contrastive Learning Enhanced Knowledge Distillation for Learning Distributionally Robust Vehicle Routing Problems

Expand
  • 1 School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China;
    2 School of Economics and Management, University of Chinese Academy of Sciences, Beijing 100190, China;
    3 Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China;
    4 CAS Research Center on Fictitious Economy and Data Science, University of Chinese Academy of Sciences, Beijing 100190, China;
    5 Key Laboratory of Big Data Mining and Knowledge Management, University of Chinese Academy of Sciences, Beijing 100190, China;
    6 Supplies and Equipment Center, China National Offshore Oil Corporation, Beijing 100027, China

Received date: 2024-08-24

  Revised date: 2025-07-15

  Accepted date: 2025-07-20

  Online published: 2026-10-15

Supported by

This work was supported by the Strategic Priority Research Program of Chinese Academy of Sciences (No. XDA27010101), the National Natural Science Foundation of China (Nos. 11991021, 12271503). Xin Shen was supported by the General Program of Chinese Postdoctoral Science Foundation (No. 2024M753431).

Abstract

In recent years, learning based methods (LBMs) show great potential for solving vehicle routing problems (VRPs). However, most existing LBMs exhibit poor ability in distribution generalization,which hampers their applications in the real world.One reason behind this weakness is their underlying reinforcement learning training objective, which learns the best policy through interactions with the environment while ignoring the structural properties of training instances. To address this weakness and improve the distributional robustness of learned solvers, we propose a novel framework that enhances the knowledge distillation scheme with self-supervised contrastive learning. Compared with reinforcement learning, self-supervised learning can extract rich information from inherent feature representations and relationships of data. Specifically, we introduce a lightweight auxiliary network to the teacher network, so that the corresponding self-supervised signals can be extracted from this auxiliary module for knowledge distillation. By measuring the similarity between self-supervised signals and exploiting it to guide the training process, useful hidden information can be effectively transferred from the teacher network to the student network. Numerical experiments demonstrate the effectiveness of our proposed method, especially in improving the models’ generalization ability.

Cite this article

Rui-Yang Shi, Ling-Feng Niu, Xin Shen, Yu-Hong Dai . Contrastive Learning Enhanced Knowledge Distillation for Learning Distributionally Robust Vehicle Routing Problems[J]. Journal of the Operations Research Society of China, 2026 , 14(3) : 784 -805 . DOI: 10.1007/s40305-025-00632-w

References

[1] Bengio, Y., Lodi, A., Prouvost, A.: Machine learning for combinatorial optimization: amethodological tour d’horizon. Eur. J. Oper. Res. 290, 405-421(2021)
[2] Bernhard, K., Vygen, J.: Combinatorial Optimization: Theory and Algorithms. Springer, Berlin (2008)
[3] 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. In: Proceedings of Neural Information Processing Systems, pp. 31226-31238(2022)
[4] Buciluǎ, C., Caruana, R., Niculescu-Mizil, A.: Model compression. In: Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 535-541(2006)
[5] Chen, T., Kornblith, S., Norouzi, M., Hinton, G.: A simple framework for contrastive learning of visual representations. In: Proceedings of International Conference on Machine Learning, PMLR. pp. 1597-1607(2020)
[6] Ding, Z., Dong, H.: Challenges of reinforcement learning, fundamentals, research and applications, Deep Reinforcement Learning. pp. 249-272(2020)
[7] Furlanello, T., Lipton, Z., Tschannen, M., Itti, L., Anandkumar, A.: Born again neural networks. In: Proceedings of International Conference on Machine Learning, pp. 1607-1616(2018)
[8] Giorgi, J., Nitski, O., Wang, B., Bader, G.: DeCLUTR: Deep contrastive learning for unsupervised textual representations. In: Proceedings of Annual Meeting of the Association for Computational Linguistics and the International Joint Conference on Natural Language Processing, pp. 879-895(2021)
[9] Gou, J., Yu, B., Maybank, S.J., Tao, D.: Knowledge distillation: A survey. Int. J. Comput. Vision 129, 1789-1819(2021)
[10] Guo, T., Han, C., Tang, S., Ding, M.: Solving combinatorial problems with machine learning methods, Springer Optimization and Its Applications. In: Du, D.-Z., Pardalos, P.M., Zhang, Z. (eds.) Nonlinear Combinatorial Optimization, pp. 207-229. Springer, Berlin (2019)
[11] Gutmann, M., Hyvärinen, A.: Noise-contrastive estimation: A new estimation principle for unnormalized statistical models. In: Proceedings of International Conference on Artificial Intelligence and Statistics, pp. 297-304(2010)
[12] He, K., Fan, H., Wu, Y., Xie, S., Girshick, R.: Momentum contrast for unsupervised visual representation learning. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 9729-9738(2020)
[13] Helsgaun, K.: An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems, pp. 24-50. Roskilde University, Roskilde (2017)
[14] Hinton, G., Vinyals, O., Dean, J.: Distilling the knowledge in a neural network. arXiv:1503.02531(2015)
[15] Jiang, Y., Cao, Z., Wu, Y., Song, W., Zhang, J.: Ensemble-based deep reinforcement learning for vehicle routing problems under distribution shift. In: Proceedings of Neural Information Processing Systems, pp. 53112-53125(2023)
[16] Jiang, Y., Cao, Z., Wu, Y., Zhang, J.: Multi-view graph contrastive learning for solving vehicle routing problems. In: Proceedings of Uncertainty in Artificial Intelligence, pp. 984-994(2023)
[17] 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, pp. 9786-9794(2022)
[18] Joshi, C.K., Laurent, T., Bresson, X.: An efficient graph convolutional network technique for the travelling salesman problem. arXiv:1906.01227(2019)
[19] Kim, G., Ong, Y.S., Cheong, T., Tan, P.S.: Solving the dynamic vehicle routing problem under traffic congestion. IEEE Trans. Intell. Transp. Syst. 17, 2367-2380(2016)
[20] Konstantakopoulos, G.D., Gayialis, S.P., Kechagias, E.P.: Vehicle routing problem and related algorithms for logistics distribution: a literature review and classification. Oper Res Int J 22, 2033-2062(2020)
[21] Kool, W., Van Hoof, H., Welling, M.: Attention, learn to solve routing problems! In: Proceedings of International Conference on Learning Representations, pp. 1-25(2019)
[22] Kwon, Y.D., Choo, J., Kim, B., Yoon, I., Gwon, Y., Min, S.: POMO: Policy optimization with multiple optima for reinforcement learning. In: Proceedings of Neural Information Processing Systems, pp. 21188-21198(2020)
[23] Lenstra, J.K., Kan, A.R.: Complexity of vehicle routing and scheduling problems. Networks 11, 221-227(1981)
[24] Liu, F., Lin, X., Wang, Z., Zhang, Q., Xialiang, T., Yuan, M.: Multi-task learning for routing problem with cross-problem zero-shot generalization. In: Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, New York, NY, USA. pp. 1898-1908(2024)
[25] Liu, X., Zhang, F., Hou, Z., Mian, L., Wang, Z., Zhang, J., Tang, J.: Self-supervised learning: Generative or contrastive. IEEE Trans. Knowl. Data Eng. 35, 857-876(2023)
[26] Ma, Y., Li, J., Cao, Z., Song, W., Zhang, L., Chen, Z., Tang, J.: Learning to iteratively solve routing problems with dual-aspect collaborative transformer. In: Proceedings of Neural Information Processing Systems, pp. 11096-11107(2021)
[27] Oord, A.v.d., Li, Y., Vinyals, O.: Representation learning with contrastive predictive coding. arXiv:1807.03748(2018)
[28] Shi, R., Niu, L.: A brief survey on learning based methods for vehicle routing problems. Procedia Comput. Sci. 221, 773-780(2023)
[29] Shi, W., Huang, G., Song, S., Wang, Z., Lin, T., Wu, C.: Self-supervised discovering of interpretable features for reinforcement learning. IEEE Trans. Pattern Anal. Mach. Intell. 44, 2712-2724(2020)
[30] Stanton, S., Izmailov, P., Kirichenko, P., Alemi, A.A., Wilson, A.G.: Does knowledge distillation really work? In: Proceedings of Neural Information Processing Systems, pp. 6906-6919(2021)
[31] Vinyals, O., Fortunato, M., Jaitly, N.: Pointer networks. In: Proceedings of Neural Information Processing Systems, pp. 2692-2700(2015)
[32] Wang,C.,Yang,Y.,Slumbers,O.,Han,C.,Guo,T.,Zhang,H.,Wang,J.:Agame-theoreticapproachfor improving generalization ability of TSP solvers. In: Proceedings of ICLR Workshop on Gamification and Multiagent Solutions (2022)
[33] Wang, Z., Yao, S., Li, G., Zhang, Q.: Multiobjective combinatorial optimization using a single deep reinforcement learning model. IEEE Trans. Cybern. 54, 1984-1996(2024)
[34] Wu, Y., Song, W., Cao, Z., Zhang, J., Lim, A.: Learning improvement heuristics for solving routing problems. IEEE Trans. Neural Netw. Learn. Syst. 33, 5057-5069(2022)
[35] Xiao, Y., Wang, D., Wu, X., Wu, Y., Li, B., Du, W., Wang, L., Zhou, Y.: Improving generalization of neural vehicle routing problem solvers through the lens of model architecture. Neural Netw. 187, 107380(2025)
[36] Yuan, Z., Li, G., Wang, Z., Sun, J., Cheng, R.: RL-CSL: A combinatorial optimization method using reinforcement learning and contrastive self-supervised learning. IEEE Trans. Emerg. Topics Comput. Intell. 7, 1010-1024(2023)
[37] Zhang, Z., Zhang, Z., Wang, X., Zhu, W.: Learning to solve travelling salesman problem with hardnessadaptive curriculum. In: Proceedings of the AAAI Conference on Artificial Intelligence, pp. 9136- 9144(2022)
[38] Zheng, Z., Yao, S., Li, G., Han, L., Wang, Z.: Pareto improver: learning improvement heuristics for multi-objective route planning. IEEE Trans. Intell. Transp. Syst. 25, 1033-1043(2024)
[39] Zhou, J., Wu, Y., Song, W., Cao, Z., Zhang, J.: Towards omni-generalizable neural methods for vehicle routing problems. In: Proceedings of International Conference on Machine Learning, pp. 42769-42789(2023)
Options
Outlines

/

〈 〉