Solving a Real-World Package Delivery Routing Problem Using Quantum Annealers

Solving a Real-World Package Delivery Routing Problem Using Quantum Annealers | 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 Article Solving a Real-World Package Delivery Routing Problem Using Quantum Annealers Eneko Osaba, Esther Villar-Rodriguez, Antón Asla This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-4176120/v1 This work is licensed under a CC BY 4.0 License Status: Published Journal Publication published 21 Oct, 2024 Read the published version in Scientific Reports → Version 1 posted 10 You are reading this latest preprint version Abstract Research focused on the conjunction between quantum computing and routing problems has been very prolific in recent years. Most of the works revolve around classical problems such as the Traveling Salesman Problem or the Vehicle Routing Problem. Even though working on these problems is valuable, it is also undeniable that their academic-oriented nature falls short of real-world requirements. The main objective of this research is to present a solving method for realistic instances, avoiding problem relaxations or technical shortcuts. Instead, a quantum-classical hybrid solver has been developed, coined Q4RPD, that considers a set of real constraints such as a heterogeneous fleet of vehicles, priority deliveries, and capacities characterized by two values: weight and dimensions of the packages. \Q4RPD resorts to the Leap Constrained Quadratic Model Hybrid Solver of D-Wave. To demonstrate the application of Q4RPD, an experimentation composed of six different instances has been conducted, aiming to serve as illustrative examples. Physical sciences/Physics/Quantum physics/Quantum information Physical sciences/Mathematics and computing/Computer science Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Published Journal Publication published 21 Oct, 2024 Read the published version in Scientific Reports → Version 1 posted Editorial decision: Revision requested 09 May, 2024 Reviews received at journal 24 Apr, 2024 Reviews received at journal 21 Apr, 2024 Reviewers agreed at journal 11 Apr, 2024 Reviewers agreed at journal 11 Apr, 2024 Reviewers invited by journal 11 Apr, 2024 Editor assigned by journal 11 Apr, 2024 Editor invited by journal 08 Apr, 2024 Submission checks completed at journal 03 Apr, 2024 First submitted to journal 27 Mar, 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-4176120","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Article","associatedPublications":[],"authors":[{"id":287115259,"identity":"283135b9-803f-43f0-9a2f-5cc74a710ff5","order_by":0,"name":"Eneko Osaba","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAA/klEQVRIiWNgGAWjYHACZgglwcD4AMxgZ2wgWguzwQEwnwQtbBIHkPg4Ab9082GDDww29vyzm59Vf6iwy+NvZm78wFBjE41Li+ScY8mJMxjSEmfcOWZ248CZ5GKJw4zNEgzH0nJxOc/gRo7xYR6GwwkMNxLMbhxsO5DYcJixQYKx4TBOLfY38j+DtNjL30j/VnDw34HE+UBbfuDTYiCRw5wM1MK44UaOGcPBhgOJGw4ztuG1ReJGmrHhDIO0xI13zhRLnAF6bCNQi0UCHr/wz0h+LPGhwsZe7nb7xg8VNXaJ8463P77xocYGpxao89AFEvAqHwWjYBSMglFACAAAQLdeUkEFb30AAAAASUVORK5CYII=","orcid":"","institution":"Tecnalia","correspondingAuthor":true,"prefix":"","firstName":"Eneko","middleName":"","lastName":"Osaba","suffix":""},{"id":287115260,"identity":"a7b0af70-7818-4309-9660-e36d723b19fc","order_by":1,"name":"Esther Villar-Rodriguez","email":"","orcid":"","institution":"Tecnalia","correspondingAuthor":false,"prefix":"","firstName":"Esther","middleName":"","lastName":"Villar-Rodriguez","suffix":""},{"id":287115261,"identity":"c9208e38-f921-4232-bb3a-7dd0df15bb13","order_by":2,"name":"Antón Asla","email":"","orcid":"","institution":"Serikat - Consultoría y Servicios Tecnológicos","correspondingAuthor":false,"prefix":"","firstName":"Antón","middleName":"","lastName":"Asla","suffix":""}],"badges":[],"createdAt":"2024-03-27 12:44:28","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-4176120/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-4176120/v1","draftVersion":[],"editorialEvents":[{"content":"https://doi.org/10.1038/s41598-024-75572-1","type":"published","date":"2024-10-21T15:57:40+00:00"}],"editorialNote":"","failedWorkflow":false,"files":[{"id":67681888,"identity":"bd7ea9f5-cb43-4fda-97fc-629668e519aa","added_by":"auto","created_at":"2024-10-28 16:10:56","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":3199595,"visible":true,"origin":"","legend":"","description":"","filename":"Firstversion.pdf","url":"https://assets-eu.researchsquare.com/files/rs-4176120/v1_covered_334a4223-665d-4998-af21-686b0ff2a5fa.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Solving a Real-World Package Delivery Routing Problem Using Quantum Annealers","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":"scientific-reports","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"scirep","sideBox":"Learn more about [Scientific Reports](http://www.nature.com/srep/)","snPcode":"","submissionUrl":"","title":"Scientific Reports","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"stoa","reportingPortfolio":"Scientific Reports","inReviewEnabled":true,"inReviewRevisionsEnabled":true},"keywords":"","lastPublishedDoi":"10.21203/rs.3.rs-4176120/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-4176120/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"Research focused on the conjunction between quantum computing and routing problems has been very prolific in recent years. Most of the works revolve around classical problems such as the Traveling Salesman Problem or the Vehicle Routing Problem. Even though working on these problems is valuable, it is also undeniable that their academic-oriented nature falls short of real-world requirements. The main objective of this research is to present a solving method for realistic instances, avoiding problem relaxations or technical shortcuts. Instead, a quantum-classical hybrid solver has been developed, coined Q4RPD, that considers a set of real constraints such as a heterogeneous fleet of vehicles, priority deliveries, and capacities characterized by two values: weight and dimensions of the packages. \\Q4RPD resorts to the Leap Constrained Quadratic Model Hybrid Solver of D-Wave. To demonstrate the application of Q4RPD, an experimentation composed of six different instances has been conducted, aiming to serve as illustrative examples.","manuscriptTitle":"Solving a Real-World Package Delivery Routing Problem Using Quantum Annealers","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2024-04-08 03:11:14","doi":"10.21203/rs.3.rs-4176120/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"decision","content":"Revision requested","date":"2024-05-09T07:03:46+00:00","index":"","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2024-04-24T07:10:40+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2024-04-22T03:23:10+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"c2192d80-4612-4dd9-b6a0-994843292ee8","date":"2024-04-11T21:52:45+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"de3eca95-4acc-44e8-ad22-32bd8e0ea767","date":"2024-04-11T20:47:41+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2024-04-11T19:59:11+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2024-04-11T19:46:24+00:00","index":"","fulltext":""},{"type":"editorInvited","content":"","date":"2024-04-08T13:59:26+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2024-04-03T12:53:38+00:00","index":"","fulltext":""},{"type":"submitted","content":"Scientific Reports","date":"2024-03-27T12:35:49+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"scientific-reports","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"scirep","sideBox":"Learn more about [Scientific Reports](http://www.nature.com/srep/)","snPcode":"","submissionUrl":"","title":"Scientific Reports","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"stoa","reportingPortfolio":"Scientific Reports","inReviewEnabled":true,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"94ceb552-5f74-47e5-b70a-6ab94c407694","owner":[],"postedDate":"April 8th, 2024","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"published-in-journal","subjectAreas":[{"id":30222518,"name":"Physical sciences/Physics/Quantum physics/Quantum information"},{"id":30222519,"name":"Physical sciences/Mathematics and computing/Computer science"}],"tags":[],"updatedAt":"2024-10-28T16:02:31+00:00","versionOfRecord":{"articleIdentity":"rs-4176120","link":"https://doi.org/10.1038/s41598-024-75572-1","journal":{"identity":"scientific-reports","isVorOnly":false,"title":"Scientific Reports"},"publishedOn":"2024-10-21 15:57:40","publishedOnDateReadable":"October 21st, 2024"},"versionCreatedAt":"2024-04-08 03:11:14","video":"","vorDoi":"10.1038/s41598-024-75572-1","vorDoiUrl":"https://doi.org/10.1038/s41598-024-75572-1","workflowStages":[]},"version":"v1","identity":"rs-4176120","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-4176120","identity":"rs-4176120","version":["v1"]},"buildId":"qtupq5eGEP_6zYnWcrvyt","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}