Modification of Ant Colony Optimization Algorithm to Solve the Traveling Salesman Problem

Alda Larasati Anindya, Ketut Bayu Yogha Bintoro, Silvester Dian Handy Permana

Abstract


Traveling salesman problem (TSP) is an optimization problem in determining the optimal route of a number of nodes that will only be passed once with the initial node as the final destination. One method for solving TSP is the Ant Colony Optimization (ACO) Algorithm. ACO is inspired by ant behaviour in searching for food, where ants produce pheromones to find food sources and make a route from the colony to food that will be followed by other ants. However ACO has not been considered as the optimal method for resolving TSP. This is because ACO has several shortcomings in the computational process. Comparisons between pheromones are not yet clear, and slow computing time causes the results of ACO to be not optimal. To correct these deficiencies, modifications will be made to the ACO. Modifications are made by changing some values in the ACO, such as adjusting the number of ants by the node automatically, changing the value in the pheromone renewal, and adding value to the construction of the solution. The outcome of this research is the modification of ACO did not provide shorter computing time with a more accurate final value, thus did not provide an optimal solution. The test results in this study found that the average computation time for the last iteration of each test was 0.54 second, and for the 10 iteration computation time obtained an average of 5.54 second for four tests. The amount of memory used in four tests in this study was 440.11 mb for 10 iterations.

Keywords


Ant Colony Optimization; ACO Modification; Traveling Salesman Problem

Full Text:

PDF

References


M. Dorigo and T. Stützle, Ant Colony Optimization. 2004.

I. Brezina Jr. and Z. Čičková, “Solving the Travelling Salesman Problem Using the Ant Colony Optimization,” Manag. Inf. Syst., vol. 6, no. 4, pp. 10–14, 2011.

Y. Feng, “Ant colony for the TSP,” 2010.

D. Mulia, “Aplikasi Algoritma Ant System (AS) Dalam Kasus Travelling Salesman Problem,” 2011.

N. N. Poddar and D. Kaur, “Solving the Traveling Salesman Problem using Reinforced Ant Colony Optimization techniques,” World Congr. Comput. Sci. Comput. Eng. Appl. Comput., vol. 2013, no. 2013, pp. 33–39, 2013.

A. M. Mohsen, “Annealing Ant Colony Optimization with Mutation Operator for Solving TSP,” Comput. Intell. Neurosci., vol. 2016, 2016, doi: 10.1155/2016/8932896.

H. Xu, P. Pu, and F. Duan, “Dynamic Vehicle Routing Problems with Enhanced Ant Colony Optimization,” Discret. Dyn. Nat. Soc., vol. 2018, pp. 1–13, 2018, doi: 10.1155/2018/1295485.

M. Yousefikhoshbakht, F. Didehvar, and F. Rahmati, “Modification of the ant colony optimization for solving the multiple traveling salesman problem,” Rom. J. Inf. Sci. Technol., vol. 16, no. 1, pp. 65–80, 2013, [Online]. Available: http://www.imt.ro/romjist/Volum16/Number16_1/pdf/05-MYousefikhoshbakht.pdf.




DOI: https://doi.org/10.31326/jisa.v3i2.704

Refbacks

  • There are currently no refbacks.


Copyright (c) 2020 Alda Larasati Anindya, Ketut Bayu Yogha Bintoro, Silvester Dian Handy Permana

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.


JOURNAL IDENTITY

Journal Name: JISA (Jurnal Informatika dan Sains)
e-ISSN: 2614-8404, p-ISSN: 2776-3234
Publisher: Program Studi Teknik Informatika Universitas Trilogi
Publication Schedule: June and December 
Language: Indonesia & English
APC: The Journal Charges Fees for Publishing 
IndexingEBSCODOAJGoogle ScholarArsip Relawan Jurnal IndonesiaDirectory of Research Journals Indexing, Index Copernicus International, PKP IndexScience and Technology Index (SINTA, S4) , Garuda Index
OAI addresshttp://trilogi.ac.id/journal/ks/index.php/JISA/oai
Contactjisa@trilogi.ac.id
Sponsored by: DOI – Digital Object Identifier Crossref, Universitas Trilogi

In Collaboration With: Indonesian Artificial Intelligent Ecosystem(IAIE), Relawan Jurnal IndonesiaJurnal Teknologi dan Sistem Komputer (JTSiskom)

 

 


JISA (Jurnal Informatika dan Sains) is Published by Program Studi Teknik Informatika, Universitas Trilogi under Creative Commons Attribution-ShareAlike 4.0 International License.