{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T20:09:14Z","timestamp":1778357354923,"version":"3.51.4"},"reference-count":40,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"funder":[{"DOI":"10.13039\/501100010882","name":"Tianjin Municipal Education Commission","doi-asserted-by":"publisher","award":["2020KJ037"],"award-info":[{"award-number":["2020KJ037"]}],"id":[{"id":"10.13039\/501100010882","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2026,6]]},"DOI":"10.1016\/j.tcs.2026.115962","type":"journal-article","created":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T08:11:39Z","timestamp":1775808699000},"page":"115962","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["The ripple-spreading algorithm for shortest path tour problems"],"prefix":"10.1016","volume":"1075","author":[{"given":"Yiming","family":"Ma","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiao-Bing","family":"Hu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hang","family":"Zhou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ying-Fei","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Da-Qing","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gong-Peng","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ezequiel A Di","family":"Paolo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark S.","family":"Leeson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"issue":"6","key":"10.1016\/j.tcs.2026.115962_bib0001","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/367766.368168","article-title":"Algorithm 97: shortest path","volume":"5","author":"Floyd","year":"1962","journal-title":"Commun. ACM"},{"issue":"5","key":"10.1016\/j.tcs.2026.115962_bib0002","doi-asserted-by":"crossref","first-page":"1175","DOI":"10.1109\/JSAC.2024.3365873","article-title":"Shortest path in LEO satellite constellation networks: an explicit analytic approach","volume":"42","author":"Chen","year":"2024","journal-title":"IEEE J. Sel. Areas Commun."},{"issue":"1","key":"10.1016\/j.tcs.2026.115962_bib0003","first-page":"287","article-title":"Some constrained shortest-route problems","volume":"15","author":"Bajaj","year":"1971","journal-title":"Unternehmensforschung"},{"issue":"1","key":"10.1016\/j.tcs.2026.115962_bib0004","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/s11590-010-0258-y","article-title":"Complexity analysis and optimization of the shortest path tour problem","volume":"6","author":"Festa","year":"2012","journal-title":"Optim. Lett."},{"key":"10.1016\/j.tcs.2026.115962_bib0005","series-title":"The Shortest Path Tour Problem and Its Variants","author":"Ferone","year":"2017"},{"issue":"2","key":"10.1016\/j.tcs.2026.115962_bib0006","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1109\/MCOM.2015.7045396","article-title":"Network function virtualization: challenges and opportunities for innovations","volume":"53","author":"Han","year":"2015","journal-title":"IEEE Commun. Mag."},{"key":"10.1016\/j.tcs.2026.115962_bib0007","doi-asserted-by":"crossref","first-page":"2542","DOI":"10.1109\/ACCESS.2015.2499271","article-title":"Software-defined network function virtualization: a survey","volume":"3","author":"Li","year":"2015","journal-title":"IEEE Access"},{"issue":"4","key":"10.1016\/j.tcs.2026.115962_bib0008","doi-asserted-by":"crossref","first-page":"3240","DOI":"10.1109\/TDSC.2024.3524128","article-title":"Cross-level security verification for network functions virtualization (NFV)","volume":"22","author":"Oqaily","year":"2025","journal-title":"IEEE Trans. Depend. Secure Comput."},{"issue":"3","key":"10.1016\/j.tcs.2026.115962_bib0009","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1145\/2656877.2656886","article-title":"ChoiceNet: toward an economy plane for the internet","volume":"44","author":"Wolf","year":"2014","journal-title":"ACM SIGCOMM Comput. Commun. Rev."},{"key":"10.1016\/j.tcs.2026.115962_bib0010","series-title":"2014 European Conference on Networks and Communications (EuCNC)","first-page":"1","article-title":"T-NOVA: a marketplace for virtualized network functions","author":"Xilouris","year":"2014"},{"key":"10.1016\/j.tcs.2026.115962_bib0011","series-title":"2020 6th IEEE Conference on Network Softwarization (NetSoft)","first-page":"114","article-title":"Shortest path tour problem based integer linear programming for service chaining in NFV networks","author":"Sasabe","year":"2020"},{"key":"10.1016\/j.tcs.2026.115962_bib0012","series-title":"2017 26th International Conference on Computer Communication and Networks (ICCCN)","first-page":"1","article-title":"Service-concatenation routing with applications to network functions virtualization","author":"Bhat","year":"2017"},{"issue":"2","key":"10.1016\/j.tcs.2026.115962_bib0013","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1109\/MNET.2014.6786610","article-title":"DROPv2: energy efficiency through network function virtualization","volume":"28","author":"Bolla","year":"2014","journal-title":"IEEE Netw."},{"issue":"1","key":"10.1016\/j.tcs.2026.115962_bib0014","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1109\/COMST.2015.2477041","article-title":"Network function virtualization: state-of-the-art and research challenges","volume":"18","author":"Mijumbi","year":"2015","journal-title":"IEEE Commun. Surv. Tutorials"},{"key":"10.1016\/j.tcs.2026.115962_bib0015","series-title":"Dynamic Programming and Optimal Control: Volume I","volume":"4","author":"Bertsekas","year":"2012"},{"issue":"3","key":"10.1016\/j.tcs.2026.115962_bib0016","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1016\/j.ejor.2013.04.029","article-title":"Solving the shortest path tour problem","volume":"230","author":"Festa","year":"2013","journal-title":"Eur. J. Oper. Res."},{"key":"10.1016\/j.tcs.2026.115962_bib0017","series-title":"Proceedings of the IEEE International Conference on Communications","first-page":"38.14","article-title":"Constrained routing in large sparse networks","author":"Kershenbaum","year":"1976"},{"key":"10.1016\/j.tcs.2026.115962_bib0018","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1016\/j.cor.2016.04.002","article-title":"The constrained shortest path tour problem","volume":"74","author":"Ferone","year":"2016","journal-title":"Comput. Oper. Res."},{"key":"10.1016\/j.tcs.2026.115962_bib0019","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/j.endm.2018.07.019","article-title":"An integer linear programming model for the constrained shortest path tour problem","volume":"69","author":"De Andrade","year":"2018","journal-title":"Electron. Notes Discrete Math."},{"issue":"1","key":"10.1016\/j.tcs.2026.115962_bib0020","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1080\/10556788.2018.1548015","article-title":"An efficient exact approach for the constrained shortest path tour problem","volume":"35","author":"Ferone","year":"2020","journal-title":"Optim. Methods Softw."},{"key":"10.1016\/j.tcs.2026.115962_bib0021","doi-asserted-by":"crossref","DOI":"10.1016\/j.cor.2022.105819","article-title":"Constrained shortest path tour problem: branch-and-price algorithm","volume":"144","author":"Martin","year":"2022","journal-title":"Comput. Oper. Res."},{"key":"10.1016\/j.tcs.2026.115962_bib0022","series-title":"International Conference on Optimization and Decision Science","first-page":"529","article-title":"On the forward shortest path tour problem","author":"Carrabs","year":"2017"},{"issue":"1","key":"10.1016\/j.tcs.2026.115962_bib0023","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1016\/j.ejor.2019.08.052","article-title":"Shortest path tour problem with time windows","volume":"282","author":"Pugliese","year":"2020","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"10.1016\/j.tcs.2026.115962_bib0024","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1007\/s10589-022-00405-8","article-title":"A generalized shortest path tour problem with time windows","volume":"83","author":"Di Puglia Pugliese","year":"2022","journal-title":"Comput. Optim. Appl."},{"issue":"1","key":"10.1016\/j.tcs.2026.115962_bib0025","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1002\/net.22010","article-title":"The constrained forward shortest path tour problem: mathematical modeling and GRASP approximate solutions","volume":"78","author":"Carrabs","year":"2021","journal-title":"Networks"},{"key":"10.1016\/j.tcs.2026.115962_bib0026","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1016\/j.trc.2019.05.020","article-title":"A data-parallel many-source shortest-path algorithm to accelerate macroscopic transport network assignment","volume":"104","author":"Heywood","year":"2019","journal-title":"Transp. Res. Part C Emerging Technol."},{"issue":"3","key":"10.1016\/j.tcs.2026.115962_bib0027","doi-asserted-by":"crossref","first-page":"1088","DOI":"10.1109\/TSMCB.2012.2223756","article-title":"Calculating complete and exact pareto front for multiobjective optimization: a new deterministic approach for discrete problems","volume":"43","author":"Hu","year":"2013","journal-title":"IEEE Trans. Cybern."},{"issue":"2","key":"10.1016\/j.tcs.2026.115962_bib0028","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1162\/EVCO_a_00156","article-title":"Deterministic agent-based path optimization by mimicking the spreading of ripples","volume":"24","author":"Hu","year":"2016","journal-title":"Evol. Comput."},{"key":"10.1016\/j.tcs.2026.115962_bib0029","doi-asserted-by":"crossref","DOI":"10.1016\/j.engappai.2019.08.023","article-title":"Finding the k shortest paths by ripple-spreading algorithms","volume":"87","author":"Hu","year":"2020","journal-title":"Eng. Appl. Artif. Intell."},{"issue":"3","key":"10.1016\/j.tcs.2026.115962_bib0030","doi-asserted-by":"crossref","first-page":"1245","DOI":"10.1007\/s12065-023-00822-6","article-title":"Genetic algorithms: theory, genetic operators, solutions, and applications","volume":"17","author":"Alhijawi","year":"2024","journal-title":"Evol. Intell."},{"key":"10.1016\/j.tcs.2026.115962_bib0031","doi-asserted-by":"crossref","DOI":"10.1016\/j.knosys.2023.110540","article-title":"An improved heuristic mechanism ant colony optimization algorithm for solving path planning","volume":"271","author":"Liu","year":"2023","journal-title":"Knowl. Based Syst."},{"key":"10.1016\/j.tcs.2026.115962_bib0032","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1016\/j.trb.2017.06.007","article-title":"Co-evolutionary path optimization by ripple-spreading algorithm","volume":"106","author":"Hu","year":"2017","journal-title":"Transp. Res. Part B Methodol."},{"key":"10.1016\/j.tcs.2026.115962_bib0033","doi-asserted-by":"crossref","DOI":"10.1016\/j.swevo.2021.100908","article-title":"Finding all pareto optimal paths by simulating ripple relay race in multi-objective networks","author":"Hu","year":"2021","journal-title":"Swarm Evol. Comput."},{"issue":"1","key":"10.1016\/j.tcs.2026.115962_bib0034","doi-asserted-by":"crossref","first-page":"753","DOI":"10.1007\/s40747-022-00825-3","article-title":"A deterministic and nature-inspired algorithm for the fuzzy multi-objective path optimization problem","volume":"9","author":"Ma","year":"2023","journal-title":"Complex Intell. Syst."},{"issue":"1","key":"10.1016\/j.tcs.2026.115962_bib0035","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"issue":"11","key":"10.1016\/j.tcs.2026.115962_bib0036","doi-asserted-by":"crossref","first-page":"712","DOI":"10.1287\/mnsc.17.11.712","article-title":"Finding the k shortest loopless paths in a network","volume":"17","author":"Yen","year":"1971","journal-title":"Manage. Sci."},{"issue":"18","key":"10.1016\/j.tcs.2026.115962_bib0037","doi-asserted-by":"crossref","first-page":"2129","DOI":"10.1016\/j.artint.2011.07.003","article-title":"K*: a heuristic search algorithm for finding the k shortest paths","volume":"175","author":"Aljazzar","year":"2011","journal-title":"Artif. Intell."},{"issue":"20","key":"10.1016\/j.tcs.2026.115962_bib0038","doi-asserted-by":"crossref","first-page":"10244","DOI":"10.1016\/j.amc.2012.04.002","article-title":"An efficient time and space K point-to-point shortest simple paths algorithm","volume":"218","author":"Sede\u00f1o-Noda","year":"2012","journal-title":"Appl. Math. Comput."},{"issue":"1","key":"10.1016\/j.tcs.2026.115962_bib0039","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erd\u0151s","year":"1960","journal-title":"Publ. Math. Inst. Hung. Acad. Sci."},{"issue":"2","key":"10.1016\/j.tcs.2026.115962_bib0040","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/BF02592101","article-title":"Shortest paths algorithms: theory and experimental evaluation","volume":"73","author":"Cherkassky","year":"1996","journal-title":"Math. Program."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397526002215?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397526002215?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T19:30:28Z","timestamp":1778355028000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397526002215"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6]]},"references-count":40,"alternative-id":["S0304397526002215"],"URL":"https:\/\/doi.org\/10.1016\/j.tcs.2026.115962","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2026,6]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"The ripple-spreading algorithm for shortest path tour problems","name":"articletitle","label":"Article Title"},{"value":"Theoretical Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.tcs.2026.115962","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.","name":"copyright","label":"Copyright"}],"article-number":"115962"}}