A solution method for the traveling salesman problem based on multi-scale features and dynamic optimization

A solution method for the traveling salesman problem based on multi-scale features and dynamic optimization | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article A solution method for the traveling salesman problem based on multi-scale features and dynamic optimization Yuting Xie, Qianqian Duan This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-9350580/v1 This work is licensed under a CC BY 4.0 License Status: Under Review Version 1 posted 13 You are reading this latest preprint version Abstract As a classic NP-hard problem, the Traveling Salesman Problem (TSP) exhibits exponentially increasing complexity with node quantity, making optimal solutions difficult for large-scale instances. Traditional exact and heuristic algorithms still struggle to balance computational cost with global optimality. Recently, deep learning has enabled end-to-end sequence modeling for TSP, yet existing models face limitations in global feature modeling, cross-scale generalization, and decoding stability. To address these issues, this study proposes a multi-scale deep optimization model based on an encoder-decoder architecture. In the encoding phase, an Exponential Moving Average (EMA) mechanism enhances global spatial correlation via multi-scale feature smoothing and dynamic weighting while suppressing feature noise. In the decoding phase, a Triplet-Reasoning attention mechanism captures high-order spatial dependencies through three-branch interaction (node, edge, path), balancing local coherence with global optimization. Additionally, a dynamic sampling strategy mitigates training-inference distribution shifts to improve generalization. Experimental results on benchmark datasets show that the proposed model outperforms mainstream deep learning methods in path length and optimality gap, demonstrating superior stability and global optimality, particularly on medium and large-scale instances. This work validates the effectiveness of the multi-scale EMA and Triplet-Reasoning mechanisms, providing a new direction for deep learning-based graph optimization research. Traveling salesman problem Deep learning Exponential moving average Three-branch attention mechanism Dynamic sampling strategy Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Under Review Version 1 posted Reviews received at journal 15 May, 2026 Reviews received at journal 15 May, 2026 Reviews received at journal 14 May, 2026 Reviews received at journal 10 May, 2026 Reviewers agreed at journal 10 May, 2026 Reviewers agreed at journal 10 May, 2026 Reviewers agreed at journal 09 May, 2026 Reviewers agreed at journal 08 May, 2026 Reviewers invited by journal 08 May, 2026 Editor invited by journal 17 Apr, 2026 Editor assigned by journal 09 Apr, 2026 Submission checks completed at journal 09 Apr, 2026 First submitted to journal 07 Apr, 2026 You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-9350580","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":641042583,"identity":"057eda40-8209-40b0-a293-58b00bfff832","order_by":0,"name":"Yuting Xie","email":"","orcid":"","institution":"Shanghai University of Engineering Sciences","correspondingAuthor":false,"prefix":"","firstName":"Yuting","middleName":"","lastName":"Xie","suffix":""},{"id":641042584,"identity":"2ec6b576-420e-4c5c-a670-654b3edb7141","order_by":1,"name":"Qianqian Duan","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAA5UlEQVRIiWNgGAWjYBACNvbGxgcJBhI8/FABxgZCWvh5DjcbfKiwkJNsIFaL5Iz0NsEZZyqMDQ4Qq8XgQGIbM2+bROLm82cMH/5gsJHdcID52QP8Wg62PQZp2XYjx9iYhyHNeMMBNnMDvFoONrYbQ7TwmEkzMBxO3HCAh00Cr5bDjG3SYIf1nzH/+YPhP2Etkm2MbZIzzkgYGzDkmDHwMBwgrIWfhxEUyBJyEjfSiqV5DJKNZx5mM8OrhU3++UNgVNbx8Pcf3vjxR4WdbN/x5md4taB7DYiZSVA/CkbBKBgFowA7AABA70tuowqY1AAAAABJRU5ErkJggg==","orcid":"","institution":"Shanghai University of Engineering Sciences","correspondingAuthor":true,"prefix":"","firstName":"Qianqian","middleName":"","lastName":"Duan","suffix":""}],"badges":[],"createdAt":"2026-04-08 02:38:39","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-9350580/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-9350580/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":109759434,"identity":"9a5012b8-a621-4f12-9f7f-9e810fa61b41","added_by":"auto","created_at":"2026-05-22 07:27:02","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":1062589,"visible":true,"origin":"","legend":"","description":"","filename":"paper.pdf","url":"https://assets-eu.researchsquare.com/files/rs-9350580/v1_covered_75abe3af-74b4-4dde-87b5-089b238fb889.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"A solution method for the traveling salesman problem based on multi-scale features and dynamic optimization","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"discover-computing","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"","sideBox":"Learn more about [Discover Computing](https://link.springer.com/journal/10791)","snPcode":"10791","submissionUrl":"https://submission.springernature.com/new-submission/10791/3","title":"Discover Computing","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"stoa","reportingPortfolio":"Discover Series","inReviewEnabled":true,"inReviewRevisionsEnabled":true},"keywords":"Traveling salesman problem, Deep learning, Exponential moving average, Three-branch attention mechanism, Dynamic sampling strategy","lastPublishedDoi":"10.21203/rs.3.rs-9350580/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-9350580/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eAs a classic NP-hard problem, the Traveling Salesman Problem (TSP) exhibits exponentially increasing complexity with node quantity, making optimal solutions difficult for large-scale instances. Traditional exact and heuristic algorithms still struggle to balance computational cost with global optimality. Recently, deep learning has enabled end-to-end sequence modeling for TSP, yet existing models face limitations in global feature modeling, cross-scale generalization, and decoding stability.\u003c/p\u003e \u003cp\u003eTo address these issues, this study proposes a multi-scale deep optimization model based on an encoder-decoder architecture. In the encoding phase, an Exponential Moving Average (EMA) mechanism enhances global spatial correlation via multi-scale feature smoothing and dynamic weighting while suppressing feature noise. In the decoding phase, a Triplet-Reasoning attention mechanism captures high-order spatial dependencies through three-branch interaction (node, edge, path), balancing local coherence with global optimization. Additionally, a dynamic sampling strategy mitigates training-inference distribution shifts to improve generalization.\u003c/p\u003e \u003cp\u003eExperimental results on benchmark datasets show that the proposed model outperforms mainstream deep learning methods in path length and optimality gap, demonstrating superior stability and global optimality, particularly on medium and large-scale instances. This work validates the effectiveness of the multi-scale EMA and Triplet-Reasoning mechanisms, providing a new direction for deep learning-based graph optimization research.\u003c/p\u003e","manuscriptTitle":"A solution method for the traveling salesman problem based on multi-scale features and dynamic optimization","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2026-05-18 03:16:00","doi":"10.21203/rs.3.rs-9350580/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"editorInvitedReview","content":"","date":"2026-05-15T21:26:49+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2026-05-15T08:35:40+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2026-05-14T14:42:44+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2026-05-10T12:48:54+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"166324154130101646531554696448986654238","date":"2026-05-10T08:33:19+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"165877728028199325158307158278541863373","date":"2026-05-10T04:24:54+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"78206214183012651114722191038372282708","date":"2026-05-09T14:39:51+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"255673440049262535401032208479815493627","date":"2026-05-08T09:14:18+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2026-05-08T08:17:44+00:00","index":"","fulltext":""},{"type":"editorInvited","content":"","date":"2026-04-17T07:05:58+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2026-04-09T13:48:34+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2026-04-09T13:48:02+00:00","index":"","fulltext":""},{"type":"submitted","content":"Discover Computing","date":"2026-04-08T02:25:13+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"discover-computing","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"","sideBox":"Learn more about [Discover Computing](https://link.springer.com/journal/10791)","snPcode":"10791","submissionUrl":"https://submission.springernature.com/new-submission/10791/3","title":"Discover Computing","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"stoa","reportingPortfolio":"Discover Series","inReviewEnabled":true,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"94445108-d5b2-4dcf-8189-8d6ec9d5085a","owner":[],"postedDate":"May 18th, 2026","published":true,"recentEditorialEvents":[{"type":"editorInvitedReview","content":"","date":"2026-05-15T21:26:49+00:00","index":38,"fulltext":""},{"type":"editorInvitedReview","content":"","date":"2026-05-15T08:35:40+00:00","index":37,"fulltext":""},{"type":"editorInvitedReview","content":"","date":"2026-05-14T14:42:44+00:00","index":36,"fulltext":""},{"type":"editorInvitedReview","content":"","date":"2026-05-10T12:48:54+00:00","index":35,"fulltext":""},{"type":"reviewerAgreed","content":"166324154130101646531554696448986654238","date":"2026-05-10T08:33:19+00:00","index":34,"fulltext":""},{"type":"reviewerAgreed","content":"165877728028199325158307158278541863373","date":"2026-05-10T04:24:54+00:00","index":33,"fulltext":""},{"type":"reviewerAgreed","content":"78206214183012651114722191038372282708","date":"2026-05-09T14:39:51+00:00","index":32,"fulltext":""},{"type":"reviewerAgreed","content":"255673440049262535401032208479815493627","date":"2026-05-08T09:14:18+00:00","index":31,"fulltext":""},{"type":"reviewersInvited","content":"15","date":"2026-05-08T08:17:44+00:00","index":"","fulltext":""}],"rejectedJournal":[],"revision":"","amendment":"","status":"under-review","subjectAreas":[],"tags":[],"updatedAt":"2026-05-18T03:16:00+00:00","versionOfRecord":[],"versionCreatedAt":"2026-05-18 03:16:00","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-9350580","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-9350580","identity":"rs-9350580","version":["v1"]},"buildId":"8U1c8b4HqxoKbykW_rLl7","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}