Benchmarks

The Traveling Salesman Problem (TSP) and the Capacitated Vehicle Routing Problem (CVRP) were chosen as benchmarks.

They are well known, and there are a number of cases for which optimal answers have been calculated.

For an overview of these problems and why they are difficult, click here

TSP and CVRP are actually not good examples for this technology because the problems are under-constrained and, hence, more dependent on raw search than realistic problems. But more realistic proposed NP-hard problems are too complex to be solved with any current methodology, so there are no benchmark standards to which to compare.

The problems are from two sources:

The TSP problems are from the University of Heidelberg – http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/

The CVRP problems are from BranchAndCut.org - http://www.coin-or.org/SYMPHONY/branchandcut/VRP/data/#B

On the Traveling Salesman Problems website there are symmetric and asymmetric problems.

Large symmetric TSP problems can be solved with a linear programming program called Concord.

Asymmetric TSP problems are far more difficult. The largest solved asymmetric TSP problem on the website is the 443 city problem, which is included in the benchmarks.

On the Constrained Vehicle Routing Problem website, the largest solved problem is 135 cities. This is included in the benchmarks. Larger problems are posed, but have no solution.

The benchmarks were run with an application using the Optimization Library. This application was run with 5 increasing levels of search on each problem to create the benchmark results.

At the deepest search level
     The symmetric TSP problems averaged 0.35% over optimal.
     The asymmetric TSP problems averaged 0.34% over optimal.
     The CVRP problems averaged 0.83% over optimal.

The benchmark times are a reflection of the application rather than the Optimization Library... Less than 5% of the time is from the Optimization Library.

The benchmarks were run on a Dell Dimension 3400 with an Intel E7400 (2.80GHz) CPU.

Benchmark Results
          Symmetric TSP
          Asymmetric TSP
          CVRP

To see a video of a TPS problem being solved, click here     (This is a link to YouTube. You will need a full screen view to see it clearly.)