Zero-mean unbiasing as a preprocessing step for greedy TSP solvers improves the quality of solutions on average.
No Thumbnail Available
Authors
Meeting name
Sponsors
Date
Journal Title
Format
Thesis
Subject
Abstract
When applied in the two-dimensional case of the symmetric traveling salesman problem (TSP), zero-mean unbiasing improves the lower bound achieved by the N-shot nearest neighbor heuristic (N-NN). Testing was conducted across configurations including instances with points in uniform distribution, points in normal distribution, and points clustered randomly. In most cases, the average improvement over unmodified N-NN was demonstrated to be ≈ 3%.
Table of Contents
DOI
PubMed ID
Degree
M.S.