A benchmark gives readers a common basis for judging an optimization method. The evaluation must use comparable inputs, budgets, information, and outcome measures. Otherwise, a reported improvement may come from the test conditions rather than the method.
Use Choosing optimization methods first if the algorithm class is still undecided.
Define the claim
State the primary contribution before designing the experiment. Common thesis contributions include:
- Applied improvement: the method improves a company’s current procedure.
- Algorithmic result: the method matches or exceeds a strong published method on shared instances.
- Modeling result: the formulation represents an operational feature that existing models omit.
- Experimental result: the study supplies a fair comparison, benchmark, or reusable dataset.
Each claim requires different evidence. An applied thesis may need historical replay, service measures, and implementation constraints. An algorithmic thesis needs standard instances, strong comparison methods, repeated runs, and exact protocol details.
Benchmark
A benchmark combines instances, reference results, outcome measures, and an experimental protocol. Established vehicle-routing benchmarks include the Solomon time-window instances and the CVRPLIB collections (Solomon, 1987; Uchoa, Pecin, & Pessoa, 2017).
Record the benchmark version and any preprocessing. Match the original objective, constraints, time limits, and instance interpretation. A small difference in fleet size, rounding, or distance calculation can invalidate the comparison.
Company baseline
Industry projects often have no public benchmark. Reconstruct the current procedure as accurately as possible and test both approaches with the same historical information.
Use several levels of comparison when feasible:
- The company procedure shows practical improvement.
- A simple heuristic checks whether complexity is justified.
- An exact solution or bound on small cases checks solution quality.
- An adapted published method gives a research-level reference.
Historical replay must respect the information available at the original decision time. Using future demand, realized travel times, or completed orders can make the new method appear stronger than it is.
Simulation and exact references
Simulation can test policies under repeated demand, travel-time, or disruption scenarios. Validate the simulator against observed statistics and confirm that it reproduces the baseline’s known behavior.
Exact solutions on reduced instances provide another check. They reveal optimality gaps and formulation errors, even when the full problem is too large for an exact solver.
Outcome measures
Choose measures that correspond to the thesis claim. Typical measures include objective value, runtime, optimality gap, service level, late orders, emissions, resource use, and result variability.
Define every measure, unit, aggregation rule, and direction of improvement. Report trade-offs rather than hiding them in one weighted score. A method that reduces distance by 4% while doubling late deliveries has changed the outcome, and readers need both values.
For stochastic methods, report the number of runs, seeds, central tendency, and spread. Include the best run only when that statistic has a stated purpose.
Testing workflow
Separate method development from final evaluation.
Pilot
Use a small, representative subset to detect implementation errors and remove methods that clearly fail. Give each candidate the same budget.
Configuration
Tune parameters on training instances. Record the search space, configuration budget, random seeds, and selected values. Decide the stopping rule before the final evaluation.
Held-out evaluation
Freeze the code and parameters. Run the method on instances that did not affect development or tuning. Use several seeds for stochastic algorithms and report all planned outcome measures.
Sensitivity analysis
Change assumptions or parameters that may alter the conclusion. Suitable tests include demand growth, travel-time variation, penalty weights, fleet size, and instance scale. Explain which conclusions remain stable.
Ablation and addition studies
An ablation removes one component while holding the rest of the method fixed. The comparison estimates the component’s contribution. An addition study starts with a simple method and adds components in a fixed order.
Suppose a routing heuristic contains a construction rule, ruin-and-recreate step, local search, and adaptive operator weights. Compare the full version with versions that remove one component at a time. Use the same instances, seeds, and budgets.
Report interactions when the components depend on each other. Removing 2 components together may produce a different result from the sum of 2 separate ablations.
Selective reporting and overfitting
Selective reporting occurs when the analyst tries many instances, measures, seeds, or parameter settings and reports only favorable results. Overfitting occurs when method development adapts too closely to the evaluation instances. Both practices weaken the claim.
Protect the evaluation by fixing the protocol before the final run:
- reserve held-out instances;
- define the primary outcome measure;
- state the number of runs and statistical comparisons;
- report failed conditions and unfavorable results;
- retain the code, data, parameters, and seeds.
Running 5 algorithm variants and reporting the best result from each instance does not describe one reproducible method. Report the 5 variants separately or select one through a declared training procedure.
Reviewable reporting
Give readers enough information to repeat the experiment:
- instance source, exclusions, and preprocessing;
- hardware, software, solver, and version information;
- time, iteration, and evaluation budgets;
- parameter values, tuning procedure, and random seeds;
- complete result tables or a public data file.
Use equivalent stopping rules across methods. A 60-second limit for one method and an unlimited run for another needs an explicit reason.
Negative results
A negative result can support a useful conclusion when the test is fair and the boundary is clear. State the original hypothesis, tested conditions, outcome, and likely explanation.
Before accepting a negative result, check the implementation, baseline, constraints, tuning budget, and outcome measures. Then report where the method fails and which alternative performs better. The explanation may identify a weak neighborhood, expensive evaluation, unstable penalty, or unsuitable problem structure.
Use this reporting order:
- State the expected effect and its rationale.
- Describe the instances, budgets, and comparison methods.
- Present the outcome and variability.
- Explain the supported boundary of the conclusion.
Complete reporting lets future work distinguish a failed idea from a failed implementation.