{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T19:41:23Z","timestamp":1784144483694,"version":"3.55.0"},"reference-count":58,"publisher":"Frontiers Media SA","license":[{"start":{"date-parts":[[2023,6,22]],"date-time":"2023-06-22T00:00:00Z","timestamp":1687392000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["frontiersin.org"],"crossmark-restriction":true},"short-container-title":["Front. Appl. Math. Stat."],"abstract":"<jats:p>Vehicle routing problems are a class of NP-hard combinatorial optimization problems which attract a lot of attention, as they have many practical applications. In recent years there have been new developments solving vehicle routing problems with the help of machine learning, since learning how to automatically solve optimization problems has the potential to provide a big leap in optimization technology. Prior work on solving vehicle routing problems using machine learning has mainly focused on auto-regressive models, which are connected to high computational costs when combined with classical exact search methods as the model has to be evaluated in every search step. This paper proposes a new method for approximately solving the capacitated vehicle routing problem with time windows (CVRPTW) via a supervised deep learning-based approach in a non-autoregressive manner. The model uses a deep neural network to assist finding solutions by providing a probability distribution which is used to guide a tree search, resulting in a machine learning assisted heuristic. The model is built upon a new neural network architecture, called graph convolutional network, which is particularly suited for deep learning tasks. Furthermore, a new formulation for the CVRPTW in form of a quadratic unconstrained binary optimization (QUBO) problem is presented and solved via quantum-inspired computing in cooperation with Fujitsu, where a learned problem reduction based upon the proposed neural network is applied to circumvent limitations concerning the usage of quantum computing for large problem instances. Computational results show that the proposed models perform very well on small and medium sized instances compared to state-of-the-art solution methods in terms of computational costs and solution quality, and outperform commercial solvers for large instances.<\/jats:p>","DOI":"10.3389\/fams.2023.1155356","type":"journal-article","created":{"date-parts":[[2023,6,23]],"date-time":"2023-06-23T17:53:01Z","timestamp":1687542781000},"update-policy":"https:\/\/doi.org\/10.3389\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Solving the capacitated vehicle routing problem with time windows via graph convolutional network assisted tree search and quantum-inspired computing"],"prefix":"10.3389","volume":"9","author":[{"given":"Jorin","family":"Dornemann","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1965","published-online":{"date-parts":[[2023,6,22]]},"reference":[{"key":"B1","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611973594","volume-title":"Vehicle Routing","author":"Toth","year":"2014"},{"key":"B2","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1287\/trsc.1070.0223","article-title":"Tabu search, partial elementarity, and generalized k-path inequalities for the vehicle routing problem with time windows","volume":"42","author":"Desaulniers","year":"2008","journal-title":"Transport Sci."},{"key":"B3","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1002\/net.20332","article-title":"A branch-and-price-based large neighborhood search algorithm for the vehicle routing problem with time windows","volume":"54","author":"Prescott-Gagnon","year":"2009","journal-title":"Networks."},{"key":"B4","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1007\/3-540-49481-2_30","article-title":"Using constraint programming and local search methods to solve vehicle routing problems","volume-title":"Principles and Practice of Constraint Programming \u2013 CP98","author":"Shaw","year":"1998"},{"key":"B5","first-page":"6281","article-title":"Learning to perform local rewriting for combinatorial optimization","volume-title":"Proceedings of the 33rd International Conference on Neural Information Processing Systems","author":"Chen","year":"2019"},{"key":"B6","article-title":"A learning-based iterative method for solving vehicle routing problems","author":"Lu","year":"2020","journal-title":"8th International Conference on Learning Representations, 2020"},{"key":"B7","first-page":"9861","article-title":"Reinforcement Learning for Solving the Vehicle Routing Problem","volume-title":"Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS'18","author":"Nazari","year":"2018"},{"key":"B8","article-title":"Attention, learn to solve routing problems! In: 7th International Conference on Learning Representations, 2019 (New Orleans, LA)","author":"Kool","year":"2019"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2006.09100","article-title":"Learning to solve vehicle routing problems with time windows through joint attention","author":"Falkner","year":"2020","journal-title":"arXiv preprint arXiv:2006.09100"},{"key":"B10","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1007\/BF02022044","article-title":"Local search in routing problems with time windows","volume":"4","author":"Savelsbergh","year":"1985","journal-title":"Ann Operat Res."},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1906.01227","article-title":"An efficient graph convolutional network technique for the travelling salesman problem","author":"Joshi","year":"2019","journal-title":"arXiv preprint arXiv:1906.01227"},{"key":"B12","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1007\/s00291-020-00604-x","article-title":"Generalization of machine learning for problem reduction: a case study on travelling salesman problems","volume":"43","author":"Sun","year":"2020","journal-title":"OR Spectrum."},{"key":"B13","unstructured":"2022"},{"key":"B14","volume-title":"An Extension of the Lin-Kernighan-Helsgaun TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems","author":"Helsgaun","year":"2017"},{"key":"B15","unstructured":"PerronL\n            FurnonV\n          Google OR-Tools2022"},{"key":"B16","first-page":"2692","article-title":"Pointer networks","volume-title":"Advances in Neural Information Processing Systems","author":"Vinyals","year":"2015"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1611.09940","article-title":"Neural combinatorial optimization with reinforcement learning","author":"Bello","year":"2016","journal-title":"arXiv preprint arXiv:1611.09940"},{"key":"B18","first-page":"318","article-title":"Learning internal representations by error propagation","volume-title":"Parallel Distributed Processing: Explorations in the Microstructure of Cognition, Volume 1: Foundations","author":"Rumelhart","year":"1986"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1910.07210","article-title":"On learning paradigms for the travelling salesman problem","author":"Joshi","year":"2019","journal-title":"arXiv preprint arXiv:1910.07210"},{"key":"B20","first-page":"21188","article-title":"POMO: policy optimization with multiple optima for reinforcement learning","author":"Kwon","year":"2020","journal-title":"Advances in Neural Information Processing Systems"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1803.09621","article-title":"Learning the multiple traveling salesmen problem with permutation invariant pooling networks","author":"Kaempfer","year":"2018","journal-title":"arXiv preprint arXiv:1803.09621"},{"key":"B22","first-page":"609","article-title":"Reinforcement learning with combinatorial actions: an application to vehicle routing","volume-title":"Proceedings of the 34th International Conference on Neural Information Processing Systems","author":"Delarue","year":"2020"},{"key":"B23","doi-asserted-by":"crossref","first-page":"636","DOI":"10.1007\/978-981-15-5577-0_51","article-title":"A deep reinforcement learning algorithm using dynamic attention model for vehicle routing problems","volume-title":"Artificial Intelligence Algorithms and Applications","author":"Peng","year":"2020"},{"key":"B24","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1016\/j.ejor.2020.07.063","article-title":"Machine learning for combinatorial optimization: A methodological tour d'horizon","volume":"290","author":"Bengio","year":"2021","journal-title":"Eur J Oper Res"},{"key":"B25","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/0004-3702(77)90026-1","article-title":"Speech understandingsystems: report of a steering committee","volume":"9","author":"Medress","year":"1977","journal-title":"Artif Intell."},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1706.07450","article-title":"Revised note on learning algorithms for quadratic assignment with graph neural networks","author":"Nowak","year":"2017","journal-title":"arXiv preprint arXiv:1706.07450"},{"key":"B27","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1109\/TNN.2008.2005605","article-title":"The graph neural network model","volume":"20","author":"Scarselli","year":"2009","journal-title":"IEEE Trans Neural Netw."},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1711.07553","article-title":"Residual gated graph ConvNets","author":"Bresson","year":"2017","journal-title":"arXiv preprint arXiv:1711.07553"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2205.00772","article-title":"Large neighborhood search based on neural construction heuristics","author":"Falkner","year":"2022","journal-title":"arXiv preprint arXiv:2205.00772"},{"key":"B30","article-title":"Hierarchical reinforcement learning for vehicle routing problems with time windows","author":"Wang","year":"2021","journal-title":"Proceedings of the Canadian Conference on Artificial Intelligence"},{"key":"B31","article-title":"Learn to design the heuristics for vehicle routing problem","author":"Gao","year":"2020","journal-title":"arXiv preprint arXiv:2002.08539"},{"key":"B32","article-title":"Graph attention networks","volume-title":"6th International Conference on Learning Representations, ICLR 2018","author":"Veli\u010dkovi\u0107","year":"2018"},{"key":"B33","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/j.eswa.2019.04.056","article-title":"A reinforcement learning-based multi-agent framework applied for solving routing and scheduling problems","volume":"131","author":"Silva","year":"2019","journal-title":"Expert Syst Appl."},{"key":"B34","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/0-387-25486-2_2","article-title":"Shortest path problems with resource constraints","volume-title":"Column Generation","author":"Irnich","year":"2005"},{"key":"B35","doi-asserted-by":"crossref","first-page":"977","DOI":"10.1287\/opre.42.5.977","article-title":"Note on the complexity of the shortest path models for column generation in VRPTW","volume":"42","author":"Dror","year":"1994","journal-title":"Operat Res."},{"key":"B36","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1287\/trsc.33.1.101","article-title":"2-path cuts for the vehicle routing problem with time windows","volume":"33","author":"Kohl","year":"1999","journal-title":"Transport Sci."},{"key":"B37","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1287\/opre.1070.0449","article-title":"Subset-row inequalities applied to the vehicle-routing problem with time windows","volume":"56","author":"Jepsen","year":"2008","journal-title":"Operat Res."},{"key":"B38","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1007\/978-3-319-07557-0_33","article-title":"Improved branch-cut-and-price for capacitated vehicle routing","volume-title":"Integer Programming and Combinatorial Optimization","author":"Pecin","year":"2014"},{"key":"B39","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1287\/ijoc.2016.0744","article-title":"New enhancements for the exact solution of the vehicle routing problem with time windows","volume":"29","author":"Pecin","year":"2017","journal-title":"INFORMS J Comput."},{"key":"B40","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1002\/net.20033","article-title":"An exact algorithm for the elementary shortest path problem with resource constraints: application to some vehicle routing problems","volume":"44","author":"Feillet","year":"2004","journal-title":"Networks."},{"key":"B41","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1016\/j.orl.2004.11.011","article-title":"Accelerated label setting algorithms for the elementary resource constrained shortest path problem","volume":"34","author":"Boland","year":"2006","journal-title":"Operat Res Lett."},{"key":"B42","doi-asserted-by":"publisher","first-page":"239","DOI":"10.3138\/infor.45.4.239","article-title":"New refinements for the solution of vehicle routing problems with branch and price","volume":"45","author":"Feillet","year":"2007","journal-title":"Inform Syst Operat Res."},{"key":"B43","doi-asserted-by":"publisher","first-page":"1269","DOI":"10.1287\/opre.1110.0975","article-title":"New route relaxation and pricing strategies for the vehicle routing problem","volume":"59","author":"Baldacci","year":"2011","journal-title":"Operat Res."},{"key":"B44","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2011.07.037","article-title":"Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints","volume":"218","author":"Baldacci","year":"2012","journal-title":"Eur J Operat Res."},{"key":"B45","doi-asserted-by":"publisher","first-page":"224","DOI":"10.3390\/a12110224","article-title":"A QUBO model for the traveling salesman problem with time windows","volume":"12","author":"Papalitsas","year":"2019","journal-title":"Algorithms."},{"key":"B46","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/s11128-021-03405-5","article-title":"Unconstrained binary models of the travelling salesman problem variants for quantum optimization","volume":"21","author":"Salehi","year":"2022","journal-title":"Quant Inform Process."},{"key":"B47","doi-asserted-by":"crossref","first-page":"2251","DOI":"10.1145\/3520304.3533988","article-title":"Enhancing a QUBO solver via data driven multi-start and its application to vehicle routing problem","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference Companion","author":"Suen","year":"2022"},{"key":"B48","first-page":"329","article-title":"A beam search based algorithm for the capacitated vehicle routing problem with time windows","volume-title":"Federated Conference on Computer Science and Information Systems 2013","author":"Akeb","year":"2013"},{"key":"B49","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1007\/978-3-031-08011-1_14","article-title":"Deep policy dynamic programming for vehicle routing problems","volume-title":"Integration of Constraint Programming, Artificial Intelligence, and Operations Research","author":"Kool","year":"2022"},{"key":"B50","first-page":"448","article-title":"Batch normalization: accelerating deep network training by reducing internal covariate shift","volume-title":"Proceedings of the 32nd International Conference on International Conference on Machine Learning","author":"Ioffe","year":"2015"},{"key":"B51","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1811.11538","article-title":"Quantum Bridge Analytics I: a tutorial on formulating and using QUBO models","author":"Glover","year":"2018","journal-title":"arXiv preprint arXiv:1811.11538"},{"key":"B52","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/0-387-25486-2_3","article-title":"Vehicle routing problem with time windows","volume-title":"Column Generation","author":"Kallehauge","year":"2005"},{"key":"B53","unstructured":"2022"},{"key":"B54","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/978-3-030-14082-3_2","article-title":"Embedding inequality constraints for quantum annealing optimization","volume-title":"Quantum Technology and Optimization Problems","author":"Vysko\u010dil","year":"2019"},{"key":"B55","first-page":"45","article-title":"Application of digital annealer for faster combinatorial optimization","volume":"55","author":"Sao","year":"2019","journal-title":"Fujitsu Sci Tech J."},{"key":"B56","article-title":"Automatic differentiation in PyTorch","volume-title":"NIPS-W","author":"Paszke","year":"2017"},{"key":"B57","doi-asserted-by":"publisher","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":"Operat Res."},{"key":"B58","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1412.6980","article-title":"Adam: a method for stochastic optimization","author":"Kingma","year":"2014","journal-title":"arXiv preprint arXiv:1412.6980v9"}],"container-title":["Frontiers in Applied Mathematics and Statistics"],"original-title":[],"link":[{"URL":"https:\/\/www.frontiersin.org\/articles\/10.3389\/fams.2023.1155356\/full","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,23]],"date-time":"2023-06-23T17:53:30Z","timestamp":1687542810000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.frontiersin.org\/articles\/10.3389\/fams.2023.1155356\/full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,22]]},"references-count":58,"alternative-id":["10.3389\/fams.2023.1155356"],"URL":"https:\/\/doi.org\/10.3389\/fams.2023.1155356","relation":{},"ISSN":["2297-4687"],"issn-type":[{"value":"2297-4687","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,22]]},"article-number":"1155356"}}