An Ante-Hoc Explainable Graph Attention Network for Routing Optimization

With the recently developed deep learning methods, routing optimization problems have been significantly intensified. Although so effective, such models are inherently black boxes, and remain of little practical applicability. This paper discusses the Explainable Graph Neural Networks (XGNN) to solve routing optimization problems, proposing an ante-hoc explanation approach through an encoder-decoder based graph attention (GAT) mechanism to capture complex spatial relationships between nodes effectively. Through the explainable encoder, insights on how the routing problem is represented by the model are given. Attention patterns in the decoder then assess the impact of each condition on the front-stage route output. The proposed method describes the influences on each node selection in the generated path. The method was evaluated under the Traveling Salesman Problem (TSP); pertinently, the results showed that it provided critical insights into the decision-making process. We benchmark XGAT on 128 publicly available TSP instances (20, 50, and 100 cities). Out-of-the-box, it produces tours within 1.7% of the hybrid GnnGLS baseline on TSP-100 while remaining fully transparent. These insights would thus not only improve the understanding of the model’s behavior but also ease the development of stronger and perhaps more reliable TSP solvers