Real Routing Nco Eval

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

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.

Citation

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

• arXiv: 2503.16159