Applying ACO to Large Scale TSP Instances

Darren M Chitty*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

29 Citations (Scopus)

Abstract

Ant Colony Optimisation (ACO) is a well known metaheuristic that has proven successful at solving Travelling Salesman Problems (TSP). However, ACO suffers from two issues; the first is that the technique has significant memory requirements for storing pheromone levels on edges between cities and second, the iterative probabilistic nature of choosing which city to visit next at every step is computationally expensive. This restricts ACO from solving larger TSP instances. This paper will present a methodology for deploying ACO on larger TSP instances by removing the high memory requirements, exploiting parallel CPU hardware and introducing a significant efficiency saving measure. The approach results in greater accuracy and speed. This enables the proposed ACO approach to tackle TSP instances of up to 200K cities within reasonable timescales using a single CPU. Speedups of as much as 1200 fold are achieved by the technique.

Original languageEnglish
Title of host publicationAdvances in Computational Intelligence Systems - Contributions Presented at the 17th UK Workshop on Computational Intelligence
PublisherSpringer Verlag
Pages104-118
Number of pages15
ISBN (Print)9783319669380
DOIs
Publication statusPublished - 1 Jan 2018
Event17th UK Workshop on Computational Intelligence, UKCI 2017 - Cardiff, United Kingdom
Duration: 6 Sept 20178 Sept 2017

Publication series

NameAdvances in Intelligent Systems and Computing
Volume650
ISSN (Print)2194-5357

Conference

Conference17th UK Workshop on Computational Intelligence, UKCI 2017
Country/TerritoryUnited Kingdom
CityCardiff
Period6/09/178/09/17

Keywords

  • Ant Colony Optimisation
  • High performance computing
  • Travelling Salesman Problem

Fingerprint

Dive into the research topics of 'Applying ACO to Large Scale TSP Instances'. Together they form a unique fingerprint.

Cite this