izpis_h1_title_alt

Obhod trgovskega potnika po zemljevidu Slovenije
ID Eržen, Nika (Author), ID Fijavž, Gašper (Mentor) More about this mentor... This link opens in a new window

.pdfPDF - Presentation file, Download (6,00 MB)
MD5: 6AB5425CCBE06C23741EB62FE97AD432

Abstract
Problem trgovskega potnika je dobro znan NP-težak problem. Cilj problema je obresti določeno množico mest tako, da pri tem prehodimo čim krajšo pot in se vrnemo v izhodišče. V magistrski nalogi smo poiskali obhod trgovskega potnika po 6007 naseljih Slovenije glede na geografske razdalje med naselji. Za iskanje smo uporabili programa LKH in Concorde. S programom LKH smo poiskali zgornjo mejo obhoda trgovskega potnika. Nato smo s programom Concorde poiskali spodnjo mejo za obhod trgovskega potnika in jo nato izboljševali, dokler nismo dosegli izenačenja spodnje in zgornje meje. Našli smo obhod dolžine 7733,125km in pokazali njegovo optimalnost.

Language:Slovenian
Keywords:problem trgovskega potnika, geografski podatki
Work type:Master's thesis/paper
Organization:FRI - Faculty of Computer and Information Science
Year:2018
PID:20.500.12556/RUL-104981 This link opens in a new window
Publication date in RUL:19.10.2018
Views:1372
Downloads:247
Metadata:XML DC-XML DC-RDF
:
Copy citation
Share:Bookmark and Share

Secondary language

Language:English
Title:Traveling salesman problem on the map of Slovenia
Abstract:
The traveling salesman problem is a well known NP-hard problem. Given a list of cities and the distances between each pair of cities, the goal is to find the shortest possible route that visits each city and returns to the origin city. In the thesis we found the solution to the traveling salesman problem on 6007 settlements in Slovenia using the geographical distance between the settlements. To find the solution we used programs LKH and Concorde. With LKH we obtained the upper bound of traveling salesman tour. Than we used Concorde to obtain and improve the lower bound of the traveling salesman tour. We have found the tour of length 7733,125km and have shown that it is optimal.

Keywords:traveling salesman problem, geographical data

Similar documents

Similar works from RUL:
Similar works from other Slovenian collections:

Back