Obhod trgovskega potnika po zemljevidu Slovenije

Eržen, Nika (avtor), Fijavž, Gašper (mentor)

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.

• Jezik: Slovenski jezik
• Ključne besede: problem trgovskega potnika, geografski podatki
• Vrsta gradiva: Magistrsko delo/naloga
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Leto izida: 2018
• PID: 20.500.12556/RUL-104981
• Datum objave v RUL: 19.10.2018

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Traveling salesman problem on the map of Slovenia

Izvleček

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.

• Ključne besede: traveling salesman problem, geographical data