• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Student
Title
Supervisor
Faculty
Educational Programme
Final Grade
Year of Graduation
Ekaterina Beresneva
Implementation and Assessment of Resource-Efficient Algorithms for Metric TSP
Software Engineering
(Bachelor’s programme)
2017
The Travelling Salesman Problem (TSP) is a fundamental task in a class of combinatorial optimization problems which consists of finding a Hamiltonian circuit of minimal length. Solutions of the TSP are generally used for costs minimization tasks in logistics and manufacturing, such as finding the best tour for round-the-world trip or construction of very large-scale integration schemes. A special case of the TSP is Metric TSP, where the triangle inequality holds.

The objective of this article is to determine a group of Pareto optimal algorithms for Metric TSP under criteria of run time efficiency and qualitative performance as a part of the experimental study. In this paper, we consider only heuristic algorithms providing near optimal solutions in polynomial time, since the TSP is NP-hard.

Classification of algorithms for Metric TSP is presented. Groups of feasible heuristic algorithms and their modifications are described. The data structure and the details of the research methodology are provided. Two real-life kinds of inputs are used for the experimental study: very large scale integration schemes and geographic coordinated of cities. Finally, results and prospective research are discussed.

The paper contains 113 pages, 13 illustrations, 7 tables, 14 schemes, 67 bibliography items, 11 appendices.

Keywords: travelling salesman problem, resource-efficient algorithm, heuristic algorithm, Metric TSP, computational experiment, NP-hard problem.

Student Theses at HSE must be completed in accordance with the University Rules and regulations specified by each educational programme.

Summaries of all theses must be published and made freely available on the HSE website.

The full text of a thesis can be published in open access on the HSE website only if the authoring student (copyright holder) agrees, or, if the thesis was written by a team of students, if all the co-authors (copyright holders) agree. After a thesis is published on the HSE website, it obtains the status of an online publication.

Student theses are objects of copyright and their use is subject to limitations in accordance with the Russian Federation’s law on intellectual property.

In the event that a thesis is quoted or otherwise used, reference to the author’s name and the source of quotation is required.

Search all student theses