Perbandingan Metode Ant Colony Optimization dengan Depth First Search pada Traveling Salesman Problem untuk Drone dalam Operasi Bantuan Bencana

ALFREDO ARYASENA, Ir. Bertha Maya Shopa, ST., M.Sc., Ph.D., IPU., ASEAN.Eng.

2022 | Skripsi | S1 TEKNIK INDUSTRI

Waktu adalah hal yang penting dalam operasi penanggulangan bencana. Terutama setelah terjadinya bencana, jumlah korban jiwa dapat menjadi besar jika operasi penanggulangan tidak dapat dilakukan dengan cepat. Dalam situasi tertentu, kondisi infrastruktur dan lingkungan yang rusak pasca bencana mengakibatkan sulit untuk mencari korban yang selamat. Untuk mengatasi masalah ini, unmanned aerial vehicle (UAV) biasanya digunakan karena kemudahan UAV dalam melakukan survei lokasi bencana di udara. Meskipun UAV dapat dengan mudah melakukan operasi penanggulangan bencana, UAV memiliki batasan yaitu kapasitas energi. UAV harus dikerahkan bersama ground vehicle (GV) untuk dapat menyelesaikan tugas-tugas yang diberikan. GV bertugas untuk mengisi ulang atau menukar baterai UAV saat melakukan operasi penanggulangan bencana. Maka dari itu, koordinasi antara UAV dan GV menjadi penting dalam operasi ini. Penelitian ini berfokus dalam penentuan rute UAV dan koordinasi antara UAV dan GV untuk pencarian korban bencana alam yang selamat pasca bencana menggunakan Ant Colony Optimization (ACO). Terdapat 2 tahap dalam penentuan rute, pertama rute UAV di udara ditentukan dengan ACO yang kemudian rute darat ditentukan dengan algoritma menggunakan rute udara yang telah dibuat sebelumnya. Objek penelitian ini adalah Erupsi Merapi tahun 2010 yang merupakan salah satu erupsi gunung merapi di Indonesia. Hasil dari penelitian ini dibandingkan dengan hasil penelitian sebelumnya yang menggunakan metode Depth-First Search (DFS). Rute yang dibangun menggunakan ACO membutuhkan waktu 90,48 menit sedangkan rute dari penelitian sebelumnya membutuhkan waktu 95,48 menit. Sehingga, rute yang diperoleh dari ACO 5 menit lebih cepat rute yang diperoleh dari DFS.

Time is of the essence in disaster relief operation. Especially after a disaster happened, the casulties might be huge if disaster relief operation can't be done quickly. In certain situations, the condition of infrastructure and enviroment post-disaster makes it difficult to search for survivors. To solve this, Unmanned Aerial Vehicle (UAV) is often deployed since UAV can survey the location easily from the air. Regardless of UAV's ability to perform a disaster relief operation, UAV has a limited energy capacity. UAV needs to be deployed with a ground vehicle (GV) in order to perform their tasks. GV is in charge of recharging or swapping UAV battery during the operation. As such, the coordination between UAV and GV becomes an important part in the operation. This research focuses on constructing a route for the UAV and coordination between UAV and GV to find survivors using Ant Colony Optimization (ACO). There are 2 steps in the construction, the first one is the UAV route while in the air constructed using the ACO. And then the ground route is constructed using an algorithm with the UAV route from the previous step. The object in this research is the 2010 Merapi eruption, which is one of the volcano eruption in Indonesia. The result of this research will be compared with the result from previous research that used Depth-First Search (DFS). The route from ACO needs 90.48 minutes to complete whereas the route from previous research needs 95.48 minutes. Therefore, the route constructed using ACO is 5 minutes faster than the route constructed using DFS.

Kata Kunci : disaster relief operation, traveling salesman problem, unmanned aerial vehicle, ground vehicle, ant colony optimization.