This article is cited in 2 papers

COMPUTER SOFTWARE AND COMPUTING EQUIPMENT

Research of the task solution of the traveling salesman

V. O. Boroznov

Astrakhan State Technical University

Abstract: The review of the most widespread algorithms used for the task solution of the traveling salesman such as: exact (exhaustive algorithm, method of paths and limits), heuristic (method of distant inclusion, BV-method) and search (Genetic algorithms, Ant Colony System — ACS-Q) is given. The comparative analysis of the algorithms, concerning the quality of the received solutions and their “speed” has shown: heuristic algorithms are undeniable “leaders” in speed with good ratio quality/time; the exact methods are poorly suitable for the solution of tasks of the large dimensions (are not capable to solve a task for reasonable time); the algorithms of search are the compromise between heuristics and exact methods, but they require selection of parameters. The temporary estimations given to algorithms, allow to estimate time of the task solution and to choose the most suitable method, when the speed is a critical parameter.

Keywords: traveling salesman’s task, exact algorithms, heuristic algorithms, search algorithms, assessment of time complexity, the speed of combinatorial algorithms.

UDC: 681.31.00

Received: 07.10.2009