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

Jose M. del Castillo

Transportation Research Part B: Methodological, 1998, vol. 33, issue 2, 123-152

Abstract: A procedure for solving, suboptimally, the traveling salesman problem is presented. The set of points on the traveling salesman tour is distributed over 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 construction to a sorting problem. Namely, the tour is constructed by visiting the points in radial or angular order depending on the part of the sector on which they are located. The optimal partition is derived by a continuous approximation of the set of points. It is defined by a single parameter and simple 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 could be obtained for problems up to a few hundred points. The results show that the euclidean length of the tours produced by the partition procedure grows, on average, like , where A is the region area and N the number of points. The initial tours are improved by means of the Or's algorithm and the final tours obtained are nearly as good as those given by more intrincate improvement heuristics. The whole procedure, that is, the tour construction and improvement heuristics, is rather simple to implement on a computer, which makes it very appealing to use in routing software.

Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191-2615(98)00034-4
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:33:y:1998:i:2:p:123-152

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().