Development of New Heuristics for the Euclidean Traveling SalesmanProblem

Abstract

Many heuristics have been developed to approximate optimal tours for the Euclidean Traveling Salesman Problem (ETSP). While much progress has been made, there are few quick heuristics which consistently produce tours within 4 percent of the optimal solution. This project examines a few of the well known heuristics and introduces two improvements, Maxdiff and Checks. Most algorithms, during tour constrution, add a city to the subtour because the city best satisfies some criterion. Maxdiff, applied to an algorithm, ranks a city according to its effect (based on the algorithm's criterion) if it is not added to the subtour.