An Analysis of Several Heuristics for the Traveling Salesman Problem

TLDR

Polynomial‑time heuristics that produce near‑optimal tours for the traveling salesman problem are examined. The study evaluates these heuristics by comparing tour lengths to the optimal length, focusing on nearest‑neighbor and insertion methods. Nearest‑neighbor tours achieve a logarithmic approximation ratio, while nearest and cheapest insertion methods attain a constant factor of 2, and worst‑case lower bounds of logarithmic and 2(1−1/n) ratios are demonstrated.

Abstract

Several polynomial time algorithms finding “good,” but not necessarily optimal, tours for the traveling salesman problem are considered. We measure the closeness of a tour by the ratio of the obtained tour length to the minimal tour length. For the nearest neighbor method, we show the ratio is bounded above by a logarithmic function of the number of nodes. We also provide a logarithmic lower bound on the worst case. A class of approximation methods we call insertion methods are studied, and these are also shown to have a logarithmic upper bound. For two specific insertion methods, which we call nearest insertion and cheapest insertion, the ratio is shown to have a constant upper bound of 2, and examples are provided that come arbitrarily close to this upper bound. It is also shown that for any $n\geqq 8$, there are traveling salesman problems with n nodes having tours which cannot be improved by making $n/4$ edge changes, but for which the ratio is $2(1-1/n)$.