engleski

Some new results on the travelling salesman problem

The travelling salesman problem (or The sales representative problem) has been insufficiently explored so far. One of the first results on this issue was provided by Euler in 1759 (The problem of moving a knight on the chess board), Knight's Tour Problem. Papers on this subject were written by A.T. Vandermonde (1771), T.P. Kirkman (1856) and many others. The sales representative problem is a major challenge due to the application in solving theoretical and practical problems such as the quality of algorithms and of optimization methods. This well-known optimization problem has been extensively studied from several aspects since 1930. In general form the study was started by Karl Menger, seeking the shortest route through all points of a finite set with known distances between every two points. Since then, there have been many formulations of the problem. In this paper we shall provide an analysis of the nature of the commercial representative problem, and highlight its complexity and some ways of its solution. We shall use graph theory, and pay particular attention to the search of Hamiltonian cycle of minimum weight in the weighted graph. During the paper development we were led by the following question: "How to minimize the total distance travelled by a sales representative in order to visit n given locations exactly once and return to the starting point?"

graph, top, edge, trail, algorithm, cycle

nije evidentirano