[SOTA Comparison] Vehicle Routing

Algorithmic Innovation
1

Our Vehicle Routing Challenge Evaluator provides a streamlined framework for benchmarking TIG Vehicle Routing algorithms against state-of-the-art (SOTA) methods on key academic datasets.

The goal of this thread is to encourage community involvement in shaping our evaluation framework. We invite you to contribute by engaging with this post – read our rationale for the current approach, share your feedback, suggest new benchmark datasets, propose complementary comparison metrics, or recommend additional SOTA algorithms to include.

The remainder of this post explains the rationale behind our current selection of datasets, benchmark SOTA algorithms, and comparison metrics, and outlines the features we are planning to add in future updates.

Datasets

The evaluation suite currently supports one primary benchmark dataset for the Vehicle Routing with Time Windows Problem (VRPTW). All instances and their corresponding best known solution (BKS) are sourced from CVRPLIB.

Currently supported benchmark dataset:

  • Homberger–Gehring Instances[1]: An extended VRPTW benchmark consisting of 300 instances: 10 instances for each of the 6 Solomon class types at customer sizes of 200, 400, 600, 800, and 1,000.

Benchmark instance types, defined by Solomon (1987)[2], are categorized according to customer distribution patterns: random (R), clustered (C), or random-clustered (RC), and the tightness of time windows: tight (1) or loose (2). The instances in TIG align most closely with the RC1 category.

SOTA Benchmark Methods

Rationale for Selected Method

To provide a relevant and rigorous comparison, we benchmark TIG algorithms against the SOTA method “Hybrid Genetic Algorithm with Adaptive Diversity Management” (HGSADM). The results for HGSADM are sourced from the paper by Vidal et al. (2013)[3]

Vidal’s Hybrid Genetic Search (HGS) is widely regarded as one of the most effective algorithms for solving a wide range of Vehicle Routing Problem (VRP) variants. The version included in this evaluator, HGSADC, is tailored for VRPTW. Its performance in terms of both solution quality and runtime is a benchmark milestone we aim to surpass.

Comparison Metrics

Similar to how we compare solution quality in our knapsack evaluator, we evaluate algorithm performance using the Relative Percentage Deviation (RPD) from the Best Known Solution (BKS). It is calculated as:

RPD(\%)=\frac{\text{solution_distance} - \text{BKS}}{\text{solution_distance}​}\times100

This metric focuses on total distance, as this is the main objective function we aim to minimize, and does not consider the number of routes.

The evaluator currently includes two visualisations:

  • A graph tracking the average RPD of the top-earning TIG algorithm by round against the SOTA algorithm HGSADM for each benchmark dataset type.
    • A graph comparing the average RPD by instance size across benchmark instance types for the top-performing TIG algorithms alongside HGSADC.

Future Work

We are continually enhancing the evaluation suite, with several key improvements planned:

  • Support for additional datasets, including the original Solomon VRPTW instances.
  • Precise runtime comparisons to better evaluate the speed and efficiency of TIG algorithms relative to SOTA methods.
  • Inclusion of more SOTA comparison algorithms.

  1. Gehring, H. and Homberger, J., 1999, May. A parallel hybrid evolutionary metaheuristic for the vehicle routing problem with time windows. In Proceedings of EUROGEN99 (Vol. 2, pp. 57-64). Springer Berlin. ↩︎

  2. Marius M. Solomon. Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints . Operations Research , 35(2):254–265, 1987. ↩︎

  3. Vidal, T., Crainic, T.G., Gendreau, M. and Prins, C., 2013. A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows. Computers & operations research , 40 (1), pp.475-489. ↩︎