Abstract
dc:description.abstractOne of the simplest, but still NP-hard, routing problems is the Traveling Salesman Problem (TSP). In the TSP, one is given a set of cities and a way of measuring the distance between cities. One has to find the shortest tour that visits all cities exactly once and returns back to the starting city. In state-of-the-art algorithms, they all assume that a complete graph is given as an input. However, for very large graphs, generating all edges in a complete graph, which corresponds to finding shortest paths for all city pairs, could be time-consuming. This is definitely a major obstacle for some real-life applications, especially when the tour needs to be generated in real-time. The objective, in this thesis, is to find a near-optimal TSP tour with a reduced set of edges in the complete graph. In particular, the following problems are investigated: which subset of edges can be produced in a shorter time comparing to the time for generating the complete graph? Is there a subset of edges in the complete graph that results in a better near-optimal tour than other sets? With a non-complete graph, which improvement algorithms work better? In this thesis, we study six algorithms to generate subsets of edges in a complete graph. To evaluate the proposed algorithms, extensive experiments are conducted with the well-known TSP data in a TSP library. In these experiments, we evaluate these algorithms in terms of tour quality, time and scalability.
Degree
thesis:*- Grantor dc:publisher
- University of Waterloo
- Year dc:date.issued
- 2010
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Emami Taba, Mahsa Sadat
Subjects
dc:subject × 2Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/10012/4906