Double - ended nearest and loneliest neighbour – a nearest neighbour heuristic variation for the travelling salesman problem

From IFORS Developing Countries Online Resources
Jump to: navigation, search

by: Fernando Guilherme Silvano Lobo Pimentel


This paper presents a new tour construction heuristic for the travelling salesman problem that introduces the concept of loneliness of a city computed from the average distance of that city to all others and combines it with ideas from other nearest neighbour heuristics. Having the same time complexity of the faster nearest neighbour heuristics, the new method clearly leads to better tours, outperforming them as well as several other tour construction heuristics reported in the literature. A promising feature of the proposed heuristic is that it gives some priority to more isolated locations in travel route definitions. The earlier distribution of goods and services to loneliest sites might be considered a positive social externality that is appealing to the application of heuristics by public or private institutions that are engaged in acts of social responsibility.

Keywords: Travelling Salesman, Heuristics, Nearest Neighbour

Link to material: