Use of Ant Colony Optimization Algorithm for Determining Traveling Salesman Problem Routes

Authors

  • Bib Paruhum Silalahi Institut Pertanian Bogor
  • Nurul Fathiah Institut Pertanian Bogor
  • Prapto Tri Supriyo Institut Pertanian Bogor

DOI:

https://doi.org/10.15642/mantik.2019.5.2.100-111

Keywords:

Algorithm, Optimization, Ant Colony Optimization, Traveling Salesman Problem

Abstract

Ant Colony Optimization is one of the meta-heuristic methods used to solve combinatorial optimization problems that are quite difficult. Ant Colony Optimization algorithm is inspired by ant behavior in the real world to build the shortest path between food sources and their nests. Traveling Salesman Problem is a problem in optimization. Traveling Salesman Problem is a problem to find the minimum distance from the initial node to the whole node with each node must be visited exactly once and must return to the initial node. Traveling Salesman Problem is a non-deterministic polynomial-time complete problem. This research discusses the solution of the Traveling Salesman Problem using the Ant Colony Optimization algorithm and also using the exact algorithm. The results showed that the greater the size of the Traveling Salesman Problem case, the longer the execution time required. The results also showed that the execution times of the Ant Colony Optimization are much faster than the execution time of the exact method.

Downloads

Download data is not yet available.

References

F. Fadhillah, B. P. Silalahi, and M. Ilyas, “Modifikasi stepsize pada metode steepest descent dalam pengoptimuman fungsi: kasus fungsi kuadratik diagonal”, Jurnal Matematika dan Aplikasinya, vol. 13, no. 1, pp. 47-60, Juli 2014, doi:10.29244/jmap.13.1.47-60.

S. Idaman, B. P. Silalahi, and S. Guritman S, “Penyelarasan arah vektor gradien untuk menentukan step size metode steepest descent pada fungsi nonlinear kuadratik banyak variable”, Journal of Mathematics and Its Applications, vol. 17, no. 1, pp. 47-59, Juli 2018, doi: 10.29244/jmap.17.1.47-60.

B. P. Silalahi, D. Wungguli, and S. Guritman, “Steepest descent method with new step sizes”, World Academy of Science, Engineering, and Technology, International Journal of Mathematical and Computational Sciences, vol. 9, no. 7, pp. 378- 384, 2015

N. Haqueqy, B. P. Silalahi, and I. S. Sitanggang, “Uji komputasi algoritme varian metode Newton pada permasalahan optimasi nonlinear tanpa kendala”, Journal of Mathematics and Its Applications, vol. 15, no. 2, pp. 63-76, Desember 2016, doi: 10.29244/jmap.15.2.63-76

B. P. Silalahi and M. S. Dewi, “Comparison of Sensitivity Analysis on Linear Optimization Using Optimal Partition and Optimal Basis (In The Simplex Method) At Some Cases”, Published by Indonesian Mathematical Society, pp. 82-90, April 2014.

B. P. Silalahi, R. Laila, and I. S. Sitanggang, ”A combination method for solving nonlinear equations”, IOP Conference Series: Materials Science and Engineering, vol. 166, issue 1, 012011, 2017, doi:10.1088/1757-899X/166/1/012011

B. P. Silalahi, Siswandi, A. Aman, “Tinjauan terhadap Metode Pengoptimuman Pendekatan Newton”, Journal of Mathematics and Its Applications, vol. 17, no. 2, pp. 141-155, Desember 2018.

M. A. Saifudin, B. P. Silalahi, and I. S. Sitanggang, “Star catalog generation for satellite attitude navigation using density-based clustering”, Journal of Computer Science, vol. 11, no. 12, pp. 1082- 1089, 2015

D. Lalang, B. P. Silalahi, and F. Bukhari, “Vehicle Routing Problem TIME Windows dengan Pengemudi Sesekali”, Journal of Mathematics and Its Applications, vol. 17, no. 2, pp. 87-99, Desember 2018, doi: 10.29244/jmap.17.2.87-99.

S. R. M. Making, B. P. Silalahi BP, and F. Bukhari, “Multi depot vehicle routing problem dengan pengemudi sesekali”, Jurnal Matematika dan Aplikasinya, vol. 17, no. 1, pp. 75-86, Juli 2018, doi: 10.29244/jmap.17.1.75-86

H. Mayyani, B. P. Silalahi BP, and A. Aman, “Frequency determination of bus rapid transit (BRT) applied on service system of trans mataram metro bus to minimize the operational cost”, International Journal of Engineering and Management Research (IJEMR), vol. 7, issue 6, pp. 134-140, 2017

J. Heizer and B. Render, “Operations Management 9th Edition", Jakarta: Salemba Empat, 2010

F. D. Wihartiko, A. Buono, and B. P. Silalahi, “Integer programming model for optimizing bus timetable using genetic algorithm”, IOP Conference Series: Materials Science and Engineering. Vol. 166, 012016, 2017

F. Y. Bisilisin, Y. Herdiyeni, B. P. Silalahi, “Optimasi K-Means clustering menggunakan particle swarm optimization pada sistem identifikasi tumbuhan obat berbasis citra”, Jurnal Ilmu Komputer dan Agri-Informatika, vol. 3, no. 1, pp.37-46, 2014

D. Rahmalia and A. Rohmah, “Optimisasi Perencanaan Produksi Pupuk Menggunakan Firefly Algorithm”, mantik, vol. 4, no. 1, pp. 1-6, May 2018.

D. Rahmalia and A. Rohmah, “Optimisasi Perencanaan Produksi Pupuk Menggunakan Firefly Algorithm”, mantik, vol. 4, no. 1, pp. 1-6, May 2018.

B. P. Silalahi, “Evaluation of interior-point method in Scilab”, IOP Conference Series: Earth and Environmental Science, vol. 299, number 1, 012040, 2019, doi:10.1088/1755-1315/299/1/012040.

B. P. Silalahi, “Sharper analysis of upper bound for the iteration complexity of an interior point method using primal-dual full-Newton step algorithm”, Far East Journal of Mathematical Sciences, vol. 95, issue 1, pp. 69-80, 2014.

M. Dorigo and T. Stützlem, “The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances. In: Glover F., Kochenberger G.A. (eds) Handbook of Metaheuristics. International Series in Operations Research & Management Science, vol. 57. Springer, 2003.

G. Nemhauser and L. Wolsey, “Integer and Combinatorial Optimization”, New York: A Wiley-Interscience, 1999

M. Dorigo and L. M. Gambardella, "Ant colony system: a cooperative learning approach to the traveling salesman problem," in IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, pp. 53-66, April 1997.

doi: 10.1109/4235.585892.

W. Liu, S. Li, F. Zhao, and A. Zheng, "An ant colony optimization algorithm for the Multiple Traveling Salesmen Problem," 2009 4th IEEE Conference on Industrial Electronics and Applications, Xi'an, 2009, pp. 1533-1537. doi: 10.1109/ICIEA.2009.5138451.

M. Dorigo and K. Socha, “An Introduction to Ant Colony Optimization”, Belgia (BE), IRIDIA-Technical Report Series, April 2007

Downloads

Published

2019-10-27

How to Cite

Silalahi, B. P., Fathiah, N., & Supriyo, P. T. (2019). Use of Ant Colony Optimization Algorithm for Determining Traveling Salesman Problem Routes. Jurnal Matematika MANTIK, 5(2), 100–111. https://doi.org/10.15642/mantik.2019.5.2.100-111

Issue

Vol. 5 No. 2 (2019): Mathematics and Applied Mathematics

Section

Articles

License

Authors who publish with this journal agree to the following terms:
  1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
  2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
  3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work