acceptodds
Under review as a conference paper at ICLR 2027

CARD: Coupled Asymmetric Role-and-Distance in Real-World Vehicle Routing

Abstract

Deep reinforcement learning has achieved strong performance in vehicle routing problems (VRPs), yet existing methods mostly ignore both distance and role asymmetries in real-world VRPs, with a few addressing only one. We identify that these two asymmetries are inherently coupled: existing solvers that handle only one degrade more under combined shifts than under each shift separately. We propose CARD, a Coupled Asymmetric Role-and-Distance framework that eliminates this coupling by jointly handling both asymmetries. For asymmetric distance, CARD uses an attention mechanism that explicitly takes both the original and transposed cost matrices as input, while implicitly encoding role distinctions via its MLP scorer. For asymmetric roles, CARD introduces a role-aware training paradigm that operates on the role-reversed view alongside the original view, regularizing the policy through shared gradients. CARD consistently outperforms state-of-the-art neural solver RADAR across four VRP variants, with larger gains under more severe asymmetry, and achieves 5× training speedup to the same performance level. Crucially, CARD remains robust on real-world routing benchmarks across a wide range of distribution shifts without retraining.

Primary area:
reinforcement learning
Keywords:
Neural combinatorial optimization, vehicle routing problem, deep reinforcement learning, asymmetric distance, pickup and delivery

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 2 reviews, above 27% of the others.
Reviewer_SwyiOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes CARD, a RADAR-based neural solver for routing problems with asymmetric travel costs and service roles. It introduces role-reversed training and inference and reports improvements over the evaluated baselines on four routing variants, including larger and distribution-shifted instances.

Critical strengths

The paper studies useful routing settings that combine asymmetric travel costs with pickup, delivery, or backhaul constraints. The experiments cover several problem variants and include cross-scale, out-of-distribution, and real-world evaluations.

Critical weaknesses
  1. The novelty of the distance-aware attention component is questionable. The proposed MLP scorer in Eq. (2) appears to follow the same formulation already used in RADAR, which also combines query–key scores with forward and reverse costs through an MLP before Sinkhorn normalization. Section 4.1 motivates this design by comparing it with linear additive attention, but this does not distinguish it from RADAR.

  2. It is unclear how role information enters the encoder. Figure 1 shows SVD-based initialization from the cost matrix, while Eq. (2) only uses query–key scores and directional costs. If the encoder does not explicitly receive role information, how can its attention scores capture the role-dependent interactions claimed in Section 4.1? In particular, would the attention scores change if the pickup and delivery roles were swapped while keeping the cost matrix fixed?

Questions for authors
  1. The presentation of the main results is misleading. Tables 1–3 report absolute objective values for CARD but percentage gaps relative to CARD for the baselines, could the authors also report the relative gap of CARD instead?
  2. Could the authors report also include the running time of baselines under similar hardware setting in their main results tables?
  3. Could the authors compare the proposed attention scorer against a simpler role-aware node-initialization design?
Reviewer_RfvkOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes CARD, a neural combinatorial optimization framework designed to jointly address asymmetric travel costs and asymmetric service roles in vehicle routing problems. The approach has two main components: (1) a distance-aware attention mechanism that incorporates both forward and reverse travel costs into an MLP-based attention scorer, and (2) a role-aware training strategy that jointly optimizes the original and role-reversed views using a shared policy and cross-view reward baseline. The method is evaluated on four asymmetric vehicle routing variants, including synthetic benchmarks, cross-scale and out-of-distribution settings, and real-world distance matrices from RRNCO. The authors report improvements over RADAR and other neural baselines in solution quality, generalization, and training efficiency.

Critical strengths
  1. Relevant problem formulation. The paper studies a meaningful limitation of neural routing solvers: the interaction between asymmetric travel costs and pickup/delivery or linehaul/backhaul roles.
  2. A reasonably simple architecture. Incorporating Cij and Cji into an MLP-based attention scorer is straightforward and potentially useful for learning directional cost patterns.
  3. Multiple problem variants and evaluation settings. The authors evaluate four routing variants, several instance sizes, synthetic distribution shifts, and real-world distance matrices. This is broader than an evaluation on a single synthetic routing problem.
  4. Attention to computational efficiency. The paper reports wall-clock training time and attempts to compare inference under matched computational budgets, which is important for neural combinatorial optimization.
Critical weaknesses
  1. Equation 11 follows algebraically from subtracting the same global mean from all trajectories. It does not establish that the corresponding policy-gradient estimates are negatively correlated, because the gradients also depend on the individual trajectories' log-likelihood gradients. Moreover, Equation (9) is an algebraic decomposition of the weighted gradients. If the two views have equal numbers of valid starts, the decomposition does not provide the proposed additional balancing mechanism. The paper also describes the cross-view baseline as a source of regularization, but does not adequately distinguish the effect of a shared baseline from that of jointly optimizing the two views with shared model parameters.

  2. The demand shifts reduce the range of the non-dominant role's demands from [1,10] to [1,5]. This may change problem difficulty independently of any interaction with distance asymmetry. Indeed, Appendix A.13 acknowledges that the HP shift simplifies the problem for CARD. Furthermore, the experiments compare the performance degradation of existing solvers with that of CARD, but do not fully isolate whether the proposed method eliminates an interaction between the two sources of difficulty or simply handles the selected shifts better.

  3. The paper uses different inference augmentation counts for different neural methods. The authors attempt to control for runtime, which is reasonable, but the comparison should report actual wall-clock inference times and solution quality together for each method and setting. A matched time budget should be verified empirically rather than inferred from augmentation counts alone.

  4. The methodological novelty of CARD appears limited, as its main components distance-aware attention and role-aware training build upon existing techniques. The primary contribution seems to be their integration to address more complex VRP variants, rather than a fundamentally new method. The paper should more clearly distinguish its approach from existing work and demonstrate the novelty of the proposed combination.

Questions for authors
  1. If N_ori=N_rev, Equation (9)'s gradient-balancing term disappears. What is the precise mechanism responsible for the claimed gradient balancing and reduced variance in the typical training setting?
  2. How does the proposed cross-view baseline compare against separate view-specific baselines and a standard policy-gradient baseline under the same training budget?
  3. Does the super-additive degradation persist across all four routing variants and across shifts that increase rather than simplify problem difficulty?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.