Graph convolutional neural network assisted Monte Carlo Tree Search for the Capacitated Vehicle Routing Problem with Time Windows

First published in
AIRO Springer Series  
Number in series
15
Start Page
243
End Page
253
Citation
AIRO Springer Series 15: 243-253 (2025)
Publisher DOI
10.1007/978-3-031-90095-2_21
Scopus ID
2-s2.0-105019303357
Publisher
Springer
ISBN
978-3-031-90095-2
The Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) is a well-known combinatorial optimization problem that extends the classical Vehicle Routing Problem to account for additional real-world constraints such as truck capacity and customer time windows. Recent studies have explored the use of deep graph convolutional networks (GCNs) to predict the arcs that are part of the optimal tour for the Travelling Salesman Problem and related routing problems. We propose a novel context complemented graph convolutional network (CCGCN) which is integrated into a Monte Carlo Tree Search (MCTS) to solve the CVRPTW sequentially. The deep convolutional part of the proposed neural network builds efficient CVRPTW graph representations, whereas the context part processes information of partially built tours to output probabilities on which vertex to add next to the tour, which are used during the expansion of the search tree. For simulating final solution values within the Monte Carlo search tree, we conducted experiments using two different heuristics: LKH3 and a beam search. By leveraging the probabilities provided by our CCGCN and employing a variation of Upper Confidence Bound applied to trees, we effectively manage the tradeoff between exploration and exploitation, thus reducing the optimality gap compared to solutions generated solely by LKH3. Evaluations of the proposed heuristic are performed on benchmark instances of the CVRPTW with up to 100 customers; these show promising results.
Subjects
Graph convolutional network
Monte Carlo tree search
Vehicle routing
DDC Class
510: Mathematics