Vision-Assisted Foundation Model for Solving Multi-Task Vehicle Routing Problems

Technical Summary: Vision-Assisted Foundation Model for Solving Multi-Task Vehicle Routing Problems

Problem Definition
Multi-task Vehicle Routing Problems (VRPs) involve optimizing routing costs while satisfying diverse customer constraints, such as backhaul demands (B), open routes (O), duration limits (L), and time windows (TW). The combination of these constraints creates an exponential number of VRP variants (e.g., 16 variants from four constraints). Existing neural solvers typically rely on graph-based modalities, encoding constraints as node attributes. However, these approaches face limitations: they struggle to learn complex spatial relationships and constraint interactions as tasks become more intricate, and training separate models for each variant is computationally prohibitive. Furthermore, existing vision-based methods for combinatorial optimization have been limited to single-task scenarios (e.g., TSP) and often fail to encode crucial task-specific attributes like demands and time windows within the visual representation.

Methodology: Vision-Assisted Foundation Model (VaFM)
The authors propose VaFM, a foundation model that integrates vision and graph modalities to solve 16 different VRP variants simultaneously. The architecture consists of three primary components:

1. Multi-Task VRP Image Generation: To address the lack of constraint representation in existing VRP images, the authors design two input images per instance: a "demand image" and a "time window (TW) image."

   • Visual Encoding: Customer coordinates are mapped to pixel indices. Node color intensity represents continuous variables (demand magnitude or time window duration).
   • Constraint Representation: Discrete constraints are encoded via visual cues: Open Routes (O) are indicated by background color inversion; Duration Limits (L) are shown by changing node shapes (rectangles to plus signs); Backhaul demands (B) use distinct node colors (green for linehaul, blue for backhaul).
   • Input: The two images are concatenated and processed by a CNN-based vision encoder (ResNet-18).

2. Hybrid Cross-Attention Fusion Module: To overcome the fixed receptive field of standard patch embeddings and accommodate varying task requirements, VaFM employs a hybrid fusion mechanism.

   • Mechanism: Feature maps from the last two layers of the vision encoder are extracted. Patch embeddings are derived from these maps and aligned with graph node embeddings.
   • Adaptive Receptive Field: A cross-attention mechanism is used where node embeddings act as queries and flattened feature maps from the deepest layer act as keys and values. This allows the model to aggregate relevant global information (from deep layers) while retaining fine-grained local context (from shallow layers), effectively creating adaptive receptive fields for different constraints.

3. Constraint-Aware Auxiliary Task: To mitigate the issue of imbalanced pixel distribution (where constraints like O or L occupy more pixels than B or TW, potentially causing the model to overlook the latter), an auxiliary task is introduced.

   • Implementation: A classifier is attached to the vision encoder to predict the presence of each of the four constraints (O, L, B, TW).
   • Loss Function: Binary Cross-Entropy (BCE) loss is applied to this auxiliary task, ensuring the model learns balanced representations for all constraints regardless of their visual prominence.
   • Training Objective: The total loss is a weighted sum of the Reinforcement Learning (RL) loss for routing cost minimization and the auxiliary classification loss.

Key Contributions

• First Vision-Assisted Foundation Model for Multi-Task VRPs: The work introduces the first framework combining graph and vision modalities to handle multiple VRP variants simultaneously, moving beyond single-task vision solvers.
• Novel Visual Encoding and Fusion: The paper proposes specific image designs to encode diverse constraints and a hybrid cross-attention fusion module that enables adaptive receptive fields, addressing the limitations of fixed patch sizes in multi-task settings.
• Balanced Constraint Learning: The introduction of a constraint-aware auxiliary task with BCE loss effectively prevents the model from neglecting constraints with fewer visual pixels.

Experimental Results
The model was evaluated on 16 VRP variants with 50 and 100 customer nodes, comparing against State-of-the-Art (SOTA) methods including HGS-PyVRP, OR-Tools, and various neural solvers (MTPOMO, MVMoE, RF-MoE-L).

• Performance: VaFM (specifically the VaFM-MoE-L variant) achieved the best performance in 15 out of 16 cases for N=50 and 12 out of 16 for N=100.
• Complex Constraints: The performance gap between VaFM and graph-only baselines widened as the number of constraints increased. For instance, on tasks with 3 or 4 constraints, VaFM showed significant improvements in the optimality gap compared to the baseline RF-MoE-L.
• Generalization: While VaFM showed strong zero-shot generalization to larger scales (N=200) and unseen constraint combinations (mixed backhaul), it exhibited some instability on real-world datasets and specific time-window-heavy tasks, suggesting limitations in color-based discrimination at larger scales.
• Efficiency: VaFM requires slightly more inference time than graph-only baselines due to the vision branch but remains significantly faster than heuristic solvers like HGS-PyVRP.

Significance and Claims
The paper claims that VaFM demonstrates the potential of integrating vision modalities into graph-based neural solvers to enhance the representation of complex, multi-constraint optimization problems. The authors assert that their approach successfully captures patch-level semantics (spatial demand distributions and service time patterns) that are difficult for pure graph models to learn. The results suggest that vision-assisted models are particularly superior for VRP variants with complex, interacting constraints. However, the authors modestly acknowledge limitations, noting that the current visual encoding (relying on single-color intensity) may struggle with fine-grained discrimination in large-scale instances and that future work is needed to improve generalization on real-world datasets and unseen constraints, potentially through multi-modal large language models.