Penentuan jalur terpendek dengan menggunakan metode ant colony optimization

INDONESIA:

Algoritma Ant Colony Optimization (ACO) merupakan salah satu metode heuristik yang diadopsi dari perilaku koloni semut yang dikenal sebagai sistem semut. Koloni semut mampu menemukan rute terpendek dalam perjalanan dari sarang ke tempat-tempat sumber makanan berdasarkan jejak atau yang disebut dengan zat Pheromone pada lintasan yang telah dilalui. Semakin banyak semut yang melalui suatu lintasan, maka akan semakin jelas bekas jejak kakinya.

Lokasi di Kota Malang memungkinkan pengendara untuk menghabiskan waktu yang cukup lama di dalam perjalanan. Dalam perjalanan seseorang harus mengunjungi beberapa fasilitas dari suatu tempat dan kembali lagi ke tempat pemberangkatan semula, sehingga menyebabkan pentingnya waktu, bahan bakar, dan tenaga yang dimiliki. Oleh karena itu, perlunya mencari rute jalan agar dapat menentukan jalur terpendek untuk sampai ke lokasi tujuan. Tujuan dari permasalahan jalur terpendek adalah untuk mencari jalur yang memiliki jarak terdekat antara titik asal dan titik tujuan.

Cara menemukan rute terpendek dari suatu lokasi ke lokasi yang lain, dalam penelitian ini yaitu perpustakaan kampus (r) ke perpustakaan kampus (s) adalah dengan mengunakan metode Ant Colony Optimization dengan input berupa perpustakaan asal dan tujuan, serta sebuah graf yang merepresentasikan titik sebagai perpustakaan kampus dan garis atau sisi sebagai jalur yang menghubungkannya. Kemudian mencari harga penguapan pheromone dengan menggunakan rumus:

〖∆τ〗_rs^k=Q/C^k .

Pada jalur perjalanan semut ke-25 terhitung panjang jalur adalah 8,8 dan memiliki penguapan pheromone yang terbanyak dibanding penguapan pheromone pada jalur lainnya yaitu 0,1136. Semakin banyak semut yang melalui jalur 25 maka semakin banyak semut yang mengikutinya. Demikian juga dengan jalan selain jalur ke-25, semakin sedikit semut yang melalui, maka Pheromone yang ditinggalkan semakin berkurang bahkan hilang. Dari sinilah kemudian terpilihlah rute terpendek. Dan bagi peneliti selanjutnya, disarankan untuk dapat membandingkan antara metode-metode algoritma semut yang lain.

ENGLISH:

Ant colony optimization algorithm (ACO) is one of the heuristic methods adopted from the behavior of ant colonies known as the ant systems. Ant colonies are able to find the shortest route on their way from their nest to a food source based on traces called pheromones on their transversing trajectory. The more ants pass through a trajectory, the more footprints will become clear.

The location in malang city allows riders to spend a long time on their way. On the way, they must visit some facilities from a place and back to a departure site, thus causing the importance of time, fuel, and energy possessed be important. Therefore, it needs to find a route in order to determine the shortest path to get to the destination location. The purpose of the shortest path problem is to find the path that has the closest distance between the origin and the destination.

Determining the shortest path from one location to another,-in this research it is campus library (r) to campus library (s)-is using ant colony optimization method and its input is the first library, the destination and a graph which represents a point as a campus library and lines or edges as the connecting path. Then determining the value of pheromone evaporation using the formula:

〖∆τ〗_rs^k=Q/C^k ,

On the path of the 25 ant, the path length is 8,8 and it has the highest pheromone evaporation compared to pheromone evaporation on the other path and it is 0.1136. The more ants go through the 25 path, the more ants follow it. The same as the path other than the 25 path, the fewer the ants go through it, the less the left pheromones and they are even gone. Based on that, the shortest path is selected. And for subsequent researchers, it is sugested to compare the methods of orther ant algorithms.