Real Routing Nco Eval

---
name: real-routing-nco-eval
description: Evaluates neural combinatorial optimization models on real-world vehicle routing problems, measuring their ability to generate high-quality routes under asymmetric travel constraints and generalizing to out-of-distribution city maps and location distributions. Use when the user wants to benchmark on Real-World Routing (RRNCO), or asks about evaluating this task. Reports Gap %.
metadata:
  skill_kind: dataset_eval
  source_arxiv: 2503.16159
  bibtex_key: son2025neuralcombinatorial
  confidence: high
---

# real-routing-nco-eval

> Neural Combinatorial Optimization for Real-World Routing — Son et al. (2025) (arXiv:2503.16159, 2025)

## What this evaluates

Evaluates neural combinatorial optimization models on real-world vehicle routing problems, measuring their ability to generate high-quality routes under asymmetric travel constraints and generalizing to out-of-distribution city maps and location distributions.

## Datasets

- **Real-World Routing (RRNCO)** — total ?; splits: train (-1), test (-1); repo https://github.com/ai4co/real-routing-nco

## Metrics

- `Cost` — range: other
  - Total routing cost (distance or duration) across all vehicles in the generated solution.
- `Gap %` **(primary)** — range: percent
  - Relative gap percentage calculated as ((Model Cost - Baseline Cost) / Baseline Cost) * 100, where the baseline is the classical solver LKH3.

## Input / output format

**Input**: Graph representation of city locations with normalized coordinates in [0,1]^2, asymmetric distance/duration matrices, and contextual gating features.

**Output**: A set of vehicle routes (ordered sequences of city indices) satisfying capacity and time window constraints, or a single TSP tour.

## Scoring recipe

```python
def compute_metrics(predictions, instances, baseline_costs):
    costs = []
    for sol, inst in zip(predictions, instances):
        costs.append(calculate_route_cost(sol, inst))
    costs = np.array(costs)
    gap = ((costs - baseline_costs) / baseline_costs) * 100
    return {'Cost': float(np.mean(costs)), 'Gap %': float(np.mean(gap))}
```

## Common pitfalls

- Models trained on synthetic data often fail to generalize to real-world asymmetric travel durations and topologies.
- Gap % is relative to a classical solver (LKH3), not necessarily the true optimal, so it measures practical competitiveness rather than theoretical optimality.
- Out-of-distribution evaluation is split into city-level and cluster-level generalization, which require separate model evaluations and cannot be averaged together.

## Evidence (verbatim from paper)

> Table 2. Comparison of NCO solvers and their training data generators on real-world (RRNCO) data. Our RRNCO model with the proposed data generator achieves the best results.

| Model | Data Generator | In-dist | | OOD (city) | | OOD (cluster) | |
| --- | --- | --- | --- | --- | --- | --- | --- |
| | | Cost | Gap % | Cost | Gap % | Cost | Gap % |

## Citation

```bibtex
@misc{son2025neuralcombinatorial,
  title={Neural Combinatorial Optimization for Real-World Routing},
  author={Son et al. (2025)},
  year={2025},
  note={arXiv:2503.16159}
}
```

- arXiv: 2503.16159