Dornemann, JorinJorinDornemannKlein, TobiasTobiasKlein2025-10-302025-10-302025-10-11AIRO Springer Series 15: 243-253 (2025)978-3-031-90095-2https://hdl.handle.net/11420/58385The 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.enGraph convolutional networkMonte Carlo tree searchVehicle routingNatural Sciences and Mathematics::510: MathematicsBook Part10.1007/978-3-031-90095-2_21Book Chapter