Heterogeneous graph neural networks for scalable asymmetric traveling salesman problem optimization
Walid Guettala, Ákos Holló-Szabó, László Gulyás, János Botzheim · Neurocomputing · 2026
The Asymmetric Traveling Salesman Problem (ATSP), a cornerstone of logistics optimization, is challenging due to its non-Euclidean, asymmetric cost structure and the scalability limits of current Graph Neural Networks (GNNs). We present a three-stage pipeline that combines a new Heterogeneous Line Graph , a relation-aware GNN, and regret-guided optimization. First, converts directed edges into nodes connected via four distinct adjacency types. This transformation preserves asymmetric relations and reduces density by 25% relative to the undirected . Second, Het-GAT processes to learn edge-level regret with relation fusion via summation, concatenation, or attention. When trained on ATSP50 without local search, Het-GAT-Concat attains a 91.88% regret correlation and 9.96% optimality gap. Third, the Batch-Selecting Regret-Guided Edge Builder Heuristic, followed by Regret-Guided Pre-Evaluating 3-Opt, constructs and refines tours in and time respectively. This pipeline reduces gaps by 29.0% and time by 27.2% versus Nearest Neighbor + 2-Opt + Relocation across problem sizes. Against Global and Local Optimization Policies (GLOP), Het-GAT-Concat achieves significantly lower gaps: 8.34% versus 27.96% (ATSP250) and 7.89% versus 38.96% (ATSP500), with runtimes of 0.75s versus 14.86s and 7.20s versus 17.06s, respectively. Het-GAT-Attn achieves an 8.50% gap at ATSP250 and 8.54% at ATSP500 with runtimes of 2.48s and 23.37s. Both variants are 86% faster than LKH-3, enabling real-time application, while reducing training time by 98% and training data by 75%. The approach effectively scales to 1000 nodes via subgraph inference.