Electrical and Computer Engineering ETDs

Publication Date

9-9-2010

Abstract

Graph problems model many real life applications, where the quantity of the nodes often changes with time. In such graphs, the evaluation of shortest tour is important as various guiding and navigation systems use this information. Nodes of a graph, in many applications, often change over time, and evaluation of shortest tour is essential whenever a new node is added or deleted. We propose an algorithm that deals with such situations. We have used the Ant System with a different meta-heuristics, to find the shortest tour in a graph. We have analyzed the performance of our proposed algorithm with other algorithms by using the problem instances given in TSPLIB. The proposed modification to the Ant System heuristics will also work for directed and non-fully connected graphs. We show the use of meta-heuristics that make our algorithm free from stagnation, that is, we prevent the ants from taking up the same tour repeatedly which helps to continuously search for better results. Our approach further adopts a method that is a modification to Gallants Technique, to choose the appropriate convergence within the reasonable computation time.'

Keywords

Ant algorithms, Traveling-salesman problem--Computer simulation.

Document Type

Thesis

Language

English

Degree Name

Computer Engineering

Level of Degree

Masters

Department Name

Electrical and Computer Engineering

First Committee Member (Chair)

Verzi, Stephen J.

Second Committee Member

Ghani, Nasir

Download

Share

COinS