Journal of the Operations Research Society of China >

2025 , Vol. 13 >Issue 4: 1083 - 1107

DOI: https://doi.org/10.1007/s40305-023-00507-y

HiTSP: Towards a Hierarchical Neural Framework for Large-scale Traveling Salesman Problems

Expand
  • 1 Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China;
    2 Theory Lab, Central Research Institute, 2012 Labs, Huawei Technologies Co., Ltd., Shenzhen 518129, Guangdong, China;
    3 Department of Computer Science and Engineering, Hong Kong University of Science and Technology, Sai Kung, Hong Kong, China;
    4 Center of Discrete Mathematics, Fuzhou University, Quanzhou 350116, Fujian, China

Received date: 2022-05-12

  Revised date: 2023-08-25

  Online published: 2025-12-19

Supported by

This work was supported by the National Natural Science Foundation of China (No. 12071077).

Fold

Abstract

Recently, learned heuristics have been widely applied to solve combinatorial optimization problems (e.g., traveling salesman problem (TSP)). However, the scalability of these learning-based methods hinders the applications in practical scenarios. Specifically, models pre-trained on the small-scale data generalize poorly to large-scale problems. Moreover, learning the heuristics directly for large-scale problems costs tremendous time and space. To extend the scalability of learned heuristics on TSP, we propose a Hierarchical neural framework for solving large-scale traveling salesman problems (HiTSPs) based on a divide-and-conquer strategy. In particular, the HiTSP framework first divides the large-scale problem into small-scale subproblems by node clustering. Each subproblem is conquered by a modified pointer network learned from reinforcement learning. The tour of the original TSP is constructed by linking solutions of subproblems and optimized by a novel segmented local search algorithm. Notably, the segmented local search algorithm leverages the node clustering information to prune many unnecessary operations and significantly reduces the complexity in theory. Extensive experiments show that HiTSP outperforms state-of-the-art learning-based methods and Google OR-Tools in large-scale cases. Moreover, compared to the best heuristic algorithms, HiTSP has a significant advantage in efficiency for large-scale TSP problems.

Key words： Hierarchical neural framework; Divide-and-conquer; Modified pointer network; Segmented local search algorithm

Cite this article

Jian-Feng Liu, Zi-Hao Wang, Wei Zhang, Chao-Rui Zhang, Jian-Feng Hou, Bo Bai, Gong Zhang . HiTSP: Towards a Hierarchical Neural Framework for Large-scale Traveling Salesman Problems[J]. Journal of the Operations Research Society of China, 2025 , 13(4) : 1083 -1107 . DOI: 10.1007/s40305-023-00507-y

References

[1] Held, M., Karp, R.M.: The traveling-Salesman problem and minimum spanning trees. Oper. Res. 18(6), 1138–1162 (1970)
[2] Eiselt, H.A., Gendreau, M., Laporte, G.: Arc routing problems, Part I: the chinese postman problem. Oper. Res. 43(2), 231–242 (1995)
[3] McFarlane, D., Giannikas, V., Lu, W.: Intelligent logistics: involving the customer. Comput. Ind. 81, 105–115 (2016)
[4] Applegate, D.L., Bixby, R.E., Chvatal, V., Cook, W.J.: The traveling Salesman problem: a computational study. Princeton University Press, USA (2006)
[5] Held, S., Müller, D., Rotter, D., Scheifele, R., Traub, V., Vygen, J.: Global routing with timing constraints. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 37(2), 406–419 (2017)
[6] Laporte, G.: The Traveling Salesman Problem: An overview of exact and approximate algorithms. Eur. J. Oper. Res. 59(2), 231–247 (1992)
[7] Chauhan, C., Gupta, R., Pathak, K.: Survey of methods of solving TSP along with its implementation using dynamic programming approach. Int. J. Comput. Appl. 52(4), 12–19 (2012)
[8] Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report, Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group (1976)
[9] Keld, H.: An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur. J. Oper. Res. 126(1), 106–130 (2000)
[10] Johnson, D.S.: Local optimization and the traveling salesman problem. In: International Colloquium on Automata, Languages, and Programming, pp. 446–461 (1990)
[11] Rosenkrantz, D.J., Stearns, R.E., Lewis, P.M., Ⅱ.: An analysis of several heuristics for the traveling salesman problem. SIAM J. Comput. 6(3), 563–581 (1977)
[12] Colorni, A., Dorigo, M., Maniezzo, V., : Distributed optimization by ant colonies. In: Proceedings of the First European Conference on Artificial Life, vol. 142, pp. 134–142. Paris, France (1991)
[13] Hlaing, Z.C.S.S., Khine, M.A.: Solving traveling salesman problem by using improved ant colony optimization algorithm. Int. J. Inf. Educ. Technol. 1(5), 404 (2011)
[14] Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983)
[15] Geng, X., Chen, Z., Yang, W., Shi, D., Zhao, K.: Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search. Appl. Soft Comput. 11(4), 3680–3689 (2011)
[16] Glover, F.: Tabu Search-Part Ⅱ. ORSA J. Comput. 2(1), 4–32 (1990)
[17] Basu, S.: Tabu search implementation on traveling salesman problem and its variations: a literature survey (2012) https://doi.org/10.4236/ajor.2012.22019
[18] Lombardi, M., Milano, M.: Boosting combinatorial problem modeling with machine learning. In: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. arXiv:1807.05517 (2018)
[19] Bengio, Y., Lodi, A., Prouvost, A.: Machine learning for combinatorial optimization: a methodological Tour d’Horizon. Eur. J. Oper. Res. 290(2), 405–421 (2020)
[20] Vinyals, O., Fortunato, M., Jaitly, N.: Pointer Networks. In: Advances in Neural Information Processing Systems, pp. 2692–2700 (2015)
[21] Joshi, C.K., Laurent, T., Bresson, X.: An efficient graph convolutional network technique for the travelling salesman problem. arXiv: 1906.01227 (2019)
[22] Bello, I., Pham, H., Le, Q.V., Norouzi, M., Bengio, S.: Neural combinatorial optimization with reinforcement learning. In: 5th International Conference on Learning Representations. arXiv:1611.09940 (2017)
[23] Kool, W., van Hoof, H., Welling, M.: Attention, learn to solve routing problems! In: 7th International Conference on Learning Representations. arXiv:1803.08475 (2019)
[24] Ma, Q., Ge, S., He, D., Thaker, D., Drori, I.: Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning. arXiv: 1911.04936 (2019)
[25] Dai, H., Khalil, E.B., Zhang, Y., Dilkina, B., Song, L.: Learning combinatorial optimization algorithms over graphs. In: Advances in Neural Information Processing Systems, pp. 6348–6358 (2017)
[26] Deudon, M., Cournut, P., Lacoste, A., Adulyasak, Y., Rousseau, L.: Learning heuristics for the TSP by policy gradient. In: Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 15th International Conference, CPAIOR, vol. 10848, pp. 170–181 (2018)
[27] Bresson, X., Laurent, T.: The transformer network for the traveling salesman problem. arXiv:2103.03012 (2021)
[28] Goh, Y.L., Lee, W.S., Bresson, X., Laurent, T., Lim, N.: Combining reinforcement learning and optimal transport for the traveling salesman problem. arXiv:2203.00903 (2022)
[29] Lin, S., Kernighan, B.W.: An effective heuristic algorithm for the traveling-salesman problem. Oper. Res. 21(2), 498–516 (1973)
[30] Hopfield, J.J., Tank, D.W.:“Neural”Computation ofdecisionsin optimization problems.Biol.Cybern. 52(3), 141–152 (1985)
[31] Wu, Y., Song, W., Cao, Z., Zhang, J., Lim, A.: Learning improvement heuristics for solving the travelling salesman problem. arXiv: 1912.05784 (2019)
[32] Fu, Z.-H., Qiu, K.-B., Zha, H.: Generalize a small pre-trained model to arbitrarily large tsp instances. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, pp. 7474–7482 (2021)
[33] Ouyang, W., Wang, Y., Han, S., Jin, Z., Weng, P.: Improving generalization of deep reinforcement learning-based tsp solvers. In: 2021 IEEE Symposium Series on Computational Intelligence (SSCI), pp. 01–08. IEEE (2021)
[34] Xin, L., Song, W., Cao, Z., Zhang, J.: Neurolkh: Combining deep learning model with lin-kernighanhelsgaun heuristic for solving the traveling salesman problem. Adv. Neural. Inf. Process. Syst. 34, 7472–7483 (2021)
[35] Mazyavkina, N., Ivanov, S., Burnaev, E., Sviridov, S.: Reinforcement learning for combinatorial optimization: a survey. Comput. Oper. Res. 134, 105400–105400 (2021)
[36] Zheng, J., He, K., Zhou, J., Jin, Y., Li, C.-M.: Reinforced lin-kernighan-helsgaun algorithms for the traveling salesman problems. Knowl.-Based Syst. 260, 110144 (2023)
[37] Ding, C., Cheng, Y., He, M.: Two-level genetic algorithm for clustered traveling salesman problem with application in large-scale tsps. Tsinghua Sci. Technol. 12(4), 459–465 (2007)
[38] Park, D.C., Figueras, A.L., Chen, C.: A hierarchical approach for solving large-scale traveling salesman problem. In: Proceedings of 1994 IEEE International Conference on Neural Networks (ICNN’94), vol. 7, pp. 4613–4618. IEEE (1994)
[39] Yang, J.-Q., Yang, J.-G., Chen, G.-L.: Solving large-scale tsp using adaptive clustering method. In: 2009 Second International Symposium on Computational Intelligence and Design, vol. 1, pp. 49–51. IEEE (2009)
[40] Cook, W., Seymour, P.: Tour merging via branch-decomposition. Informs J. Comput. 15(3), 233–248 (2003)
[41] Deng, Y., Liu, Y., Zhou, D.: An improved genetic algorithm with initial population strategy for symmetric tsp. Math. Probl. Eng. 2015, 212794 (2015). https://doi.org/10.1155/2015/212794
[42] Bazylevych, R.P., Kutelmakh, R., Dupas, R., Bazylevych, L.: Decomposition algorithms for largescale clustered tsp. In: Indian International Conference on Artificial Intelligence pp. 255–267 (2007)
[43] Ng, A.Y., Jordan, M.I., Weiss, Y.: On spectral clustering: analysis and an algorithm. In: Advances In Neural Information Processing Systems, pp. 849–856 (2002)
[44] von Luxburg, U.: A tutorial on spectral clustering. Stat. Comput. 17(4), 395–416 (2007)
[45] Likas, A., Vlassis, N., Verbeek, J.: The global k-means clustering algorithm. Pattern Recognit. 36(2), 451–461 (2003)
[46] Cho, K., Merriënboer, B.V., Gulcehre, C., Bahdanau, D., Bougares, F., Schwenk, H., Bengio, Y.: Learning phrase representations using RNN encoder-decoder for statistical machine translation. In: Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, pp. 1724–1734 (2014)
[47] Williams, R.J.: Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning 8(3–4), 229–256 (1992)
[48] Kingma, D.P., Ba, J.: Adam: A method for stochastic optimization. In: 3rd International Conference on Learning Representations. arXiv:1412.6980 (2015)
[49] Google: Google’s optimization tools(OR-Tools) (2020). https://developers.google.com/optimization/routing
[50] TSPLIB. http://www.iwr.uniheidelberg.de/groups/comopt/software/TSPLIB95/
Options
Outlines

/

〈 〉

Copyright © Operations Research Society of China, The Periodicals Agency of Shanghai University , and Springer-Verlag Berlin Heidelberg 2016