Penerapan Algoritma Ant System dalam Menemukan Jalur Optimal pada Traveling Salesman Problem (TSP) dengan Kekangan Kondisi Jalan
Abstract
The completion of Traveling Salesman Problem (TSP) is to find the shortest path to visit all of the cities. With the shortest path, it is expected that the travel time will also be shorter. In fact, when a salesman visits all of the cites in his list, he will find obstacles such as poor road conditions, congestion, damaged roads, or other constraints. Therefore, although the shortest path has been established, if there is an obstacle the travel time to all cities will be longer. One way to solve the TSP is by ant algorithm. The modifications were made to the Ant System by providing constraint pheromone to each road which could not be passed and also gave a long distance to the roads that should not be passed. The results of this study indicate that the ants never pass constrained sections, for square grid data also two data from TSPLIB95. This occurs because the segments were given constraints, the pheromone were weighted 0 and given the longest distance.
References
M. Dorigo and T. Stützle, Ant Colony Optimization, The MIT Press, Cambridge, Massachusetts London, England, 2004.
M. Dorigo, V. Maniezzo, and A. Colorni, Positive feedback as a search strategy, Technical Report 91-016, 1991.
M. Dorigo, V. Maniezzo, and A. Colorni, The Ant System: Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics–Part B, Vol.26, No.1, 1996, pp.1-13, 1996.
E. Bonabeau, M. Dorigo, and G. Theraulaz, Swarm Intelligence From Natural to Artificial Systems, New York Oxford, Oxford University Press, 1999.
I. Mutakhiroh, F. Saptono, N. Hasanah, R. Wiryadinata, Pemanfaatan Metode Heuristik Dalam Pencarian Jalur Terpendek Dengan Algoritma Semut dan Algoritma Genetik, Seminar Nasional Aplikasi Teknologi Informasi 2007 (SNATI 2007), ISSN: 1907-5022, 2007.
I. Mutakhiroh, Indrato, T. Hidayat, Pencarian Jalur Terpendek Menggunakan Algoritma Semut, Seminar Nasional Aplikasi Teknologi Informasi 2007(SNATI 2007), ISSN: 1907-5022, 2007.
A. Leksono Algoritma Ant Colony Optimization (ACO) Untuk Menyelesaikan Traveling Salesman Problem (TSP),Skripsi, F. MIPA UNDIP, 2009.
B. Yuwono, AS. Aribowo, BW. Siswanto, Implementasi Algoritma Koloni Semut Pada Proses Pencarian Jalan Protokol di Kota Yogyakarta, Seminar Nasional Informatika (semnasIF), ISSN: 1979-2328, 2009.
CJ. Eyckelhof, N. Snoek, Ant Systems for a Dynamic TSP Ants caught in a traffic jam, Dept. of Computer Science, University of Twente,2001.
M. Guntsch, M. Middendorf and H. Schmeck, An ant colony optimization approach to dynamic TSP. In Lee Spector et al., editor, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), pages 860–867, San Francisco, California, USA, 7-11 July 2001.
E. Chen and X. Liu,Multi-Colony Ant Algorithm. In Ant Colony Optimization-Methods and Applications. Edited by Avi Ostfeld., InTech, 2011.
© Jurnal Nasional Teknik Elektro dan Teknologi Informasi, under the terms of the Creative Commons Attribution-ShareAlike 4.0 International License.
1.png)
