A heuristic for the traveling salesman problem based on a continuous approximation

A procedure for solving, suboptimally, the traveling salesman problem is pr esented. The set of points on the traveling salesman tour is distributed ov er a region having the shape of a circular or ring sector. The procedure is based on an optimal partition of the sector and reduces the tour construct ion to a sorting problem. Namely, the tour is constructed by visiting the p oints in radial or angular order depending on;the part of the sector on whi ch they are located. The optimal partition is derived by a continuous appro ximation of the set of points. It is defined by a single parameter and simp le analytical expressions for it are obtained. A great number of numerical tests were carried out to evaluate the performance of the procedure. These tests allowed a measure of the difference from the optimum solution that co uld be obtained for problems up to a few hundred points. The results show t hat the euclidean length of the tours produced by the partition procedure g rows, on average, like root AN where A is the region area and N the number of points. The initial tours are improved by means of the Or's algorithm an d the final tours obtained are nearly as good as those given by more intrin cate improvement heuristics. The whole procedure, that is, the tour constru ction and improvement heuristics, is rather simple to implement on a comput er, which makes it very appealing to use in routing software. (C) 1998 Else vier Science Ltd. All rights reserved.