Routefinder Vrp Eval

routefinder-vrp-eval

RouteFinder: Towards Foundation Models for Vehicle Routing Problems — Berto et al. (2024) (arXiv:2406.15007, 2024)

What this evaluates

Evaluates a foundation model's ability to solve and generalize across 48 distinct Vehicle Routing Problem (VRP) variants. It probes constraint satisfaction, route optimization, and zero-shot adaptation to unseen attribute combinations like multi-depots and mixed backhauls.

Datasets

• VRP variants (unified generation) — total ?; splits: test (-1); repo https://github.com/ai4co/routefinder

Metrics

• optimality gap (primary) — range: percent
  • Gap = (Model_Objective - Best_Known_Objective) / Best_Known_Objective * 100%. Lower values indicate better performance relative to the best-known heuristic solution.

Input / output format

Input: 2D coordinates for depot(s) and customers, vehicle capacity, linehaul/backhaul demands, time windows, duration limits, and attribute flags indicating the VRP variant.

Output: A sequence of routes (ordered lists of customer indices) satisfying all constraints.

Scoring recipe

def compute_gap(model_obj, best_known_obj):
    if best_known_obj == 0:
        return 0.0
    return (model_obj - best_known_obj) / best_known_obj * 100.0

Common pitfalls

• Traditional solvers use fixed time limits (10s/20s) while neural models use multi-start rollouts with augmentations, making direct speed comparisons unfair.
• The 'best-known' solutions marked with * are heuristic bounds, not proven optima, so the gap is relative to a solver-dependent baseline.
• Neural models select the best of n×8 augmented rollouts per instance, which significantly increases inference time compared to single-pass baselines.

Evidence (verbatim from paper)

RouteFinder reduces optimality gaps by over 10% compared to state-of-the-art multi-task models, demonstrating superior generalization and scalability. We evaluate all approaches on 1,000 instances of held-out test data for each size n of each variant.

Citation

@misc{berto2024routefinder,
  title={RouteFinder: Towards Foundation Models for Vehicle Routing Problems},
  author={Berto et al. (2024)},
  year={2024},
  note={arXiv:2406.15007}
}

• arXiv: 2406.15007