{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T03:55:30Z","timestamp":1774929330861,"version":"3.50.1"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,6,1]],"date-time":"2024-06-01T00:00:00Z","timestamp":1717200000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,6,6]],"date-time":"2024-06-06T00:00:00Z","timestamp":1717632000000},"content-version":"vor","delay-in-days":5,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001775","name":"University of Technology Sydney","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001775","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Mach. Intell."],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The vehicle routing problem (VRP) is an example of a combinatorial optimization problem that has attracted academic attention due to its potential use in various contexts. VRP aims to arrange vehicle deliveries to several sites in the most efficient and economical manner possible. Quantum machine learning offers a new way to obtain solutions by harnessing the natural speedups of quantum effects, although many solutions and methodologies are modified using classical tools to provide excellent approximations of the VRP. In this paper, we employ <jats:bold>6<\/jats:bold> and <jats:bold>12<\/jats:bold> qubit circuits, respectively, to build and evaluate a hybrid quantum machine learning approach for solving VRP of 3- and 4-city scenarios. The approach employs quantum support vector machines (QSVMs) trained using a variational quantum eigensolver on a static or dynamic ansatz. Different encoding strategies are used in the experiment to transform the VRP formulation into a QSVM and solve it. Multiple optimizers from the IBM Qiskit framework are also evaluated and compared<\/jats:p>","DOI":"10.1007\/s42484-024-00161-4","type":"journal-article","created":{"date-parts":[[2024,6,6]],"date-time":"2024-06-06T13:01:38Z","timestamp":1717678898000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Solving the vehicle routing problem via quantum support vector machines"],"prefix":"10.1007","volume":"6","author":[{"given":"Nishikanta","family":"Mohanty","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bikash K.","family":"Behera","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christopher","family":"Ferrie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,6,6]]},"reference":[{"issue":"1","key":"161_CR1","doi-asserted-by":"publisher","first-page":"6329","DOI":"10.1038\/s41598-021-85474-1","volume":"11","author":"IF Araujo","year":"2021","unstructured":"Araujo IF, Park DK, Petruccione F, da Silva AJ (2021) A divide-and-conquer algorithm for quantum state preparation. Sci Rep 11(1):6329. https:\/\/doi.org\/10.1038\/s41598-021-85474-1","journal-title":"Sci Rep"},{"key":"161_CR2","doi-asserted-by":"crossref","unstructured":"Azad U, Behera BK, Ahmed EA, Panigrahi PK, Farouk A (2023) Solving vehicle routing problem using quantum approximate optimization algorithm vol 24. Available from: https:\/\/ieeexplore.ieee.org\/document\/9774961","DOI":"10.1109\/TITS.2022.3172241"},{"key":"161_CR3","doi-asserted-by":"publisher","first-page":"883","DOI":"10.1103\/RevModPhys.39.883","volume":"39","author":"SG Brush","year":"1967","unstructured":"Brush SG (1967) History of the Lenz-Ising model. Rev Mod Phys 39:883\u2013893. https:\/\/doi.org\/10.1103\/RevModPhys.39.883","journal-title":"Rev Mod Phys"},{"key":"161_CR4","doi-asserted-by":"publisher","unstructured":"Cerezo M, Arrasmith A, Babbush R, Benjamin SC, Endo S, Fujii K et\u00a0al (2021) Variational quantum algorithms. Nat Rev Phys 3(9):625\u2013644. https:\/\/doi.org\/10.1038\/s42254-021-00348-9arXiv:2012.09265","DOI":"10.1038\/s42254-021-00348-9"},{"key":"161_CR5","doi-asserted-by":"crossref","unstructured":"Crispin A, Syrichas A (2013) Quantum annealing algorithm for vehicle scheduling. In: 2013 IEEE International Conference on Systems, Man, and Cybernetics, pp 3523\u20133528. ISSN: 1062-922X. Available from: https:\/\/ieeexplore.ieee.org\/document\/6722354","DOI":"10.1109\/SMC.2013.601"},{"key":"161_CR6","doi-asserted-by":"crossref","unstructured":"Dasari V, Im MS, Beshaj L (2020) Solving machine learning optimization problems using quantum computers. In: Blowers M, Hall RD, Dasari VR (eds). Online Only, United States: SPIE. Available from: https:\/\/www.spiedigitallibrary.org\/conference-proceedings-of-spie\/11419\/2565038\/Solving-machine-learning-optimization-problems-using-quantum-computers\/10.1117\/12.2565038.full","DOI":"10.1117\/12.2565038"},{"issue":"4","key":"161_CR7","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/s11128-019-2236-3","volume":"18","author":"P Date","year":"2019","unstructured":"Date P, Patton R, Schuman C, Potok T (2019) Efficiently embedding QUBO problems on adiabatic quantum computers. Quantum Inf Process 18(4):117. https:\/\/doi.org\/10.1007\/s11128-019-2236-3","journal-title":"Quantum Inf Process"},{"key":"161_CR8","unstructured":"et al (2024) MSA.: Qiskit: an open-source framework for quantum computing. Available from: https:\/\/github.com\/Qiskit\/qiskit\/tree\/0.25.0"},{"key":"161_CR9","unstructured":"Farhi E, Goldstone J, Gutmann S (2014) A quantum approximate optimization algorithm. Available from: arXiv:1411.4028v1"},{"key":"161_CR10","unstructured":"Farhi E, Goldstone J, Gutmann S, Sipser M (2000) Quantum computation by adiabatic evolution. Available from: https:\/\/arxiv.org\/abs\/quant-ph\/0001106v1"},{"key":"161_CR11","doi-asserted-by":"crossref","unstructured":"Feld S, Roch C, Gabor T, Seidel C, Neukart F, Galter I et\u00a0al (2019) A hybrid solution method for the capacitated vehicle routing problem using a quantum annealer vol 6. Available from: https:\/\/www.frontiersin.org\/article\/10.3389\/fict.2019.00013","DOI":"10.3389\/fict.2019.00013"},{"key":"161_CR12","doi-asserted-by":"crossref","unstructured":"Gentinetta G, Thomsen A, Sutter D, Woerner S (2024) The complexity of quantum support vector machines","DOI":"10.22331\/q-2024-01-11-1225"},{"key":"161_CR13","doi-asserted-by":"crossref","unstructured":"Glick JR, Gujarati TP, Corcoles AD, Kim Y, Kandala A, Gambetta JM et\u00a0al (2024) Covariant quantum kernels for data with group structure","DOI":"10.1038\/s41567-023-02340-9"},{"key":"161_CR14","doi-asserted-by":"crossref","unstructured":"Glover F, Kochenberger G, Ma M, Du Y (2020) Quantum Bridge Analytics II: QUBO-Plus, network optimization and combinatorial chaining for asset exchange. 4OR. 18(4):387\u2013417. Publisher Springer","DOI":"10.1007\/s10288-020-00464-9"},{"key":"161_CR15","doi-asserted-by":"crossref","unstructured":"Grover LK (1996) A fast quantum mechanical algorithm for database search. Available from: https:\/\/arxiv.org\/abs\/quant-ph\/9605043v3","DOI":"10.1145\/237814.237866"},{"key":"161_CR16","unstructured":"Guerreschi GG (2021) Solving quadratic unconstrained binary optimization with divide-and-conquer and quantum algorithms. arXiv:2101.07813"},{"key":"161_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TQE.2021.3049230","volume":"2","author":"S Harwood","year":"2021","unstructured":"Harwood S, Gambella C, Trenev D, Simonetto A, Bernal D, Greenberg D (2021) Formulating and solving routing problems on quantum computers. IEEE Trans Quantum Eng 2:1\u201317. https:\/\/doi.org\/10.1109\/TQE.2021.3049230","journal-title":"IEEE Trans Quantum Eng"},{"key":"161_CR18","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1038\/s41586-019-0980-2","volume":"567","author":"V Havlicek","year":"2019","unstructured":"Havlicek V, Corcoles AD, Temme K, Harrow AW, Kandala A, Chow JM et al (2019) Supervised learning with quantum enhanced feature spaces. Nature 567:209\u2013212","journal-title":"Nature"},{"key":"161_CR19","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1103\/RevModPhys.81.865","volume":"81","author":"R Horodecki","year":"2009","unstructured":"Horodecki R, Horodecki P, Horodecki M, Horodecki K (2009) Quantum entanglement. Rev Mod Phys 81:865\u2013942. https:\/\/doi.org\/10.1103\/RevModPhys.81.865","journal-title":"Quantum entanglement. Rev Mod Phys"},{"key":"161_CR20","doi-asserted-by":"crossref","unstructured":"Irie H, Wongpaisarnsin G, Terabe M, Miki A, Taguchi S (2019) Quantum annealing of vehicle routing problem with time, state and capacity. In: Feld S, Linnhoff-Popien C (eds) Quantum Technology and Optimization Problems. Lecture Notes in Computer Science. Cham Springer International Publishing pp 145\u2013156. Available from: https:\/\/link.springer.com\/chapter\/10.1007\/978-3-030-14082-3_13","DOI":"10.1007\/978-3-030-14082-3_13"},{"key":"161_CR21","unstructured":"Jordan S (2024) Available from: https:\/\/quantumalgorithmzoo.org\/#ONML. https:\/\/quantumalgorithmzoo.org\/"},{"key":"161_CR22","unstructured":"Kariya A, Behera BK (2024) Investigation of quantum support vector machine for classification in NISQ era"},{"key":"161_CR23","doi-asserted-by":"publisher","unstructured":"Kochenberger G, Hao JK, Glover F, Lewis M, L\u00fc Z, Wang H et al (2014) The unconstrained binary quadratic programming problem: a survey. J Combin Optim 28. https:\/\/doi.org\/10.1007\/s10878-014-9734-0","DOI":"10.1007\/s10878-014-9734-0"},{"issue":"3","key":"161_CR24","first-page":"9","volume":"4","author":"SN Kumar","year":"2012","unstructured":"Kumar SN, Panneerselvam R (2012) A survey on the vehicle routing problem and its variants. Intell Inf Manage 4(3):9","journal-title":"Intell Inf Manage"},{"key":"161_CR25","doi-asserted-by":"publisher","unstructured":"LaRose R, Coyle B (2020) Robust data encodings for quantum classifiers. Phys Rev A 102:032420. https:\/\/doi.org\/10.1103\/PhysRevA.102.032420","DOI":"10.1103\/PhysRevA.102.032420"},{"issue":"3","key":"161_CR26","doi-asserted-by":"publisher","first-page":"482","DOI":"10.3390\/quantum3030032","volume":"3","author":"R Leporini","year":"2021","unstructured":"Leporini R, Pastorello D (2021) Support vector machines with quantum state discrimination. Quantum Rep 3(3):482\u2013499","journal-title":"Quantum Rep"},{"key":"161_CR27","doi-asserted-by":"publisher","unstructured":"Lucas A (2014) Ising formulations of many NP problems. Front Phys 2. https:\/\/doi.org\/10.3389\/fphy.2014.00005","DOI":"10.3389\/fphy.2014.00005"},{"key":"161_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/tqe.2023.3303989","volume":"4","author":"N Mohanty","year":"2023","unstructured":"Mohanty N, Behera BK, Ferrie C (2023) Analysis of the vehicle routing problem solved via hybrid quantum algorithms in the presence of noisy channels. IEEE Trans Quantum Eng 4:1\u201314. https:\/\/doi.org\/10.1109\/tqe.2023.3303989","journal-title":"IEEE Trans Quantum Eng"},{"key":"161_CR29","doi-asserted-by":"publisher","unstructured":"Montanaro A (2016) Quantum algorithms: an overview. npj Quantum Inf 2(1):15023. https:\/\/doi.org\/10.1038\/npjqi.2015.23","DOI":"10.1038\/npjqi.2015.23"},{"key":"161_CR30","unstructured":"National Academies of Sciences E (2019) Chapter: 3 Quantum Algorithms and Applications. In: Quantum Computing: Progress and Prospects. Available from: https:\/\/www.nap.edu\/catalog\/25196\/quantum-computing-progress-and-prospects"},{"issue":"2","key":"161_CR31","first-page":"7","volume":"55","author":"FE Office","year":"2019","unstructured":"Office FE (2019) Application of digital annealer for faster combinatorial optimization. FUJITSU Sci Tech J 55(2):7","journal-title":"FUJITSU Sci Tech J"},{"key":"161_CR32","unstructured":"Paddle Quantum (2024) Available from: https:\/\/qml.baidu.com\/tutorials\/machine-learning\/encoding-classical-data-into-quantum-states.html"},{"issue":"1","key":"161_CR33","doi-asserted-by":"publisher","first-page":"4213","DOI":"10.1038\/ncomms5213","volume":"5","author":"A Peruzzo","year":"2014","unstructured":"Peruzzo A, McClean J, Shadbolt P, Yung MH, Zhou XQ, Love PJ et al (2014) A variational eigenvalue solver on a photonic quantum processor. Nat Commun 5(1):4213. https:\/\/doi.org\/10.1038\/ncomms5213","journal-title":"Nat Commun"},{"key":"161_CR34","unstructured":"Qiskit (2024) Lecture 5.1 - building a quantum classifier. Available from: https:\/\/www.youtube.com\/watch?v=-sxlXNz7ZxU"},{"key":"161_CR35","unstructured":"Qiskit: vehicle routing (2024). Available from: https:\/\/qiskit.org\/ecosystem\/optimization\/tutorials\/07_examples_vehicle_routing.html"},{"key":"161_CR36","doi-asserted-by":"publisher","unstructured":"Rebentrost P, Mohseni M, Lloyd S (2014) Quantum support vector machine for big data classification. Phys Rev Lett 113(13). https:\/\/doi.org\/10.1103\/physrevlett.113.130503","DOI":"10.1103\/physrevlett.113.130503"},{"key":"161_CR37","unstructured":"Singh SP (2020) The Ising model: brief introduction and its application. IntechOpen. Publication Title: Solid State Physics - Metastable, Spintronics Materials and Mechanics of Deformable Bodies - Recent Progress. Available from: https:\/\/www.intechopen.com\/chapters\/71210"},{"key":"161_CR38","unstructured":"Srinivasan K, Satyajit S, Behera BK, Panigrahi PK (2018) Efficient quantum algorithm for solving travelling salesman problem: an IBM quantum experience. arXiv preprint arXiv:1805.10928v1"},{"key":"161_CR39","doi-asserted-by":"publisher","unstructured":"Zhou L, Wang ST, Choi S, Pichler H, Lukin MD (2020) Quantum approximate optimization algorithm: performance, mechanism, and implementation on near-term devices. Phys Rev X 10(2):021067. Publisher American Physical Society. https:\/\/doi.org\/10.1103\/PhysRevX.10.021067","DOI":"10.1103\/PhysRevX.10.021067"}],"container-title":["Quantum Machine Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-024-00161-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42484-024-00161-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-024-00161-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,24]],"date-time":"2024-06-24T16:08:25Z","timestamp":1719245305000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42484-024-00161-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["161"],"URL":"https:\/\/doi.org\/10.1007\/s42484-024-00161-4","relation":{},"ISSN":["2524-4906","2524-4914"],"issn-type":[{"value":"2524-4906","type":"print"},{"value":"2524-4914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6]]},"assertion":[{"value":"18 August 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 April 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 June 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"34"}}