Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/17617
Title: A metaheuristic ant colony optimization algorithm for symmetric and asymmetric traveling salesman problems
Authors: Raya, Lilysuriazna Binti
Advisors: Lucas, C
Date, P
Keywords: ACO;TSP;ATSP;TSP
Issue Date: 2018
Publisher: Brunel University London
Abstract: This research addresses solving two types of Travelling Salesman Problems (TSP) which are the symmetric TSP (STSP) and the asymmetric TSP (ATSP). The TSP is a problem of finding a minimal length closed tour that visits each city once. If the distances between each pair of cities are the same in both directions, the problem is a STSP, otherwise, it is an ATSP. In this thesis, a new metaheuristic algorithm which is based on Ant Colony Optimization (ACO) is proposed to solve these problems. The key idea is to enhance the ability of exploration and exploitation by incorporating a metaheuristic approach with an exact method. A new strategy for creating ‘Intelligent Ants’ is introduced to construct the solution tours. This strategy aims at reducing the computational time by heuristically fixing part of the solution tour and improving the accuracy of the solutions through the usage of a solver, specifically for large size instances. Moreover, this proposed algorithm employs new ways of depositing and evaporating pheromone. A different approach of global updating of pheromone is proposed in which the pheromone is deposited only on the edges belonging to the colony-best ant and evaporated only on the edges belonging to the colony-worst ant that are not in the colony-best ant. Additionally, the parameters of the proposed algorithm which include the number of colonies, the number of ants in each colony, the relative influence of the pheromone trail 𝛼 and the pheromone evaporation rate 𝜌 are expressed as a function of the problem size. Comparisons with other sets of parameter values suggested in the literature have been investigated which illustrate the advantages of the choice of the proposed parameter settings. Further, in order to evaluate the performance of the proposed algorithm, a set of standard benchmark problems from the TSPLIB with up to 442 cities were solved and the results obtained were compared with other approaches from the literature. The proposed algorithm has proven to be competitive and shows better performance in 63% of the 16 algorithms in terms of solution quality and obtained the optimum solutions in 70% of the 33 instances, proving that it is a good alternative approach to solve these hard combinatorial optimisation problems.
Description: This thesis was submitted for the award of Doctor of Philosophy and was awarded by Brunel University London
URI: http://bura.brunel.ac.uk/handle/2438/17617
Appears in Collections:Dept of Mathematics Theses
Mathematical Sciences

Files in This Item:
File Description SizeFormat 
FulltextThesis.pdfEmbargoed until 04/03/20221.79 MBAdobe PDFView/Open    Request a copy


Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.