VAGPO: Vision-augmented Asymmetric Group Preference Optimization for the Routing Problems

Zhiguang Cao, Shiyan Liu, Bohan Tan, Yan JinarXiv 2025 · DOI · arXiv

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.

The VAGPO architecture combines visual and sequential encoding with preference optimization.

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.

Training performance comparison showing VAGPO's superior convergence speed and solution quality.

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

Abstract

Graph routing problems play a vital role in web-related networks, where finding optimal paths across graphs is essential for efficient data transmission and content delivery. Classic routing formulations such as the Traveling Salesman Problem (TSP) and the Capacitated Vehicle Routing Problem (CVRP) represent fundamental graph optimization challenges. Recent data-driven optimization methods have made significant progress, yet they often face limitations in training efficiency and generalization to large-scale instances. In this paper, we propose a novel Vision-augmented Asymmetric Group Preference Optimization (VAGPO) approach. By leveraging ResNet-based visual encoding and Transformer-based sequential modeling, VAGPO captures both spatial structure and temporal dependencies. Furthermore, we introduce an asymmetric group preference optimization strategy that significantly accelerates convergence compared to commonly used policy gradient methods. Experimental results on generated TSP and CVRP instances, as well as real-world datasets, demonstrate that the proposed VAGPO approach achieves highly competitive solution quality. Additionally, VAGPO exhibits strong generalization to larger instances (up to 1000 nodes) without re-training, highlighting its effectiveness in both learning efficiency and scalability.
BibTeX
@misc{cao2025vagpo,
  author = {Zhiguang Cao and Shiyan Liu and Bohan Tan and Yan Jin},
  title = {{VAGPO: Vision-augmented Asymmetric Group Preference Optimization for the Routing Problems}},
  year = {2025},
  eprint = {2508.01774},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2508.01774},
}
Figure