{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,4]],"date-time":"2026-09-04T21:50:52Z","timestamp":1788558652401,"version":"build-2803163510"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,8,26]],"date-time":"2024-08-26T00:00:00Z","timestamp":1724630400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,8,26]],"date-time":"2024-08-26T00:00:00Z","timestamp":1724630400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"publisher","award":["13N15587"],"award-info":[{"award-number":["13N15587"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Sci Rep"],"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Many emerging commercial services are based on the sharing or pooling of resources for common use with the aim of reducing costs. Businesses such as delivery-, mobility-, or transport-as-a-service have become standard in many parts of the world, fulfilling on-demand requests for customers in live settings. However, it is known that many of these problems are NP-hard, and therefore both modeling and solving them accurately is a challenge. Here we focus on one such routing problem, the Ride Pooling Problem (RPP), where multiple customers can request on-demand pickups and drop-offs from shared vehicles within a fleet. The combinatorial optimization task is to optimally pool customer requests using the limited set of vehicles, akin to a small-scale flexible bus route. In this work, we propose a quadratic unconstrained binary optimization (QUBO) program and introduce efficient formulation methods for the RPP to be solved using metaheuristics, and specifically emerging quantum optimization algorithms.<\/jats:p>","DOI":"10.1038\/s41598-024-70649-3","type":"journal-article","created":{"date-parts":[[2024,8,26]],"date-time":"2024-08-26T08:02:22Z","timestamp":1724659342000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["Modeling routing problems in QUBO with application to ride-hailing"],"prefix":"10.1038","volume":"14","author":[{"given":"Michele","family":"Cattelan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sheir","family":"Yarkoni","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,8,26]]},"reference":[{"key":"70649_CR1","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/s10878-014-9734-0","volume":"28","author":"G Kochenberger","year":"2014","unstructured":"Kochenberger, G. et al. The unconstrained binary quadratic programming problem: A survey. J. Comb. Optim. 28, 58\u201381. https:\/\/doi.org\/10.1007\/s10878-014-9734-0 (2014).","journal-title":"J. Comb. Optim."},{"key":"70649_CR2","doi-asserted-by":"publisher","first-page":"5","DOI":"10.3389\/fphy.2014.00005","volume":"2","author":"A Lucas","year":"2014","unstructured":"Lucas, A. Ising formulations of many np problems. Front. Phys. 2, 5 (2014).","journal-title":"Front. Phys."},{"key":"70649_CR3","unstructured":"Farhi, E., Goldstone, J., Gutmann, S. & Sipser, M. Quantum computation by adiabatic evolution. arXiv preprint quant-ph\/0001106 (2000)."},{"key":"70649_CR4","unstructured":"Farhi, E., Goldstone, J. & Gutmann, S. A quantum approximate optimization algorithm. arXiv preprint[SPACE]arXiv:1411.4028 (2014)."},{"key":"70649_CR5","doi-asserted-by":"publisher","first-page":"5355","DOI":"10.1103\/PhysRevE.58.5355","volume":"58","author":"T Kadowaki","year":"1998","unstructured":"Kadowaki, T. & Nishimori, H. Quantum annealing in the transverse ising model. Phys. Rev. E 58, 5355 (1998).","journal-title":"Phys. Rev. E"},{"key":"70649_CR6","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1038\/nature10012","volume":"473","author":"MW Johnson","year":"2011","unstructured":"Johnson, M. W. et al. Quantum annealing with manufactured spins. Nature 473, 194\u2013198 (2011).","journal-title":"Nature"},{"key":"70649_CR7","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1038\/s41586-019-1666-5","volume":"574","author":"F Arute","year":"2019","unstructured":"Arute, F. et al. Quantum supremacy using a programmable superconducting processor. Nature 574, 505\u2013510 (2019).","journal-title":"Nature"},{"key":"70649_CR8","doi-asserted-by":"crossref","unstructured":"Li, G. et\u00a0al. On the co-design of quantum software and hardware. In: Proc. Eight Annual ACM International Conference on Nanoscale Computing and Communication, 1\u20137 (2021).","DOI":"10.1145\/3477206.3477464"},{"key":"70649_CR9","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1137\/S0036144598347011","volume":"41","author":"PW Shor","year":"1999","unstructured":"Shor, P. W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev. 41, 303\u2013332 (1999).","journal-title":"SIAM Rev."},{"key":"70649_CR10","doi-asserted-by":"crossref","unstructured":"Feynman, R.\u00a0P. Simulating physics with computers. Int. J. Theor. Phys.21 (1982).","DOI":"10.1007\/BF02650179"},{"key":"70649_CR11","unstructured":"Yarkoni, S., Raponi, E. & B\u00e4ck, T. & Schmitt, S. Introduction and review. Reports on Progress in Physics, Quantum annealing for industry applications. (2022)."},{"key":"70649_CR12","doi-asserted-by":"publisher","first-page":"012403","DOI":"10.1103\/PhysRevA.104.012403","volume":"104","author":"M Streif","year":"2021","unstructured":"Streif, M., Yarkoni, S., Skolik, A., Neukart, F. & Leib, M. Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm. Phys. Rev. A 104, 012403. https:\/\/doi.org\/10.1103\/PhysRevA.104.012403 (2021).","journal-title":"Phys. Rev. A"},{"key":"70649_CR13","doi-asserted-by":"publisher","unstructured":"Yarkoni, S. et\u00a0al. Multi-car paint shop optimization with quantum annealing. In 2021 IEEE International Conference on Quantum Computing and Engineering (QCE), 35\u201341, https:\/\/doi.org\/10.1109\/QCE52317.2021.00019 (2021).","DOI":"10.1109\/QCE52317.2021.00019"},{"key":"70649_CR14","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1038\/s41567-020-01105-y","volume":"17","author":"MP Harrigan","year":"2021","unstructured":"Harrigan, M. P. et al. Quantum approximate optimization of non-planar graph problems on a planar superconducting processor. Nat. Phys. 17, 332\u2013336 (2021).","journal-title":"Nat. Phys."},{"key":"70649_CR15","doi-asserted-by":"publisher","first-page":"3241","DOI":"10.1088\/0305-4470\/15\/10\/028","volume":"15","author":"F Barahona","year":"1982","unstructured":"Barahona, F. On the computational complexity of ising spin glass models. J. Phys. A Math. Gen. 15, 3241 (1982).","journal-title":"J. Phys. A Math. Gen."},{"key":"70649_CR16","first-page":"85","volume-title":"Reducibility among Combinatorial Problems","author":"RM Karp","year":"1972","unstructured":"Karp, R. M. Reducibility among Combinatorial Problems 85\u2013103 (Springer, 1972)."},{"key":"70649_CR17","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/j.trb.2020.10.003","volume":"142","author":"J Ke","year":"2020","unstructured":"Ke, J., Yang, H. & Zheng, Z. On ride-pooling and traffic congestion. Transp. Res. B Methodol. 142, 213\u2013231 (2020).","journal-title":"Transp. Res. B Methodol."},{"key":"70649_CR18","doi-asserted-by":"publisher","first-page":"13","DOI":"10.3389\/fict.2019.00013","volume":"6","author":"S Feld","year":"2019","unstructured":"Feld, S. et al. A hybrid solution method for the capacitated vehicle routing problem using a quantum annealer. Front. ICT 6, 13. https:\/\/doi.org\/10.3389\/fict.2019.00013 (2019).","journal-title":"Front. ICT"},{"key":"70649_CR19","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1007\/978-3-030-50433-5_42","volume-title":"Computational Science - ICCS 2020","author":"M Borowski","year":"2020","unstructured":"Borowski, M. et al. New hybrid quantum annealing algorithms for solving vehicle routing problem. In Computational Science - ICCS 2020 (eds Krzhizhanovskaya, V. V. et al.) 546\u2013561 (Springer International Publishing, 2020)."},{"key":"70649_CR20","doi-asserted-by":"publisher","first-page":"224","DOI":"10.3390\/a12110224","volume":"12","author":"C Papalitsas","year":"2019","unstructured":"Papalitsas, C., Andronikos, T., Giannakis, K., Theocharopoulou, G. & Fanarioti, S. A qubo model for the traveling salesman problem with time windows. Algorithms 12, 224. https:\/\/doi.org\/10.3390\/a12110224 (2019).","journal-title":"Algorithms"},{"key":"70649_CR21","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/978-3-030-14082-3_13","volume-title":"Quantum Technology and Optimization Problems: First International Workshop, QTOP 2019, Munich, Germany, March 18, 2019, Proceedings 1","author":"H Irie","year":"2019","unstructured":"Irie, H., Wongpaisarnsin, G., Terabe, M., Miki, A. & Taguchi, S. Quantum annealing of vehicle routing problem with time, state and capacity. In Quantum Technology and Optimization Problems: First International Workshop, QTOP 2019, Munich, Germany, March 18, 2019, Proceedings 1 (ed. Irie, H.) 145\u2013156 (Springer, 2019)."},{"key":"70649_CR22","volume-title":"Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem","author":"N Christofides","year":"1976","unstructured":"Christofides, N. Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem (Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group, 1976)."},{"key":"70649_CR23","first-page":"393","volume":"2","author":"G Dantzig","year":"1954","unstructured":"Dantzig, G., Fulkerson, R. & Johnson, S. Solution of a large-scale traveling-salesman problem. J. Oper. Res. Soc. Am. 2, 393\u2013410 (1954).","journal-title":"J. Oper. Res. Soc. Am."},{"key":"70649_CR24","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/s10479-017-2525-0","volume":"259","author":"Y Molenbruch","year":"2017","unstructured":"Molenbruch, Y., Braekers, K. & Caris, A. Typology and literature review for dial-a-ride problems. Ann. Oper. Res. 259, 295\u2013325 (2017).","journal-title":"Ann. Oper. Res."},{"key":"70649_CR25","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/j.trb.2018.02.001","volume":"111","author":"SC Ho","year":"2018","unstructured":"Ho, S. C. et al. A survey of dial-a-ride problems: Literature review and recent developments. Transp. Res. B Methodol. 111, 395\u2013421 (2018).","journal-title":"Transp. Res. B Methodol."}],"container-title":["Scientific Reports"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.nature.com\/articles\/s41598-024-70649-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.nature.com\/articles\/s41598-024-70649-3","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.nature.com\/articles\/s41598-024-70649-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,26]],"date-time":"2024-08-26T08:05:15Z","timestamp":1724659515000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.nature.com\/articles\/s41598-024-70649-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,26]]},"references-count":25,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2024,12]]}},"alternative-id":["70649"],"URL":"https:\/\/doi.org\/10.1038\/s41598-024-70649-3","relation":{},"ISSN":["2045-2322"],"issn-type":[{"value":"2045-2322","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,26]]},"assertion":[{"value":"19 February 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 August 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 August 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare no competing interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"19768"}}