Implementasi Algoritma Ant-Colony Optimization Untuk Menyelesaikan Traveling Salesman Problem Menggunakan Nanto Quadcopter Crazyflie

Abstract

Traveling Salesman Problem (TSP) adalah permasalahan optimasi untuk mencari sebuah rute terbaik yang bisa dilalui. Contoh munculnya TSP adalah pada saat suatu Unmanned Aerial Vehicle (UAV) perlu mengunjungi beberapa tempat (node) untuk melakukan pekerjaan tertentu seperti surveillance dan pemupukan. Salah satu algoritma untuk mencari solusi TSP adalah Ant-Colony Optimization (ACO). Algoritma ACO bekerja dengan cara melalui semua kemungkinan rute yang bisa dilalui, kemudian menyimpan memori tersebut untuk menentukan rute terbaik yang bisa dilalui. Tujuan penelitian ini adalah untuk menyelesaikan permasalahan TSP menggunakan algoritma ACO dan kemudian diimplementasikan pada UAV Crazyflie. Algoritma ACO yang dikembangkan akan mencari rute terbaik yang bisa dilalui, kemudian Crazyflie akan terbang sesuai dengan rute yang didapatkan. Hasil pengujian menunjukkan bahwa quadcopter Crazyflie telah berhasil terbang ke titik-titik koordinat tersebut, dengan kesalahan rata-rata posisi sebesar 0,02 meter pada sumbu-x, 0,02 meter pada sumbu-y, dan 0,01 meter pada sumbu-z.

The Traveling Salesman Problem (TSP) is an optimization problem to find the best possible route. An example TSP is when a UAV needs to visit several places (nodes) to carry out certain work, such as surveillance or fertilization. One of the algorithms for finding TSP solutions is Ant-Colony Optimization (ACO). The ACO algorithm works by going through all possible routes that can be traversed, then storing the memory to determine the best route that can be traversed. The purpose of this research is to solve the TSP problem using the ACO algorithm and then implement it on the Crazyflie UAV. The developed ACO algorithm will find the best route that can be passed, the Crazyflie will fly according to the route obtained. The test results show that the Crazyflie quadcopter has successfully flown to these coordinates, with an average position error of 0.02 meters on the x-axis, 0.02 meters on the y-axis and 0.01 meters on the z-axis.