Evaluation of Heuristic Algorithms for the TSP: A New Statistical Approach

SYNOPTIC ABSTRACT

A statistical approach to evaluation of the quality of solutions from Traveling Salesman Problem (TSP) heuristics is formulated and used. This approach is based on the value of a surrogate for the tour length; this surrogate is computed from the ranks of the intercity distances. The evaluation is performed by statistical hypothesis testing on the mean value of the surrogate produced by the heuristic under evaluation, in randomly generated problem instances. This mean is compared to a cut-off point chosen to be the expectation of the smallest surrogate value in large samples of randomly selected tours.

Key Words and Phrases:

• heuristic evaluation
• Traveling Salesman Problem
• linear rank statistics
• Monte Carlo method
• hypothesis testing
• estimation