The Anatomy of an Optimization Problem

Optimization is easy to do and surprisingly easy to miscommunicate. This page gives you a clean mental model for what an optimization problem is, how algorithms relate to it, and how to benchmark results so claims are defensible.

TipHow to use this page

• Use the quick glossary to align terminology.
• Jump to Benchmarking and Evaluation when designing experiments.
• Use the VRP vs Formula 1 mapping as a sanity check: if you can explain it in both worlds, you can explain it to a reader.

flowchart TB
  I[Problem instance + inputs] --> F[Formulation]
  F --> O[Objective]
  F --> C[Constraints]
  F --> V[Variants + randomness]
  V --> S[Solution approach / policy]
  S --> E[Benchmarking + KPIs]
  E --> K[Claim you can defend]

Figure 1: From problem definition to a claim you can defend.

Concept	One-liner	Jump
Problem instance	One fully specified case of a problem	Section 1.1
Inputs / parameters	Fixed data/assumptions given to the model	Section 1.2
Objective function	What “best” means (min/max)	Section 1.3
Constraints	Feasibility rules a solution must satisfy	Section 1.4
Variant	Modified problem definition (objective/constraints)	Section 1.5
Randomness	Stochasticity in data or algorithm	Section 1.6
Policy / decision rule	Mapping from observations to actions	Section 2.1
Baseline	Reference method/performance to compare against	Section 2.2
SOTA	Strongest published/known methods	Section 2.3
BKS	Best objective value reported so far	Section 2.4
Benchmark	Standardized testbed + protocol	Section 3.1
KPIs	Metrics you report (not just “best run”)	Section 3.3
Tests	Pilot → tune → freeze → held-out evaluation	Section 3.4
Ablation	Isolate contribution of components	Section 3.5
p-hacking	Cherry-picking / tuning on test results	Section 3.6

NoteExtended glossary (detailed)

• Problem Instance
  • Definition: A fully specified set of input data that defines a particular case of the problem (distinct from the general problem class) (Deutsche Nationalbibliothek, n.d.). It includes all parameters needed to solve that one case.
  • VRP example: E.g. a specific VRP scenario with a given depot location, a list of customer locations each with demands, vehicle capacity, etc. Solomon R101 (100 customers, time windows) is one instance of the VRPTW (Solomon, 1987).
  • Formula 1 analogy: A particular Grand Prix race event (track, weather, teams, etc.) is an “instance” of a racing problem. The 2023 Monaco GP with its unique track and conditions is one instance.
• Inputs / Parameters
  • Definition: The data and fixed parameters that serve as constants in the problem’s formulation. These include the known quantities that the objective and constraints are built on (IBM, n.d.). They are not decided by the solver but provided as part of the instance.
  • VRP example: In VRP: the set of customer coordinates, each customer’s demand, vehicle capacity, distance matrix between locations, time window intervals, etc. These are given to the solver (IBM, n.d.).
  • Formula 1 analogy: In F1: the circuit layout, number of laps, fuel capacity limit, tire compound options, and weather forecast are inputs. They are fixed conditions of a race (not under the team’s control).
• Objective Function (OF)
  • Definition: A mathematical function defining the goal of the optimization—usually to be minimized or maximized (Wikipedia contributors, n.d.a). The OF maps any feasible solution to a scalar “cost” or “value,” and the solver seeks an optimal solution that extremizes this value.
  • VRP example: In VRP: minimize total route cost (e.g. total distance or time) for serving all customers. For example, CVRP aims to minimize total distance traveled by all vehicles (SciRP, n.d.). The classic VRP OF can be written as \(\min \sum_{(i,j)} d_{ij} x_{ij}\) (minimize sum of travel distances).
  • Formula 1 analogy: In F1: the “objective” is to minimize total race time (or equivalently, finish the race as fast as possible). A team might phrase the goal as maximizing points in the championship (which correlates with finishing position). Lap time is analogous to an objective metric—lower is better (minimize lap time).
• Constraints
  • Definition: Rules or limitations that feasible solutions must satisfy (IBM, n.d.). Constraints are often equalities or inequalities reflecting real-world limits or requirements (capacity, resource limits, etc.). They carve out the feasible region of the problem.
  • VRP example: In VRP: each customer must be served by exactly one vehicle; no vehicle’s load may exceed capacity; time window constraints require service within certain times. For example, a VRPTW constraint: if customer j has latest service time \(L_j\) and service starts at time \(t_j\), then \(t_j \le L_j\) (service must begin before the time window closes). Capacity constraint: \(\sum_{i \in \text{route}} demand_i \le Q\) for vehicle capacity \(Q\). These ensure feasible routes (IBM, n.d.).
  • Formula 1 analogy: In F1: physical and regulatory constraints define the race. Examples: fuel load and engine mode limits (you cannot exceed fuel capacity or certain power usage), tire rules (must use at least two different tire compounds in dry races), and track limits (you must stay within track boundaries or incur penalties). All cars must complete the full race distance (all laps)—analogous to “visit all customers” in VRP (IBM, n.d.).
• Variant (Problem Class Extension)
  • Definition: A modified or extended version of a base problem that incorporates additional features or constraints. Variants represent classes of problems related to the original, often to model specific real-world complexities (ScienceDirect Topics, n.d.; SciRP, n.d.).
  • VRP example: The VRP family has many variants: e.g. CVRP (Capacitated VRP) adds vehicle capacity constraints; VRPTW (VRP with Time Windows) adds scheduling constraints; Pickup-and-Delivery VRP adds paired pickup/drop-off constraints. Each variant tweaks the base VRP definition. E.g. VRPTW extends CVRP by requiring each customer be served within a time window (ScienceDirect Topics, n.d.).
  • Formula 1 analogy: In F1: analogous “variants” could be different race formats or series. For instance, a sprint race vs. a standard race (a shorter race changes strategy constraints), or Formula 2 vs. Formula 1 (different rules like no refueling vs. F1’s past refueling era). They all involve racing but with variant rules (e.g., mandatory pit strategies, safety car rules) altering the optimization of strategy.
• Randomness
  • Definition: Any stochastic elements in the problem or algorithm. In optimization, randomness can appear in problem data (uncertain inputs) or within algorithms (randomized heuristics). Stochastic optimization acknowledges random variables in objective or constraints (IBM, n.d.), requiring probabilistic analysis or repeated trials.
  • VRP example: In problem instances: customer demands or travel times might be random (e.g., in a simulation of daily deliveries, demand varies). In algorithms: many VRP heuristics (e.g. Genetic Algorithms, Randomized Local Search) use random choices (random initial routes, random swaps). This means results can vary run-to-run; robust benchmarking often uses multiple runs & average performance to account for randomness.
  • Formula 1 analogy: In F1: randomness shows up as unpredictable events—weather changes, crashes triggering a safety car, or a sudden tire puncture. These stochastic events can drastically alter the outcome even if the strategy (policy) was fixed. Teams often simulate many random scenarios (rain, safety car timings) to gauge strategy robustness. Similarly, two races at the same track can differ due to random incidents, just like running a stochastic algorithm twice can yield different outcomes.
• Policy / Decision Rule
  • Definition: A policy is a strategy or mapping from states/observations to actions (Wikipedia contributors, n.d.b). In optimization or sequential decision-making, a decision rule prescribes what action to take under certain conditions. It’s often discussed in dynamic or iterative contexts—essentially the “brains” of a heuristic or algorithm that decides the next move.
  • VRP example: In VRP: a constructive heuristic uses a decision rule to build routes (e.g., Nearest Neighbor policy: “at each step, visit the nearest unserved customer next”). In a dynamic VRP or routing with real-time requests, a policy might dictate how to re-route vehicles when a new request appears (a rule like “insert the new request if it’s on the shortest detour route”). The Savings algorithm has a decision rule: merge two routes if it yields a positive “savings” in distance. These are policies guiding the solution construction.
  • Formula 1 analogy: In F1: think of the race strategy policy—for example, a rule like “If a safety car comes out after lap 20, pit for fresh tires immediately” is a decision rule. Or a simpler policy: “Run in fuel-saving mode until a competitor is within 2 seconds, then switch to attack mode.” The driver’s race engineer often programs decision rules (“Box now if degradation > X” for tire changes). Such policies map race conditions (state: gap to rivals, tire wear) to actions (pit stop, engine mode).
• Baseline
  • Definition: A baseline is a simple or previously known method/solution used as a reference point (Envisioning Vocab, n.d.). It provides a lower benchmark of performance that any new approach should at least meet or exceed. Baselines help sanity-check that a complex model actually outperforms a trivial or old solution.
  • VRP example: In VRP research: a baseline could be a known simple heuristic or even a naive solution. E.g. use a Greedy heuristic (serve nearest next each time) or a Clark-Wright savings solution as a baseline. If a new algorithm can’t beat these in cost or computation time, it’s not useful. Another baseline: the cost if one were to send each customer individually (very high cost)—useful to show improvement. Baseline results are often reported to show how much better the advanced method is (Envisioning Vocab, n.d.).
  • Formula 1 analogy: In F1: a baseline could be an older strategy or car performance. For instance, a baseline strategy might be “one pit stop at race midpoint” (simple, not optimized) to compare against more refined two-stop strategies. Or comparing a new car’s lap time to last season’s car (baseline) at the same track. If the new design isn’t faster than the baseline (old car or basic strategy), it’s back to the drawing board. Baselines set the minimum bar: e.g., “last year’s pole time was 1:30.0, so our baseline is to at least match that.”
• State-of-the-Art (SOTA)
  • Definition: The best known approach or result in the field at the current time. “State-of-the-art” denotes the highest level of performance achieved so far, typically by the leading algorithm or method (ResearchGate, n.d.). New work is often compared against the SOTA to claim improvement.
  • VRP example: For VRP, SOTA might mean the current best-performing algorithm on standard benchmarks (e.g., a cutting-edge ALNS or reinforcement learning algorithm that outperforms others), or the best known results. For example, on a classic CVRP benchmark set, a 2023 algorithm might be state-of-the-art if it finds lower costs than all prior published methods. SOTA can also refer to the performance level: e.g. “Our solver reaches the best-known solution in 95% of cases—comparable to the SOTA” (ResearchGate, n.d.).
  • Formula 1 analogy: In F1: The car/team currently dominating is state-of-the-art in racing performance. For instance, Red Bull Racing’s 2023 car is state-of-the-art—it represents the peak of what’s achievable under current regulations. SOTA in an F1 context might also be a lap record: e.g., the fastest lap ever at Monza is the “state-of-the-art lap” for that track. Everyone aims to beat it. Just as algorithms strive to beat the SOTA score, teams aim to surpass the current best lap time or strategy.
• BKS (Best Known Solution)
  • Definition: The best objective value found for a specific instance, by any method (not necessarily proven optimal). BKS is often used in benchmarking as the reference “ideal” solution for that instance (“The neurobench framework for benchmarking neuromorphic computing algorithms and systems,” 2025). It might come from an exact solver or a very long run of a heuristic.
  • VRP example: In VRP literature, benchmark instances come with published BKS values. E.g. for a Solomon VRPTW instance with 100 customers (Solomon, 1987), the best-known solution might have total distance = 1210.5 using 10 vehicles. This BKS may have been found by a very advanced algorithm or extensive search. New heuristics report their optimality gap to the BKS (how far above the best-known cost they are). The BKS serves as a yardstick (“The neurobench framework for benchmarking neuromorphic computing algorithms and systems,” 2025)—if your solution equals it, you’ve essentially matched the best known performance for that instance.
  • Formula 1 analogy: In F1: think of a track record lap time. For example, the fastest lap ever at Spa-Francorchamps is the BKS for that circuit—a benchmark for performance. Even if not an official record (perhaps set during qualifying with low fuel), it’s the best known “solution” (lap) achieved there. When teams arrive at a track, they know the lap record (BKS) and gauge their pace against it. Breaking the track record is akin to finding a new best known solution for that “instance” (track conditions).
• Benchmark (Problem Benchmark & Role)
  • Definition: In optimization, a benchmark is a set of standardized problem instances (and sometimes known results) used to evaluate and compare algorithm performance (ResearchGate, n.d.). Benchmarks provide a common testing ground so results are comparable across studies. They often come with known best solutions (or at least past bests) for reference.
  • VRP example: The VRP field relies on benchmarks like Solomon’s VRPTW instances (Solomon, 1987) or the CVRP instances introduced by Uchoa, Pecin, & Pessoa (2017). For example, the Solomon 56 VRPTW set is a classic benchmark: each algorithm is tested on all instances in that set and compared on metrics like solution quality and runtime (Solomon, 1987). The role of a benchmark is to enable apples-to-apples comparisons: every researcher uses the same set of instances (ResearchGate, n.d.). A good benchmark is diverse (testing different cases), publicly available, and has known reference results (like BKS or optimal for small ones).
  • Formula 1 analogy: In F1: one can view official test tracks or simulations as benchmarks. For instance, Barcelona is often used for winter testing—teams compare their cars’ lap times on this benchmark circuit under similar conditions. It provides a common baseline to compare car performance (since all teams run the same track). Similarly, standardized simulation scenarios (like wind tunnel tests at set airspeed, or a fixed simulator track run) serve as benchmarks—the outcomes let engineers objectively compare setups or even different cars. The idea is identical: test different “solutions” (car setups) on the same track to see which is best.
• Simulation vs. Exact Method Benchmark
  • Definition: Two flavors of benchmarking an approach: simulation/practical benchmarking involves testing algorithms in a realistic or stochastic setting (possibly with dynamic elements) to gauge practical performance (Barr et al., 1995). Exact-method benchmark means comparing algorithm results against optimal solutions on smaller instances solvable by exact methods (like MILP solvers) (“The neurobench framework for benchmarking neuromorphic computing algorithms and systems,” 2025). The exact approach provides a gold standard for quality (optimality), while simulation provides insight into performance under realistic complexities.
  • VRP example: Simulation: Suppose we test a VRP heuristic in a microsimulation of a delivery day—trucks travel on a map, traffic delays happen randomly, etc. This practical benchmark evaluates how the method handles real-life variability (robustness, response time). It might reveal issues that a static benchmark doesn’t (e.g., how the policy adapts to a traffic jam). Exact-method: Conversely, we take small VRP instances (say 10 customers) where an ILP solver can find the true optimal solution = 100 km. We run our heuristic and get 102 km; we then know it’s 2% above optimal. Using an exact solver on small cases or a known BKS (“The neurobench framework for benchmarking neuromorphic computing algorithms and systems,” 2025) lets us calculate an optimality gap—a critical benchmarking measure. Both types complement each other.
  • Formula 1 analogy: In F1: Simulation benchmark: teams use race simulators (or computer simulations) to test strategies—e.g. simulate 1000 race scenarios with different safety car timings to evaluate a pit strategy’s average outcome. This is akin to a practical benchmark—it tests the strategy in a “realistic” environment (virtual race). Exact benchmark: an F1 analogue might be calculating the theoretical optimal lap. Engineers sometimes compute an “optimal lap” by combining the best sector times or using optimal control theory on the track model. That’s like an exact solver’s outcome—the absolute best possible lap if everything were perfect. A driver’s actual lap time can be compared to this theoretical optimum (say the optimal is 1:30.000 and the driver does 1:30.500, a 0.5s gap). This tells how close the real performance is to the theoretical best—similar to measuring an algorithm’s gap to optimal on small instances.
• KPI (Key Performance Indicator)
  • Definition: A quantifiable metric used to evaluate the performance or success relative to objectives (ResearchGate, n.d.). In optimization experiments, KPIs are the measures reported for comparison—they can be directly the objective value, or secondary metrics like runtime, solution robustness, etc. Good KPIs align with what users care about (solution quality, time, cost, etc.) and are comparable across methods.
  • VRP example: Common KPIs in VRP benchmarking: Solution cost (total distance or total cost)—primary KPI since VRP is cost-minimizing. Computation time (CPU seconds)—crucial for assessing efficiency. Optimality gap—difference from known optimal/BKS, in %. Possibly also number of vehicles used (in VRP minimizing vehicles is sometimes part of objective or a secondary goal). For VRPTW, one might also report number of late deliveries as a KPI if allowed. Each experiment may report a table of KPIs per instance or averages (ResearchGate, n.d.). For example: “Algorithm A average cost = 1230 (2% gap), runtime = 60s” vs “Algorithm B average cost = 1250 (4% gap), runtime = 30s”. KPIs must be chosen carefully to truly reflect performance differences.
  • Formula 1 analogy: In F1: Teams track myriad KPIs to gauge performance. The primary KPI is lap time or race time (since the objective is to finish fastest). But many supporting KPIs exist: tire degradation rate (how quickly tires lose performance), pit stop duration, fuel consumption per lap, and reliability measures (like mean time between failures). For strategy optimization, a key KPI might be “expected finishing position” or probability of a podium given a strategy. During a race, teams also use live KPIs: gap to competitor, tire wear percentage—to decide actions. Just as in optimization, where we might weigh multiple KPIs (quality vs. runtime), in F1 a team balances lap time vs. tire wear as dual KPIs for strategy. Ultimately, points scored in the championship is the high-level KPI that sums it all up.
• Tests (Pilot, Tuning, Held-out)
  • Definition: In experimental methodology, “tests” refer to phases of evaluation: pilot tests are initial trial runs to validate setup and parameters on a small scale; tuning tests involve using some data (or instances) to adjust algorithm parameters (like hyperparameters) for best performance; held-out tests are final evaluations on instances never used in development, to fairly assess generalization. Separating tuning and held-out testing prevents overfitting to the test set (OpenReview, n.d.).
  • VRP example: For a VRP algorithm development: one might do a pilot test on 2–3 small instances first, to catch bugs and get a sense of performance. Then, use a tuning set of instances (say 10 instances from a benchmark) to calibrate parameters (e.g., set the tabu list length in Tabu Search, or learning rate in an RL approach). Only after choosing parameters, the algorithm is run on a held-out test set (other benchmark instances not seen in tuning) to report results. For example, if developing on Solomon instances, you might tune on half of them and then test on the other half to see how well it does without cherry-picking. This protocol ensures credibility of results—it mimics how the algorithm would perform on genuinely new VRP instances.
  • Formula 1 analogy: In F1: Teams similarly phase their testing. Pilot test: a shakedown of the new car (few laps to ensure systems work)—analogous to pilot experiment, not for performance but to validate the setup. Tuning tests: the extensive practice sessions and simulator runs where the car’s setup (suspension, aero, engine maps) is tweaked—this is like hyperparameter tuning, using the track as “training data.” Engineers adjust settings to optimize performance given that track’s conditions. Held-out test: the race itself is essentially the held-out evaluation—you cannot tweak setup once the race starts, and it’s where the performance counts. If the car was over-tuned to the practice conditions (e.g., optimised for a cooler track but race day is hotter), performance might suffer—an analogy to overfitting. In essence, how the car performs in the race (held-out) is the true test of the tuning done earlier.
• Ablation / Addition
  • Definition: An ablation study systematically removes or switches off components of a system to assess their individual contributions (Wikipedia contributors, n.d.c)#:~:text=In%20artificial%20intelligence%20%20,2). Conversely, an “addition” study might start from a baseline and add components one by one to see the incremental benefit. These tests help identify which features of an algorithm (or system) are responsible for performance changes. It’s a form of sensitivity analysis for algorithm design.
  • VRP example: Suppose a new VRP heuristic has multiple modules (e.g., a local search phase, a ruin-and-recreate phase, and a learning mechanism). In an ablation study, we might disable the learning mechanism and run the algorithm, then disable the ruin-and-recreate, etc., measuring performance each time. If removing the learning module causes only a tiny drop in solution quality, but removing local search causes a huge drop, we learn that local search is critical while the learning module might be superfluous. An addition experiment might start with a basic VRP solver, then add the ruin-and-recreate module—see improvement +X%; then add learning—see improvement +Y%. This isolates each component’s value. Such studies prevent authors from overclaiming: e.g., if a fancy module doesn’t actually improve results, an ablation will reveal it.
  • Formula 1 analogy: In F1: Teams do something analogous when testing new parts. Ablation: remove a new aerodynamic part (say, take off an upgraded front wing) and run the car—observe the lap time change. If the car becomes 0.3s slower, that wing’s contribution is roughly 0.3s gain. Addition: or start with last race’s setup and then add the new wing—see the improvement. They often A/B test by running one car with the update and one without in practice. This is exactly identifying component contributions. Another example: turning off a driver assist (like traction control, back in the days when it was allowed) to see how much it was helping lap time. The goal is to quantify each element’s impact. In both racing and algorithms, ablation helps avoid the “kitchen sink” approach where you throw in many ideas without understanding which actually work.
• p-hacking & Overfitting
  • Definition: p-hacking (from statistics) is the practice of tweaking analysis or running many experiments until you get a desirable result, then reporting only that result (Alphanome, n.d.). In algorithm research, this can mean repeatedly adjusting or selecting experiments to “prove” one method is better, capitalizing on randomness rather than true merit. Overfitting in this context means tailoring an algorithm too specifically to the benchmark or tuning data, so that it performs well there but poorly elsewhere (OpenReview, n.d.). It often stems from excessive tuning or implicitly using test feedback in development.
  • VRP example: In VRP/optimization research: p-hacking might look like this—you run your heuristic on 20 random instances; most runs show no improvement over baseline, but a couple instances show big improvement. You choose to report only those or you adjust the narrative to highlight them, ignoring where it did worse. Or you tune parameters on the test set itself (even unintentionally) by trying many variants and only publishing the best result—effectively training on the test data (OpenReview, n.d.). Overfitting happens if, say, you fine-tune your algorithm specifically for the Solomon benchmark instances (Solomon, 1987) (maybe you noticed a pattern in their coordinates distribution and coded a special case). It might then beat all competitors on Solomon set. But when faced with a slightly different VRP instance in the real world, that specialized trick may fail badly. This is why authors use held-out tests and random instance generation to check generalization. As Hooker (1995) cautioned, many “track-meet” style comparisons encourage overfitting to benchmarks rather than true scientific progress.
  • Formula 1 analogy: In F1: Overfitting would be like designing a car that is a “one-track wonder.” For example, a team might optimize their car heavily for high-speed circuits (Monza, etc.) because those were the tracks in preseason tests—the car sets record laps in testing (benchmark), but when the season goes to a street circuit (Monaco, different characteristics) the car struggles. They over-optimized for the test tracks and lost general performance balance. Similarly, if a team keeps adjusting the setup to perfectly suit the qualifying session conditions, they might end up with a setup that overheats tires in the race—they overfit to qualy. p-hacking in F1 might be compared to a team doing dozens of practice runs and only highlighting the single fastest lap (maybe achieved with draft or beyond limits), misleading stakeholders about the car’s true pace. In essence, focusing only on when things look good and ignoring when they don’t. Both p-hacking and overfitting produce an illusion of performance that may not hold in unbiased evaluation. Teams, like researchers, combat this by validating on diverse tracks and not just chasing one metric (e.g., not just a one-lap time, but race stint average, tire wear etc.).

Problem Formulation: Core Concepts

Understanding an optimization problem begins with how the problem itself is defined. Key elements include the problem instance (the specific case/data you’re solving), the inputs and parameters that describe that instance, the objective function that quantifies what you’re trying to achieve, and the constraints that any solution must satisfy. Often there are different variants of a base problem, and some problems or algorithms involve randomness. We discuss each in turn, with examples from the Vehicle Routing Problem (VRP) and analogies to Formula 1 racing.

Problem Instance

In optimization literature, a problem instance refers to a fully specified set of data defining a particular problem to be solved (Deutsche Nationalbibliothek, n.d.). It is one concrete realization of a problem class. For example, the VRP is a problem class, and a specific set of customers, distances, and vehicle information constitutes one instance of VRP. The instance includes all information needed to actually run an algorithm and get a solution for that case. Authors often emphasize the difference between the general problem and a specific instance—failing to specify which one is meant can cause confusion (Deutsche Nationalbibliothek, n.d.).

In VRP terms, an instance might be something like Solomon’s benchmark instance R101, which has 100 customers with given locations and time windows, and a depot location. Solving that one instance means finding routes for vehicles that visit all those 100 specific customers. Another instance might have a different distribution of customers or different numbers. We compare algorithm performance on sets of instances.

TipFormula 1 analogy

A single Grand Prix race (e.g., the 2023 Monaco GP) is like a problem instance. The general problem class is “winning an F1 race,” but each race has unique data: the track layout, weather on that day, which teams and drivers are present, etc. Solving the strategy for Monaco 2023 won’t automatically solve Monza 2023, just as an algorithm tuned to one instance might not directly solve another. Each race stands alone as a specific scenario (instance) with its own parameters.

Inputs and Parameters

Every instance comes with given data and fixed parameters that define it. These inputs/parameters are the known quantities that the optimization model takes as given (IBM, n.d.). They can include numeric parameters, data tables, or any constants in the mathematical formulation. In a mathematical optimization model, we often call them “parameters” (distinguishing them from decision variables, which are to be decided by the solver).

In VRP, the inputs include the list of customer locations (often their coordinates), the demand of each customer (how much goods they need), the vehicles’ characteristics (capacity, number of vehicles or fleet size, maybe vehicle speed), and the distance or travel time between every pair of locations (usually given by a matrix). Additionally, if time windows are involved (VRPTW), those time window values for each customer are input parameters. For example, in the RapidLogistics scenario described by IBM, one would gather customer locations, their time windows, package sizes, vehicle capacities, fuel limits, etc. as the input data (IBM, n.d.). All this information together forms the problem instance.

It’s important to note that these inputs are not under our control—they are part of the problem description. The role of an algorithm is to take these inputs and produce outputs (the decision variables, like which route each vehicle takes).

NotePractical note

Sometimes a distinction is made between instance data and algorithm parameters. Here we’re focusing on the instance data. Algorithm parameters (like a tabu tenure in Tabu Search or population size in a Genetic Algorithm) are a different kind of parameter—they belong to the algorithm, not the problem. One must be careful not to confuse tuning algorithm parameters with the problem’s parameters.

TipFormula 1 analogy

The inputs and parameters of a race are things like the track characteristics (length, number of turns, DRS zones), the weather forecast, and regulations (fuel capacity, tire compound options). The team cannot change these; they are given. For example, “race will be 58 laps, track temperature 45°C, and you have 3 sets of hard tires available”—these are fixed inputs. Just as an optimization algorithm takes problem data as input, an F1 team takes all these conditions as the inputs to their strategy planning. (The decision variables in this analogy would be things like which lap to pit on, which tire to use—the team will decide those.)

Objective Function

The objective function (OF) is the mathematical function that defines the goal of the optimization problem. It maps any candidate solution to a numerical value (often called the cost, score, or utility), and we seek to either minimize or maximize this value (Wikipedia contributors, n.d.a). In most operations research problems, by convention we minimize a cost (maximization can be converted to minimization by negating the function).

The objective function formalizes the problem’s goal. In the VRP, the typical objective is to minimize the total distance traveled by all vehicles (or total delivery time or total cost, which usually correlates with distance). For instance, if \(d_{ij}\) is the distance between customer \(i\) and \(j\), a simple VRP objective might be:

\[\min \sum_{v \in \text{vehicles}} \sum_{(i,j) \in \text{route}(v)} d_{ij}.\]

This sums up all legs of all routes. Another equivalent objective is minimize total fuel or travel time, etc., since those are usually proportional to distance in a road network context.

In academic terms, the objective function provides the “criterion” by which we judge solutions (Wikipedia contributors, n.d.a). A feasible solution that achieves the best (minimum or maximum) objective value is an optimal solution. There may be multiple objectives (multi-objective optimization), but let’s stick to single-objective for simplicity here.

In our VRP example, suppose we have 10 vehicles and a set of customers. One feasible solution is a set of 5 routes with a total of 200 km traveled. Another solution has 210 km. The objective function value for the first is 200 (km). Since VRP is a minimization problem, 200 is better. The algorithm’s job is to search the space of possible routes to find the minimum possible total distance (subject to constraints). In well-known benchmarks, sometimes the optimal value is known for small instances, or we have a best known value for larger ones (that best known is effectively the lowest objective value found so far by anyone).

The objective function is often specific to the problem’s purpose. If the problem variant changes, the objective might change too (for example, in a Minimize Vehicles VRP, one might primarily minimize the number of vehicles used, with distance as a secondary objective).

TipFormula 1 analogy

The objective in a race is to finish first (which can be seen as maximizing the points or minimizing the race time). If we think in terms of a quantifiable metric: minimize total race time is a clear objective (or equivalently minimize lap time for a single lap scenario like qualifying). In fact, teams often break it down: the race time is fixed + pit stop time + any delays, etc., and they try to minimize that. If we treat each strategic decision (like when to pit) as variables, the objective function is the final race time or final position. Every team is optimizing (implicitly or explicitly) this function under the constraints of the rules and their car’s capabilities.

Another objective teams consider is maximizing championship points over a season (which might occasionally conflict with minimizing time in one race—think of scenarios where settling for second yields more points than risking a DNF by pushing too hard). But focusing on a single race, the lap time or total time is the objective. The phrase “optimize our strategy” in F1 literally means “find the plan (tire choices, pit timing, fuel modes) that yields the shortest race time or best finishing position.”

Constraints

Constraints are the rules of the game in an optimization problem—conditions that any feasible solution must satisfy (IBM, n.d.). They can be equalities or inequalities. Constraints carve out what is allowed and disallow infeasible solutions, even if those might have good objective values. In a well-posed optimization problem, the optimal solution must be one of the feasible solutions (i.e., satisfy all constraints).

The VRP has several fundamental constraints in its classic form:

• Each customer is visited exactly once (cannot skip a customer or serve one twice).
• Route capacity constraint: The sum of demands on any single vehicle’s route cannot exceed the vehicle’s capacity \(Q\). If a vehicle has capacity 100 (maybe units of weight or volume), and customers on its route have demands that sum to 120, that route violates capacity.
• Route time or distance constraint: If there’s a maximum route length or driver working hour limit, each route’s total length/time must be below that.
• Time window constraints (for VRPTW): If customer \(j\) must be served between time \(E_{j}\) and \(L_{j}\) (earliest and latest), and if a vehicle arrives earlier it must wait until \(E_{j}\), and it cannot arrive after \(L_{j}\). This often is encoded as \(t_{j} \leq L_{j}\) (service must start by latest time) and also \(t_{j} \geq E_{j}\) (can’t start before opening). If a vehicle can’t make it in that interval, that assignment is not allowed.

Mathematically, constraints in VRP are often written using binary decision variables \(x_{ij}\) meaning “vehicle goes from i to j”. For example, the constraint that each customer j is visited exactly once can be written as:

\[\sum_i x_{ij} = 1 \quad \forall j \text{ (each customer } j \text{ has exactly one incoming arc)}.\]

And

\[\sum_j x_{ij} = 1 \quad \forall i \text{ (each customer } i \text{ has exactly one outgoing arc)}.\]

Those ensure a single visit. Capacity constraints might be formulated via subtour elimination or flow constraints, but conceptually it’s as described above.

What constraints do is ensure the solution is implementable. You might find a fantastically short route that serves all customers if you ignore capacity—but when capacity is enforced, that route might be illegal because the truck can’t carry everything. So constraints incorporate real-world limits (like vehicle capacity, working time, etc.) into the optimization.

In the VRP example, if we have a 1000 kg capacity per truck and one customer orders 1200 kg, then clearly one truck can’t carry it. A constraint would force that either that customer is split (if split delivery allowed, which is a different variant) or more likely in VRP each customer must be on one route, so this instance might actually be infeasible unless there’s a second truck to split the load or such. Feasibility is as important as optimality—an algorithm must find a feasible solution first (meeting all constraints), then among feasibles find the optimal.

TipFormula 1 analogy

Constraints in racing are the regulations and physical limits that strategies must respect. For instance:

• Fuel limit: Teams start with a certain fuel load (since 2010s, refueling is banned, so effectively fuel tank size and fuel flow rate are constraints). They cannot exceed a certain fuel flow rate during the race (regulatory constraint) (IBM, n.d.), and they must not run out of fuel before the finish (a practical constraint).
• Tire rules: There is a famous constraint in dry races: you must use at least two different tire compounds. This means a strategy that tries to run the whole race on one set of tires (even if it were fastest in theory) is illegal—similar to how a VRP solution skipping a customer is not allowed even if it lowers distance.
• Driver time limits: A driver must drive the car; there’s no swapping drivers in F1. So a “constraint” is that the same driver has to complete the race distance without relief—not usually binding, but in endurance races (other series) there are constraints like “no driver may drive more than 4 hours straight”.
• Car design constraints: These aren’t constraints in the strategy optimization, but they are in the engineering optimization: e.g., engine power must not exceed X, car must meet weight minimum, etc. Those are like design optimization constraints (a separate problem the team solved in the factory).

During the race, constraints like the safety car delta (you must stay above a certain lap time under safety car) or pit lane speed limit also constrain what moves you can make. They ensure fairness/safety, akin to problem constraints ensuring feasibility.

In summary, constraints in both contexts eliminate certain possibilities: A pit strategy that violates tire rules is not valid, just as a VRP route that violates time windows is not valid. Any optimization approach has to navigate these rules. Skilled optimization often involves tight constraints—e.g., binding time windows or capacity—which make finding a feasible (let alone optimal) solution challenging.

Variant (Problem Class Extension)

Many optimization problems come in families of related variants. A variant is essentially a twist on the base problem, introducing new constraints or objectives, or altering assumptions, to model a different scenario. Variants extend the problem class (SciRP, n.d.). They’re important because real-world situations often add complexity beyond the simplest formulation.

The VRP is a classic example: it has spawned dozens of variants:

• Capacitated VRP (CVRP): The basic VRP where vehicles have limited capacity (if not stated, “VRP” usually implies capacity by default in many texts). The base “truck routing” problem typically includes capacity, so sometimes people say “VRP” and mean CVRP.
• VRP with time windows (VRPTW): Adds a time window constraint for each customer. This drastically changes the nature of the problem—a route must not only be short, it also has to schedule within allowed times. This variant is much harder because it combines routing with scheduling.
• VRP with pickup and delivery: Here some goods must be picked up at certain locations and dropped off at others (e.g., think ride-sharing or courier picking up parcels from a depot and delivering to customers). This introduces precedence constraints (pickup must occur before drop-off, and often in the same route).
• Stochastic VRP: Some element (like demand or travel time) is random, and you might want a solution that anticipates that (robust or recourse).
• Dynamic VRP: Requests come in on-the-fly (like real-time).
• …and many more (split delivery VRP, multi-depot VRP, heterogeneous fleet VRP, etc.).

Each variant is essentially a new problem class in itself, albeit related. Researchers often extend algorithms to handle a variant. A “variant” in problem terms is like a new level of the problem family tree: e.g., VRP \(\to\) VRPTW is adding time windows.

From a benchmarking perspective, variants often require new benchmark sets. The best algorithms for one variant might differ from another. For instance, an algorithm great at CVRP might need significant changes to handle VRPTW effectively.

TipFormula 1 analogy

We can compare this to variations in racing or race rules. For example:

• A standard Grand Prix vs. a Sprint race weekend. The sprint is shorter (100 km race on Saturday with no pit stop required by rule). It’s a variant of the race format. Teams might need different strategies (maybe no pit stops at all in a sprint). An optimal solution for a 300 km race isn’t the same as for a 100 km race.
• Wet race vs dry race: The rules introduce a variant when it rains—teams can use wet tires and the tire compound rule about using two dry compounds is waived (so the strategy problem changes). It’s almost like a different variant of the problem because the constraints shift (must use two types of dry tires is removed).
• Different series: F2 vs F1 vs endurance racing—each has its own rules (in endurance, multiple drivers, refueling allowed, etc.). That’s analogous to entirely different problem variants. A strategy that wins in F1 might not even be applicable in endurance racing.
• Another neat analogy: qualifying vs race. Qualifying is a time trial (no need to manage tires beyond one lap, minimal fuel, etc.) whereas a race is a long-haul optimization. Qualifying is like a variant where the objective is pure one-lap time and constraints are different (e.g., you can burn fuel freely in a single lap). Teams treat them as separate optimization problems.

So, variants in both optimization and racing require adjusting the approach. If you’re a “state-of-the-art” solver for the base VRP, you may need to incorporate new techniques for VRPTW. Likewise, a team great at dry setups might struggle in rain until they adapt.

Randomness

Randomness in optimization can refer to two things: 1. Stochastic inputs: the problem data itself might be random or uncertain. 2. Randomized algorithms: the algorithm makes random choices (Monte Carlo methods, random initial seeds, etc.).

In problems: When an optimization problem has uncertainty, we enter the realm of stochastic optimization. For example, demands might not be known exactly and instead have probability distributions (stochastic VRP), or travel times might vary (stochastic or robust routing). In such cases, the objective might be to minimize expected cost or a risk measure, and constraints might need to hold with some probability. This adds complexity because now a solution can’t be just a fixed number—or if it is, we measure how it performs on average or in worst-case. Often people simulate random scenarios to test solution robustness.

In benchmarking and algorithm testing: Even if the problem is deterministic, many heuristics use randomness. For instance, simulated annealing or genetic algorithms start with random solutions and apply random mutations. Even deterministic heuristics might have random tie-breakers. As Hooker (1995) noted, to properly characterize an algorithm’s performance, you often need repeated runs (simulation) to see the distribution of outcomes, not just one outcome (Barr et al., 1995). A single run might be lucky or unlucky, so we use random seeds and average results.

In VRP algorithms, randomness is very common: e.g., a random perturbation in a local search to escape a local optimum, or a random customer order in a constructive heuristic to diversify solutions. Therefore, when benchmarking a stochastic algorithm, it’s standard to run it multiple times on the same instance and report average or best-of-N results, and maybe standard deviations.

Implications: Randomness necessitates statistical thinking. If Algorithm A beats Algorithm B by 1% on average but has high variance, one might wonder if that’s significant or just luck. Statistical tests (t-tests, etc.) can be used, though there are pitfalls there too (p-hacking concerns—more on that later).

Also, some benchmark methodologies incorporate randomness by testing on many random instances drawn from a generator, rather than a fixed set. This can give a broader picture of performance (ensuring an algorithm isn’t tailored to just a few specific instances).

NoteVRP example

Suppose we generate 100 random VRP instances of 50 customers each and run two algorithms on all 100. We might find Algorithm X was better on 80 of those, tying on 10, and worse on 10. This gives confidence that X is generally better, not just on a cherry-picked instance. This is a “statistical benchmarking” approach (Barr et al., 1995) akin to what is recommended by some researchers for robust comparisons.

Another aspect: Monte Carlo simulation might be used within a method (e.g., Monte Carlo Tree Search for VRP, or simulating traffic scenarios). If so, controlling random seeds for reproducibility is important. Good practice is to report whether results are averaged over several runs and if so, how many and the seed management.

TipFormula 1 analogy

Randomness in racing comes from unpredictable events, for example:

• Weather: a forecast might say 20% chance of rain. Teams have to plan for the uncertain event of rain (this is like a stochastic optimization problem—you could optimize expected outcome, or plan a strategy that’s a bit suboptimal in dry but much better if rain happens, etc.).
• Safety cars / crashes: you cannot predict if a safety car will come out, but you can estimate probabilities (maybe historically a 50% chance at certain circuits). Strategy often includes “if safety car comes in this window, do X.” This is almost like a policy that accounts for a random event.
• Driver error or component failure: random from the strategists’ perspective.

Teams often simulate thousands of race variants with random safety car timings to see which strategy yields the best average result or the least worst-case. That is them doing stochastic optimization experimentally.

Also, in testing car setups, teams sometimes introduce random changes (a bit like random search in optimization) to explore the setup space, especially in simulations.

From an analogy perspective: if a team tried one strategy in one race and another in a different race, the outcome difference might not solely be due to strategy but due to random incidents. Similarly, in algorithms, one run’s outcome might differ due to random chance, so you want multiple trials.

In summary, randomness means we deal with probabilities and distributions. It adds a layer of complexity: instead of a single deterministic outcome, we think in terms of expected performance or reliability. Both VRP solvers and F1 teams face uncertainty and must design solutions that are good on average or protect against the worst cases, not just optimize for one fixed scenario.

Solution Approaches and Algorithm Performance Concepts

Once a problem is formulated, we turn to how to solve it or how to measure the quality of solutions. This section covers concepts related to solution methods and performance: what is a policy or decision rule (often relevant in heuristics or dynamic problems), what do we use as a baseline method, what constitutes the state-of-the-art, and what is a best-known solution for an instance. Understanding these terms helps in setting context for new research: e.g., “We propose a new algorithm; we compare it against baselines and SOTA, and we report how close we get to BKS.”

Policy / Decision Rule

A policy (or decision rule) is essentially a strategy that tells an algorithm or agent what action to take in each possible situation (Wikipedia contributors, n.d.b). In static optimization, we usually compute a solution (a set of decisions). But in iterative or dynamic contexts, a policy is the rule that iteratively builds a solution or reacts to changes. The term “policy” is heavily used in areas like reinforcement learning or stochastic optimization (policy for decisions under uncertainty), and “decision rule” is common in decision science (mapping observations to actions).

In the context of heuristic algorithms for VRP, you can think of a policy as the greedy rule or construction heuristic guideline. For example, one of the simplest construction heuristics for VRP is the Nearest Neighbor heuristic: start at the depot, then repeatedly go to the nearest not-yet-visited customer. This is a policy: given the current city, the rule “go to nearest neighbor” decides the next action. It’s a deterministic policy in this case (state = current node & remaining unvisited, action = pick next node by shortest distance).

Another example: Clarke and Wright’s Savings algorithm for VRP calculates a “savings” for combining two routes and then uses a rule to merge routes in descending order of savings. The decision rule there is: “if merging two routes i and j yields the highest remaining savings and is feasible (doesn’t violate capacity), do that merge next”. That’s the policy guiding the algorithm’s sequence of merges.

In more complex or dynamic VRPs, you might have policies for whether to dispatch a new vehicle or wait for more orders, etc. For instance, in an online VRP (new orders come during the day), a policy could be “assign any new incoming order to the currently nearest vehicle if it has capacity, otherwise defer it to a secondary vehicle”. That rule will dictate how the routes evolve in real-time.

Policies also come into play in metaheuristics: e.g., in Ant Colony Optimization for VRP, ants construct routes probabilistically by a rule: “with probability \(p\), choose the next customer based on pheromone trail intensity and distance (some formula)”. That probabilistic rule is a policy (stochastic policy).

From a benchmarking perspective, why discuss policy? Because sometimes instead of comparing whole algorithms, researchers compare decision policies or components. For example, “which routing heuristic is best as a construction policy before applying local search?” Or in learning approaches, one may train a policy (like using reinforcement learning to learn a dispatching policy). So it’s useful to articulate what decision rule is being used.

NoteVRP example (worked)

Consider the split delivery VRP variant for a moment, where you can split a customer’s demand among multiple vehicles.

A policy for constructing a solution might be: “Always fully load one vehicle at a time (fill it until adding another customer would violate capacity, then start a new vehicle).” That’s one decision rule for building a feasible solution greedily. Another policy might be “evenly distribute load among vehicles” (not typical, but just as an illustrative contrast). Depending on the policy, the outcomes differ, and one can test which yields better solutions on average.

Another example is in dynamic ride-sharing: one policy could be “first-come, first-served”—assign each rider to the nearest vehicle as they request. Another more complex policy could be “batch requests over 5 minutes, then solve an optimization for that batch.” These are different strategies (policies) to make decisions. Researchers often test such policies in simulations to see which performs better (like in terms of wait times or distance).

TipFormula 1 analogy

In a race, the team essentially has a race policy/strategy which tells them what to do in various contingencies. For example, a simple deterministic policy: “We will pit on lap 20 for hard tires, unless a safety car comes before lap 20 (then pit immediately under the safety car).” Here the policy has an if-then: if safety car during window, do X, else do scheduled stop at lap 20. Another decision rule might be “if our car is running in clean air, stay out; if we get stuck behind a slower car, pit earlier to undercut.” That’s a state-based policy (state = being stuck behind a slower car, action = pit early).

Drivers themselves have policies: e.g., “don’t fight your teammate if he’s faster” might be a team policy (mapping state: teammate approaching, to action: yield position).

In F1, policies can be adaptive: an example is fuel saving strategies—some teams have a rule “if gap > 5s to car behind, go into fuel-save mode” to ensure finishing the race with enough fuel. That’s essentially a threshold policy.

The reason to formalize these is that increasingly in racing (and other fields) people use algorithms to optimize or even learn these policies (like AI coaches etc.). The better the decision rule, the better the outcome.

To link back to optimization benchmarking: if someone develops a new policy for a known problem (say a new dispatch rule for dynamic VRP), they will compare it to baseline policies. This is analogous to comparing algorithms, but at the level of strategy rather than final solution quality.

Baseline

A baseline is a reference point used in experiments to ground the results. In optimization, a baseline is often a very simple or previously published method that is easy to implement or widely known (Envisioning Vocab, n.d.). It might not be the best, but it’s something to compare against to show improvement. The baseline sets a minimal level of performance that you’d expect any new approach to reach.

Why baselines? Because if a fancy algorithm cannot even beat a naive approach, then it’s probably not useful. Baselines help sanity-check. They are also useful for context: readers may not know how good a new algorithm’s cost “1230” is, but if you say “for context, a greedy nearest neighbor heuristic gives 1300 on the same instances”, then they know 1230 is better by X%.

Common baselines in VRP include:

• Nearest Neighbor heuristic: a quick greedy approach. It’s often a decent but not great solution. If a new algorithm can’t beat NN, that’s a red flag.
• Clarke-Wright Savings: a classical heuristic from 1964; often used as a baseline for CVRP because it’s well-known and very fast.
• Random solution: sometimes a completely random route (or random permutation of customers assigned to vehicles sequentially) is used as a worst-case baseline. It usually has a horrendous objective value, but it gives a frame (like “our method is 50% of the cost of a random assignment”).
• Human/planning solution: in some applied papers, what the company’s manual planning achieved is used as a baseline.
• Simplified version of the new method: e.g., if you propose a two-phase algorithm, you might baseline against using only phase 1 without phase 2, etc. (This crosses into ablation territory as well.)

Baselines can also be previous generation algorithms. For example, if writing a paper in 2025, one might use a known heuristic from 2010 as a baseline. It’s known not to be state-of-the-art, but it’s a reference point to see how far things have come.

In terms of metrics, a baseline might yield a solution say 10% worse than the best-known. If your new method is 2% within best-known, that is a huge improvement over baseline. Or maybe baseline runtime is 1 second, your method is 10 seconds—then one comments on the trade-off.

One has to choose baselines wisely: too weak and it’s meaningless (“my algorithm beats doing nothing”—not impressive), too strong and you might struggle to show improvement (though one should try to beat strong baselines eventually).

From the connected sources: baselines are described as simple methods using heuristics or basic models (Envisioning Vocab, n.d.), and their purpose is to be a reference point. A quote: “Serving as a standard point of comparison, baseline helps researchers and practitioners assess the performance gains achieved when new models are developed.” (Envisioning Vocab, n.d.).

NoteVRP baseline example

If we develop a new metaheuristic for VRP, we might compare against:

• Baseline 1: Clarke-Wright (deterministic outcome, say cost = 1200 for instance X).
• Baseline 2: a simple Genetic Algorithm from the literature (known approach, cost = 1150 for instance X).
• Our method: cost = 1100 for instance X.

By showing these, we indicate our method improves beyond the trivial solution (CW) and even beyond a known GA, setting a new mark.

Another baseline could be an MILP solver with a very short time limit. For example, “we let CPLEX run for 60 seconds (a baseline exact approach) and it found a solution of cost 1130; our heuristic finds 1100 in the same time.” That compares against an exact baseline under limited resources.

TipFormula 1 analogy

Baselines in racing might be:

• Lap time of the previous car model (last year’s car). If the new car isn’t at least as fast in testing, that’s worrying.
• A simple strategy like “no pit stop” (if it were allowed) or “one-stop at halfway” can be a baseline strategy. More complex strategies should outperform it in simulation.
• The performance of the worst team could even serve as a baseline (though usually everyone wants to beat that by default).

Specifically, imagine a new aerodynamic upgrade: the baseline is the car without the upgrade. They test: Car without upgrade laps in 1:35.2, with upgrade laps in 1:34.8. So baseline was 1:35.2, new is better by 0.4s. If it was worse, that upgrade would be trashed.

In strategy terms: one might consider a baseline strategy like “never use soft tires because they wear quickly”—maybe it’s not optimal, but it’s simple. If a fancy strategy that micromanages tire usage doesn’t beat the baseline of just using hards and one-stop, then all that fancy work was pointless.

So, just as in algorithm development, F1 teams have baseline configurations and strategies (often based on prior experience or simplest assumptions) and then try more elaborate ones, always checking if the complexity actually yields an improvement.

State-of-the-Art (SOTA)

The state-of-the-art refers to the best known performance or technique in the field at present. If something is “SOTA,” it is currently unsurpassed by competitors on the agreed metrics. Researchers strive to either match or exceed the state-of-the-art. It’s a moving target: as soon as someone publishes a better result, the SOTA is updated.

In optimization problems like VRP, there can be SOTA algorithms and SOTA results:

• SOTA algorithm: the algorithm that currently yields the best results (e.g., lowest costs) on average or on a benchmark set.
• SOTA result/solution: the best known solution or record for a specific instance or set.

Often, SOTA implies the best algorithm overall. In practice, SOTA is benchmark-dependent: a method can look SOTA on one instance suite and merely competitive on another. For example, CVRP results are commonly reported on suites like Uchoa et al. (2017), while VRPTW results are often reported on Solomon’s instances (Solomon, 1987).

We identify SOTA by comparing all known methods. If algorithm A consistently gives the lowest total distance on standard benchmarks (and within reasonable time) compared to all others in literature, we crown it SOTA.

In practice, when writing a paper one would say: “We compare against the state-of-the-art: algorithm X by So-and-so (2022), which currently has the best published results on this benchmark.” Then your new results might show improvements. If you beat the SOTA, you typically claim a new SOTA.

However, caution: sometimes SOTA might refer to best published results, but there could be unpublished or very new results you missed. So authors often phrase “to the best of our knowledge, this is state-of-the-art.”

From the earlier reference, we saw an example caption where “The state-of-the-art algorithm was the best performing system in [the evaluation]…” (ResearchGate, n.d.). That exemplifies that by definition SOTA = best performing system.

In VRP, because there are numerous variants and even within one variant different instance types, SOTA might be segmented. For example, one algorithm might be SOTA on random uniform instances, another on clustered instances. Or one is SOTA for large instances, another for small (especially if exact vs heuristic). So SOTA can be context-specific.

Nevertheless, generally there’s an understanding of which method is top-performing overall. Literature reviews or survey papers often identify the SOTA.

NoteVRP SOTA example

A practical way to interpret “SOTA” in CVRP is: does your method reliably match or improve BKS values on standard instance suites (under a fair protocol)? On the heuristic side, names you will often encounter include LKH3¹ and ALNS-style methods². If a new algorithm repeatedly improves BKS values (and releases solutions so others can verify), it is reasonable to describe it as setting a new state-of-the-art for that benchmark. We might cite results like: Algorithm Y improved 20 out of 100 best-known solutions in the benchmark, thus establishing a new state-of-the-art.

² Adaptive Large Neighborhood Search (ALNS) is a ruin-and-recreate metaheuristic with adaptive operator selection Ropke & Pisinger (2006).

¹ Lin–Kernighan is a classic variable k-opt local search originally proposed for the Traveling Salesman Problem (TSP) Lin & Kernighan (1973); Helsgaun’s LKH family is a widely used implementation Helsgaun (2000).

Another dimension is SOTA in runtime vs SOTA in solution quality. Sometimes an algorithm might give slightly worse solutions but 10x faster—is that SOTA? Possibly in practical terms, yes (if we care about speed). So SOTA can also be qualified: e.g., “for large-scale VRP with 10,000 customers, heuristic A is SOTA in finding feasible solutions quickly, whereas heuristic B is SOTA in solution quality but slower.”

TipFormula 1 analogy

State-of-the-art in F1 is basically the top team/car of the moment. For instance, the Mercedes W11 in 2020 was state-of-the-art—it dominated, had the best lap times of any car that season (and arguably in history up to that point under those regulations). Red Bull RB19 in 2023 is SOTA. If another team develops a better car and starts winning consistently, they’ve set a new SOTA in car design.

We can also talk about SOTA strategies—though that’s less commonly phrased that way. But you could say, for example, “the current state-of-the-art pit strategy is a two-stop strategy in most races, as that has proven to yield the best average results given tire performance.” If a team finds an innovative one-stop that beats others at some tracks, that becomes the new SOTA approach for those conditions.

Lap records are another form: the outright lap record at a circuit is the SOTA lap performance on that track (under whatever conditions it was set). It’s literally the best achieved so far. Next year’s cars will try to beat it, and if they do, that’s the new record (new SOTA performance on that track).

In summary, SOTA is a benchmark for “the best we have achieved to date.” In research, achieving SOTA results is a big deal because it means you’ve advanced the field. In F1, being state-of-the-art means you’re winning championships.

Best Known Solution (BKS)

The Best Known Solution (BKS) is a term commonly used in combinatorial optimization, especially in the context of hard problems like VRP, TSP, etc., when referring to specific instances. It means exactly what it says: the best solution (optimal or not) that is known so far for that instance (“The neurobench framework for benchmarking neuromorphic computing algorithms and systems,” 2025).

If an instance’s optimum is unknown (which is often the case for large NP-hard problems), the BKS is effectively the target for others to match or beat. If someone later finds a better solution, that becomes the new BKS.

In VRP benchmarks, authors maintain tables of BKS values (and sometimes also the solution routes themselves). For example, for each instance in the Solomon VRPTW set, you might see a table: “Instance R101: Best known = 1650.8 (with 20 vehicles)”. If a new algorithm finds a solution of cost 1649 with 20 vehicles, that’s a new best known and would be noteworthy.

It’s common to see papers say “we improved the BKS for 3 instances out of 100; for the rest, we matched the BKS.” Improving a long-standing BKS is significant—it means a new record low cost.

However, note that BKS doesn’t necessarily imply an algorithm is generally better; it could be that by chance or by heavy computation one instance’s record fell. So one also looks at overall performance, but BKS is a nice concrete achievement.

Often BKS are obtained by, for example:

• Running a heuristic or metaheuristic for a very long time.
• Using an exact solver with a lot of computing power or clever techniques.
• Human experts sometimes (less so now, but historically someone might manually tweak a TSP tour to improve it slightly).

Sometimes we discover later that what was thought to be best known was actually optimal (when an exact proof is attained). Then it’s not just BKS but actually optimal.

The source we found described how a best known solution is often found by a high-powered solver given a lot of runtime (“The neurobench framework for benchmarking neuromorphic computing algorithms and systems,” 2025). In other words, BKS often comes from either very powerful (and possibly impractical) methods or luck. They serve as a benchmark for algorithm performance comparison.

For VRP, researchers maintain websites like CVRPLIB, etc., where current BKS values are listed for famous instances. These are community records.

Interplay with SOTA: SOTA algorithms are usually the ones that consistently hit or beat most BKS on a set. But an algorithm might not be SOTA generally yet it found one new BKS by chance. So BKS can be instance-specific bragging rights.

NoteVRP BKS example

In Uchoa et al. (2017), the authors introduced a widely used suite of CVRP instances. Their best-known solutions (BKS) are tracked (and updated) in CVRPLIB (CVRPLIB, n.d.).

If someone writes a new paper on CVRP, they will test on those instances and report how close they get to those BKS, or if they improved any. It’s common to report something like “average gap to BKS = 0.5%” for a heuristic.

As an example, let’s say instance X has BKS cost = 500. If your algorithm finds 500 too, you hit BKS (gap 0%). If you find 505, your gap is +1%. If you somehow find 495, then 495 becomes the new BKS (and you should report that proudly, and usually provide the solution so others can verify it and use it moving forward).

TipFormula 1 analogy

A BKS in racing terms is akin to a track record or perhaps a season record. For example, the fastest lap ever at Suzuka Circuit (under race conditions) is a specific number. That is the best known performance on that “instance” (Suzuka on a particular day, etc.). In racing, conditions differ year to year, so track records can be broken when conditions are better or cars improve.

Another example: the longest distance traveled in a 24-hour Le Mans (in miles) is a record (which could be considered a best known achievement for that “instance” of a 24-hour race under certain weather). Teams aim to beat that distance if possible in subsequent years, analogous to beating a BKS cost.

In a way, each Grand Prix circuit each year is an “instance,” and the lap record is the BKS for that instance. The pole position time each year might be like the solution found by the fastest “algorithm” (team/car). The absolute record across years is the all-time BKS.

However, in racing, regulations change, so it’s not a perfect analogy (whereas in VRP, the instance stays the same so comparability is direct). But we can still say: if in 2018 the lap record was 1:30.5 and in 2019 a car did 1:30.1, that 1:30.1 is new best known performance for that track. Everyone is then aware that to be the fastest ever, they need <1:30.1.

If we take an analogy at a micro level: suppose an F1 team simulator predicts the theoretical best pit strategy would result in a race time of 1h30m10s for a given race, and the team achieves 1h30m15s. The best known “solution” (maybe the theoretical optimum) is 1h30m10s; the team was 5 seconds off. If another team managed 1h30m05s (maybe due to a timely safety car, etc.), they achieved an even better outcome (though in reality cross-team comparisons are complicated by different cars etc.). But if we focus purely on strategy, one might say “Team Alpha’s strategy yielded a finishing time only 5s off the theoretical optimum, that’s basically the best known for this scenario.”

So conceptually, both fields chase best known achievements—be it lowest cost or fastest time. Those best known become targets for the next competitor or algorithm to aspire to.

Benchmarking and Evaluation: Methodology and Pitfalls

After formulating the problem and developing solution methods, we need to benchmark algorithms—i.e., evaluate them in a systematic way to understand their performance. This section covers what benchmarks are and why they’re used, the difference between using simulation vs. exact methods for benchmarking, the choice of Key Performance Indicators (KPIs) to measure success, and how to properly conduct tests (including pilot studies, tuning, and held-out evaluations). We also discuss experiments like ablation studies to validate contributions of algorithm components, and caution against p-hacking and overfitting—which can mislead benchmarking results if not guarded against.

Benchmark (Definition and Role)

In optimization research, a benchmark is essentially a standard set of test cases and evaluation criteria that the community agrees upon for comparing algorithms (ResearchGate, n.d.). The role of a benchmark is to provide an objective, fair ground for assessing how good an algorithm is relative to others. Good benchmarks have several characteristics:

• Representative of relevant problems (so results generalize to real needs).
• Public and consistent: everyone uses the same instances and conditions, so results are directly comparable.
• Some known references: often benchmarks come with known best solutions, or at least baseline results from existing algorithms, so one can tell if a new result is competitive.

For example, in VRP, the Solomon 1987 VRPTW instances and Boyd’s 2003 1000-node instances are common benchmarks. Researchers testing a new VRPTW algorithm will almost certainly include the Solomon set in their experiments. This allows readers to compare the results with prior papers that also used Solomon’s instances. If someone else in 2020 made a table of results on these instances, and now your 2025 algorithm shows better numbers in a new table, it’s clear advancement (assuming the comparison is fair).

Benchmarks often evolve: if algorithms get so good that they all get very close to optimal on existing small benchmarks, the community might introduce larger or more complex instances to further differentiate methods (essentially raising the bar). As noted by Barr et al. (1995), accessible libraries of standard test problems are essential for fair benchmarking—without agreed benchmarks, everyone tests on different problems and comparisons become meaningless. This led to resources like TSPLIB (Reinelt, n.d.) and CVRPLIB (CVRPLIB, n.d.), which are public repositories of instances.³

³ TSPLIB focuses on Traveling Salesman Problem instances; CVRPLIB focuses on Capacitated VRP instances and commonly reports best-known solutions (BKS).

Another component of benchmarking is having standard metrics. For example, in VRP benchmarks, we typically report total distance and number of vehicles used (if variable) and computational time. If someone reported, say, fuel consumption or CO2 emissions instead, it would be hard to compare unless a conversion is given. So agreeing on metrics (KPIs) is part of benchmarking.

Benchmarking studies sometimes also involve aggregating results over sets (like average percentage above best-known across 100 instances, etc.). There are even frameworks to statistically analyze performance across many instances (e.g., the Wilcoxon signed-rank test⁴ to see if one algorithm is significantly better than another across a set).

⁴ A non-parametric paired test used to compare two methods across many instances without assuming normality.

To illustrate the role: A benchmark is like a referee. Instead of an author saying “my algorithm is great on problems I generated myself,” the benchmark says “okay, prove it on these known standard problems that everyone else has tried.” It forces a level playing field and often exposes strengths and weaknesses of algorithms (maybe algorithm A does well on clustered customer instances but poorly on random ones—a diverse benchmark will show that pattern).

NoteVRP specifics

The CVRP has had multiple benchmark sets over time (e.g., early instances from Christofides, Mingozzi, & Toth (1979), the “Golden” instances distributed via CVRPLIB (CVRPLIB, n.d.), and the more recent suite introduced in Uchoa et al. (2017)). Each time, when a new set comes, researchers test old algorithms on it to establish baseline, then new ones try to beat those. It drives progress. If an algorithm is overfit to one benchmark, a new benchmark can reveal that (suddenly it may underperform, indicating it was specialized to the old set). This happened historically—e.g., some heuristics were tuned to a set of 50-customer instances; when 1000-customer benchmarks came, they didn’t scale well.

TipFormula 1 analogy

In a sense, F1 has benchmarks too. The most direct analogy is the pre-season testing sessions. They occur on known tracks (Barcelona has been a common test track). All teams run their new cars there. It’s not an official race, but it benchmarks performance—people compare lap times, reliability, tire degradation. It’s not perfectly controlled (fuel loads can differ, etc.), but it gives an idea of the car ranking. Barcelona is the benchmark track because it’s well-rounded (fast, slow corners mixture). A team that is fastest in Barcelona testing is “benchmarking” themselves as likely the fastest car generally.

Additionally, in-season, teams use certain reference points: for example, Silverstone and Barcelona are tracks where if your car is good, it’s considered generally good (like a broad benchmark). Monaco is a specialty track—doing well there doesn’t guarantee overall performance. Similarly in optimization, a single instance or single type might not tell full story—so we prefer a suite of instances for a robust benchmark.

Even within a race weekend, free practice sessions serve as benchmarking opportunities—teams test race pace in FP2, qualifying pace in FP3 perhaps, and compare those times as benchmarks to gauge if their setup changes improved the car relative to others (who are all testing under similar conditions).

One more analogy: the F1 Power Unit test bench. Engine manufacturers test their engines on a dynamometer (test bench) measuring horsepower, fuel efficiency, etc., under standardized conditions. Those are internal benchmarks: e.g., “this year’s engine yields 1000hp at 13,000 rpm which is 20hp better than last year’s”—that’s benchmarking the new design versus the baseline (last year) in a controlled environment.

So, whether in OR or F1, benchmarking means setting up standard conditions to measure performance in a way that can be compared fairly over time or across competitors.

Simulation vs. Exact Method Benchmarking

When evaluating algorithms (especially heuristics for hard problems), there are different methodologies. Two common ones are:

• Simulation (practical) benchmarking: Test algorithms in conditions close to real-world or under dynamic/stochastic scenarios, often using simulation models. The emphasis is on practical performance: does the algorithm still work well when reality is messy? Can it handle on-the-fly changes? Simulation can also refer to empirically testing runtime and solution quality on many instances (not an analytical performance proof, but observed behavior) (Barr et al., 1995). As Hooker (1995) argued, simulation can help characterize algorithm performance beyond just the final answer (e.g., quality over time, sensitivity to input changes) (Barr et al., 1995).
• Exact-method benchmarking: Use exact optimization methods (like Mixed Integer Programming solvers, branch-and-bound, etc.) on smaller instances to get optimal solutions, and then see how close a heuristic gets to that optimum (“The neurobench framework for benchmarking neuromorphic computing algorithms and systems,” 2025). It provides a gold standard for solution quality. If the instance is small enough (or time limit generous enough) that an exact method can find an optimum (or a very tight lower bound), then any heuristic solution can be evaluated by gap = (heuristic - optimal)/optimal * 100%. This is a very concrete way to measure quality.

Simulation benchmarking in VRP: Suppose we want to benchmark how a VRP algorithm would perform for a delivery company in practice. We might simulate a series of 5 random days of deliveries, where each day’s customers are randomly generated with certain spatial patterns, demands, maybe some orders cancel last-minute, etc. We then deploy our algorithm in this simulation and measure outcomes (total miles, late deliveries, computational time available vs used, etc.). We could also simulate traffic conditions to see if the algorithm can re-route quickly. This kind of test answers questions like “Would this algorithm actually save cost in a real company scenario? Does it handle uncertainties?” It’s less about matching a known optimum and more about robustness and practical impact.

In a research paper context, simulation might also mean: measure algorithm performance statistics by running it many times (with different random seeds or instance variations) to assess average behavior, not just on a few fixed instances.

Exact benchmarking in VRP: We take a benchmark instance, say with 50 customers, and solve it to proven optimality using a MILP solver or specialized exact algorithm. Now we have the optimal total distance =, say, 530. Our heuristic finds a solution of 545. We calculate gap = (545 - 530)/530 = 2.83%. We do this for a set of instances, and maybe report average gap = 3% for our heuristic. This is a powerful evaluation because it directly tells how close to optimal we are. It also allows ranking heuristics: if another heuristic has average gap 5%, ours is clearly better in quality.

However, exact benchmarking is limited to instances small enough to solve (or if not fully solve, at least get a very good lower bound). On larger instances where exact methods can’t finish, we rely on best known (BKS) as the reference instead of true optimal.

Often, papers will do both: use exact comparisons on small instances, and use BKS or heuristic-to-heuristic comparisons on larger ones.

Time benchmarking: Another angle: sometimes an “exact method baseline” refers to giving an exact solver the same time as a heuristic and seeing what it can do. For instance, “in 60 seconds, Gurobi finds a solution of cost X (maybe not optimal yet), while our heuristic finds Y (hopefully better or same) in 60 seconds.” This is a fair comparison of a heuristic versus an exact approach under time constraints.

Competitions (like ROADEF, EURO, etc.) often have a simulation component nowadays. For example, in some routing competitions, solutions were tested in a simulation environment with uncertain demands or with interactive decision processes. That forces algorithms to be not just static optimizers but responsive policies. It’s a very practical benchmark method.

From the references, we saw mention that simulation can be a way to do descriptive experiments (understand algorithm behavior) (Barr et al., 1995), whereas pure competition on final results is just one aspect. Also the nature.com piece basically outlined that a best-known solution (like from an exact solver given lots of time) can serve as the target for evaluation (“The neurobench framework for benchmarking neuromorphic computing algorithms and systems,” 2025)—that’s exactly using an exact method’s result to benchmark heuristics.

TipFormula 1 analogy

This is an interesting one.

Simulation benchmarking (racing). Teams use simulators to try out strategies and car setups. This is akin to testing an algorithm in realistic scenarios. For instance, before a race, a team might simulate 1000 possible race scenarios (varying safety car timings, weather, etc.) for both Strategy A and Strategy B. If Strategy A yields an average finishing time 5 seconds better than B over those scenarios, they conclude A is better. This is benchmarking strategies via simulation. It’s not “exact” because races are too complex to solve optimally (and have randomness). But through many simulations, teams estimate which strategy is superior—analogous to empirically testing heuristics on many random instances to see which one performs better on average.

The use of digital twins and simulations in F1 is also huge: e.g., teams simulate a new aerodynamic part’s effect in a CFD (computational fluid dynamics) simulation (like a wind tunnel simulation) to benchmark its improvement in downforce or drag.

Exact benchmarking (racing). There’s no direct “exact solver” for a race, because a race is a continuous dynamic system with many variables and some uncertainty. But theoretical limits can act as an “exact-ish” reference: for example, the theoretical optimal lap (given physics, what’s the fastest possible lap time if everything were perfect). If a driver’s lap is 1:21.046 and simulation says the car could theoretically do 1:20.500 in ideal conditions, then the driver’s lap is 0.546 seconds off the theoretical best. Teams often do this analysis in qualifying: “Given our car’s simulations, the best possible was X, our driver did Y, so he was 0.2s from the car’s limit.” That’s akin to a gap to optimum.

Another exact-ish reference could be using linear programming for simplified race models. For instance, one might formulate an LP for tire usage to see what’s the absolute minimum time possible in a simplified setting (this might not be realistic, but provides a lower bound on race time).

In summary

• Simulation benchmarking is about realism: test in a virtual/empirical environment that mimics real conditions to see practical performance.
• Exact benchmarking is about optimality: compare against the best possible (in a simplified scenario) to measure how far off you are.

Both are valuable. In research, a mix of both is ideal: you want to know if your algorithm is near-optimal on what it can handle (exact comparison), and also know that it works in messy scenarios (simulation).

Key Performance Indicators (KPIs)

When we conduct experiments or real-world operations, we need metrics to judge performance. Key Performance Indicators (KPIs) are those metrics most relevant to the goals (Klipfolio, n.d.). In optimization algorithm benchmarking, typical KPIs include:

• Solution quality: e.g., objective function value of the solution (distance, cost, etc.). Often measured relative to something (percent above optimum or BKS).
• Computational time: how long the algorithm took (CPU seconds, wall-clock time). Sometimes also memory usage, etc., if relevant.
• Reliability / success rate: for stochastic algorithms, maybe the fraction of runs that hit the optimum or a certain threshold.
• Stability: standard deviation of solution quality over runs (if the algorithm is randomized, do results vary a lot or are they consistent?).

In a broader sense, if we were benchmarking not just the algorithm but an implementation, KPIs could include things like ease of use, but let’s stick to quantitative ones.

For VRP specifically, typical KPIs include:

• Total distance / total cost of routes (or number of vehicles if minimizing vehicles is part of the objective). If an algorithm finds shorter routes, it’s better.
• Constraint violations (when relevant): if there are constraints like time windows, one might measure the number of violations when using heuristics that allow temporary infeasibilities during search.
• Computation time (speed): crucial especially for real-time or large-scale settings. Sometimes one draws a trade-off curve: solution quality vs computation time (like a Pareto front of that trade-off).
• Optimality gap (derived): % over optimal/BKS. It’s a nice normalized measure to compare across instances of different scale.
• Scalability: how does runtime grow as number of customers grows? (This is more of an analysis than a single metric, but it can still be operationalized as “solves instances of size X within Y minutes”.)

In academic benchmarking, we often present tables of results per instance, then summary KPIs like average gap, best/worst-case, etc. We might also use performance profiles (cumulative distribution of how many instances solved within certain gap, etc. - as proposed by Dolan & Moré for benchmarking).

KPIs should align with what matters in practice. For instance, if one algorithm is 0.5% better in distance but takes 2 hours, and another is 1% worse but takes 2 minutes, depending on the use case, one KPI (time) might matter more than that small difference in distance. So sometimes a multi-criteria evaluation is needed. In research papers, they might primarily focus on solution quality if comparing heuristics that all run within some time limit (time is secondary since all are “fast enough”). But if one algorithm is much slower, they’ll note that too.

Also, memory usage or ease of implementation could be a KPI in some cases (especially in competitions or commercial evaluation), but in research papers, those are rarely quantified.

In (ResearchGate, n.d.), the authors track multiple metrics in a different domain; the same idea applies in optimization benchmarking: define and report KPIs explicitly. Similarly, in VRP one might consider multiple aspects: distance, vehicles, maybe “service level” (if some deliveries missed or delayed, in a more complicated scenario).

If benchmarking algorithms that produce not just one solution but maybe a set (like Pareto front in multi-objective), KPIs might include coverage of Pareto front, etc. But let’s keep it single-objective for simplicity.

TipFormula 1 analogy

KPIs for a team might be:

• Lap time (single-lap pace)—crucial for qualifying.
• Race pace / average lap time during a stint—crucial for the race.
• Tire degradation rate—how many seconds per lap do you lose as tires wear? A big performance indicator for strategy.
• Pit stop time—a measurable KPI for pit crew performance.
• Reliability—number of mechanical failures or DNFs (0 is ideal).
• Points scored—ultimate KPI over a season (because that’s what wins championships).
• Budget adherence (since budget cap)—a KPI for management.

During a race, teams have live KPIs like gap to car ahead/behind, fuel remaining, etc., but those are tactical. Strategic KPIs are like average points per race, etc.

When teams compare upgrades, they use KPIs: e.g., “this new rear wing gives +15 points of downforce (KPI) at cost of +5% drag (another KPI).” They have to decide if that trade-off is worth it given track type (some tracks favor downforce, others low drag).

In an F1 broadcast, one might see a graphic: “Team A vs Team B—pit stop average: 2.5s vs 2.8s, straight-line speed: 330 km/h vs 335 km/h, tire wear: -0.1s/lap vs -0.15s/lap.” These are KPIs being compared. Ultimately, finishing position is a function of many KPIs (car speed, reliability, pit efficiency).

Analogous to optimization: solution quality is a function of algorithm’s search effectiveness (like car speed), and runtime is like resources used (like fuel or tires). If an algorithm was a car, quality is how quick it finishes (like race time) and runtime is how much “effort” or “fuel/computation” it burned. We want a good balance.

In summary, KPIs are how we measure success. Without clear KPIs, you can’t rigorously say one method is better. In optimization, the objective function value is always a KPI (since that’s what we ultimately care about solving), but practical considerations add others like time. In F1, winning is the objective, but many performance indicators feed into that.

Tests: Pilot, Tuning, and Held-out Evaluation

When performing computational experiments or any empirical study, it’s crucial to structure testing properly:

• Pilot tests: preliminary runs (not for final analysis) to ensure everything works and to get a rough idea of outcomes. A pilot might reveal, for example, that your parameter ranges are way off (algorithm always fails or is too slow). You might do a pilot on a handful of instances to decide time limits, or to see if you need to adjust your code or experiment setup.
• Tuning (validation) phase: adjust your algorithm’s parameters (hyperparameters) to achieve best performance. Importantly, tuning should be done on a separate set of instances (or via cross-validation techniques) distinct from the ones you will report final results on (OpenReview, n.d.). Otherwise, you risk overfitting your algorithm to the test instances. The tuning set can be thought of as “training data” for the algorithm’s configuration.
• Held-out test: final evaluation on data that was never used in development (OpenReview, n.d.). This gives an unbiased assessment of how the algorithm performs. If during tuning you inadvertently looked at the test results and tweaked things accordingly, then it’s no longer held-out—that leads to overfitting. Many competitions or papers inadvertently “train on the test” by repeatedly testing on the benchmark and tweaking; eventually, the algorithm may become specialized to those benchmark instances, which is why it’s recommended to (at least mentally) separate a portion as unseen.

For example, you might have a parameter like “how many iterations to run” or “what penalty weight for constraint violations.” You try different values on the tuning set, pick what gives best average result there. Some sophisticated approaches use automated parameter tuning (like algorithm configurators, e.g., IRACE, SMAC, etc.) on a training set of instances.

In academic practice for OR, often the benchmark instances are actually known in advance (like Solomon instances, etc.). Everyone kind of tunes to them over time (this is why performance creeps up, a form of “overfitting to benchmarks”). One remedy is if new benchmarks appear unexpectedly, to see if methods generalize. Another partial remedy is to use cross-validation style: partition instances into a few sets, tune on one, test on another, and rotate. But in OR this is not done as often as in machine learning, possibly because instance sets are smaller and hand-crafted.

Nevertheless, some recent papers do explicitly separate a set for tuning. For example, they might pick 5 instances out of 25 as a validation set to calibrate parameters, then report results on the other 20 (untuned for those specifically).

Also, statistical tests often assume the test set was not used to make decisions. If you tune on the test set, classical statistical significance tests on improvement are invalid (you’ve biased things).

A common warning: having full access to holdout (test) data and making many attempts effectively trains on it. Ideally, holdout performance should only be evaluated once or at most a small number of times—in practice, researchers do iterate, but the less the better.

Pilot example (VRP): Run your algorithm on 2 small instances for 10 seconds to see if it produces a feasible solution, check if any obvious bugs (like routes violating capacity) occur. Maybe you realize you forgot to handle something because a pilot run threw an error or gave a crazy solution. Then fix it.

Tuning example (VRP): You have a Tabu Search with parameters: tabu tenure, number of iterations, etc. You select 5 representative instances (say small, medium, large, and different customer distributions) as tuning set. You systematically try tenure = 5, 10, 15,... and see which gives best average result on them. You find 10 is best compromise. You fix tenure=10 for final algorithm. Now you run final algorithm on the full benchmark (which might include those 5? Ideally exclude them now or at least the tuning means the final results on those 5 are biased high). In absence of separate test, some might report results on all including the tuned ones but note that parameters were tuned on them—which isn’t ideal but at least transparent.

Held-out in OR example: Some competitions like the PRPlib (pickup and routing problems library) hide some test instances. Participants tune on provided ones, and then their algorithm is run on secret ones for final score—that mimics held-out testing.

Why this matters: If you don’t do this separation, you risk overfitting (which we discuss later). An extreme example: you could fine-tune your algorithm specifically for each test instance (like manually or via some automated huge search). It will do great on those, but that proves nothing about general algorithm quality; it just memorized those instances. This is analogous to machine learning where a model can memorize the training data and get 100% accuracy there but fail on new data.

As Hooker (1995) argued, algorithm testing needs to be more scientific. Part of that is not fooling ourselves by over-tuning to known instances. He argued for generating random instances to test algorithms (which is a form of held-out, since you’d generate new ones that algorithm wasn’t specifically tuned to) (Hooker, 1995).

TipFormula 1 analogy

• Pilot tests in F1: When a team builds a new car, the very first run (like a shakedown at a filming day or first lap in testing) is a pilot—they check systems, not aiming for performance but to see if everything works (no leaks, brakes work, etc.). They might run at half speed just to gather initial data. This is analogous to pilot experiments to ensure your algorithm runs without crashing and yields a feasible solution.

• Tuning in F1: Absolutely critical. Practice sessions (and even simulation before that) are essentially tuning the setup (suspension settings, wing angles, engine mapping) for that specific track. The team knows the “test” (the race) conditions somewhat (track, weather forecast). They try different setups in practice (like algorithm tries parameter sets on tuning instances) and see lap times and tire wear (the KPIs). They find an optimal setup through this search—that’s them tuning to the “problem instance” of that race.

However, consider a longer term: A team designs a car before the season (that’s like developing an algorithm before knowing specific instances). They have to guess a setup baseline that works across many tracks. They might optimize certain parameters via simulations using historical data (like algorithmers tune parameters using a set of instances from past years). Then for each new race (new instance), they fine-tune (like hyperparameter adjustment) in practice.

• Held-out analogy: In F1, you don’t really have “hold out” in the same way, because the race itself is the test that matters. They do tune on the actual track during practice (so not exactly a separate dataset). But once qualifying is done, for parc fermé, they can’t change setup for the race—the race is then a bit of a held-out test for how the setup performs under different fuel and long runs. Sometimes teams find they over-optimized quali at expense of race (overfitting to one scenario).

A clearer analogy: think of a team that runs many simulations in winter on tracks A, B, C to optimize car design. Then the first time they run on a new track D without prior testing is like held-out—will their design generalize? For example, Brawn GP in 2009 did minimal wind tunnel (due to resources) but aced the first races—their concept was generally strong (generalizable). Other teams sometimes focus on known weaknesses in last year’s car (i.e., “train” on last year’s issues), but a new rule or track might expose a different weakness that they didn’t tune for.

Another analogy: in-season, there’s a limit on testing. So teams cannot test unlimitedly on all tracks (no unlimited practice—that’s like limiting how much you can tune on test set). They must rely on prior knowledge and simulation (like training and validation) and then perform on race day.

In summary: The principle of separating tuning and final testing applies widely: whether it’s algorithms or race setups, if you optimize too specifically to the data you have, you might not do well on new data. In ML and OR, we enforce that by holding out test sets. In F1, they face it by not having infinite practice and encountering varied conditions—the team that adapts best without over-committing to one scenario tends to succeed (like designing a car flexible enough for all tracks vs optimizing for just high-speed tracks).

Ablation and Addition Studies

When an algorithm or system has multiple components, ablation studies are used to understand the contribution of each component (Wikipedia contributors, n.d.c). In an ablation study, you “ablate” (remove or disable) one component at a time and see how performance changes. This helps answer questions like: Did the new local search routine I added actually improve results, or was it the other component that did?

If an algorithm is a combination of ideas A, B, and C, one can test:

• Full version: A+B+C.
• Ablate A: run with B+C only.
• Ablate B: run with A+C only.
• Ablate C: run with A+B only.
• Optional: ablate combinations for thoroughness.

By comparing the outcomes (e.g., solution cost or runtime), you can quantify the impact of each part. If removing component A causes a big drop in performance, A is important. If removing C makes little difference, maybe C wasn’t that useful after all (or its effect overlaps with others).

Addition studies are like the inverse: you might start from a simple baseline and add components one by one to see improvement. For example: start with a greedy algorithm (baseline), then add local search \(\to\) see improvement, then add adaptive tuning \(\to\) see further improvement, etc. This constructs a picture of how each feature contributes incrementally.

These studies provide evidence to back up claims like “our novel component X improves the results by 5% on average”—you would only know that by comparing with/without X under controlled conditions.

It also helps guard against “piling on techniques” without understanding them. Sometimes researchers throw many heuristics together; an ablation can show that some of those aren’t needed or perhaps even hurt slightly.

From the Wikipedia reference, “An ablation study aims to determine the contribution of a component to an AI system by removing the component and analyzing the performance” (Wikipedia contributors, n.d.c). That’s exactly it.

NoteVRP algorithm example

Imagine you propose a new VRP metaheuristic with:

• A giant-tour initial solution (where you solve TSP and split into vehicles, a common heuristic).
• A ruin-and-recreate phase (remove some customers randomly and reinsert, repeatedly).
• A learning mechanism that adjusts some insertion heuristics probabilities.

To validate this design, you do ablations:

1. Remove the learning mechanism; keep the rest. Maybe performance (gap to BKS) worsens from 1% to 2%. So learning gave ~1% benefit.
2. Remove ruin-and-recreate (perhaps just do initial + local improvement). If performance goes to 5% gap, clearly ruin-and-recreate was crucial to get from 5% to ~1-2%.
3. Remove both extras (just the initial solution). Maybe the gap is 10%. So each component contributed to closing the gap from 10% down to 1%.

You might find the learning mechanism had a smaller effect than ruin-and-recreate. That insight is valuable and can be reported: “The ruin-and-recreate step yields the majority of improvement (roughly 4% better solutions), while the adaptive learning yields an additional 1% improvement”.

If a component has no effect (ablation shows ~no change), it might be unnecessary complexity. If it has a negative effect (with it results are worse, without it better), that’s surprising and suggests a bug, misconfiguration, or that the component is actively harmful (perhaps overfitting or wasting time).

Ablation in machine learning is very standard (e.g., remove one input feature or network module and see effect on accuracy).

In operations research, not all papers do it, but it’s becoming more common especially if an algorithm is complex. It increases the rigor of the study.

TipFormula 1 analogy

Teams effectively do ablation tests on the car. It’s not called that, but:

• Addition test: When a new upgrade part is introduced, teams often do back-to-back tests: one run with the new part, one run without (the rest of the car the same). This is like an addition test (adding the part).
• Removal test: They remove/disable a piece to see its effect (e.g., testing a car without DRS or with a simplified front wing), though they rarely do that deliberately unless for data gathering.

One clear example: sometimes in practice, teams run one car with an old specification and the other car with a new spec (if both drivers agree) to directly compare. That’s a classic A/B test.

They measure lap times, sector times, tire wear differences. From that, they conclude “the new floor is giving us +0.3s advantage in high-speed corners but -0.1s in straight line due to drag, net +0.2s per lap—good, let’s use it.” If it was net negative, they’d revert to old spec.

Another example: if a team suspects an issue, they might run with some systems turned down/off to isolate a problem (e.g., run engine in a lower mode to see if a vibration is from the engine or chassis). Or cover a brake duct to see effect on temperatures.

So yes, in engineering they do similar experiments: Ablation = remove or disable something. For example, tape over a winglet (removing its effect) to see how much downforce is lost, thereby knowing how much that winglet contributed.

Addition = adding a prototype piece to see how much it gains.

One can also ablate driver aids (if any allowed)—e.g., in older times, turning off traction control to see how much it helped lap time. Or nowadays, test with and without using battery deployment at certain places to gauge effect (though they plan those with simulation mostly).

In strategy terms, ablation might be like “imagine we didn’t have a second pit stop—how much time would we lose?” They simulate leaving something out (like not doing a pit stop, or not using a certain tire compound) to see if that component of strategy was beneficial.

At a meta-level, ablation in racing could also refer to understanding contributions: e.g., “Wind tunnel says front wing accounts for 30% of total downforce, rear wing 40%, floor 30%.” They know this by effectively simulating ablation (turn off floor aero, see downforce drop).

So both in optimization and racing, ablation analysis is key to understanding complex system performance.

p-hacking and Overfitting

Now we come to pitfalls that can lead us to draw wrong conclusions if we’re not careful.

p-hacking originally stands for “statistical significance hacking,” where researchers test multiple hypotheses or data configurations until they find something with a statistically significant p-value, often by chance (Alphanome, n.d.). In algorithm benchmarking, a similar concept occurs if one runs a huge number of experiments or tweaks and selectively reports only the favorable outcomes. Essentially, if you have enough flexibility, you can eventually stumble on an instance or metric that makes your algorithm look good, even if in reality there’s no consistent improvement.

For example, suppose I have an algorithm and I test it on 10 instances; on 3 of them it beats the competitor, on 7 it doesn’t. If I only report those 3 (or emphasize them), that’s cherry-picking—akin to p-hacking in spirit. Or I measure 5 different metrics (distance, vehicles used, runtime, CO2, service quality) and only report the one where mine looks best, ignoring that maybe on others it was worse. That’s also cherry-picking results.

Another scenario: I run my stochastic algorithm 30 times and only report the single best run (or even worse, run various random seeds behind the scenes and only disclose the seed that gave best result). That’s not an honest average performance, it’s picking a lucky shot, which might not be reproducible or typical.

All these practices can mislead. They’re tempting when trying to “prove” your method is best, but they violate scientific rigor. As Hooker (1995) and others have argued, the “competitive testing” mindset incentivizes cherry-picking—you just want to show you win, rather than truly understanding when/why.

Overfitting in algorithm design refers to tailoring the algorithm too much to the test instances or environment, so it loses generality (OpenReview, n.d.). For instance, say all benchmark instances have clustered customers. You could code a special heuristic that assumes clusters and exploits that. It might do extremely well on those benchmarks but if faced with a non-clustered instance, it fails or performs poorly. This algorithm is overfit to the benchmark’s idiosyncrasies.

Another form: tuning parameters specifically to each instance (like parameter control that is manually set after seeing instance data)—effectively optimizing algorithm behavior per instance. That can overfit because if the instance distribution changes, those tuned values may not be good.

The openreview “Benchmark Lottery” snippet described how over time, researchers might incorporate many tricks that are specifically effective on a particular benchmark, thereby achieving high performance on that benchmark but those tricks may not generalize to other problems (OpenReview, n.d.). They called it “leading models are quickly adapted by re-using their code, pre-trained weights, and hyperparameters ... The adapted recipes for scoring high are not necessarily universal and may be applicable only to a single narrow task” (OpenReview, n.d.). That captures creeping overfitting in ML benchmarks, and it mirrors what can happen in OR benchmarking.

Consequences: - If one p-hacks or overfits, they might claim SOTA, but when a new benchmark or real-world scenario appears, their method might underperform dramatically. - This also wastes effort—you might think your method is great due to biased tests, but you haven’t truly improved the underlying technique, just exploited test specifics.

Preventing p-hacking: - Fix your evaluation protocol ahead of time (like pre-registering in science). For example, decide “I will run each algorithm 10 times and report the average and std dev” before seeing results, rather than fishing for a favorable way. - Use statistical tests properly and account for doing multiple comparisons if you do (there are corrections like Bonferroni for multiple hypothesis testing). - Be transparent: report all relevant results, not just the best slice. If your algorithm is worse on some instances, mention it or at least don’t hide it. Often an average or median metric can help summarize overall. - In competitions, have an external benchmark where the designer can’t tweak after seeing it (e.g., hidden test instances).

Preventing overfitting: - As discussed, use held-out tests. Try your algorithm on problems outside the ones you tuned it for. For example, after optimizing for Solomon VRPTW, test it on some randomly generated VRPTW instances to see if it’s still good. - Keep an eye on whether improvements are algorithmic general improvements or just special-case handling. If it’s the latter, acknowledge that limitation. - Encourage benchmarks to be broad. If you only test on 3 instances, you risk overfitting to them; if you test on 100 varied instances, it’s harder (though not impossible) to overfit all. - There’s also an argument: do research on principles, not just on beating benchmarks. As Hooker (1995) argued, it is better to understand algorithm behavior (scientific method) rather than purely chase benchmark leaderboards. The latter leads to hacks for specific cases (track meets analogy).

WarningVRP example: p-hacking

Suppose I implemented 5 variants of my algorithm (different parameter sets or different sub-heuristics). Instead of objectively deciding on one approach beforehand, I run all 5 on benchmarks and then in the paper only present the best results from among them for each instance, without saying I tried 5. This is p-hacking because I effectively did 5 “experiments” and reported the best—the reader might think that one approach always was used, but actually I cherry-picked per instance or overall. If I don’t penalize for these multiple trials, I’m inflating the chance that my results look good due to luck.

Another subtle one: if you test on a suite of 30 instances and one algorithm is better on 25 and loses on 5, you should report that honestly. If you instead drop those 5 instances from the discussion claiming they were “outliers” without justification, you are cherry-picking data to favor your method.

WarningVRP example: overfitting

Let’s say all your test instances have 50 customers within a 10x10 square. You notice your algorithm struggles with those that have customers all around the edges. So you add a special repair step that specifically addresses edge cases (like if a cluster on the edge is isolated, do something special). It works for these instances. But in a different distribution (like a multi-depot scenario or a weird shape region), that “edge cluster heuristic” might do something unnecessary or wrong. It wasn’t a general improvement, just a fix for a pattern in the test data. Unless that pattern is universal in real cases, you overfit.

An even more blatant case: if one encoded some known optimal solutions or partial routes for the specific benchmark instances (basically cheating by using knowledge of the test answers). That’s extreme overfitting—it’s like a student memorizing answers to a known test instead of learning the material.

This happened historically in some algorithm competitions (not maliciously, but inadvertently)—e.g., algorithms that were heavily parameter-tuned on specific test sets often failed to win when tested on new instances because they were too tailored.

TipFormula 1 analogy

p-hacking in F1: Imagine a team runs 100 laps in practice with minor setup tweaks each time and only tells the media the fastest lap they did, saying “we’re very quick”—ignoring that 99 laps were slower or had issues. That is cherry-picking one data point out of many. Another example: if a team tested 5 new parts and 1 gave a great lap time improvement by coincidence (maybe due to weather change), and they highlight that as evidence their upgrade program is superb, ignoring that the other 4 parts did nothing or made worse—that’s selective evidence.

There’s less of this in a public way because performance is visible on track, but internally if a manager only looks at best-case simulations and not average-case, they could be misleading themselves about the car’s potential. It’s like convincing yourself “we can win because in simulation scenario #42 we won,” whereas ignoring that in most scenarios they didn’t—cherry-picking optimism.

Overfitting in F1: This is akin to designing the car or strategy too specifically for certain conditions. For car design, if a team optimizes their aerodynamics for one type of corner (say high-speed) at expense of others, they’ll fly at tracks like Monza or Silverstone but struggle at twisty tracks (like Monaco or Hungary). They’ve “overfit” the design to high-speed circuits. In 2019, Ferrari had a car very fast on straights but poor in corners—one could say it was optimized for low-drag (good at tracks with long straights) but overfit to that concept, losing overall balance.

Another scenario: strategies overfit to assumptions. For example, expecting no safety car and planning a very marginal tire strategy might be optimal on paper (like perfect conditions), but as soon as reality deviates (safety car happens), that strategy crumbles. It was over-optimized to a specific expected scenario without enough robustness.

On a smaller scale, within a race: if a driver pushes super hard to set fastest laps (optimizing lap time metric) but in doing so overheats tires and then loses performance—they over-optimized short-term pace at expense of overall race (like overfitting to a performance metric while losing sight of main goal).

We even have something literally called the “qualifying setup” vs “race setup” tension. A car can be trimmed for one lap pace (qualifying) or for race consistency (long runs). If you overfit to qualifying (low fuel, new tires performance), you might kill the tires in race or have instability with heavy fuel. So teams must avoid overfitting car setup to one condition at expense of another. They often compromise (sacrifice a bit of quali pace for better race pace).

In conclusion, p-hacking and overfitting are practices to avoid for credible benchmarking. The solution is careful experimental design (train/test splits, not doing too many unchecked comparisons) and honesty in reporting. Ideally, as some suggest, we should be aiming for more scientific testing of algorithms: formulate hypotheses, test them, report even if they fail, and focus on understanding rather than just winning benchmarks (Hooker, 1995). This yields more robust algorithms in the long run, and ensures that improvements are real and not mirages.

Conclusion

In summary, the anatomy of an optimization problem involves a clear definition of the problem instance, inputs, objective, and constraints, awareness of problem variants and any randomness, and extends to how we devise solution strategies (policies) and evaluate those solutions against baselines, current state-of-the-art, and known best results. A rigorous benchmarking pipeline uses standard problem sets, proper metrics (KPIs), careful experiment design (with tuning vs. held-out tests, ablations), and guards against common pitfalls like p-hacking and overfitting.

By mapping these concepts to both a Vehicle Routing Problem context and a Formula 1 racing analogy, we can appreciate their universal relevance: whether routing trucks or racing cars, we define the goal, operate under constraints, innovate strategies, and measure performance in a structured way. In both domains, success comes not just from raw speed or initial cleverness, but from disciplined testing, iteration, and understanding of what truly contributes to better performance versus what might just be a lucky or narrow win.

The ultimate goal is to develop optimization methods (or race plans) that are robust, efficient, and genuinely effective, standing up to unbiased benchmarks and real-world challenges. By following the academic rigor—precise definitions, comprehensive benchmarking, and honest analysis—we ensure that progress in optimization is real and lasting, much like how engineering rigor and fair competition ensure that the fastest car on track is truly the best and not just benefiting from a quirk.

References

Alphanome. (n.d.). When algorithms chase significance: Understanding p-hacking in the age of AI. Retrieved January 17, 2026, from https://www.alphanome.ai/post/when-algorithms-chase-significance-understanding-p-hacking-in-the-age-of-ai

CVRPLIB. (n.d.). CVRPLIB. Retrieved January 17, 2026, from http://vrp.atd-lab.inf.puc-rio.br/index.php/en/

Deutsche Nationalbibliothek. (n.d.). Record 1214641016. Retrieved January 17, 2026, from https://d-nb.info/1214641016/34

Envisioning Vocab. (n.d.). Baseline. Retrieved January 17, 2026, from https://www.envisioning.com/vocab/baseline

IBM. (n.d.). What is optimization modeling? Retrieved January 17, 2026, from https://www.ibm.com/think/topics/optimization-model

Klipfolio. (n.d.). What is a key performance indicator (KPI)? Retrieved January 17, 2026, from https://www.klipfolio.com/resources/articles/what-is-a-key-performance-indicator

OpenReview. (n.d.). Benchmark pitfalls discussion. Retrieved January 17, 2026, from https://openreview.net/pdf?id=5Str2l1vmr-

Reinelt, G. (n.d.). TSPLIB 95. Retrieved January 17, 2026, from http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/

ResearchGate. (n.d.). Comparing the performance of the baseline algorithm with a state-of-the-art. Retrieved January 17, 2026, from https://www.researchgate.net/figure/Comparing-the-performance-of-the-baseline-algorithm-with-a-state-of-the-art-text_fig7_23707171

ScienceDirect Topics. (n.d.). Vehicle routing problem - an overview. Retrieved January 17, 2026, from https://www.sciencedirect.com/topics/social-sciences/vehicle-routing-problem

SciRP. (n.d.). A survey on the vehicle routing problem and its variants. Retrieved January 17, 2026, from https://www.scirp.org/journal/paperinformation?paperid=19355

Wikipedia contributors. (n.d.a). Mathematical optimization. Retrieved January 17, 2026, from https://en.wikipedia.org/wiki/Mathematical_optimization

Wikipedia contributors. (n.d.b). Decision rule. Retrieved January 17, 2026, from https://en.wikipedia.org/wiki/Decision_rule

Wikipedia contributors. (n.d.c). Ablation (artificial intelligence). Retrieved January 17, 2026, from https://en.wikipedia.org/wiki/Ablation_(artificial_intelligence)

The neurobench framework for benchmarking neuromorphic computing algorithms and systems. (2025). Nature Communications. Retrieved January 17, 2026, from https://www.nature.com/articles/s41467-025-56739-4

Uchoa, E., Pecin, D., & Pessoa, A. (2017). New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research.

Ropke, S., & Pisinger, D. (2006). An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science.

Helsgaun, K. (2000). An effective implementation of the lin-kernighan traveling salesman heuristic. European Journal of Operational Research.

Barr, R. S. et al. (1995). Guidelines for computational experiments. Retrieved January 17, 2026, from https://www.cs.ubc.ca/~hutter/EARG.shtml/earg/papers04-05/BarEtAl95.pdf

Hooker, J. N. (1995). Ordinal comparison of heuristic algorithms using stochastic optimization. Retrieved January 17, 2026, from https://sci2s.ugr.es/keel/pdf/specific/articulo/Ordinal%20Comparison%20of%20Heuristic%20Algorithms%20Using%20Stochastic%20Optimization.pdf

Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research.

Christofides, N., Mingozzi, A., & Toth, P. (1979). The vehicle routing problem.

Lin, S., & Kernighan, B. W. (1973). An effective heuristic algorithm for the traveling-salesman problem. Operations Research.