{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,31]],"date-time":"2026-07-31T18:13:04Z","timestamp":1785521584445,"version":"3.56.0"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,1,22]],"date-time":"2022-01-22T00:00:00Z","timestamp":1642809600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,1,22]],"date-time":"2022-01-22T00:00:00Z","timestamp":1642809600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004382","name":"polska akademia nauk","doi-asserted-by":"publisher","award":["2019\/33\/B\/ST6\/02011"],"award-info":[{"award-number":["2019\/33\/B\/ST6\/02011"]}],"id":[{"id":"10.13039\/501100004382","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004382","name":"polska akademia nauk","doi-asserted-by":"publisher","award":["2020\/37\/N\/ST6\/02220"],"award-info":[{"award-number":["2020\/37\/N\/ST6\/02220"]}],"id":[{"id":"10.13039\/501100004382","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"published-print":{"date-parts":[[2022,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Quantum computing is offering a novel perspective for solving combinatorial optimization problems. To fully explore the possibilities offered by quantum computers, the problems need to be formulated as unconstrained binary models, taking into account limitation and advantages of quantum devices. In this work, we provide a detailed analysis of the travelling salesman problem with time windows (TSPTW) in the context of solving it on a quantum computer. We introduce quadratic unconstrained binary optimization and higher-order binary optimization formulations of this problem. We demonstrate the advantages of edge-based and node-based formulations of the TSPTW problem. Additionally, we investigate the experimental realization of the presented methods on a quantum annealing device. The provided results pave the path for utilizing quantum computer for a variety of real-world tasks which can be cast in the form of travelling salesman problem with time windows.<\/jats:p>","DOI":"10.1007\/s11128-021-03405-5","type":"journal-article","created":{"date-parts":[[2022,1,22]],"date-time":"2022-01-22T07:02:46Z","timestamp":1642834966000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":61,"title":["Unconstrained binary models of the travelling salesman problem variants for quantum optimization"],"prefix":"10.1007","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2033-2881","authenticated-orcid":false,"given":"\u00d6zlem","family":"Salehi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6320-7699","authenticated-orcid":false,"given":"Adam","family":"Glos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8790-101X","authenticated-orcid":false,"given":"Jaros\u0142aw Adam","family":"Miszczak","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,1,22]]},"reference":[{"key":"3405_CR1","unstructured":"Gutin, G., Punnen, A. (eds.): The Traveling Salesman Problem and its Variations. Combinatorial Optimization. Kluwer Academic Press (2002)"},{"key":"3405_CR2","unstructured":"Chvatal, V., Applegate, D.L., Bixby, R.E., Cook, W.J.: The Traveling Salesman Problem: A Computational Study. Princeton Series in Applied Mathematics, Princeton University Press (2011)"},{"key":"3405_CR3","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/S0927-0507(05)80106-9","volume":"8","author":"J Desrosiers","year":"1995","unstructured":"Desrosiers, J., Dumas, Y., Solomon, M.M., Soumis, F.: Time constrained routing and scheduling. Handbooks Oper. Res. Manage. Sci. 8, 35\u2013139 (1995)","journal-title":"Handbooks Oper. Res. Manage. Sci."},{"issue":"3","key":"3405_CR4","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/j.jksus.2010.03.002","volume":"22","author":"NA El-Sherbeny","year":"2010","unstructured":"El-Sherbeny, N.A.: Vehicle routing with time windows: an overview of exact, heuristic and metaheuristic methods. J. King Saud Univ. Sci. 22(3), 123\u2013131 (2010)","journal-title":"J. King Saud Univ. Sci."},{"issue":"1","key":"3405_CR5","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/BF02022044","volume":"4","author":"MW Savelsbergh","year":"1985","unstructured":"Savelsbergh, M.W.: Local search in routing problems with time windows. Ann. Oper. Res. 4(1), 285\u2013305 (1985)","journal-title":"Ann. Oper. Res."},{"key":"3405_CR6","doi-asserted-by":"publisher","first-page":"79","DOI":"10.22331\/q-2018-08-06-79","volume":"2","author":"J Preskill","year":"2018","unstructured":"Preskill, J.: Quantum computing in the NISQ era and beyond. Quantum 2, 79 (2018)","journal-title":"Quantum"},{"key":"3405_CR7","doi-asserted-by":"crossref","unstructured":"Peruzzo, A., McClean, J., Shadbolt, P., Yung, M.H., Zhou, X.Q., Love, P.J., Aspuru-Guzik, A., O\u2019brien, J.L.: A variational eigenvalue solver on a photonic quantum processor. Nat. Commun. 5(1), 1\u20137 (2014)","DOI":"10.1038\/ncomms5213"},{"key":"3405_CR8","unstructured":"Farhi, E., Goldstone, J., Gutmann, S.: A quantum approximate optimization algorithm (2014) arXiv preprint arXiv:1411.4028"},{"issue":"2","key":"3405_CR9","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0304-4149(89)90040-9","volume":"33","author":"B Apolloni","year":"1989","unstructured":"Apolloni, B., Carvalho, C., De Falco, D.: Quantum stochastic optimization. Stoch. Process. Appl. 33(2), 233\u2013244 (1989)","journal-title":"Stoch. Process. Appl."},{"issue":"5","key":"3405_CR10","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(5), 5355 (1998)","journal-title":"Phys. Rev. E"},{"key":"3405_CR11","unstructured":"Farhi, E., Goldstone, J., Gutmann, S., Sipser, M.: Quantum computation by adiabatic evolution (2000). arXiv preprint quant-ph\/0001106"},{"issue":"1","key":"3405_CR12","doi-asserted-by":"publisher","first-page":"012322","DOI":"10.1103\/PhysRevA.65.012322","volume":"65","author":"AM Childs","year":"2001","unstructured":"Childs, A.M., Farhi, E., Preskill, J.: Robustness of adiabatic quantum computation. Phys. Rev. A 65(1), 012322 (2001)","journal-title":"Phys. Rev. A"},{"key":"3405_CR13","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/j.tcs.2020.01.024","volume":"816","author":"CC McGeoch","year":"2020","unstructured":"McGeoch, C.C.: Theory versus practice in annealing-based quantum computing. Theoret. Comput. Sci. 816, 169\u2013183 (2020)","journal-title":"Theoret. Comput. Sci."},{"issue":"5","key":"3405_CR14","doi-asserted-by":"publisher","first-page":"054401","DOI":"10.1088\/1361-6633\/ab85b8","volume":"83","author":"P Hauke","year":"2020","unstructured":"Hauke, P., Katzgraber, H.G., Lechner, W., Nishimori, H., Oliver, W.D.: Perspectives of quantum annealing: Methods and implementations. Rep. Prog. Phys. 83(5), 054401 (2020)","journal-title":"Rep. Prog. Phys."},{"issue":"6195","key":"3405_CR15","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1126\/science.1252319","volume":"345","author":"TF R\u00f8nnow","year":"2014","unstructured":"R\u00f8nnow, T.F., Wang, Z., Job, J., Boixo, S., Isakov, S.V., Wecker, D., Martinis, J.M., Lidar, D.A., Troyer, M.: Defining and detecting quantum speedup. Science 345(6195), 420\u2013424 (2014)","journal-title":"Science"},{"issue":"7346","key":"3405_CR16","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1038\/nature10012","volume":"473","author":"MW Johnson","year":"2011","unstructured":"Johnson, M.W., Amin, M.H., Gildert, S., Lanting, T., Hamze, F., Dickson, N., Harris, R., Berkley, A.J., Johansson, J., Bunyk, P., et al.: Quantum annealing with manufactured spins. Nature 473(7346), 194\u2013198 (2011)","journal-title":"Nature"},{"issue":"11","key":"3405_CR17","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(11), 224 (2019)","journal-title":"Algorithms"},{"issue":"10","key":"3405_CR18","doi-asserted-by":"publisher","first-page":"1309","DOI":"10.1080\/02331934.2013.824445","volume":"62","author":"I Kara","year":"2013","unstructured":"Kara, I., Koc, O.N., Alt\u0131parmak, F., Dengiz, B.: New integer linear programming formulation for the traveling salesman problem with time windows: minimizing tour duration with waiting times. Optimization 62(10), 1309\u20131319 (2013)","journal-title":"Optimization"},{"issue":"4598","key":"3405_CR19","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671\u2013680 (1983)","journal-title":"Science"},{"issue":"2","key":"3405_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2200\/S00585ED1V01Y201407QMC008","volume":"5","author":"CC McGeoch","year":"2014","unstructured":"McGeoch, C.C.: Adiabatic quantum computation and quantum annealing: theory and practice. Synth. Lect. Quantum Comput. 5(2), 1\u201393 (2014)","journal-title":"Synth. Lect. Quantum Comput."},{"key":"3405_CR21","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":"3405_CR22","doi-asserted-by":"crossref","unstructured":"Perdomo-Ortiz, A., Feldman, A., Ozaeta, A., Isakov, S.V., Zhu, Z., O\u2019Gorman, B., Katzgraber, H.G., Diedrich, A., Neven, H., de Kleer, J., et al.: Readiness of quantum optimization machines for industrial applications. Phys. Rev. Appl. 12(1), 014004 (2019)","DOI":"10.1103\/PhysRevApplied.12.014004"},{"issue":"5","key":"3405_CR23","doi-asserted-by":"publisher","first-page":"938","DOI":"10.1287\/opre.31.5.938","volume":"31","author":"EK Baker","year":"1983","unstructured":"Baker, E.K.: An exact algorithm for the time-constrained travelling salesman problem. Oper. Res. 31(5), 938\u2013945 (1983)","journal-title":"Oper. Res."},{"issue":"7","key":"3405_CR24","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1002\/net.3230230706","volume":"23","author":"A Langevin","year":"1993","unstructured":"Langevin, A., Desrochers, M., Desrosiers, J., G\u00e9linas, S., Soumis, F.: A two-commodity flow formulation for the traveling salesman and the makespan problems with time windows. Networks 23(7), 631\u2013640 (1993)","journal-title":"Networks"},{"issue":"3","key":"3405_CR25","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1287\/ijoc.1110.0456","volume":"24","author":"R Baldacci","year":"2012","unstructured":"Baldacci, R., Mingozzi, A., Roberti, R.: New state-space relaxations for solving the traveling salesman problem with time windows. INFORMS J. Comput. 24(3), 356\u2013371 (2012)","journal-title":"INFORMS J. Comput."},{"issue":"2","key":"3405_CR26","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1002\/net.3230110207","volume":"11","author":"N Christofides","year":"1981","unstructured":"Christofides, N., Mingozzi, A., Toth, P.: State-space relaxation procedures for the computation of bounds to routing problems. Networks 11(2), 145\u2013164 (1981)","journal-title":"Networks"},{"issue":"2","key":"3405_CR27","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1287\/opre.43.2.367","volume":"43","author":"Y Dumas","year":"1995","unstructured":"Dumas, Y., Desrosiers, J., Gelinas, E., Solomon, M.M.: An optimal algorithm for the travelling salesman problem with time windows. Oper. Res. 43(2), 367\u2013371 (1995)","journal-title":"Oper. Res."},{"issue":"1","key":"3405_CR28","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1287\/trsc.32.1.12","volume":"32","author":"G Pesant","year":"1998","unstructured":"Pesant, G., Gendreau, M., Potvin, J.-Y., Rousseau, J.-M.: An exact constraint logic programming algorithm for the traveling salesman problem with time windows. Transp. Sci. 32(1), 12\u201329 (1998)","journal-title":"Transp. Sci."},{"issue":"4","key":"3405_CR29","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1287\/ijoc.14.4.403.2827","volume":"14","author":"F Focacci","year":"2002","unstructured":"Focacci, F., Lodi, A., Milano, M.: A hybrid exact algorithm for the TSPTW. INFORMS J. Comput. 14(4), 403\u2013417 (2002)","journal-title":"INFORMS J. Comput."},{"key":"3405_CR30","unstructured":"Cappart, Q., Moisan, T., Rousseau, L.-M., Pr\u00e9mont-Schwarz, I., Cire, A.: Combining reinforcement learning and constraint programming for combinatorial optimization (2020). arXiv preprint arXiv:2006.01610"},{"key":"3405_CR31","doi-asserted-by":"crossref","unstructured":"Hadfield, S., Wang, Z., Rieffel, E.G., O\u2019Gorman, B., Venturelli, D., Biswas, R.: Quantum approximate optimization with hard and soft constraints. In: Proceedings of the Second International Workshop on Post Moores Era Supercomputing, pp.\u00a015\u201321 (2017)","DOI":"10.1145\/3149526.3149530"},{"key":"3405_CR32","doi-asserted-by":"crossref","unstructured":"Hadfield, S., Wang, Z., O\u2019Gorman, B., Rieffel, E.G., Venturelli, D., Biswas, R.: From the quantum approximate optimization algorithm to a quantum alternating operator ansatz. Algorithms 12(2), 34 (2019)","DOI":"10.3390\/a12020034"},{"key":"3405_CR33","unstructured":"Glos, A., Krawiec, A., Zimbor\u00e1s, Z.: Space-efficient binary optimization for variational computing (2020). arXiv preprint arXiv:2009.07309"},{"issue":"5","key":"3405_CR34","doi-asserted-by":"publisher","first-page":"057701","DOI":"10.1103\/PhysRevE.70.057701","volume":"70","author":"R Marto\u0148\u00e1k","year":"2004","unstructured":"Marto\u0148\u00e1k, R., Santoro, G.E., Tosatti, E.: Quantum annealing of the travelling-salesman problem. Phys. Rev. E 70(5), 057701 (2004)","journal-title":"Phys. Rev. E"},{"issue":"36","key":"3405_CR35","doi-asserted-by":"publisher","first-page":"R393","DOI":"10.1088\/0305-4470\/39\/36\/R01","volume":"39","author":"GE Santoro","year":"2006","unstructured":"Santoro, G.E., Tosatti, E.: Optimization using quantum mechanics: quantum annealing through adiabatic evolution. J. Phys. A: Math. Gen. 39(36), R393 (2006)","journal-title":"J. Phys. A: Math. Gen."},{"key":"3405_CR36","doi-asserted-by":"crossref","unstructured":"Borowski, M., Gora, P., Karnas, K., B\u0142ajda, M., Kr\u00f3l, K., Matyjasek, A., Burczyk, D., Szewczyk, M., Kutwin, M.: New hybrid quantum annealing algorithms for solving vehicle routing problem. In: International Conference on Computational Science, pp.\u00a0546\u2013561. Springer (2020)","DOI":"10.1007\/978-3-030-50433-5_42"},{"key":"3405_CR37","doi-asserted-by":"crossref","unstructured":"Irie, H., Wongpaisarnsin, G., Terabe, M., Miki, A., Taguchi, S.: Quantum annealing of vehicle routing problem with time, state and capacity. In: International Workshop on Quantum Technology and Optimization Problems, pp.\u00a0145\u2013156. Springer (2019)","DOI":"10.1007\/978-3-030-14082-3_13"},{"key":"3405_CR38","unstructured":"Ascheuer, N.: Hamiltonian path problems in the on-line optimization of flexible manufacturing systems (1996)"},{"key":"3405_CR39","unstructured":"Boothby, K., Bunyk, P., Raymond, J., Roy, A.: Next-generation topology of D-Wave quantum processors (2020). arXiv preprint arXiv:2003.00133"},{"key":"3405_CR40","unstructured":"Rosenberg, I.G.: Reduction of bivalent maximization to the quadratic case (1975)"},{"key":"3405_CR41","doi-asserted-by":"crossref","unstructured":"Tabi, Z., El-Safty, K.H., Kallus, Z., H\u00e1ga, P., Kozsik, T., Glos, A., Zimbor\u00e1s, Z.: Quantum optimization for the graph coloring problem with space-efficient embedding. In: 2020 IEEE International Conference on Quantum Computing and Engineering (QCE), pp.\u00a056\u201362. IEEE (2020)","DOI":"10.1109\/QCE49297.2020.00018"},{"key":"3405_CR42","doi-asserted-by":"crossref","unstructured":"Anschuetz, E., Olson, J., Aspuru-Guzik, A., Cao, Y.: Variational quantum factoring. In: International Workshop on Quantum Technology and Optimization Problems, pp.\u00a074\u201385. Springer (2019)","DOI":"10.1007\/978-3-030-14082-3_7"},{"issue":"1","key":"3405_CR43","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/s10878-014-9734-0","volume":"28","author":"G Kochenberger","year":"2014","unstructured":"Kochenberger, G., Hao, J.-K., Glover, F., Lewis, M., L\u00fc, Z., Wang, H., Wang, Y.: The unconstrained binary quadratic programming problem: a survey. J. Comb. Optim. 28(1), 58\u201381 (2014)","journal-title":"J. Comb. Optim."},{"key":"3405_CR44","unstructured":"Dattani, N.: Quadratization in discrete optimization and quantum mechanics (2019). arXiv preprint arXiv:1901.04405"},{"key":"3405_CR45","doi-asserted-by":"crossref","unstructured":"Mandal, A., Roy, A., Upadhyay, S., Ushijima-Mwesigwa, H.: Compressed quadratization of higher order binary optimization problems. In: Proceedings of the 17th ACM International Conference on Computing Frontiers, pp.\u00a0126\u2013131 (2020)","DOI":"10.1145\/3387902.3392627"},{"issue":"5","key":"3405_CR46","first-page":"8","volume":"53","author":"S Tsukamoto","year":"2017","unstructured":"Tsukamoto, S., Takatsu, M., Matsubara, S., Tamura, H.: An accelerator architecture for combinatorial optimization problems. Fujitsu Sci. Tech. J 53(5), 8\u201313 (2017)","journal-title":"Fujitsu Sci. Tech. J"}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-021-03405-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11128-021-03405-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-021-03405-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,16]],"date-time":"2022-02-16T09:40:14Z","timestamp":1645004414000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11128-021-03405-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,22]]},"references-count":46,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["3405"],"URL":"https:\/\/doi.org\/10.1007\/s11128-021-03405-5","relation":{},"ISSN":["1570-0755","1573-1332"],"issn-type":[{"value":"1570-0755","type":"print"},{"value":"1573-1332","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,22]]},"assertion":[{"value":"28 June 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 December 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"67"}}