[feed] pefprints@pef.uni-lj.si | [feed] Atom [feed] RSS 1.0 [feed] RSS 2.0 |
slovenščina
Logo            
  Logo Login | Create Account
 
 

The travelling salesman problem

Kaja Zupanc (2012) The travelling salesman problem. Diploma thesis.

[img]
Preview
PDF
Download (13Mb)

    Abstract

    In the travelling salesman problem we are given a graph. The task of the salesman is to find the shortest (or cheapest) possible route by visiting each vertex (that represents cities) exactly once and returning to the initial vertex (city). A Hamilton cycle is a cycle in a graph, in which each vertex is visited only once. In the travelling salesman problem we are thus searching for a Hamilton cycle with a minimum price. The problem was posed in 19th century by the Irish mathematician W. R. Hamilton. Today, this is one of the most intensively studied problems in combinatorial optimization. The travelling salesman problem belongs to the class of NP-hard problems. In particular, this means that we (so far) cannot construct a polynomial-time algorithm that would solve this problem. The bachelor's thesis deals with exact and approximation algorithms for solving the traveling salesman problem. We present an exact Concorde algorithm for solving symmetric traveling salesman problems and use it to examine how good two approximation algorithms are: the nearest neighbour algorithm and the double-tree algorithm. We also explore applicability of the travelling salesman problem to various problems encountered in the fields of science and engineering.

    Item Type: Thesis (Diploma thesis)
    Keywords: travelling salesman problem, Hamilton cycle, Concorde, nearest neighbour algorithm, double-tree algorithm
    Number of Pages: 76
    Language of Content: Slovenian
    Mentor / Comentors:
    Mentor / ComentorsIDFunction
    doc. dr. Primož ŠparlMentor
    Link to COBISS: http://www.cobiss.si/scripts/cobiss?command=search&base=50126&select=(ID=9366089)
    Institution: University of Ljubljana
    Department: Faculty of Education
    Item ID: 1026
    Date Deposited: 13 Sep 2012 14:17
    Last Modified: 13 Sep 2012 14:17
    URI: http://pefprints.pef.uni-lj.si/id/eprint/1026

    Actions (login required)

    View Item