Introduction
Combinatorial optimization problems, specifically graph routing tasks like the Traveling Salesman Problem (TSP) and the Capacitated Vehicle Routing Problem (CVRP), are cornerstones of logistics and network design. While exact solvers like Concorde guarantee optimality, their exponential time complexity makes them impractical for real-time applications. Deep learning has emerged as a promising alternative, typically framing routing as a sequence generation task. However, standard sequential models often fail to capture the global geometric structure of 2D graphs and suffer from high-variance reinforcement learning (RL) training.
VAGPO (Vision-augmented Asymmetric Group Preference Optimization) addresses these challenges by introducing a hybrid architecture that treats graph instances as both sequences and images. By combining visual spatial awareness with a novel preference-based learning strategy, VAGPO achieves state-of-the-art solution quality with significantly improved training efficiency and generalization.
Methodology: Bridging Vision and Sequence
The core innovation of VAGPO lies in its dual-modal representation and its specialized optimization objective.
1. Vision-augmented Representation
Unlike traditional methods that rely solely on node coordinates as sequences, VAGPO converts graph instances into 224x224 grayscale images. In these images, pixel intensities represent node locations and, in the case of CVRP, customer demands. A frozen, pre-trained ResNet-18 serves as a visual encoder, extracting rich spatial features that capture intrinsic geometric regularities like clusters and density patterns.
2. Cross-modal Feature Fusion
To integrate these visual insights with sequential data, VAGPO employs a Transformer-based encoder. A Multi-Head Attention (MHA) mechanism fuses the visual features from the ResNet with the sequential embeddings. This allows the decoder to "look" at the global spatial layout while sequentially determining the next node in the route.
3. Asymmetric Group Preference Optimization (AGPO)
Standard RL methods like REINFORCE often struggle with high variance in routing problems. VAGPO introduces AGPO, a preference-based approach. Instead of a scalar reward, AGPO compares groups of trajectories. It generates multiple solutions starting from different nodes, categorizing them into "preferred" (top-k) and "non-preferred" (bottom-k) sets. The model is then optimized to maximize the likelihood of the preferred group. By using asymmetric weights ($\beta_w > \beta_l$), the algorithm prioritizes learning from high-quality solutions, leading to more stable and faster convergence.
Experimental Results
VAGPO was evaluated on synthetic datasets (TSP and CVRP up to 1000 nodes) and real-world benchmarks like TSPLIB.
Superior Accuracy and Efficiency
VAGPO sets a new benchmark for neural routing solvers. On TSP-100, it achieved an optimality gap of just 0.03% relative to Concorde, outperforming previous state-of-the-art models like POMO+PO (0.07%). Crucially, VAGPO demonstrates remarkable training efficiency, converging to competitive performance in approximately one-tenth the epochs required by baseline models.
Zero-Shot Scalability and Real-World Robustness
One of the most significant advantages of the vision-augmented approach is its generalization capability. A VAGPO model trained on 100-node instances can solve 500-node TSPs with a 13.09% gap, significantly better than the 17.76% gap of sequential-only baselines. This suggests that the visual encoder learns fundamental spatial principles that scale beyond the training distribution. Furthermore, tests on the TSPLIB benchmark confirmed that VAGPO's performance remains robust across diverse real-world node distributions.
Conclusion and Future Directions
VAGPO demonstrates that incorporating visual spatial awareness into graph routing models significantly enhances both solution quality and training stability. By leveraging pre-trained vision models and a group-based preference optimization strategy, it bridges the gap between traditional heuristics and modern deep learning.
Future work may explore higher-resolution visual encodings or more advanced architectures like Vision Transformers (ViTs) to further minimize information loss during image conversion. Additionally, extending this vision-augmented framework to non-Euclidean or higher-dimensional routing problems presents an exciting frontier for research.
Summary updated