Skip to main content
EN
HR
Početna
O repozitoriju
Kontakt
vup.hr
Repozitorij Veleučilišta u Požegi
Repozitorij ocjenskih radova
Pregledavanje
Prema autoru
Prema godini
Prema organizacijskoj jedinici
Prema području
Prema vrsti rada
Svih dokumenata
Napredno pretraživanje
Pohranjivanje
Search Term
Preuzmi
PDF 257.4 KB
Znanstveni rad - Prethodno/kratko priopćenje
7
3
Some new results on the travelling salesman problem
Crnjac Milić, Dominika; Kvesić, Ljiljanka (2015)
Za citiranje koristite ovu mrežnu adresu:
https://urn.nsk.hr/urn:nbn:hr:112:788452
Podaci o radu
Jezik rada
engleski
Naslov (engleski)
Some new results on the travelling salesman problem
Autor
Crnjac Milić, Dominika
Kvesić, Ljiljanka
Sažetak rada (engleski)
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 (engleski)
graph
top
edge
trail
algorithm
cycle
Vrsta rada
znanstveni rad - prethodno/kratko priopćenje
Status objave rada
objavljen
Vrsta recenzije
recenziran - međunarodna recenzija
Naslov časopisa
International Journal Vallis Aurea
Brojčani podaci
2015, Vol. vol.1, br. no.2, str. 33-40
ISSN
2412-5210
e-ISSN
1849-8485
Datum
datum objave publikacije: 12.2015.
URL rada
https://hrcak.srce.hr/index.php?show=clanak&id_clanak_jezik=230155
Znanstveno područje
DRUŠTVENE ZNANOSTI
Ekonomija
Ustanova
Sveučilište Josipa Jurja Strossmayera u Osijeku, Fakultet elektrotehnike, računarstva i informacijskih tehnologija Osijek
URN:NBN
https://urn.nsk.hr/urn:nbn:hr:112:788452