Article

Solving geometric TSP with ants

Authors:

Thang N. Bui,

Mufit ColpanAuthors Info & Claims

GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation

Pages 271 - 272

https://doi.org/10.1145/1068009.1068051

Published: 25 June 2005 Publication History

Get Access

Abstract

This paper presents an ant-based approach for solving the Traveling Salesman Problem (TSP). Novel concepts of this algorithm that distinguish it from the other heuristics are the inclusion of a preprocessing stage and the use of a modified version of an ant-based approach with local optimization in multi stages. Experimental results show that this algorithm outperforms ACS [1] and is comparable to MMAS [4] for Euclidean TSP instances. Of the 40 instances of Euclidean TSP from TSPLIB [5] that were tested, this algorithm found the optimal solution for 37 instances. For the remaining instances, this algorithm returned solutions that were within 0.3% of the optimum.

References

[1]

Dorigo, M. and L. Gambardella, "Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem," IEEE Transactions on Evolutionary Computation, 1(1), 1997, pp. 53--66.

Digital Library

Google Scholar

[2]

Bentley, J.L., "Fast Algorithms for Geometric Traveling Salesman Problems," ORSA Journal on Computing, 4(4), 1992, pp. 387--411.

Crossref

Google Scholar

[3]

Fredman, M. L., D. S. Johnson, L. A. McGeoch, and G. Ostheimer, "Data Structures for Traveling Salesmen," Journal of Algorithms, 18, 1995, pp. 432--479.

Digital Library

Google Scholar

[4]

Stutzle, T. and H. Hoos, "Improvements on the Ant-System : Introducing the MAX-MIN Ant System," Proceedings of Artificial Neural Nets and Genetic Algorithms, Springer Verlag, Wien, Austria, 1998, pp. 245--249.

Google Scholar

[5]

TSPLIB: Library of Sample Instances for the TSP. University of Heilderberg, Department of Computer Science, February 2005, http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/.

Google Scholar

Cited By

View all

Diez HGarcía SMujika AMoreno AOyarzun D(2016)Virtual training of fire wardens through immersive 3D environmentsProceedings of the 21st International Conference on Web3D Technology10.1145/2945292.2945296(43-50)Online publication date: 22-Jul-2016
https://dl.acm.org/doi/10.1145/2945292.2945296

Index Terms

Solving geometric TSP with ants
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction

Recommendations

A modified ant system to achieve better balance between intensification and diversification for the traveling salesman problem

Adaptive solution construction and pheromone updating strategies.Better balance between intensification and diversification in the search process.Adjustment of construction parameter values throughout the entire process.Easy extension by adding local ...
Revisiting elitism in ant colony optimization
GECCO'03: Proceedings of the 2003 international conference on Genetic and evolutionary computation: PartI

Ant Colony Optimization (ACO) has been applied successfully in solving the Traveling Salesman Problem. Marco Dorigo et al. used Ant System (AS) to explore the Symmetric Traveling Salesman Problem and found that the use of a small number of elitist ants ...
An interactive simulation and analysis software for solving TSP using Ant Colony Optimization algorithms

Traveling salesman problem (TSP) is one of the extensively studied combinatorial optimization problems and tries to find the shortest route for salesperson which visits each given city precisely once. Ant colony optimization (ACO) algorithms have been ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation

June 2005

2272 pages

ISBN:1595930108

DOI:10.1145/1068009

Editor:
Hans-Georg Beyer
Vorarlberg University of Applied Sciences, Austria
,
General Chair:
Una-May O'Reilly
CSAIL, MIT

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 June 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

GECCO05

Sponsor:

GECCO05: Genetic and Evolutionary Computation Conference

June 25 - 29, 2005

Washington DC, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
961
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)1

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Diez HGarcía SMujika AMoreno AOyarzun D(2016)Virtual training of fire wardens through immersive 3D environmentsProceedings of the 21st International Conference on Web3D Technology10.1145/2945292.2945296(43-50)Online publication date: 22-Jul-2016
https://dl.acm.org/doi/10.1145/2945292.2945296

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

A modified ant system to achieve better balance between intensification and diversification for the traveling salesman problem

Revisiting elitism in ant colony optimization

An interactive simulation and analysis software for solving TSP using Ant Colony Optimization algorithms

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations