Implementasi Ant Colony Optimization (Aco) Dan Modified Ant Colony Optimization (Maco) Pada Traveling Salesman Problem (Tsp)

• Main Author: Jessica Putri Wandira
• Format: Theses and Dissertations NonPeerReviewed
• Language: Indonesian; Indonesian; Indonesian; Indonesian
• Published: 2019
• Subjects: T58.6-58.62 Management information systems
• Online Access: http://repository.unair.ac.id/91603/9/ABSTRAK%20ST.SI.40-19%20Wan%20i.pdf; http://repository.unair.ac.id/91603/10/DAFTAR%20ISI%20ST.SI.40-19%20Wan%20i.pdf; http://repository.unair.ac.id/91603/11/DAFTAR%20PUSTAKA%20ST.SI.40-19%20Wan%20i.pdf; http://repository.unair.ac.id/91603/4/FULL%20TEXT%20ST.SI.40-19%20Wan%20i.pdf; http://repository.unair.ac.id/91603/; http://lib.unair.ac.id
• Institution: Universitas Airlangga

Traveling Salesman Problem (TSP) adalah permasalahan yang mengharuskan seorang salesman mengunjungi semua kota dengan ketentuan setiap kota hanya dikunjungi satu kali dan mengharuskannya kembali lagi ke kota awal. Tujuan dari permasalahan ini adalah untuk mendapatkan rute kombinasi kota terpendek. Penelitian ini melakukan penerapan Algoritma Ant Colony Optimization (ACO) dan Modified Ant Colony Optimization (MACO) untuk menyelesaikan TSP. Algoritma MACO merupakan pengembangan dari Algoritma ACO dimana terdapat pembaruan yaitu proses update feromon lokal. Algoritma ini terinspirasi dari perilaku semut asli yang meninggalkan sarang untuk mencari makanan dan kembali lagi ke sarangnya. Pada penelitian ini, menggunakan data berukuran kecil (5 hingga 24 kota), sedang (25 hingga 49 kota) dan besar (50 hingga 100 kota). Algoritma ACO dan MACO disusun ke dalam program komputer dengan web programming. Dari hasil penelitian, ditemukan bahwa pada data kecil, baik Algoritma ACO maupun MACO dapat menghasilkan rute terbaik yang sama dengan solusi optimal yaitu 668 dan 582.2 untuk tipe simetris dan asimetris. Untuk data sedang, Algoritma ACO menghasilkan rute terbaik 3408 dengan persentase kedekatan sebesar 111% dan MACO sebesar 1844 dengan persentase kedekatan sebesar 14%. Sedangkan untuk data besar, Algoritma ACO menghasilkan rute terbaik 162302 dengan persentase kedekatan sebesar 348%. Untuk data besar yang dihitung menggunakan Algoritma MACO 43316 memiliki persentase kedekatan 20%.