{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T06:21:38Z","timestamp":1782973298370,"version":"3.54.5"},"reference-count":49,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2026,6,29]],"date-time":"2026-06-29T00:00:00Z","timestamp":1782691200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004775","name":"Natural Science Foundation of Gansu Province","doi-asserted-by":"crossref","award":["26JRRA480"],"award-info":[{"award-number":["26JRRA480"]}],"id":[{"id":"10.13039\/501100004775","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100004775","name":"Natural Science Foundation of Gansu Province","doi-asserted-by":"crossref","award":["26JRRA478"],"award-info":[{"award-number":["26JRRA478"]}],"id":[{"id":"10.13039\/501100004775","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Capacitated vehicle routing with time windows (CVRPTW) is a natural target for coherent Ising machines (CIMs), but a direct multi-vehicle arc encoding scales as O(mN2) and exceeds the variable budget of current CIM-compatible systems. We argue the bottleneck is encoding density, not expressiveness, and present LSQ, a hardware-aware sparse Quadratic Unconstrained Binary Optimization (QUBO) framework that decouples CVRPTW into a compact customer-to-route assignment QUBO and a classical intra-route ordering step under a soft no-wait service convention. LKH candidate edges compress the per-route edge space from O(N2) to O(KN), and a per-route dynamic-penalty subroutine encodes time-window sensitivities as binary variables in a round-wise outer loop. On a six-vehicle, 51-node reference instance curated from long-term operational data, LSQ shrinks the maximum single-submission QUBO from 15,300 arc variables to 342 logicalQUBOvariables (\u223c45\u00d7 compression), cuts travel time by 22.9% (74 vs. 96), and cuts route duration by 11.2% (174 vs. 196) against an OR-Tools soft-window baseline at the same fleet size. OR-Tools retains an advantage on raw time-window penalty (1600 vs. 3540) and runtime; under the scalar operational cost \u2211kT(\u03c0k)+\u2211i\u2113i(\u03c4i), OR-Tools is therefore the better single-objective solver, and the comparison is a multi-objective trade-off rather than a scalar dominance claim. Ablations confirm that the LKH prior recovers Held\u2013Karp on a 15-customer TSP at 53 vs. 120 variables and that the dynamic-penalty encoding reduces compressed time-window loss by 15.25% at constant travel. All hardware claims refer to QUBO sizing on a Kaiwu\/CIM-compatible backend, not physical CIM execution.<\/jats:p>","DOI":"10.3390\/a19070525","type":"journal-article","created":{"date-parts":[[2026,6,30]],"date-time":"2026-06-30T00:55:11Z","timestamp":1782780911000},"page":"525","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Hardware-Aware Sparse QUBO Encoding for CVRPTW on Coherent Ising Machines: An LKH-Guided Variable-Compression Framework"],"prefix":"10.3390","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-5453-1787","authenticated-orcid":false,"given":"Zhitao","family":"Wu","sequence":"first","affiliation":[{"name":"School of Electronics and Information Engineering, Wuyi University, Jiangmen 529020, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-5732-5699","authenticated-orcid":false,"given":"Zonglin","family":"Yang","sequence":"additional","affiliation":[{"name":"School of Criminal Technology, Guangdong Police College, Guangzhou 510440, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jie","family":"Zhou","sequence":"additional","affiliation":[{"name":"School of Criminal Technology, Guangdong Police College, Guangzhou 510440, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xuechen","family":"Li","sequence":"additional","affiliation":[{"name":"School of Electronics and Information Engineering, Wuyi University, Jiangmen 529020, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hongmin","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Emergency Technology and Management, Wuyi University, Jiangmen 529020, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2026,6,29]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1287\/mnsc.6.1.80","article-title":"The truck dispatching problem","volume":"6","author":"Dantzig","year":"1959","journal-title":"Manag. Sci."},{"key":"ref_2","first-page":"393","article-title":"Solution of a large-scale traveling-salesman problem","volume":"2","author":"Dantzig","year":"1954","journal-title":"J. Oper. Res. Soc. Am."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1016\/0377-2217(92)90192-C","article-title":"The vehicle routing problem: An overview of exact and approximate algorithms","volume":"59","author":"Laporte","year":"1992","journal-title":"Eur. J. Oper. Res."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Toth, P., and Vigo, D. (2014). Vehicle Routing: Problems, Methods, and Applications, SIAM.","DOI":"10.1137\/1.9781611973594"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1137\/0110015","article-title":"A dynamic programming approach to sequencing problems","volume":"10","author":"Held","year":"1962","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Karp, R.M. (2009). Reducibility among combinatorial problems. 50 Years of Integer Programming 1958\u20132008: From the Early Years to the State-of-the-Art, Springer.","DOI":"10.1007\/978-3-540-68279-0_8"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1007\/s43069-021-00101-z","article-title":"Worst-case analysis of a new heuristic for the travelling salesman problem","volume":"3","author":"Christofides","year":"2022","journal-title":"Oper. Res. Forum"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1287\/opre.21.2.498","article-title":"An effective heuristic algorithm for the traveling-salesman problem","volume":"21","author":"Lin","year":"1973","journal-title":"Oper. Res."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1016\/S0377-2217(99)00284-2","article-title":"An effective implementation of the Lin\u2013Kernighan traveling salesman heuristic","volume":"126","author":"Helsgaun","year":"2000","journal-title":"Eur. J. Oper. Res."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1016\/j.compeleceng.2018.02.049","article-title":"An adaptive large neighborhood search heuristic for dynamic vehicle routing problems","volume":"67","author":"Chen","year":"2018","journal-title":"Comput. Electr. Eng."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"2403","DOI":"10.1016\/j.cor.2005.09.012","article-title":"A general heuristic for vehicle routing problems","volume":"34","author":"Pisinger","year":"2007","journal-title":"Comput. Oper. Res."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"5355","DOI":"10.1103\/PhysRevE.58.5355","article-title":"Quantum annealing in the transverse Ising model","volume":"58","author":"Kadowaki","year":"1998","journal-title":"Phys. Rev. E"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1038\/nature10012","article-title":"Quantum annealing with manufactured spins","volume":"473","author":"Johnson","year":"2011","journal-title":"Nature"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Lucas, A. (2014). Ising formulations of many NP problems. Front. Phys., 2.","DOI":"10.3389\/fphy.2014.00005"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1007\/s10878-014-9734-0","article-title":"The unconstrained binary quadratic programming problem: A survey","volume":"28","author":"Kochenberger","year":"2014","journal-title":"J. Comb. Optim."},{"key":"ref_16","unstructured":"Glover, F., Kochenberger, G., and Du, Y. (2018). A tutorial on formulating and using QUBO models. arXiv."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1287\/opre.40.2.342","article-title":"A new optimization algorithm for the vehicle routing problem with time windows","volume":"40","author":"Desrochers","year":"1992","journal-title":"Oper. Res."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1287\/opre.12.4.568","article-title":"Scheduling of vehicles from a central depot to a number of delivery points","volume":"12","author":"Clarke","year":"1964","journal-title":"Oper. Res."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1287\/trsc.31.2.170","article-title":"A tabu search heuristic for the vehicle routing problem with soft time windows","volume":"31","author":"Taillard","year":"1997","journal-title":"Transp. Sci."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1016\/j.cor.2012.07.018","article-title":"A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows","volume":"40","author":"Vidal","year":"2013","journal-title":"Comput. Oper. Res."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1287\/opre.35.2.254","article-title":"Algorithms for the vehicle routing and scheduling problems with time window constraints","volume":"35","author":"Solomon","year":"1987","journal-title":"Oper. Res."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1287\/trsc.1030.0057","article-title":"Vehicle routing problem with time windows, Part II: Metaheuristics","volume":"39","author":"Gendreau","year":"2005","journal-title":"Transp. Sci."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1287\/trsc.1030.0056","article-title":"Vehicle routing problem with time windows, Part I: Route construction and local search algorithms","volume":"39","author":"Gendreau","year":"2005","journal-title":"Transp. Sci."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Ayodele, M. (2022). Penalty weights in QUBO formulations: Permutation problems. Proceedings of the European Conference on Evolutionary Computation in Combinatorial Optimization (Part of EvoStar), Springer.","DOI":"10.1007\/978-3-031-04148-8_11"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Irie, H., Wongpaisarnsin, G., Terabe, M., Miki, A., and Taguchi, S. (2019). Quantum annealing of vehicle routing problem with time, state and capacity. Proceedings of the International Workshop on Quantum Technology and Optimization Problems, Springer.","DOI":"10.1007\/978-3-030-14082-3_13"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"19768","DOI":"10.1038\/s41598-024-70649-3","article-title":"Modeling routing problems in QUBO with application to ride-hailing","volume":"14","author":"Cattelan","year":"2024","journal-title":"Sci. Rep."},{"key":"ref_27","unstructured":"Zorn, M., Braun, M., Ertl, M., Kiss, T., Oropeza, S.J., Linnhoff-Popien, C., and Stein, J. (2026). Quantum Optimization Methods for the Generalized Traveling Salesman Problem. arXiv."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Papalitsas, C., Andronikos, T., Giannakis, K., Theocharopoulou, G., and Fanarioti, S. (2019). A QUBO model for the traveling salesman problem with time windows. Algorithms, 12.","DOI":"10.20944\/preprints201909.0154.v1"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Dornemann, J. (2023). Solving the capacitated vehicle routing problem with time windows via graph-based quantum and quantum-inspired methods. Front. Appl. Math. Stat., 9.","DOI":"10.3389\/fams.2023.1155356"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Dornemann, J., Shaglel, S., Kliesch, M., and Taraz, A. (2025, January 15\u201319). A hybrid quantum-inspired and deep-learning workflow for capacitated vehicle routing with time windows. Proceedings of the Learning and Intelligent Optimization Conference (LION), Prague, Czech Republic.","DOI":"10.1007\/978-3-032-09192-5_8"},{"key":"ref_31","unstructured":"Upadhyay, M., and Jones, M.N. (2025). Comparative studies of quantum annealing, digital annealing, and classical solvers for reaction network pathway analysis and mrna codon selection. arXiv."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"937","DOI":"10.1038\/nphoton.2014.249","article-title":"Network of time-multiplexed optical parametric oscillators as a coherent Ising machine","volume":"8","author":"Marandi","year":"2014","journal-title":"Nat. Photonics"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"603","DOI":"10.1126\/science.aah4243","article-title":"A coherent Ising machine for 2000-node optimization problems","volume":"354","author":"Inagaki","year":"2016","journal-title":"Science"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"614","DOI":"10.1126\/science.aah5178","article-title":"A fully programmable 100-spin coherent Ising machine with all-to-all connections","volume":"354","author":"McMahon","year":"2016","journal-title":"Science"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"eaau0823","DOI":"10.1126\/sciadv.aau0823","article-title":"Experimental investigation of performance differences between coherent Ising machines and a quantum annealer","volume":"5","author":"Hamerly","year":"2019","journal-title":"Sci. Adv."},{"key":"ref_36","unstructured":"Applegate, D.L., Bixby, R.E., Chv\u00e1tal, V., and Cook, W.J. (2011). The traveling salesman problem: A computational study. The Traveling Salesman Problem, Princeton University Press."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Rosenberg, G., Haghnegahdar, P., Goddard, P., Carr, P., Wu, K., and De Prado, M.L. (2015, January 15). Solving the optimal trading trajectory problem using a quantum annealer. Proceedings of the 8th Workshop on High Performance Computational Finance, Austin, TX, USA.","DOI":"10.1145\/2830556.2830563"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Stollenwerk, T., Lobe, E., and Jung, M. (2019). Flight gate assignment with a quantum annealer. Proceedings of the International Workshop on Quantum Technology and Optimization Problems, Springer.","DOI":"10.1007\/978-3-030-14082-3_9"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Neukart, F., Compostella, G., Seidel, C., Von Dollen, D., Yarkoni, S., and Parney, B. (2017). Traffic flow optimization using a quantum annealer. Front. ICT, 4.","DOI":"10.3389\/fict.2017.00029"},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Feld, S., Roch, C., Gabor, T., Seidel, C., Neukart, F., Galter, I., Mauerer, W., and Linnhoff-Popien, C. (2019). A hybrid solution method for the capacitated vehicle routing problem using a quantum annealer. Front. ICT, 6.","DOI":"10.3389\/fict.2019.00013"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/s42484-026-00375-8","article-title":"An advanced hybrid quantum tabu search approach to vehicle routing problems","volume":"8","author":"Holliday","year":"2026","journal-title":"Quantum Mach. Intell."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"2149","DOI":"10.1109\/QCE65121.2025.00235","article-title":"QUEST: QUantum-Enhanced Shared Transportation","volume":"Volume 1","author":"Onah","year":"2025","journal-title":"Proceedings of the 2025 IEEE International Conference on Quantum Computing and Engineering (QCE)"},{"key":"ref_43","unstructured":"Perron, L., and Furnon, V. (2026, June 20). Google OR-Tools: Software Suite for Combinatorial Optimization. Available online: https:\/\/developers.google.com\/optimization\/."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Omar, A., Omar, Y., Solayman, M., and Mansour, H. (2025). Comparative Analysis of Ant Colony Optimization and Google OR-Tools for Solving the Open Capacitated Vehicle Routing Problem in Logistics. Proceedings of the 2025 Intelligent Methods, Systems, and Applications (IMSA), IEEE.","DOI":"10.1109\/IMSA65733.2025.11167077"},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"Wouda, N.A., Lan, L., and Kool, W. (2024). PyVRP: A high-performance VRP solver package. arXiv.","DOI":"10.1287\/ijoc.2023.0055"},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/s11128-008-0082-9","article-title":"Minor-embedding in adiabatic quantum computation: I. The parameter setting problem","volume":"7","author":"Choi","year":"2008","journal-title":"Quantum Inf. Process."},{"key":"ref_47","unstructured":"Farhi, E., Goldstone, J., and Gutmann, S. (2014). A quantum approximate optimization algorithm. arXiv."},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Hadfield, S., Wang, Z., O\u2019gorman, B., Rieffel, E.G., Venturelli, D., and Biswas, R. (2019). From the quantum approximate optimization algorithm to a quantum alternating operator ansatz. Algorithms, 12.","DOI":"10.3390\/a12020034"},{"key":"ref_49","first-page":"1","article-title":"SVRPBench: A Realistic Benchmark for Stochastic Vehicle Routing Problem","volume":"38","author":"Heakl","year":"2026","journal-title":"Adv. Neural Inf. Process. Syst."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/19\/7\/525\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T04:59:25Z","timestamp":1782968365000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/19\/7\/525"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,29]]},"references-count":49,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2026,7]]}},"alternative-id":["a19070525"],"URL":"https:\/\/doi.org\/10.3390\/a19070525","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,29]]}}}