Deep Reinforcement Learning Combined with Transformer to Solve the Traveling Salesman Problem

Deep Reinforcement Learning Combined with Transformer to Solve the Traveling Salesman Problem | 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 Deep Reinforcement Learning Combined with Transformer to Solve the Traveling Salesman Problem Chang Liu, Xue-Feng Feng, Feng Li, Qing-Long Xian, Zhen-Hong Jia, and 2 more This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-5153062/v1 This work is licensed under a CC BY 4.0 License Status: Under Review Version 1 posted 9 You are reading this latest preprint version Abstract The Transformer model is widely employed to address the traveling salesman problem due to its robust global information acquisition, learning, and generalization capabilities. However, its high computational complexity and limited accuracy require further refinement. To overcome these shortcomings, a novel model is proposed, integrating a lightweight CNN embedding layer with a Transformer model enhanced by an efficient Pyramid Compressed Attention (PSA) mechanism. The introduction of the lightweight CNN embedding layer significantly reduces the number of parameters and computational complexity, allowing for the flexible extraction of local spatial features between neighboring nodes, while maintaining the ability to handle larger-scale datasets. The PSA mechanism, on one hand, improves solution accuracy by accounting for both local neighborhood relations and global dependencies. On the other hand, its multi-scale nature enables the model to adapt to problems of varying scales, ensuring strong performance for both small- and large-scale problems. Extensive experiments conducted on random datasets as well as the public TSPLIB dataset have demonstrated that the proposed model surpasses other deep reinforcement learning algorithms in terms of solution quality and generalization ability. traveling salesman problem deep reinforcement learning combinatorial optimization problem transformer Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Under Review Version 1 posted Editorial decision: Revision requested 22 Oct, 2024 Reviews received at journal 22 Oct, 2024 Reviews received at journal 12 Oct, 2024 Reviewers agreed at journal 12 Oct, 2024 Reviewers agreed at journal 12 Oct, 2024 Reviewers invited by journal 12 Oct, 2024 Editor assigned by journal 26 Sep, 2024 Submission checks completed at journal 26 Sep, 2024 First submitted to journal 25 Sep, 2024 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-5153062","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":369090316,"identity":"5c1083a9-140b-4c72-8fde-d59eb3ebd2b6","order_by":0,"name":"Chang Liu","email":"","orcid":"","institution":"Xinjiang University","correspondingAuthor":false,"prefix":"","firstName":"Chang","middleName":"","lastName":"Liu","suffix":""},{"id":369090318,"identity":"c311a745-9561-47e6-b8fc-3b02181b93ca","order_by":1,"name":"Xue-Feng Feng","email":"","orcid":"","institution":"Xinjiang Uygur Autonomous Region Research Institute of Measurement and Testing","correspondingAuthor":false,"prefix":"","firstName":"Xue-Feng","middleName":"","lastName":"Feng","suffix":""},{"id":369090319,"identity":"5462db18-cc08-481b-b90d-888cda68a727","order_by":2,"name":"Feng Li","email":"","orcid":"","institution":"Xinjiang Uygur Autonomous Region Research Institute of Measurement and Testing","correspondingAuthor":false,"prefix":"","firstName":"Feng","middleName":"","lastName":"Li","suffix":""},{"id":369090320,"identity":"c90f726c-b227-4995-a259-59a97989fb05","order_by":3,"name":"Qing-Long Xian","email":"","orcid":"","institution":"Xinjiang Uygur Autonomous Region Research Institute of Measurement and Testing","correspondingAuthor":false,"prefix":"","firstName":"Qing-Long","middleName":"","lastName":"Xian","suffix":""},{"id":369090321,"identity":"9c4e04e7-d6ef-4e07-837f-918cf4d7befe","order_by":4,"name":"Zhen-Hong Jia","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAAuElEQVRIiWNgGAWjYBACxgYeNoYPDGwgtgHxWhhnkKSFgYGHjZkHwiJSC3P/2WOPbdv4EhvYm7dJMNTcIcZh59KNc86wJTbwHCuTYDj2jAgtjT1m0jkVQC0SOWYSjA2HidDSzGMmbWEA1CL/hlgtbUAtDGBbeIjV0sNjJtlzhs24jSet2CLhGBFaDPvPmEn8bDsm289+eOONDzXEaGkAU8cgkZlAWAMDgzyEqiFG7SgYBaNgFIxUAABXFTG7K8mDiwAAAABJRU5ErkJggg==","orcid":"","institution":"Xinjiang University","correspondingAuthor":true,"prefix":"","firstName":"Zhen-Hong","middleName":"","lastName":"Jia","suffix":""},{"id":369090322,"identity":"18d02029-46d7-48bc-96ea-dcd58e32a227","order_by":5,"name":"Yu-Hang Wang","email":"","orcid":"","institution":"Xinjiang University","correspondingAuthor":false,"prefix":"","firstName":"Yu-Hang","middleName":"","lastName":"Wang","suffix":""},{"id":369090323,"identity":"2142eede-2f42-4937-8a44-39c477f8240e","order_by":6,"name":"Zong-Dong Du","email":"","orcid":"","institution":"Xinjiang University","correspondingAuthor":false,"prefix":"","firstName":"Zong-Dong","middleName":"","lastName":"Du","suffix":""}],"badges":[],"createdAt":"2024-09-25 15:08:18","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-5153062/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-5153062/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":68261362,"identity":"e113379f-8c26-4cfa-9194-754b13ba0a7f","added_by":"auto","created_at":"2024-11-05 12:05:22","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":562248,"visible":true,"origin":"","legend":"","description":"","filename":"DeepReinforcementLearningCombinedwithTransformertoSolvetheTravelingSalesmanProblem.pdf","url":"https://assets-eu.researchsquare.com/files/rs-5153062/v1_covered_700d54a1-23b6-4790-a3a1-345c607ca95d.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Deep Reinforcement Learning Combined with Transformer to Solve the Traveling Salesman Problem","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":true,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"the-journal-of-supercomputing","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"","sideBox":"Learn more about [The Journal of Supercomputing](https://www.springer.com/journal/11227)","snPcode":"11227","submissionUrl":"https://submission.nature.com/new-submission/11227/3","title":"The Journal of Supercomputing","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"stoa","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false},"keywords":"traveling salesman problem, deep reinforcement learning, combinatorial optimization problem, transformer","lastPublishedDoi":"10.21203/rs.3.rs-5153062/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-5153062/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eThe Transformer model is widely employed to address the traveling salesman problem due to its robust global information acquisition, learning, and generalization capabilities. However, its high computational complexity and limited accuracy require further refinement. To overcome these shortcomings, a novel model is proposed, integrating a lightweight CNN embedding layer with a Transformer model enhanced by an efficient Pyramid Compressed Attention (PSA) mechanism. The introduction of the lightweight CNN embedding layer significantly reduces the number of parameters and computational complexity, allowing for the flexible extraction of local spatial features between neighboring nodes, while maintaining the ability to handle larger-scale datasets. The PSA mechanism, on one hand, improves solution accuracy by accounting for both local neighborhood relations and global dependencies. On the other hand, its multi-scale nature enables the model to adapt to problems of varying scales, ensuring strong performance for both small- and large-scale problems. Extensive experiments conducted on random datasets as well as the public TSPLIB dataset have demonstrated that the proposed model surpasses other deep reinforcement learning algorithms in terms of solution quality and generalization ability.\u003c/p\u003e","manuscriptTitle":"Deep Reinforcement Learning Combined with Transformer to Solve the Traveling Salesman Problem","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2024-11-05 11:57:14","doi":"10.21203/rs.3.rs-5153062/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"decision","content":"Revision requested","date":"2024-10-22T13:14:32+00:00","index":"","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2024-10-22T05:42:20+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2024-10-12T20:59:29+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"246590122190290290270356379522382726741","date":"2024-10-12T20:43:50+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"309576601925261702977878977842697809234","date":"2024-10-12T17:10:35+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2024-10-12T16:28:23+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2024-09-26T09:08:29+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2024-09-26T09:06:12+00:00","index":"","fulltext":""},{"type":"submitted","content":"The Journal of Supercomputing","date":"2024-09-25T14:59:44+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"the-journal-of-supercomputing","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"","sideBox":"Learn more about [The Journal of Supercomputing](https://www.springer.com/journal/11227)","snPcode":"11227","submissionUrl":"https://submission.nature.com/new-submission/11227/3","title":"The Journal of Supercomputing","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"stoa","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false}}],"origin":"","ownerIdentity":"babb9a36-7e40-4cbd-8323-a542c01abeb7","owner":[],"postedDate":"November 5th, 2024","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"under-review","subjectAreas":[],"tags":[],"updatedAt":"2024-11-05T11:57:14+00:00","versionOfRecord":[],"versionCreatedAt":"2024-11-05 11:57:14","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-5153062","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-5153062","identity":"rs-5153062","version":["v1"]},"buildId":"qtupq5eGEP_6zYnWcrvyt","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}