{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T16:58:58Z","timestamp":1776185938384,"version":"3.50.1"},"reference-count":38,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62350710215"],"award-info":[{"award-number":["62350710215"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62372095"],"award-info":[{"award-number":["62372095"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62502078"],"award-info":[{"award-number":["62502078"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62172077"],"award-info":[{"award-number":["62172077"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Computers &amp; Operations Research"],"published-print":{"date-parts":[[2026,7]]},"DOI":"10.1016\/j.cor.2026.107471","type":"journal-article","created":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T07:35:37Z","timestamp":1774078537000},"page":"107471","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Better approximation algorithms for clustered TSP and subgroup planning"],"prefix":"10.1016","volume":"191","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2322-750X","authenticated-orcid":false,"given":"Jingyang","family":"Zhao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1012-2373","authenticated-orcid":false,"given":"Mingyu","family":"Xiao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2742-5562","authenticated-orcid":false,"given":"Junqiang","family":"Peng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-2260-706X","authenticated-orcid":false,"given":"Ziliang","family":"Xiong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/j.cor.2026.107471_b1","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/s12597-012-0107-0","article-title":"An exact algorithm for the clustered travelling salesman problem","volume":"50","author":"Ahmed","year":"2013","journal-title":"Opsearch"},{"issue":"5","key":"10.1016\/j.cor.2026.107471_b2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2818310","article-title":"Improving christofides\u2019 algorithm for the st path TSP","volume":"62","author":"An","year":"2015","journal-title":"J. ACM"},{"issue":"1\u20132","key":"10.1016\/j.cor.2026.107471_b3","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/S0167-6377(98)00046-7","article-title":"A 5\/3-approximation algorithm for the clustered traveling salesman tour and path problems","volume":"24","author":"Anily","year":"1999","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"10.1016\/j.cor.2026.107471_b4","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1002\/(SICI)1097-0037(199707)29:4<205::AID-NET3>3.0.CO;2-J","article-title":"Restricted delivery problems on a network","volume":"29","author":"Arkin","year":"1997","journal-title":"Networks: An Int. J."},{"issue":"2","key":"10.1016\/j.cor.2026.107471_b5","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1016\/j.ejor.2020.01.053","article-title":"A transformation technique for the clustered generalized traveling salesman problem with applications to logistics","volume":"285","author":"Baniasadi","year":"2020","journal-title":"European J. Oper. Res."},{"issue":"23","key":"10.1016\/j.cor.2026.107471_b6","doi-asserted-by":"crossref","first-page":"908","DOI":"10.1016\/j.ipl.2012.08.020","article-title":"An improved approximation algorithm for the clustered traveling salesman problem","volume":"112","author":"Bao","year":"2012","journal-title":"Inform. Process. Lett."},{"issue":"1","key":"10.1016\/j.cor.2026.107471_b7","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1145\/321105.321111","article-title":"Dynamic programming treatment of the travelling salesman problem","volume":"9","author":"Bellman","year":"1962","journal-title":"J. ACM"},{"issue":"2","key":"10.1016\/j.cor.2026.107471_b8","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/0305-0548(75)90015-5","article-title":"The clustered traveling salesman problem","volume":"2","author":"Chisman","year":"1975","journal-title":"Comput. Oper. Res."},{"key":"10.1016\/j.cor.2026.107471_b9","series-title":"Worst-case analysis of a new heuristic for the travelling salesman problem","author":"Christofides","year":"1976"},{"key":"10.1016\/j.cor.2026.107471_b10","series-title":"Introduction to algorithms","author":"Cormen","year":"2022"},{"issue":"4","key":"10.1016\/j.cor.2026.107471_b11","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1016\/S1007-0214(07)70068-8","article-title":"Two-level genetic algorithm for clustered traveling salesman problem with application in large-scale TSPs","volume":"12","author":"Ding","year":"2007","journal-title":"Tsinghua Sci. Technol."},{"issue":"1","key":"10.1016\/j.cor.2026.107471_b12","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1145\/6462.6502","article-title":"Efficient algorithms for finding maximum matching in graphs","volume":"18","author":"Galil","year":"1986","journal-title":"ACM Comput. Surv."},{"issue":"4","key":"10.1016\/j.cor.2026.107471_b13","doi-asserted-by":"crossref","first-page":"639","DOI":"10.1287\/opre.45.4.639","article-title":"An approximation algorithm for the traveling salesman problem with backhauls","volume":"45","author":"Gendreau","year":"1997","journal-title":"Oper. Res."},{"issue":"4","key":"10.1016\/j.cor.2026.107471_b14","doi-asserted-by":"crossref","first-page":"1109","DOI":"10.1007\/s00453-017-0293-5","article-title":"An experimental evaluation of the best-of-many christofides\u2019 algorithm for the traveling salesman problem","volume":"78","author":"Genova","year":"2017","journal-title":"Algorithmica"},{"issue":"4","key":"10.1016\/j.cor.2026.107471_b15","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1007\/s004530010045","article-title":"Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem","volume":"28","author":"Guttmann-Beck","year":"2000","journal-title":"Algorithmica"},{"issue":"4","key":"10.1016\/j.cor.2026.107471_b16","doi-asserted-by":"crossref","first-page":"555","DOI":"10.7155\/jgaa.00478","article-title":"Approximation algorithms for not necessarily disjoint clustered tsp.","volume":"22","author":"Guttmann-Beck","year":"2018","journal-title":"J. Graph Algorithms Appl."},{"issue":"2","key":"10.1016\/j.cor.2026.107471_b17","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1109\/TEPM.2010.2046327","article-title":"Evolutionary path planning with subpath constraints","volume":"33","author":"Gyorfi","year":"2010","journal-title":"IEEE Trans. Electron. Packag. Manuf."},{"issue":"1","key":"10.1016\/j.cor.2026.107471_b18","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1137\/0110015","article-title":"A dynamic programming approach to sequencing problems","volume":"10","author":"Held","year":"1962","journal-title":"J. Soc. Ind. Appl. Math."},{"issue":"5","key":"10.1016\/j.cor.2026.107471_b19","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0167-6377(91)90016-I","article-title":"Analysis of christofides\u2019 heuristic: Some paths are more difficult than cycles","volume":"10","author":"Hoogeveen","year":"1991","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"10.1016\/j.cor.2026.107471_b20","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1109\/TRO.2012.2222272","article-title":"Path planning under kinematic constraints by rapidly exploring manifolds","volume":"29","author":"Jaillet","year":"2013","journal-title":"IEEE Trans. Robot."},{"key":"10.1016\/j.cor.2026.107471_b21","series-title":"53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021","first-page":"32","article-title":"A (slightly) improved approximation algorithm for metric TSP","author":"Karlin","year":"2021"},{"issue":"2","key":"10.1016\/j.cor.2026.107471_b22","first-page":"60","article-title":"Improving approximation ratios for the clustered traveling salesman problem","volume":"63","author":"Kawasaki","year":"2020","journal-title":"J. Oper. Res. Soc. Japan"},{"issue":"9","key":"10.1016\/j.cor.2026.107471_b23","doi-asserted-by":"crossref","first-page":"972","DOI":"10.1057\/palgrave.jors.2601420","article-title":"Some applications of the clustered travelling salesman problem","volume":"53","author":"Laporte","year":"2002","journal-title":"J. Oper. Res. Soc."},{"issue":"2","key":"10.1016\/j.cor.2026.107471_b24","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/0377-2217(79)90099-7","article-title":"Procedures for travelling salesman problems with additional constraints","volume":"3","author":"Lokin","year":"1979","journal-title":"European J. Oper. Res."},{"key":"10.1016\/j.cor.2026.107471_b25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.cie.2017.12.018","article-title":"New hybrid heuristic algorithm for the clustered traveling salesman problem","volume":"116","author":"Mestria","year":"2018","journal-title":"Comput. Ind. Eng."},{"issue":"12","key":"10.1016\/j.cor.2026.107471_b26","doi-asserted-by":"crossref","first-page":"3218","DOI":"10.1016\/j.cor.2012.10.001","article-title":"GRASP with path relinking for the symmetric euclidean clustered traveling salesman problem","volume":"40","author":"Mestria","year":"2013","journal-title":"Comput. Oper. Res."},{"key":"10.1016\/j.cor.2026.107471_b27","unstructured":"Nash, A., Koenig, S., Likhachev, M., 2009. Incremental Phi*: Incremental Any-Angle Path Planning on Grids. In: Proceedings of the 21st International Joint Conference on Artificial Intelligence, IJCAI 2009. pp. 1824\u20131830."},{"issue":"2","key":"10.1016\/j.cor.2026.107471_b28","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1002\/cav.1622","article-title":"Planning approaches to constraint-aware navigation in dynamic environments","volume":"26","author":"Ninomiya","year":"2015","journal-title":"Comput. Animat. Virtual Worlds"},{"key":"10.1016\/j.cor.2026.107471_b29","series-title":"Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016","first-page":"669","article-title":"An approximation algorithm for the subpath planning problem","author":"Safilian","year":"2016"},{"issue":"3","key":"10.1016\/j.cor.2026.107471_b30","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1145\/321958.321975","article-title":"P-complete approximation problems","volume":"23","author":"Sahni","year":"1976","journal-title":"J. ACM"},{"key":"10.1016\/j.cor.2026.107471_b31","series-title":"A systematic review of approximability results for traveling salesman problems leveraging the TSP-T3CO definition scheme","author":"Saller","year":"2023"},{"key":"10.1016\/j.cor.2026.107471_b32","series-title":"Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017","first-page":"4412","article-title":"An improved approximation algorithm for the subpath planning problem and its generalization","author":"Sumita","year":"2017"},{"key":"10.1016\/j.cor.2026.107471_b33","series-title":"Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015","first-page":"1916","article-title":"Reduced time-expansion graphs and goal decomposition for solving cooperative path finding sub-optimally","author":"Surynek","year":"2015"},{"issue":"2","key":"10.1016\/j.cor.2026.107471_b34","doi-asserted-by":"crossref","first-page":"14:1","DOI":"10.1145\/3309715","article-title":"Approaching 3\/2 for the s-t-path TSP","volume":"66","author":"Traub","year":"2019","journal-title":"J. ACM"},{"issue":"3","key":"10.1016\/j.cor.2026.107471_b35","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1137\/20M135594X","article-title":"Reducing path TSP to TSP","volume":"51","author":"Traub","year":"2022","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.cor.2026.107471_b36","series-title":"Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019","first-page":"1539","article-title":"A 1.5-approximation for path TSP","author":"Zenklusen","year":"2019"},{"key":"10.1016\/j.cor.2026.107471_b37","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.cor.2017.07.008","article-title":"Metaheuristics for the tabu clustered traveling salesman problem","volume":"89","author":"Zhang","year":"2018","journal-title":"Comput. Oper. Res."},{"key":"10.1016\/j.cor.2026.107471_b38","series-title":"AAAI-25, Sponsored By the Association for the Advancement of Artificial Intelligence, February 25 - March 4, 2025, Philadelphia, PA, USA","first-page":"26742","article-title":"Improved approximation algorithms for clustered TSP and subgroup planning","author":"Zhao","year":"2025"}],"container-title":["Computers &amp; Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0305054826000894?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0305054826000894?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T16:04:26Z","timestamp":1776182666000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0305054826000894"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7]]},"references-count":38,"alternative-id":["S0305054826000894"],"URL":"https:\/\/doi.org\/10.1016\/j.cor.2026.107471","relation":{},"ISSN":["0305-0548"],"issn-type":[{"value":"0305-0548","type":"print"}],"subject":[],"published":{"date-parts":[[2026,7]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Better approximation algorithms for clustered TSP and subgroup planning","name":"articletitle","label":"Article Title"},{"value":"Computers & Operations Research","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.cor.2026.107471","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 Elsevier Ltd. All rights are reserved, including those for text and data mining, AI training, and similar technologies.","name":"copyright","label":"Copyright"}],"article-number":"107471"}}