Solving the capacitated vehicle routing problem with time windows via graph convolutional network assisted tree search and quantum-inspired computing

被引:5
作者
Dornemann, Jorin [1 ]
机构
[1] Hamburg Univ Technol, Inst Math, Hamburg, Germany
关键词
deep learning; graph convolutional network; beam search; vehicle routing; time windows; quadratic unconstrained binary optimization; ALGORITHM; INEQUALITIES; BRANCH;
D O I
10.3389/fams.2023.1155356
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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.
引用
收藏
页数:17
相关论文
共 58 条
[1]  
Akeb H, 2013, FED CONF COMPUT SCI, P329
[2]  
[Anonymous], GUROBI OPTIMIZER REF, P2021
[3]   Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints [J].
Baldacci, Roberto ;
Mingozzi, Aristide ;
Roberti, Roberto .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2012, 218 (01) :1-6
[4]   New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem [J].
Baldacci, Roberto ;
Mingozzi, Aristide ;
Roberti, Roberto .
OPERATIONS RESEARCH, 2011, 59 (05) :1269-1283
[5]  
Bello I., 2017, NEURAL COMBINATORIAL, DOI DOI 10.48550/ARXIV.1611.09940
[6]   Machine learning for combinatorial optimization: A methodological tour d'horizon [J].
Bengio, Yoshua ;
Lodi, Andrea ;
Prouvost, Antoine .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2021, 290 (02) :405-421
[7]   Accelerated label setting algorithms for the elementary resource constrained shortest path problem [J].
Boland, N ;
Dethridge, J ;
Dumitrescu, I .
OPERATIONS RESEARCH LETTERS, 2006, 34 (01) :58-68
[8]  
Bresson X, 2018, Arxiv, DOI arXiv:1711.07553
[9]  
Chen XY, 2019, ADV NEUR IN, V32
[10]  
Delarue A, 2020, ADV NEUR IN, V33