Prethodno priopćenje
https://doi.org/10.2507/IJVA.1.2.4.15
Some new results on the travelling salesman problem
Dominika Crnjac Milić
; Faculty of Electrical Engineering, J.J Strossmayer University of Osijek, Osijek, Croatia
Ljiljanka Kvesić
; Faculty of Science and Education, University of Mostar, Mostar, Bosnia and Herzegovina
Sažetak
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?"
Nowadays, there are many formulations of the commercial representative problem and we shall mention two equivalent formulations:
a) A set of places that a sales representative has to visit exactly once and return to the starting point is determined, the distance between places being known.
The question is in which order a sales representative should visit the places so that the total length of his tour is minimal
b) A Hamiltonian cycle of minimum weight should be determined in the weighted graph.
Note that the formulation of the problem is very simple, but finding solutions inflicts great difficulties. For a graph of n vertices there are n! maximum number of Hamiltonian cycles, thus the problem of factorial complexity occurs.
Ključne riječi
graph; top; edge; trail; algorithm; cycle
Hrčak ID:
156112
URI
Datum izdavanja:
15.12.2015.
Posjeta: 2.050 *