Solving geometric TSP with ants

Thang N. Bui; Mufit Colpan

doi:10.1145/1068009.1068051

Solving geometric TSP with ants

Thang N. Bui, Mufit Colpan

School of Science, Engineering & Technology (Harrisburg)

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Scopus citations

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.

Original language	English (US)
Title of host publication	GECCO 2005 - Genetic and Evolutionary Computation Conference
Editors	H.G. Beyer, U.M. O'Reilly, D. Arnold, W. Banzhaf, C. Blum, E.W. Bonabeau, E. Cantu-Paz, D. Dasgupta, K. Deb, al et al
Pages	271-272
Number of pages	2
DOIs	https://doi.org/10.1145/1068009.1068051
State	Published - 2005
Event	GECCO 2005 - Genetic and Evolutionary Computation Conference - Washington, D.C., United States Duration: Jun 25 2005 → Jun 29 2005

Publication series

Name	GECCO 2005 - Genetic and Evolutionary Computation Conference

Other

Other	GECCO 2005 - Genetic and Evolutionary Computation Conference
Country/Territory	United States
City	Washington, D.C.
Period	6/25/05 → 6/29/05

All Science Journal Classification (ASJC) codes

General Engineering

Access to Document

10.1145/1068009.1068051

Cite this

Bui, T. N., & Colpan, M. (2005). Solving geometric TSP with ants. In H. G. Beyer, U. M. O'Reilly, D. Arnold, W. Banzhaf, C. Blum, E. W. Bonabeau, E. Cantu-Paz, D. Dasgupta, K. Deb, & A. et al (Eds.), GECCO 2005 - Genetic and Evolutionary Computation Conference (pp. 271-272). (GECCO 2005 - Genetic and Evolutionary Computation Conference). https://doi.org/10.1145/1068009.1068051

@inproceedings{4db099b18a6c4d52b92101ea1aa1022a,

title = "Solving geometric TSP with ants",

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.",

author = "Bui, {Thang N.} and Mufit Colpan",

year = "2005",

doi = "10.1145/1068009.1068051",

language = "English (US)",

isbn = "1595930108",

series = "GECCO 2005 - Genetic and Evolutionary Computation Conference",

pages = "271--272",

editor = "H.G. Beyer and U.M. O'Reilly and D. Arnold and W. Banzhaf and C. Blum and E.W. Bonabeau and E. Cantu-Paz and D. Dasgupta and K. Deb and {et al}, al",

booktitle = "GECCO 2005 - Genetic and Evolutionary Computation Conference",

note = "GECCO 2005 - Genetic and Evolutionary Computation Conference ; Conference date: 25-06-2005 Through 29-06-2005",

}

Bui, TN & Colpan, M 2005, Solving geometric TSP with ants. in HG Beyer, UM O'Reilly, D Arnold, W Banzhaf, C Blum, EW Bonabeau, E Cantu-Paz, D Dasgupta, K Deb & A et al (eds), GECCO 2005 - Genetic and Evolutionary Computation Conference. GECCO 2005 - Genetic and Evolutionary Computation Conference, pp. 271-272, GECCO 2005 - Genetic and Evolutionary Computation Conference, Washington, D.C., United States, 6/25/05. https://doi.org/10.1145/1068009.1068051

Solving geometric TSP with ants. / Bui, Thang N.; Colpan, Mufit.
GECCO 2005 - Genetic and Evolutionary Computation Conference. ed. / H.G. Beyer; U.M. O'Reilly; D. Arnold; W. Banzhaf; C. Blum; E.W. Bonabeau; E. Cantu-Paz; D. Dasgupta; K. Deb; al et al. 2005. p. 271-272 (GECCO 2005 - Genetic and Evolutionary Computation Conference).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Solving geometric TSP with ants

AU - Bui, Thang N.

AU - Colpan, Mufit

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=32444449310&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=32444449310&partnerID=8YFLogxK

U2 - 10.1145/1068009.1068051

DO - 10.1145/1068009.1068051

M3 - Conference contribution

AN - SCOPUS:32444449310

SN - 1595930108

SN - 9781595930101

T3 - GECCO 2005 - Genetic and Evolutionary Computation Conference

SP - 271

EP - 272

BT - GECCO 2005 - Genetic and Evolutionary Computation Conference

A2 - Beyer, H.G.

A2 - O'Reilly, U.M.

A2 - Arnold, D.

A2 - Banzhaf, W.

A2 - Blum, C.

A2 - Bonabeau, E.W.

A2 - Cantu-Paz, E.

A2 - Dasgupta, D.

A2 - Deb, K.

A2 - et al, al

T2 - GECCO 2005 - Genetic and Evolutionary Computation Conference

Y2 - 25 June 2005 through 29 June 2005

ER -

Solving geometric TSP with ants

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Cite this