Perbandingan Performansi Ant Colony Optimization dan Depth-First Search untuk Traveling Salesman Problem dalam Operasi Bantuan Bencana

ALFREDO ARYASENA, Prof. Ir. Bertha Maya Shopa, S.T., M.Sc., Ph.D., IPU., ASEAN Eng.

2023 | Tesis | MAGISTER TEKNIK INDUSTRI

Penelitian ini menginvestigasi sebuah routing problem untuk Unmanned Aerial Vehicle (UAV) pada operasi bantuan bencana dimana UAV bertugas untuk melakukan survei lokasi dan menentukan stasiun pendaratan untuk mengisi ulang energi. Hal ini membutuhkan perencanaan yang dibantu dengan menggunakan Depth-First Search (DFS) dan Ant Colony Optimization (ACO). Adapun fungsi tujuan yang ingin dicapai di sini yaitu minimasi total waktu dari rute UAV. Saat diimplementasikan pada kasus Merapi tahun 2010, DFS dapat menemukan rute dengan cepat tetapi tidak selalu optimal sedangkan ACS dapat menemukan rute yang lebih baik tetapi membutuhkan waktu yang lebih lama. Metode ACS hanya 2 menit lebih baik dari DFS sehingga terdapat permasalahan apakah ACS lebih baik dari DFS pada kasus yang lebih besar. Untuk menyelesaikan masalah ini, dilakukan eksperimen berupa computational study dimana jaringan yang dibuat secara acak dengan 4 ukuran berbeda (10 - 25 target, 5 - 10 stasiun pendaratan) digunakan untuk menguji ACS dan DFS. Hasilnya akan dianalisa untuk menentukan apakah ACS lebih baik digunakan dalam menentukan rute UAV dalam operasi bantuan bencana.

This research investigates a routing problem for Unmanned Aerial Vehicle (UAV) in disaster relief operations. Where the UAV is tasked with conducting a site survey and determining landing stations for recharging. This requires planning using Depth-First Search (DFS) and Ant Colony Optimization (ACO). The objective function of this problem is to minimize the total time of the UAV route. When implemented in the Merapi case in 2010, DFS was able to find a route quickly, but it was not always optimal. ACS was able to find a better route, but it took longer computational time than DFS method. The route generated by ACS is only 2 minutes better than DFS so there is a problem of whether ACS is better than DFS in larger cases. To solve this problem, an experiment in the form of computational study was carried out in which randomly generated networks with 4 different sizes (10 - 25 targets, 5 - 10 landing stations) were used to test ACS and DFS. The results will be analyzed to determine whether ACS is better used in determining the UAV route in disaster relief operations.

Kata Kunci : disaster relief operation, traveling salesman problem, unmanned aerial vehicle, ant colony optimization, depth-first search, computational study